Friday, 3 February 2012

Fast Pathfinding via Symmetry Breaking

This paper at AI Game Dev has immediate and natural application to roguelikes, and uses a number of techniques I've not seen discussed elsewhere. The headline quote is 'up to 30 times improvement on A*'.

I can see RSR being extended for Dijkstra maps, by storing the map cost at each rectangle corner, instead of every grid, and interpolating if required. (Paging Pender).

6 comments:

Pender said...

Very interesting article! I'm not confident that it has much application to Dijkstra maps, though, since I imagine that filling a rectangle with a gradient is approximately as expensive as straightforwardly propagating the Dijkstra map across it.

JohnH said...

Interesting!

RogerN said...

Fascinating. Both the article and the fact that I am capable of drooling over pathfinding algorithms.

Joshua Day said...

This is also not quite as useful when cells do have different costs (or other measures of value) -- but I think that in the common roguelike case, where you just want your agents to approximate a Bresenham segment of minimal length, it's just about perfect.

Jonathan Stickles Fox said...

Though designed for fixed costs, it looks adaptable to variable costs, checking for cheaper/more expensive neighbors instead of just blocked neighbors, and reacting appropriately. As long as there are still large open areas with consistent cost, it should help with those.

SharonrR Dipaolo said...


Thats interesting...