[font="Times"][font="arial, verdana, tahoma, sans-serif"]Hi,

I thought the following article, from my blog, might be of interest to the GameDev.net community:[/font]
http://harablog.word...metry-breaking/

In it I discuss two recent algorithms (developed as part of my doctoral research) which can speed up optimal grid-based pathfinding by quite a bit compared to vanilla A*. Both are very simple to understand and apply: the main idea is to identify and eliminate so called "symmetric path segments". A* is usually forced to expand many nodes on many such equivalent segments (especially when crossing large open areas) and this can slow down search significantly. One of the methods has low memory and low pre-processing requirements. The other has none. At present the work is limited to uniform-cost grid maps (i.e. straight moves cost 1, diagonal moves cost sqrt(2)) but extensions to weighted grids do not appear impossible.

Anyway, I encourage questions or comments; I'll do my best to try and answer each one. [/font]

[font="Times"]EDIT:[/font]
[font="Times"]Part 2[/font][font="Times"] is now up! Here I describe how a simple map decomposition, based on empty rectangles, can sometimes quite dramatically speed up pathfinding on uniform-cost grids.[/font]

Part 3 of this series is now up! In it I outline Jump Point Search: a combination of two really simple neighbour pruning rules that, together, can speed up optimal pathfinding on grid maps by up to 30 times. In addition to being very fast, this method is applied online, requires no pre-processing and has zero memory overhead.

Can you give more examples of the case where A* expands too many redundant nodes? The last time I had a serious problem with overexploration was actually a bug in my A* implementation; generally if heuristics are good I personally have seen pretty well-focused searches. It may just be a characteristic of the kind of graphs I've been working on, though (arbitrary 3-space waypoint graphs versus 2-space uniform-weighted grids).

It's easy to make up such problems. Simply pick a start and goal that requires the optimal path to go around an obstacle or around a cul-de-sac which lies in the same direction as the goal. In these cases simple heuristic functions like Manhattan Distance or Euclidean Distance severely under-estimate the cost-to-go and you end up with many nodes that appear promising but which are worthless. On a grid this problem is further compounded by the fact that each of these nodes is usually reachable by many symmetric path segments. Infact, the larger the local area that must be crossed, the more symmetry it contains.

I'd be very curious to hear how your techniques generalize to graph search problems versus just uniform-grid search problems, as A* is a much more general algorithm than just path-finding on a 2D uniform plane.
[/quote]

It is unclear to me if simple pruning operators like RSR and JPS generalise to arbitrary problem graphs. It might be possible to pre-process the search space and identify symmetric regions but I do not have a strong theoretical result. Such questions are the subject of future work for my research

If I were working with waypoint graphs, I might look into Contraction Hierarchies [1] or Transit Node Routing [2] as a way of reducing my search space to speed up optimal pathfinding. CHs pre-process a map and introduce "shortcut edges" that allow macro-steps to be taken during search. Transit Nodes on the other hand identify a small set of nodes that appear on a large portion of shortest paths between arbitrary nodes and store a database of exact distances between all such nodes. Also stored are exact costs between nodes in a local neighbourhood and their nearest transit nodes. You can also combine both approaches for even better results but keep in mind that in each case the best results are achieved by discarding A* in favour of Dijkstra's Algorithm.

[1] R. Geisberger, P. Sanders, D. Schultes, D. Delling. Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks.
In 7th Workshop on Experimental Algorithms (WEA), LNCS 5038, pp. 319-333. © Springer, 2008.

[2] H. Bast, S. Funke, P. Sanders, D. Schultes. Fast Routing in Road Networks with Transit Nodes.
Science, Vol. 316. no. 5824, p. 566, 27. April 2007.

In any case, it's something that hierarchical searches have historically solved well for me personally. A good hierarchical implementation of A* sounds like a combo of the two techniques you mentioned, with perhaps a stronger emphasis on what effectively amounts to caching commonly used sequences of nodes into higher-level graphs. I've seen both automatic precomputation and manual design methods for doing this; depends on the data set really. I'll readily admit that my experience is more informed by pragmatics and experimentation than actual academic research, though :-)

Hierarchical search is very nice (not to mention fast) but it is usually suboptimal and the returned solutions usually need to be refined. The two methods I discuss in the article are, by comparison, always grid-optimal and require no refinement search. Furthermore, you can easily combine both RSR and JPS with hierarchical search or some other existing optimisation technique. For example: compute an abstract graph by dividing the map into neighbourhoods. Then, compute an abstract path for some arbitrary instance. Later, when you need to refine the abstract path, use JPS to speed up each neighbourhood crossing.

Anyways... I think it's an interesting concept although I unfortunately lack the time to dig into the actual methodology for myself. Definitely keep us posted when you get to working on arbitrary-cost grids and even arbitrary-shaped graphs; I'd love to see it!
[/quote]


I have some ideas here but nothing worth writing about yet. I'll keep you posted though ;)

Part 2 of this series is now up. In it, I describe how using a simple empty rectangle decomposition can sometimes quite dramatically speed up pathfinding on uniform-cost grids.

The third and final part of this series is now up. In it I outline Jump Point Search: a combination of two really simple neighbour pruning rules that, together, can speed up optimal pathfinding on grid maps by up to 30 times. In addition to being very fast, this method is applied online, requires no pre-processing and has zero memory overhead.

Interesting read, I like the basic concept.

I've only quickly skimmed through it and not looked at the paper at all, but is this limited to dealing with pathfinding on grids where cells are either passable or not (i.e boolean checks)?
If so doesn't that tend to limit there usefulness?

Interesting read, I like the basic concept.

I've only quickly skimmed through it and not looked at the paper at all, but is this limited to dealing with pathfinding on grids where cells are either passable or not (i.e boolean checks)?
If so doesn't that tend to limit there usefulness?

The method is specific to uniform-cost grids. That means that all tiles are either traversable or not and the cost of moving from one traversable tile to another is fixed (i.e. 1 for straight steps, sqrt(2) for diagonals). This is a common enough domain that I don't regard specialising for it as a weakness. But yes, it does reduce the applicability of the technique.

Having said that: you could apply a simple variation of this method to some weighted grids. For example: use A* + JPS to pathfind across uniform cost regions and stop recursing when you encounter a node with a neighbour in a different-cost region. This simple approach will, I think, work nicely if you have a map with a few large uniform cost areas -- which is usually the case in an RTS for example. I haven't sat down to and tried to prove optimality but off the top of my head, it seems like it should work.

The method is specific to uniform-cost grids. That means that all tiles are either traversable or not and the cost of moving from one traversable tile to another is fixed (i.e. 1 for straight steps, sqrt(2) for diagonals). This is a common enough domain that I don't regard specialising for it as a weakness. But yes, it does reduce the applicability of the technique.

Having said that: you could apply a simple variation of this method to some weighted grids. For example: use A* + JPS to pathfind across uniform cost regions and stop recursing when you encounter a node with a neighbour in a different-cost region. This simple approach will, I think, work nicely if you have a map with a few large uniform cost areas -- which is usually the case in an RTS for example. I haven't sat down to and tried to prove optimality but off the top of my head, it seems like it should work.

Yeah I read that 'Uniform-cost grid' bit, just wanted to double check. As I said I like the idea, it seems straightforward and offers obvious benefits, hopefully providing a spring board to variable cost cells.