Hello. I just got my A* pathfinding algorithm working well, and just as I was about to actually implement it into the game, I realized something. I want to be able to have portals, gateways and teleporting in my game, meaning that the fastest way to the target could be through a portal. At first, I figured that this would be as easy as adding an extra “neighbor” to the teleport nodes, but this would not work with A*, since the heuristic for each node is required to be less than or equal to the actual cost of the path from it to the goal. A portal may allow the unit to travel an extraordinary distance at a very low cost, which means that the heuristic would be inaccurate and worthless. Do I have to fall back to Dijkstra’s, which is a lot less effective?
Yes.
Or you could make your search algorithm more specialized, making the portals the destinations of your search(es) and in the next iteration, make them the source from where you (continue to) search the target. Once you found a couple of paths, join them together into a single path. It’s not trivial to get this right, but it is probably much faster than ‘bruteforce’ Dijkstra.
If its low numbers of portals you can do hacks like Riven said.
E.g. calculate shortest path via each possible portal and take smallest of the options (although if using several portals in an individual path, the combinations grow FAST).
You can hack this a little further by pre-computing the distance of each location to the nearest portal . The when computing a distance, you can calculate the shortest path, and then ignore portal usage if this distance is smaller than the nearest portal at either end of the path.
To really nail this problem, you pre-process, e.g. run something like Brandes inbetween centrality algorithm. But presumably you want to stick to whatever you have coded currently.
The only code I have at the moment is a test program. I have yet to actually integrate it to the game I’m making.
I thought about keeping the portals in mind when calculating the heuristic value of each node. This would require me to do some pre-processing before each job, basically some pre-computed heuristics between portals based on the goal node. However, this is a similar problem to path-finding in itself, which means that I the pre-computing could get very very slow with many portals, possibly eliminating the gain from using the heuristics later completely (in an extreme case of course).
I have plans for some pretty advanced path-finding optimizations later, but for now, I’ll just stick with Dijkstra’s then. However the paths I get from Dijkstra’s are pretty random and blocky, which might result in the path not being followed optimally by units since they aren’t limited to 4 or 8 directions like the path-finding is. I think I need some kind of tie-breaker, but how is this implemented? I want a more straight line between corners. Currently (assuming 8 neighbors per node) it first only walks diagonally until it gets to the same X or Y as the target and then walks axis-aligned to the target, like this:
http://img829.imageshack.us/img829/3932/pathfindingexample.png
The light blue/teal node is the goal.
I obviously want it to move in a line towards when moving across larger spaces. How would I accomplish this? Obviously, such a path would have the exact same cost, but simply not be selected because the path above is the path it would find first.
How static/dynamic are the portals? It sounds like hierarchical A* would be a good fit: http://webdocs.cs.ualberta.ca/~mmueller/ps/hpastar.pdf
Well, great. Thanks. I thought I came up with the idea of hierarchical A*. I’ll just add it to my “Already invented algorithms I’ve come up with”-list, right under ray-marched volumetric lighting and depth peeling. :’( :’( :’(
…
Everything is dynamic (but not changing too often), including walls and terrain cost, so hierarchical A* would work fine as we don’t have to reprocess the whole map on each change.
that pdf is a good read.
oot, where do you guys got above pic? it’s funny.