Dijkstra Maps Visualized | Hacker News Reader

Dijkstra Maps Visualized

roguebasin.com

128 pointsNKosmatos15 comments

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

reddit community with seeded contests: https://www.reddit.com/r/brogueforum/

original game: https://sites.google.com/site/broguegame/

Seems like this was hugged to death by HN.

Web Archive link: https://web.archive.org/web/20230107220815/http://www.rogueb...

The article links to another one as well called "The Incredible Power of Dijkstra Maps": https://web.archive.org/web/20221116170436/http://www.rogueb...

> 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.

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

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.

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.

Yeah, I think you're right.

Maybe I should delete my parent response.

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/

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."

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

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 , yes the same Chebyshev as in Chebyshev's inequality https://en.wikipedia.org/wiki/Chebyshev%27s_inequality .)

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/FULLTEXT...

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.

Reminds me of minesweeper

Reply on news.ycombinator.com