We just started working on our next project and we decided to use your excellent package for this. I have currently setup a point graph (which I modified a little to add our own rules for connecting nodes).
Anyway, I’m trying to get the pathfinding to make use of the looping/teleporting that we do on certain points in the level using a node link but I just can’t get it to work.
I’ve tried setting the cost factor to 0 and -1, and I’ve changed the script execution order of AstarPath, as specified in the documents.
In the screenshots below you can see that the pathfinding doesn’t use the links as I’d expect. (The target is in the upper left corner)
After a while I figured that maybe these links are only usable between 2 different graphs, not to link the same graph to itself again. Anyway as a fix I implemented some extra method code to predict jumps from a node to another node to include looping.
In the screenshots below you can see that my code did connect the nodes as I expected, but somehow the pathfinding fails to give me a path with the following error: “Searched whole area but could not find target”.
If I place the target near an object that your algorithm made itself it does however make find the target:
Sorry for the late answer.
I am afraid I don’t really understand your screenshots. There are a bunch of red lines and a bunch of green ones, but I am not sure what they indicate. Do you mind explaining it?
No, it should be usable on the same graph.
One thing that is not really that well explained is that if you are using one-way links you will have to make a small modification to the system. The scripts will partition the nodes into connected components, however connected components are only strongly connected components if all connections are bidirectional which some other parts of the code assumes. This partition is done because if a path is requested from one connected component to another and all connections are bidirectional, then the script can immediately say that no such path exists (because in that case the start and end should be in the same connected component), which saves a bunch of processing power (otherwise it will have to search the whole connected component just to find out that there was no path). This doesn’t matter that much for smaller graphs, but it can be crucial for larger ones.
Anyway, you seem to use one-directional links, so you will need to find the FloodFill methods (should be in the AstarPath.cs script) and put a ‘return;’ statement at the top of each one to disable the rest of the code from running.
I understand the confusion with those lines,all the bend lines are for my own (not really related to this) system to predict if I can jump from my current position to the next waypoint position. Red ones are unable to get to the target or got a hit with the ground before completing the jump (or dash), blue ones are completed jumps and green paths can reach the target.
In my last 2 screenshots you can see the target (green character) on the bottom, but somehow it can’t find a path. When I place the character on the same platform it will however find a path (the grey cube is the next position on the path).
The strange thing here is that I added a single if statement to also check IsValidJumpConnection after IsValidConnection in PointGenerator to let my jump prediction return true if it can be reached by jumping and dashing. But somehow it won’t use those paths in calculation. (basically the settings of your system will only connect waypoints on the same platform with each other. All the other connections in the screenshot are made by me). It will only use the paths that your system returned true for.
Hmm strange, I wasn’t using a onedirectional connection, the only other thing that I can imagine is that it won’t traverse along those connection because the physical distance in unity is bigger. But this should be fixed by setting the cost factor to 0 right? (What I had in my first post).
I hope this makes any sense at all, otherwise I’ll try and explain the problem(s) better tomorrow (the day for this project) with some screenshots.
If you are using the pro version and have the optimizeForSparseGraph option enabled, then the ‘Max Distance’ and ‘Limits’ set in the inspector are implicitly accounted for, so even if the IsValidConnection method would return true for two nodes that were further away than the max distance, it still would not connect them. Maybe this is the problem?
Setting the cost factor to zero may cause it to use those connections, however doing that also removes one of the conditions required for the A* algorithm to work. Namely that the cost to get between two nodes is at least as a high as the real world distance. You can disable the A* algorithm and use Dijkstra’s algorithm instead by setting the Heuristic to None in A* Inspector -> Settings -> Pathfinding. I probably should add a warning for this in the node link inspector…
The thing I’m trying to achieve is that our level is loopable. I was using the node links to connect the left side of the screen to the right side of the screen.
The distance in unity might be 20m for example but in world size it would be 0m, that’s why I set the cost to 0.
That would require you to set the heuristic to None as mentioned above.
The reason is that if your character was on the left side of the world and a path was requested to the right side of the world. The A* algorithm would normally start to search towards the right, not really searching much towards the left because that is in the wrong direction anyway. Obviously in this case it is optimal to go left and loop around to the right side of the world, but the algorithm doesn’t know that. The Dijkstra algorithm does not make any such assumption (however it slower as a consequence).
