One thing that annoys me about my own A* pages is that they use grids for the examples. A* is not restricted to grids. A* works on any directed graph. A* on uniform grids is often slow, so people have come up with various ways to make the algorithm faster. I feel like the "right" thing to do is not to change the algorithm but to change the data.
Graph search is used when you want to make "global" decisions that involve potentially analyzing large parts of the map. You look ahead all the way to the end before you can decide anything. It's a waste to use it on "local" decisions that you can make without looking far ahead. Suppose you have this game map (from Baldur's Gate):
What's the easiest thing to do? Make each tile into a graph node:
This is a fine solution, but A* will take a while to find the paths. There are a lot of nodes to visit. Some algorithms will make A* faster by using a cheaper way to visit the nodes. However, it's even faster if you skip most nodes altogether. For any path on this map, almost all of steps can be decided locally, by just following a straight line. There's no need to give those nodes to A*. Instead of making every tile into a pathfinding graph node, give a smaller graph to A*:
You'll need to annotate the map with this graph, either manually in a level editor or automatically with a preprocessing algorithm. A* will run much faster on the tiny graph than the dense grid graph. If you're looking to optimize A* on a grid, consider changing the data before you consider changing the algorithm. Navigation meshes, visibility graphs, and hierarchical approaches are all worth a look.
I have a little more written here and here, but one of these days I will update my pages to put less emphasis on grids.
Labels: grids , pathfinding
To avoid the manual artist step, wouldn't it be possible to simply *join* the original small tiles? Or try to fill the level with the biggest bounding boxes you can fit and use the algorithm on those.
Anonymous: yes, you can either do it manually or with a preprocessing algorithm. There are many different map representations (nav mesh, etc.) and there are also many different ways of constructing them.
Very nice article. I have been meaning to implement A* in a small project of my own and this idea had never occurred to me. Thanks.
I think the reason those selected points are optimal is because they offer the most visibility for the fewest points. You could probably autogen these points from a given grid through.
Anonymous #2: The points I chose for this diagram are the ones where paths might have to change direction. A better principle would be to find the points where the pathfinder has to make a choice. I agree, for many types of maps you can write an algorithm to find the points.
Thank you for illustrating this.
This is exactly the feature I've added a year ago into this javascript A* implementation:
Specifically beginning here: Ability to have non-grid layouts
In other words, the library can manage either a grid or a list of linked nodes.
Parameters are obviously specified differently.
But internally, it's the same A* algorithm.
Documentation isn't that complete but the test file illustrate both usages.
Indeed, most of samples / libraries restrict you to grids.
The javascript loose typing system probably made it easier to reuse the same algo...
But whatever, the point is: A* is not limited to grids.
So it's up to you: choose the best approch!
Your article make it very clear: better use your brain than choose the "fastest implementation out there"!
A* might be (very) fast... but when milliseconds matter, watch your node count and adapt!
You talk about using an algorithm to make the number of nodes smaller but I'm not sure of how to do this. In my situation I am procedurally generating a map using a square grid. Do you have any resources or advice on how I could reduce the number of nodes in this scenario?
Hi Branden, I was experimenting here http://www.redblobgames.com/pathfinding/visibility-graphs/ but didn't finish that page :(
For procedural generation, it depends on how you're generating things. Dungeon maps for example are often built with “rooms” and “hallways”, and you can build the pathfinding graph at procedural generation time by keeping track of the doorways. Inside a room, each door node would link to every other door node in the room. In a hallway, a door node would link to the other end of the hallway. For open world (outdoor) maps you might try a hierarchical approach where you first find an approximate path using larger steps (maybe 10x10 grid blocks) and then you use the regular pathfinder to find a path from one block to another. For my polygon map generator I could find paths from polygon to polygon first, and then from tile to tile within each polygon.
These kinds of things are very specific to the kind of procedural generation you're using so it's hard to give general advice, other than: if at all possible, generate the pathfinding graph as part of the procedural generation, instead of generating only the map and then trying to reconstruct the pathfinding graph.
Post a Comment