12 ms·

A fascinating AI technique is used in one of the best roguelikes, Brogue. The author called it "Dijkstra Maps". Basically it's about generating a heatmap for al

by b0rsuk 7y ago

A fascinating AI technique is used in one of the best roguelikes, Brogue. The author called it "Dijkstra Maps". Basically it's about generating a heatmap for all the squares on the level. You can start with 0 at player position, and from that point use a simple floodfill algorithm, putting down increasing numbers with each step. Then a monster simply examines all adjacent squares and selects the one with lowest number. This has at least two notable advantages: 1. You only need to do the path generation once, and it scales very well with the number of monsters. 2. It's really good at combining several concerns, because you can generate a couple of heat maps for different concerns and add them up. For example one heat map is about proximity to player. Another could be about proximity to health pickups, or proximity to cover, or proximity to open space if a monster likes to keep distance and shoot. If a gas trap is triggered, you can use a "danger" heat map. Then a monster can easily get closer to player and at the same time choose the path which has fewer harmful effects. That's why centaur archers in Brogue are so annoying, monsters avoid traps intelligently, monster groups avoid wasting their numerical advantage by chasing player through a corridor. He described it in detail in this article: http://www.roguebasin.com/index.php?title=The_Incredible_Power_of_Dijkstra_Maps http://www.roguebasin.com/index.php?title=The_Incredible_Pow... And in case you're wondering, Brogue source code is licensed on AGPLv3.

Jaxan 7y ago
So basically just a shortest path algorithm starting from the player to all other tiles?
- masklinn 7y ago
  Sounds like that's what the base layer is yes, though the additional layers are interesting.
- fwip 7y ago
  Not exactly - a shortest path algorithm would lead to the monsters "anticipating" the player coming around the obstacle and cutting them off. The algorithm is summarized in the article as: "When an enemy enters the Chase state it tries to raycast to the player and if nothing is in the way - chase em! If something is in the way, it goes through the scent trail in order and tries to raycast to each scent until it can see one, then - chase it!" With complex geometry, this will frequently lead to a non-optimal route, and is probably more fun to play against.
- xsmasher 7y ago
  Not really - a shortest path algorithm outputs a single path between a start and an end point. This gives you a value (distance to player) for every square on the board; you can do a lot of things with that data, like choose between multiple "best steps" based on some other preference, or choose "best steps" for a large number of monsters efficiently.
  - fwip 7y ago
    No, it doesn't give you a distance-to-player for every square on the board. It is closer to giving you an ordered list of 'most recent player positions' - notably, the point directly in front of the player is not necessarily in this list. These positions contain "time since player was here," which is not a distance to player. (It could be thought of as a maximum bound on distance-to-player, I suppose). If the player's route is not straight, some squares with "fresher scent" may be physically more distant from the player than squares with less fresh scent.
    - eindiran 7y ago
      Your parent comment is referring to the Dijkstra Map algorithm described in the top-level comment, not the algorithm discussed in the article.
  - zetalemur 7y ago
    Assuming this is calculated on every turn: Then it is a shortest path tree from the player position (the root) to all tiles.
60654 7y ago
Sounds like a classic potential field implementation, and yeah, they're very useful. There are two problems: scaling with map size (large maps or high detail maps), and update cost in action-heavy games (if the field source moves on every frame). But for small roguelikes it's a very good fit.
- b0rsuk 7y ago
  Thanks for the alternative name! Helps further research the technique. The core idea is relatively simple so I'm not surprised these are known. But finding a name of something you know is not easy with just a search engine.
  - 60654 7y ago
    Sure thing! And as I mentioned in another comment, if you google for "potential fields" and "flow fields" in games, there's a whole bunch of papers and talks on this.
    - eli_gottlieb 7y ago
      Interesting, because these kinds of potential fields are similar to the "predictive map" representations we see in the firing rates of hippocampal cells.
    - b0rsuk 7y ago
      Now that you mentioned "flow field", I remember seeing it in a Supreme Commander AI demonstration technique. Two columns of tanks can navigate through each other seamlessly, without chaos. And in realtime. Imagine seeing this in the days of Warcraft 1, where it was common for a unit to use left hand rule across the entire map because the bridge was momentarily occupied. https://www.youtube.com/watch?v=iHuFCnYnP9A https://www.youtube.com/watch?v=iHuFCnYnP9A
  - Marazan 7y ago
    Also get called influence maps
- 7y ago
simias 7y ago
I encountered a similar problem in a very different situation a few years ago: I had to route video streams across a network of nodes connected by point-to-point connections. At first I thought I would apply a pathfinding algorithm like A* to route each stream but given that it was an arbitrary graph and not a 2D map there was no obvious heuristic to guide the algorithm, so it devolved into an exhaustive search. But then I realized that I had relatively few nodes (a dozen at most) and many more streams to route, so it made more sense to compute the distance between every pair of nodes once (n^2 with the number of nodes using a trivial implementation, less if you optimize it but I didn't even need to) and then I could lookup the path between any two nodes in linear time. Given that this was all running on an underpowered embedded system it made a significant difference in performance when routing hundreds of streams.
- jfkebwjsbx 7y ago
  That lookup can be done in constant time, rather than linear, right?
  - simias 7y ago
    I'm not very good at big-O. I meant that in order to build the path I would need to lookup the neighboring nodes to find the closest to the target, then just to that node and continue until the end. So it's linear with the average distance I guess.
    - tpxl 7y ago
      Yeah, linear with regards to the number of nodes - double the amount of nodes and you'll need to do double the look-ups; and constant with regards to the number of streams - no matter how many streams, always the same number of look-ups.
DonHopkins 7y ago
James Gosling's Emacs screen redisplay algorithm also used similar "dynamic programming techniques" to compute the minimal cost path through a cost matrix of string edit operations (the costs depended i.e. on the number of characters to draw, length of the escape codes to insert/delete lines/characters, padding for slow terminals, etc). https://en.wikipedia.org/wiki/Gosling_Emacs https://en.wikipedia.org/wiki/Gosling_Emacs >Gosling Emacs was especially noteworthy because of the effective redisplay code, which used a dynamic programming technique to solve the classical string-to-string correction problem. The algorithm was quite sophisticated; that section of the source was headed by a skull-and-crossbones in ASCII art, warning any would-be improver that even if they thought they understood how the display code worked, they probably did not. https://donhopkins.com/home/archive/emacs/skull-and-crossbones.txt https://donhopkins.com/home/archive/emacs/skull-and-crossbon... Trivia: That "Skull and Crossbones" ASCII art is originally from Brian Reid's Scribe program, and is not copyrighted. https://donhopkins.com/home/archive/emacs/mw/display.c https://donhopkins.com/home/archive/emacs/mw/display.c /* 1 2 3 4 .... Each Mij represents the minumum cost of +---+---+---+---+----- rearranging the first i lines to map onto 1 | | | | | the first j lines (the j direction +---+---+---+---+----- represents the desired contents of a line, 2 | | \| ^ | | i the current contents). The algorithm +---+---\-|-+---+----- used is a dynamic programming one, where 3 | | <-+Mij| | M[i,j] = min( M[i-1,j], +---+---+---+---+----- M[i,j-1]+redraw cost for j,2 4 | | | | | M[i-1,j-1]+the cost of +---+---+---+---+----- converting line i to line j); . | | | | | Line i can be converted to line j by either . just drawing j, or if they match, by moving . line i to line j (with insert/delete line) */ https://donhopkins.com/home/documents/EmacsRedisplayAlgorithm.pdf https://donhopkins.com/home/documents/EmacsRedisplayAlgorith... https://dl.acm.org/doi/10.1145/1159890.806463 https://dl.acm.org/doi/10.1145/1159890.806463 A redisplay algorithm, by James Gosling. Abstract This paper presents an algorithm for updating the image displayed on a conventional video terminal. It assumes that the terminal is capable of doing the usual insert/delete line and insert/delete character operations. It takes as input a description of the image currently on the screen and a description of the new image desired and produces a series of operations to do the desired transformation in a near-optimal manner. The algorithm is interesting because it applies results from the theoretical string-to-string correction problem (a generalization of the problem of finding a longest common subsequence), to a problem that is usually approached with crude ad-hoc techniques. [...] 6. Conclusion The redisplay algorithm described in this paper is used in an Emacs-like editor for Unix and a structure editor. It's performance has been quite good: to redraw everything on the screen (when everything has changed) takes about 0.12 seconds CPU time on a VAX 11/780 running Unix. Using the standard file typing program, about 0.025 seconds of CPU time are needed to type one screenful of text. Emacs averages about 0.004 CPU seconds per keystroke (with one call on the redisplay per keystroke). Although in the interests of efficency we have stripped down algorithm 5 to algorithm 6 the result is still an algorithm which has a firm theoretical basis and which is superior to the usual ad-hoc approach.
gavinray 7y ago
This article made my morning, thank you. So fascinating how these things are still being uncovered today.
pests 7y ago
I've always known this as flow field pathfinding and it can get tricky if you have a dynamic map or enough changing that you need to recalculate often. Here's a random article I'm sure I read years ago describing it. https://leifnode.com/2013/12/flow-field-pathfinding/ https://leifnode.com/2013/12/flow-field-pathfinding/
netgusto 7y ago
I believe what you're describing is called Collaborative Diffusion, and it's been used in Pacman. https://en.wikipedia.org/wiki/Collaborative_diffusion https://en.wikipedia.org/wiki/Collaborative_diffusion
foota 7y ago
Here's a good article I've read previously about large pathfinding problems in a theme park game: https://www.gamasutra.com/view/news/288020/Game_Design_Deep_Dive_Creating_believable_crowds_in_Planet_Coaster.php https://www.gamasutra.com/view/news/288020/Game_Design_Deep_...
user5994461 7y ago
What you're looking for is influence maps. See the 2 articles linked below. They helped me tremendously when I was developing AI for a 2D game. Another unrelated thing I found very useful is Floyd Warshall. It's a graph algorithm to compute efficiently ALL shortest paths between any 2 nodes. Real time pathfinding was too slow to use, had to precompute wherever possible, turns out most of the world is fixed and can be precomputed. https://gameschoolgems.blogspot.com/2009/12/influence-maps-i.html https://gameschoolgems.blogspot.com/2009/12/influence-maps-i... https://gameschoolgems.blogspot.com/2010/03/influence-maps-ii-practical.html https://gameschoolgems.blogspot.com/2010/03/influence-maps-i... https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorit...
- jasonkester 7y ago
  Ah, influence mapping... I participated in a fun thread on comp.ai.games in 1995 where a lot of these ideas were first fleshed out. http://zhar.net/projects/gameai/influence_map.html http://zhar.net/projects/gameai/influence_map.html My contribution was to use heat transfer calculations to model the battlefield as a conductive plate with units as heat constraints. Fun times. I always wondered if that thread inspired any real world games.
adanto6840 7y ago
I believe this is "flow fields" or "potential fields" -- as mentioned by other commenters, scaling it with graph size and destination-count are two of the main issues with it. In SimAirport we use flow fields, they're great for crowds & they scale incredibly well with agent count. We use them for "long distance" traversals, and then we use "local" A-star like grid search for the "last-mile" of an agent's journey. For flow-fields, we start by dividing everything up into "sectors" based on game logic -- and then further, into "sub-sectors", essentially just basic abstractions of the graph with smaller node counts. It does have an impact on path quality but for the scale we operate at in SimAirport the trade-off is a no brainer. The abstractions then limit the flow-field's graph size & the destination-count that any given subsector (abstracted-node) can have -- essentially it's a hierarchical (pseudo HPA-star) approach to flowfield pathfinding / navigation, and the abstraction also has major benefits for reachability queries & game-logic driven "rules" (ie load-balancing of capacity-constrained paths [stairs/escalators], one-way paths [ie directed graph algos], etc).
philsnow 7y ago
IIRC he uses the same data structure but with hill climbing vs gradient descent to guide monkeys/imps/anything else that steals an item and runs from you. Clever.
manwithaplan 7y ago
> The author called it "Dijkstra Maps". > Basically it's about generating a heatmap for all the squares on the level. > You can start with 0 at player position, and from that point use a simple floodfill algorithm, putting down increasing numbers with each step. I’ve always called this Lee’s algorithm https://en.m.wikipedia.org/wiki/Lee_algorithm https://en.m.wikipedia.org/wiki/Lee_algorithm

by b0rsuk 7y ago

Jaxan 7y ago

So basically just a shortest path algorithm starting from the player to all other tiles?

masklinn 7y ago
Sounds like that's what the base layer is yes, though the additional layers are interesting.
fwip 7y ago
Not exactly - a shortest path algorithm would lead to the monsters "anticipating" the player coming around the obstacle and cutting them off. The algorithm is summarized in the article as: "When an enemy enters the Chase state it tries to raycast to the player and if nothing is in the way - chase em! If something is in the way, it goes through the scent trail in order and tries to raycast to each scent until it can see one, then - chase it!" With complex geometry, this will frequently lead to a non-optimal route, and is probably more fun to play against.
xsmasher 7y ago
Not really - a shortest path algorithm outputs a single path between a start and an end point. This gives you a value (distance to player) for every square on the board; you can do a lot of things with that data, like choose between multiple "best steps" based on some other preference, or choose "best steps" for a large number of monsters efficiently.
- fwip 7y ago
  No, it doesn't give you a distance-to-player for every square on the board. It is closer to giving you an ordered list of 'most recent player positions' - notably, the point directly in front of the player is not necessarily in this list. These positions contain "time since player was here," which is not a distance to player. (It could be thought of as a maximum bound on distance-to-player, I suppose). If the player's route is not straight, some squares with "fresher scent" may be physically more distant from the player than squares with less fresh scent.
  - eindiran 7y ago
    Your parent comment is referring to the Dijkstra Map algorithm described in the top-level comment, not the algorithm discussed in the article.
- zetalemur 7y ago
  Assuming this is calculated on every turn: Then it is a shortest path tree from the player position (the root) to all tiles.

60654 7y ago

Sounds like a classic potential field implementation, and yeah, they're very useful. There are two problems: scaling with map size (large maps or high detail maps), and update cost in action-heavy games (if the field source moves on every frame). But for small roguelikes it's a very good fit.

b0rsuk 7y ago
Thanks for the alternative name! Helps further research the technique. The core idea is relatively simple so I'm not surprised these are known. But finding a name of something you know is not easy with just a search engine.
- 60654 7y ago
  Sure thing! And as I mentioned in another comment, if you google for "potential fields" and "flow fields" in games, there's a whole bunch of papers and talks on this.
  - eli_gottlieb 7y ago
    Interesting, because these kinds of potential fields are similar to the "predictive map" representations we see in the firing rates of hippocampal cells.
  - b0rsuk 7y ago
    Now that you mentioned "flow field", I remember seeing it in a Supreme Commander AI demonstration technique. Two columns of tanks can navigate through each other seamlessly, without chaos. And in realtime. Imagine seeing this in the days of Warcraft 1, where it was common for a unit to use left hand rule across the entire map because the bridge was momentarily occupied. https://www.youtube.com/watch?v=iHuFCnYnP9A https://www.youtube.com/watch?v=iHuFCnYnP9A
- Marazan 7y ago
  Also get called influence maps
7y ago

simias 7y ago

I encountered a similar problem in a very different situation a few years ago: I had to route video streams across a network of nodes connected by point-to-point connections. At first I thought I would apply a pathfinding algorithm like A* to route each stream but given that it was an arbitrary graph and not a 2D map there was no obvious heuristic to guide the algorithm, so it devolved into an exhaustive search. But then I realized that I had relatively few nodes (a dozen at most) and many more streams to route, so it made more sense to compute the distance between every pair of nodes once (n^2 with the number of nodes using a trivial implementation, less if you optimize it but I didn't even need to) and then I could lookup the path between any two nodes in linear time. Given that this was all running on an underpowered embedded system it made a significant difference in performance when routing hundreds of streams.

jfkebwjsbx 7y ago
That lookup can be done in constant time, rather than linear, right?
- simias 7y ago
  I'm not very good at big-O. I meant that in order to build the path I would need to lookup the neighboring nodes to find the closest to the target, then just to that node and continue until the end. So it's linear with the average distance I guess.
  - tpxl 7y ago
    Yeah, linear with regards to the number of nodes - double the amount of nodes and you'll need to do double the look-ups; and constant with regards to the number of streams - no matter how many streams, always the same number of look-ups.

DonHopkins 7y ago

James Gosling's Emacs screen redisplay algorithm also used similar "dynamic programming techniques" to compute the minimal cost path through a cost matrix of string edit operations (the costs depended i.e. on the number of characters to draw, length of the escape codes to insert/delete lines/characters, padding for slow terminals, etc). https://en.wikipedia.org/wiki/Gosling_Emacs https://en.wikipedia.org/wiki/Gosling_Emacs >Gosling Emacs was especially noteworthy because of the effective redisplay code, which used a dynamic programming technique to solve the classical string-to-string correction problem. The algorithm was quite sophisticated; that section of the source was headed by a skull-and-crossbones in ASCII art, warning any would-be improver that even if they thought they understood how the display code worked, they probably did not. https://donhopkins.com/home/archive/emacs/skull-and-crossbones.txt https://donhopkins.com/home/archive/emacs/skull-and-crossbon... Trivia: That "Skull and Crossbones" ASCII art is originally from Brian Reid's Scribe program, and is not copyrighted. https://donhopkins.com/home/archive/emacs/mw/display.c https://donhopkins.com/home/archive/emacs/mw/display.c /* 1 2 3 4 .... Each Mij represents the minumum cost of +---+---+---+---+----- rearranging the first i lines to map onto 1 | | | | | the first j lines (the j direction +---+---+---+---+----- represents the desired contents of a line, 2 | | \| ^ | | i the current contents). The algorithm +---+---\-|-+---+----- used is a dynamic programming one, where 3 | | <-+Mij| | M[i,j] = min( M[i-1,j], +---+---+---+---+----- M[i,j-1]+redraw cost for j,2 4 | | | | | M[i-1,j-1]+the cost of +---+---+---+---+----- converting line i to line j); . | | | | | Line i can be converted to line j by either . just drawing j, or if they match, by moving . line i to line j (with insert/delete line) */ https://donhopkins.com/home/documents/EmacsRedisplayAlgorithm.pdf https://donhopkins.com/home/documents/EmacsRedisplayAlgorith... https://dl.acm.org/doi/10.1145/1159890.806463 https://dl.acm.org/doi/10.1145/1159890.806463 A redisplay algorithm, by James Gosling. Abstract This paper presents an algorithm for updating the image displayed on a conventional video terminal. It assumes that the terminal is capable of doing the usual insert/delete line and insert/delete character operations. It takes as input a description of the image currently on the screen and a description of the new image desired and produces a series of operations to do the desired transformation in a near-optimal manner. The algorithm is interesting because it applies results from the theoretical string-to-string correction problem (a generalization of the problem of finding a longest common subsequence), to a problem that is usually approached with crude ad-hoc techniques. [...] 6. Conclusion The redisplay algorithm described in this paper is used in an Emacs-like editor for Unix and a structure editor. It's performance has been quite good: to redraw everything on the screen (when everything has changed) takes about 0.12 seconds CPU time on a VAX 11/780 running Unix. Using the standard file typing program, about 0.025 seconds of CPU time are needed to type one screenful of text. Emacs averages about 0.004 CPU seconds per keystroke (with one call on the redisplay per keystroke). Although in the interests of efficency we have stripped down algorithm 5 to algorithm 6 the result is still an algorithm which has a firm theoretical basis and which is superior to the usual ad-hoc approach.

gavinray 7y ago

This article made my morning, thank you. So fascinating how these things are still being uncovered today.

pests 7y ago

I've always known this as flow field pathfinding and it can get tricky if you have a dynamic map or enough changing that you need to recalculate often. Here's a random article I'm sure I read years ago describing it. https://leifnode.com/2013/12/flow-field-pathfinding/ https://leifnode.com/2013/12/flow-field-pathfinding/

netgusto 7y ago

I believe what you're describing is called Collaborative Diffusion, and it's been used in Pacman. https://en.wikipedia.org/wiki/Collaborative_diffusion https://en.wikipedia.org/wiki/Collaborative_diffusion

foota 7y ago

Here's a good article I've read previously about large pathfinding problems in a theme park game: https://www.gamasutra.com/view/news/288020/Game_Design_Deep_Dive_Creating_believable_crowds_in_Planet_Coaster.php https://www.gamasutra.com/view/news/288020/Game_Design_Deep_...

user5994461 7y ago

What you're looking for is influence maps. See the 2 articles linked below. They helped me tremendously when I was developing AI for a 2D game. Another unrelated thing I found very useful is Floyd Warshall. It's a graph algorithm to compute efficiently ALL shortest paths between any 2 nodes. Real time pathfinding was too slow to use, had to precompute wherever possible, turns out most of the world is fixed and can be precomputed. https://gameschoolgems.blogspot.com/2009/12/influence-maps-i.html https://gameschoolgems.blogspot.com/2009/12/influence-maps-i... https://gameschoolgems.blogspot.com/2010/03/influence-maps-ii-practical.html https://gameschoolgems.blogspot.com/2010/03/influence-maps-i... https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorit...

jasonkester 7y ago
Ah, influence mapping... I participated in a fun thread on comp.ai.games in 1995 where a lot of these ideas were first fleshed out. http://zhar.net/projects/gameai/influence_map.html http://zhar.net/projects/gameai/influence_map.html My contribution was to use heat transfer calculations to model the battlefield as a conductive plate with units as heat constraints. Fun times. I always wondered if that thread inspired any real world games.

adanto6840 7y ago

I believe this is "flow fields" or "potential fields" -- as mentioned by other commenters, scaling it with graph size and destination-count are two of the main issues with it. In SimAirport we use flow fields, they're great for crowds & they scale incredibly well with agent count. We use them for "long distance" traversals, and then we use "local" A-star like grid search for the "last-mile" of an agent's journey. For flow-fields, we start by dividing everything up into "sectors" based on game logic -- and then further, into "sub-sectors", essentially just basic abstractions of the graph with smaller node counts. It does have an impact on path quality but for the scale we operate at in SimAirport the trade-off is a no brainer. The abstractions then limit the flow-field's graph size & the destination-count that any given subsector (abstracted-node) can have -- essentially it's a hierarchical (pseudo HPA-star) approach to flowfield pathfinding / navigation, and the abstraction also has major benefits for reachability queries & game-logic driven "rules" (ie load-balancing of capacity-constrained paths [stairs/escalators], one-way paths [ie directed graph algos], etc).

philsnow 7y ago

IIRC he uses the same data structure but with hill climbing vs gradient descent to guide monkeys/imps/anything else that steals an item and runs from you. Clever.

manwithaplan 7y ago

> The author called it "Dijkstra Maps". > Basically it's about generating a heatmap for all the squares on the level. > You can start with 0 at player position, and from that point use a simple floodfill algorithm, putting down increasing numbers with each step. I’ve always called this Lee’s algorithm https://en.m.wikipedia.org/wiki/Lee_algorithm https://en.m.wikipedia.org/wiki/Lee_algorithm