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).
Friday, 3 February 2012
Fast Pathfinding via Symmetry Breaking
Subscribe to:
Post Comments (Atom)
Posts
6 comments:
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.
Interesting!
Fascinating. Both the article and the fact that I am capable of drooling over pathfinding algorithms.
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.
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.
Thats interesting...
Post a Comment