First, I say long-time beginner because I studied the field (in my free time first, then in school), and I've been developing like half a dozen pathfinding system in the past few years... But I still suck at it.
I'm currently developing a RPG, and for the first time I have to concile high-performance with good pathfinding. I usually have only one of them.
In the past few months I've been exploring a lot of possibilities, but I'm still stuck : the best solution I found gets exponantially slow with long paths...
I think since I'm developing a Fallout-like game (not without the same kind of grid, but with the same kind of walls and obstacles), I'd like to know how they developed theirs.
I need my pathfinding to always find the best way. It is acceptable that the pathfinding be limited to a certain distance (I'm pretty sure Fallout's one was).
Now what did I try ?
I tried A* : the pathfinding is extremly quick whatever happens, but as soon as there are obstacles, the path become far from optimal.
Here's an exemple of what my A* would do :
- -> empty case
b and d -> begin and destination
x -> path
/ -> wall
- - - - - - - - - - - - - - - - - - - -
- - - - - - - - - b - - - - - - - - - -
- - - - - - - - - x - - - - - - - - - -
- - - - x x x - - x - - - - - - - - -
- - - - x / x - - x - - / - - - - - - -
- - - - x / x x x x - - / - - - - - -
- - - - x / / / / / / / / / - - - - - -
- - - - - x - - - - - - - - - - - - - -
- - - - - - x x x d - - - - - - - - -
- - - - - - - - - - - - - - - - - - - -
This is totally unacceptable. Maybe my implementation of A* is wrong, but I never found any way to implement it better than this.
Since I wasn't able to implement a A* that finds an acceptable path, I tried a Dijkstra with limited depth (depth being twice the manhattan distance between the begin and destination points).
Dijkstra does find the best path, but it is incredibly slow, especially if I put weight on the arcs (and I had to, otherwise the characters are zigzagging for no purpose). In a zone as little as 10/10, it can loop from 500 to over 4500 times before being certain that it found the best path.
A consideration was to use a thread for pathfinding. But this is harder to implement... and somehow, I feel like it's not a good idea.
I'm completly stuck. This will be my first 3D serious game, and I can't release it with a poor pathfinding system.
I need advice on what kind of pathfinding system I need to implement ?
On some of the details, I use some kind of hybrid grid : it's the grid, using arcs to connect the cases that should be connected (this way allow many objects such as doors to disconnect cases from each other). Of course I can change it if there's a better way.
Maybe it's just a bad heuristic ?
It only uses the manhattan distance. So this kind of result doesn't surprise me.
This extremly helpfull website ( http://www-cs-students.stanford.edu/~amitp/gameprog.html ) doesn't show any better heuristics for my case : it will always find crappy ways as long as there are obstacles. It proposes to divide the map in regions first to avoid these kind of problem.
The thing is, even if the subject of regions is abundantly talked about, no algorithm or explanation about how to do them are provided.
I've been trying several time to come up with an algorithm for this, but it's always completly flawed (what is required to know what a region is, what zone does it takes, what pathways connect it to what other region ?).
And Googling it, it looks like this website is actually the only one talking about regions in pathfinding algorithm.
So, new questions arise :
- What kind of heuristic can accuratly calculate the distance between two point when there are obstacles between them ?
- If we need to pre-compute regions, how do we find them ?
There should be no need to divide your world space up to get A* to work correctly. If you get incorrect results, there's a bug; chunking up the world is only going to increase the number of weird cases that can occur but are extremely hard to predict and test for. IMHO it's just a recipe for getting rare but extremely bad and frustrating results from your code.
You can't use Manhattan distance and support diagonal movement at the same time. The point of the heuristic isn't to guess the actual cost of traveling around obstacles, it's to give you an actual guess at what the optimal path could cost. If your heuristic is inadmissible (i.e. doesn't conform to the requirements of the algorithm) you will get bad results. I would suggest replacing your heuristic with a simple Euclidean distance instead and see if that helps.
This reminds me of another post about A* with a "crinkle", e.g. takes a step in the wrong direction then recovers. I would offer pretty much the same advice here.
It's definitely an implementation bug, likely for one of the following reasons:
1. Totally out of whack heuristic. I don't think the Manhattan vs Euclidean distance difference would be enough.
2. Nodes are not being closed correctly, e.g. low costs are being overwritten by higher costs.
3. Backtracking from the goal to the source is incorrect.
you defiantly have a bug in implementation, it sounds like you are ignoring nodes in the open list, so you never check if you might have a better path than a pre-existing node in the open list. either that, you are forgetting to update your parent node when you do find a better node.
