4 ms·

Dijkstra Maps Visualized

128 points by NKosmatos 4y ago

fileeditview 4y ago
Seems like this was hugged to death by HN. Web Archive link: https://web.archive.org/web/20230107220815/http://www.roguebasin.com/index.php/Dijkstra_Maps_Visualized https://web.archive.org/web/20230107220815/http://www.rogueb...
- abetusk 4y ago
  The article links to another one as well called "The Incredible Power of Dijkstra Maps": https://web.archive.org/web/20221116170436/http://www.roguebasin.com/index.php/The_Incredible_Power_of_Dijkstra_Maps https://web.archive.org/web/20221116170436/http://www.rogueb...
  - 082349872349872 4y ago
    > Most of the things a monster will do involve moving toward something or moving away from it. One can drive mobs of cattle (and other domesticated species) by taking advantage of exactly this behaviour.
abetusk 4y ago
Basically putting a gradient field on a discretized map for rogue-like games and then doing motion planning accordingly. For example, having enemies gradient ascent/descent to attack players, gradient descent/ascent to flee from players. Since many rogue-likes are played on ASCII grids, using an array to store the gradient field is not that memory intensive. I suspect one can do this in a "continuous" setting by overlaying a gradient field by consider each point of interest (enemies, players, gold) to deform the gradient in some way, say with a localized Gaussian falloff or something similar. EDIT: Sorry, this specific algorithm is linear falloff in all directions. So it's more akin to calculating Voronoi regions and saving the distance to the point of interest.
- Frost1x 4y ago
  Is it? I was just skimming the article and looking at the implementation details and it really just looks like giving a spatial dimension (a 2D grid in this case) to various graph search/traversal algorithms. In the case of this article it implies to me they were specifically looking at Dijkstra's algorithm for graph search on a grid given the name. The examples hit most the populat graph searches I'm aware of. I may have missed it in the article but I didn't see anything about trying localized search, everything seemed to use global context to find fairly optimal routes across the grid (graph) surface. Again, I did just skim so pardon me if I missed the interesting nugget.
  - abetusk 4y ago
    Yeah, I think you're right. Maybe I should delete my parent response.
  - amitp 4y ago
    It's calculating the graph distance from start node(s) to all other nodes. Although in theory it's Dijkstra's Algorithm, in practice I see people use Breadth First Search in roguelike grid worlds. The algorithm isn't limited to a grid but the visualizations look cool on a grid, which is why I use a grid in my examples [1]. Related: the gradient operation (∇ in vector calculus) on the distance field (called "dijkstra map" on that page) gives you a vector field (called "flow field" in pathfinding). [1] https://www.redblobgames.com/pathfinding/distance-to-any/ https://www.redblobgames.com/pathfinding/distance-to-any/
karussell 4y ago
For me personally raster shape (manhatten distance) makes it harder to grasp. I once did a visualization on real world graph and also shared this here on HN: https://news.ycombinator.com/item?id=31878301 https://news.ycombinator.com/item?id=31878301
- philsnow 4y ago
  A tiny nitpick: roguelikes in general don't really use Manhattan distance (but it's not Euclidean either). For instance, for getting to a tile that's 5 east and 3 north from where you are, .....x^3 ......| ......| @.....| ----->5 In Manhattan distance, that's 5+3 = 8, in Euclidean distance that's the length of the hypotenuse or about 5.83, but roguelike distance is max(5,3) = 5. (I have just learned that this is also called chessboard distance or Chebyshev distance https://en.wikipedia.org/wiki/Chebyshev_distance https://en.wikipedia.org/wiki/Chebyshev_distance , yes the same Chebyshev as in Chebyshev's inequality https://en.wikipedia.org/wiki/Chebyshev%27s_inequality https://en.wikipedia.org/wiki/Chebyshev%27s_inequality .)
matthewmorgan 4y ago
Really cool, reminds me of this article I once read: Collaborative Diffusion: Programming Antiobjects https://home.cs.colorado.edu/~ralex/papers/PDF/OOPSLA06antiobjects.pdf https://home.cs.colorado.edu/~ralex/papers/PDF/OOPSLA06antio...
robocaptain 4y ago
I believe the original author of most of this content was Brian Walker, creator of brogue, which uses Dijkstra maps to great effect. In my opinion, brogue is the greatest 'modern' traditional roguelike. latest 'community' version: https://github.com/tmewett/BrogueCE https://github.com/tmewett/BrogueCE reddit community with seeded contests: https://www.reddit.com/r/brogueforum/ https://www.reddit.com/r/brogueforum/ original game: https://sites.google.com/site/broguegame/ https://sites.google.com/site/broguegame/
deleted 4y ago
[deleted]
arbol 4y ago
Reminds me of minesweeper
tuukkah 4y ago
Would anyone have a clearer wording for this part - I don't get it at all? "Then, we rescan that map. It's the same as the basic scan, but we use whatever values happen to be in the map already."
jeffreygoesto 4y ago
Used the distance transform to speed up volume rendering back when GPUs were called ET4000 for example... Just found that they are still used today... See for example section 2.6.3 of https://www.diva-portal.org/smash/get/diva2:1330460/FULLTEXT01.pdf https://www.diva-portal.org/smash/get/diva2:1330460/FULLTEXT...
jbottoms 4y ago
This is an alternate statement of the slime-mold process. Slime-mold uses First Order Logic and pheromone decay, while the Djikstra algorithm has the advantage of being more readily extensible.

128 points by NKosmatos 4y ago

Seems like this was hugged to death by HN. Web Archive link: https://web.archive.org/web/20230107220815/http://www.roguebasin.com/index.php/Dijkstra_Maps_Visualized https://web.archive.org/web/20230107220815/http://www.rogueb...

abetusk 4y ago
The article links to another one as well called "The Incredible Power of Dijkstra Maps": https://web.archive.org/web/20221116170436/http://www.roguebasin.com/index.php/The_Incredible_Power_of_Dijkstra_Maps https://web.archive.org/web/20221116170436/http://www.rogueb...
- 082349872349872 4y ago
  > Most of the things a monster will do involve moving toward something or moving away from it. One can drive mobs of cattle (and other domesticated species) by taking advantage of exactly this behaviour.

abetusk 4y ago

Basically putting a gradient field on a discretized map for rogue-like games and then doing motion planning accordingly. For example, having enemies gradient ascent/descent to attack players, gradient descent/ascent to flee from players. Since many rogue-likes are played on ASCII grids, using an array to store the gradient field is not that memory intensive. I suspect one can do this in a "continuous" setting by overlaying a gradient field by consider each point of interest (enemies, players, gold) to deform the gradient in some way, say with a localized Gaussian falloff or something similar. EDIT: Sorry, this specific algorithm is linear falloff in all directions. So it's more akin to calculating Voronoi regions and saving the distance to the point of interest.

Frost1x 4y ago
Is it? I was just skimming the article and looking at the implementation details and it really just looks like giving a spatial dimension (a 2D grid in this case) to various graph search/traversal algorithms. In the case of this article it implies to me they were specifically looking at Dijkstra's algorithm for graph search on a grid given the name. The examples hit most the populat graph searches I'm aware of. I may have missed it in the article but I didn't see anything about trying localized search, everything seemed to use global context to find fairly optimal routes across the grid (graph) surface. Again, I did just skim so pardon me if I missed the interesting nugget.
- abetusk 4y ago
  Yeah, I think you're right. Maybe I should delete my parent response.
- amitp 4y ago
  It's calculating the graph distance from start node(s) to all other nodes. Although in theory it's Dijkstra's Algorithm, in practice I see people use Breadth First Search in roguelike grid worlds. The algorithm isn't limited to a grid but the visualizations look cool on a grid, which is why I use a grid in my examples [1]. Related: the gradient operation (∇ in vector calculus) on the distance field (called "dijkstra map" on that page) gives you a vector field (called "flow field" in pathfinding). [1] https://www.redblobgames.com/pathfinding/distance-to-any/ https://www.redblobgames.com/pathfinding/distance-to-any/

karussell 4y ago

For me personally raster shape (manhatten distance) makes it harder to grasp. I once did a visualization on real world graph and also shared this here on HN: https://news.ycombinator.com/item?id=31878301 https://news.ycombinator.com/item?id=31878301

philsnow 4y ago
A tiny nitpick: roguelikes in general don't really use Manhattan distance (but it's not Euclidean either). For instance, for getting to a tile that's 5 east and 3 north from where you are, .....x^3 ......| ......| @.....| ----->5 In Manhattan distance, that's 5+3 = 8, in Euclidean distance that's the length of the hypotenuse or about 5.83, but roguelike distance is max(5,3) = 5. (I have just learned that this is also called chessboard distance or Chebyshev distance https://en.wikipedia.org/wiki/Chebyshev_distance https://en.wikipedia.org/wiki/Chebyshev_distance , yes the same Chebyshev as in Chebyshev's inequality https://en.wikipedia.org/wiki/Chebyshev%27s_inequality https://en.wikipedia.org/wiki/Chebyshev%27s_inequality .)

matthewmorgan 4y ago

Really cool, reminds me of this article I once read: Collaborative Diffusion: Programming Antiobjects https://home.cs.colorado.edu/~ralex/papers/PDF/OOPSLA06antiobjects.pdf https://home.cs.colorado.edu/~ralex/papers/PDF/OOPSLA06antio...

robocaptain 4y ago

I believe the original author of most of this content was Brian Walker, creator of brogue, which uses Dijkstra maps to great effect. In my opinion, brogue is the greatest 'modern' traditional roguelike. latest 'community' version: https://github.com/tmewett/BrogueCE https://github.com/tmewett/BrogueCE reddit community with seeded contests: https://www.reddit.com/r/brogueforum/ https://www.reddit.com/r/brogueforum/ original game: https://sites.google.com/site/broguegame/ https://sites.google.com/site/broguegame/

deleted 4y ago

[deleted]

arbol 4y ago

Reminds me of minesweeper

tuukkah 4y ago

Would anyone have a clearer wording for this part - I don't get it at all? "Then, we rescan that map. It's the same as the basic scan, but we use whatever values happen to be in the map already."

jeffreygoesto 4y ago

Used the distance transform to speed up volume rendering back when GPUs were called ET4000 for example... Just found that they are still used today... See for example section 2.6.3 of https://www.diva-portal.org/smash/get/diva2:1330460/FULLTEXT01.pdf https://www.diva-portal.org/smash/get/diva2:1330460/FULLTEXT...

jbottoms 4y ago

This is an alternate statement of the slime-mold process. Slime-mold uses First Order Logic and pheromone decay, while the Djikstra algorithm has the advantage of being more readily extensible.