Temple of The Roguelike Forums
Development => Programming => Topic started by: ekolis on February 24, 2016, 11:05:12 AM
-
I remember reading something about them a long time ago, but all I can find now is Dijkstra's pathfinding algorithm. I've already implemented it in my game (or at least A*; it's been a while and I'm not sure if I did it right), but I was hoping to speed things up a bit by caching the maps and only updating what needs to be updated when things move around. Wasn't there an article about this somewhere? Or am I completely imagining Dijkstra maps?
And actually, this isn't a roguelike I'm working on (it's a 4X!); I want pathfinding so the ships can move around on this huge map (well, actually numerous small maps connected by "warp points"), but the algorithms seem rather relevant even in this case ;)
-
Google is thy friend:
http://www.roguebasin.com/index.php?title=The_Incredible_Power_of_Dijkstra_Maps
http://www.roguebasin.com/index.php?title=Dijkstra_Maps_Visualized
https://www.youtube.com/watch?v=IXxwOxOfuYo
Enjoy!
-
Joshua Day's series of articles on the subject is more or less unrivalled:
http://paleoludic.com/writing/whitespace-reasoning/
http://paleoludic.com/writing/a-pathfinding-primer/
http://paleoludic.com/writing/engineering-pds/
There are also a couple of articles on roguebasin:
http://www.roguebasin.com/index.php?title=The_Incredible_Power_of_Dijkstra_Maps
http://www.roguebasin.com/index.php?title=Dijkstra_Maps_Visualized
Generally, Dijkstra maps are useful when you want to calculate a large number of paths on the same map which share a source or target location (or set of locations)
-
In case it helps, I've also heard them called flow maps and influence maps.
-
I remember reading something about them a long time ago, but all I can find now is Dijkstra's pathfinding algorithm. I've already implemented it in my game (or at least A*; it's been a while and I'm not sure if I did it right)
A* is an improvement of Dijkstra which uses hints to make pathfinding faster (it boils down to Dijkstra if you don't use any hints), so it should be "even A*", not "at least A*".
-
Huh, interesting, I don't know why Google couldn't find those Roguebasin articles! Thanks!
I could have sworn Dijktstra's algorithm was an improvement on A*, not the other way around...
Oh, wow, I didn't realize these maps were that powerful, such that you can multiply them together to create nuanced AIs... - I've heard of influence maps, but I didn't realize they were so easy to compute! Now I can do things that I wanted to have in my 7DRL, such as having monsters pursue the player and NPCs, provided that the monsters are stronger, and having NPCs pursue weaker monsters and the player if he's stronger...
On large maps might they be rather slow, though? Especially if monsters/spaceships/whatever are moving about every turn? Given that you have to scan the entire map, and not stop as soon as you find a goal...
Now am I correct in reading the Roguebasin articles such that it's OK to reuse a map for multiple monsters, provided they all have the same goals? Even though the monsters are at different locations?
Also I suppose these maps could be used in reverse, provided there are no one-way paths? That is, instead of determining the path from any point on the map to the closest of points A, B, C, etc. it would determine the path from point A to any point on the map?
-
Huh, interesting, I don't know why Google couldn't find those Roguebasin articles! Thanks!
Since these mostly aren't called "Dijkstra maps" outside the roguelike development community, google tends to read the query as "dijkstra on a map". :(
On large maps might they be rather slow, though? Especially if monsters/spaceships/whatever are moving about every turn? Given that you have to scan the entire map, and not stop as soon as you find a goal...
One Dijkstra map is generally quite cheap to compute, even on a large map. Generally the number of maps to recompute each turn should be kept as small as possible. In some cases you can get away with computing the map up to a maximum distance, and setting the values outside of that area to +infinity.
Now am I correct in reading the Roguebasin articles such that it's OK to reuse a map for multiple monsters, provided they all have the same goals? Even though the monsters are at different locations?
Yes, that is the main purpose of Dijkstra maps. If each map was used only by one monster, you would be better off using A*.
Also I suppose these maps could be used in reverse, provided there are no one-way paths? That is, instead of determining the path from any point on the map to the closest of points A, B, C, etc. it would determine the path from point A to any point on the map?
Yes, if the cost of movement on the map is symmetric, then reverse paths on the Dijkstra map are also optimal. This wouldn't only be invalidated by one-way paths - Civilization-style maps where walking from hills to grass costs less than walking from grass to hills would also stop tht from working.
-
Huh, interesting, I don't know why Google couldn't find those Roguebasin articles! Thanks!
Since these mostly aren't called "Dijkstra maps" outside the roguelike development community, google tends to read the query as "dijkstra on a map". :(
To the game programming world at large, these are mostly called influence maps. Try googling: game programming influence maps. Other good search terms for the same concept are Heat Maps, Terrain Reasoning, and Using Potential Fields, and the general field of Map Analysis.
Hope this helps,
Brian aka Omnivore
PS: ah I see Tilded already gave the influence map reference as well as one I haven't heard (flow maps).
-
Thanks a lot, guys! :)
If I wanted to use an influence map for asymmetric movement costs or one-way movement, then I'd need to use a more sophisticated algorithm, I suppose? Traversing each location on the map through the map's topology, as with a traditional Dijkstra or A* algorithm? And that would be a lot slower, right? But if I just wanted non-grid-based movement, so long as it's symmetric (e.g. text adventure or MUD-style maps where you can go north, or south, or upstairs, or Dennis), the influence map would be just fine; I'd simply have a different definition of "neighbor"?
I suppose influence maps could also be used to generate terrain? I did something like that in my 2013 7DRL, "TriQuest" - I placed "hotspots" on the map, and designed "levels" of terrain such that higher level terrain would contain more dangerous monsters and might also be harder to traverse. (If you enter a "wasteland" terrain, expect very strong enemies!) But that was an open world, and I suppose it could also be used in a traditional dungeon, using the pathfinding algorithm to "dig" corridors between rooms?
-
Thanks a lot, guys! :)
If I wanted to use an influence map for asymmetric movement costs or one-way movement, then I'd need to use a more sophisticated algorithm, I suppose? Traversing each location on the map through the map's topology, as with a traditional Dijkstra or A* algorithm? And that would be a lot slower, right? But if I just wanted non-grid-based movement, so long as it's symmetric (e.g. text adventure or MUD-style maps where you can go north, or south, or upstairs, or Dennis), the influence map would be just fine; I'd simply have a different definition of "neighbor"?
You wouldn't really have to do anything special to deal with asymmetric movement costs - for locations that actors will need to pathfind away from, just make a second map using the cost values for movement in the opposite direction.
I suppose influence maps could also be used to generate terrain? I did something like that in my 2013 7DRL, "TriQuest" - I placed "hotspots" on the map, and designed "levels" of terrain such that higher level terrain would contain more dangerous monsters and might also be harder to traverse. (If you enter a "wasteland" terrain, expect very strong enemies!) But that was an open world, and I suppose it could also be used in a traditional dungeon, using the pathfinding algorithm to "dig" corridors between rooms?
Procedural generation can be very creative - I'm sure you could find hundreds of applications for Dijkstra maps :)
-
You wouldn't really have to do anything special to deal with asymmetric movement costs - for locations that actors will need to pathfind away from, just make a second map using the cost values for movement in the opposite direction.
I thought you said in an earlier post that asymmetric movement costs rendered the algorithm useless? Or would I just have to modify it to filter out "neighbors" that aren't actually connected, and/or weight movement costs based on source/destination?
-
On a symmetric graph you would be able to use the same map to pathfind in both directions. Asymmetric movement costs make the single map obtained from pathfinding *to* a location set incorrect for pathfinding *away* from the same location set; you would have to make a second map if you wanted monsters to flow in both directions.
-
I have loved using dijkstra maps for a while now... so many problems can be solved with them. One interesting application I have used recently was in stair placement on procedurally generated dungeon levels. I created an extremely maze-like map and wanted to find the furthest point from the up stairs so I could place the down stairs there. A dijkstra map allowed me to do this. Such maps can similarly be used to gauge how "fun" an area of the dungeon is, by mapping the distance to the closest objects that contribute to "fun" (traps, treasure, secret doors, enemies... etc.) And using this measure, you can ensure you don't have any extremely boring parts to your generated dungeon.
This link was mentioned above, but I would like to emphasize it as an easy place to learn about why you would want to use dijkstra maps. I really like the Dijkstra maps visualized (http://www.roguebasin.com/index.php?title=Dijkstra_Maps_Visualized) article on roguebasin. *two thumbs up*
Thanks, and happy programming!