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).
Posts
A Bundle of Information on Indie Royale [Interview]
-
[image: post thumbnail]
Last week, IndieGames.com and Desura presented a new fortnightly event
called Indie Royale. For those who haven’t checked it out ...
6 months ago
5 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.
Post a Comment