[HN Gopher] Dijkstra Maps Visualized
___________________________________________________________________
Dijkstra Maps Visualized
Author : NKosmatos
Score : 118 points
Date : 2023-01-17 10:09 UTC (12 hours ago)
(HTM) web link (www.roguebasin.com)
(TXT) w3m dump (www.roguebasin.com)
| abetusk wrote:
| 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 wrote:
| 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.
| amitp wrote:
| 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/
| abetusk wrote:
| Yeah, I think you're right.
|
| Maybe I should delete my parent response.
| arbol wrote:
| Reminds me of minesweeper
| robocaptain wrote:
| 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/
| jeffreygoesto wrote:
| 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...
| [deleted]
| karussell wrote:
| 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
| philsnow wrote:
| 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 .)
| tuukkah wrote:
| 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."
| fileeditview wrote:
| Seems like this was hugged to death by HN.
|
| Web Archive link:
| https://web.archive.org/web/20230107220815/http://www.rogueb...
| abetusk wrote:
| The article links to another one as well called "The Incredible
| Power of Dijkstra Maps":
| https://web.archive.org/web/20221116170436/http://www.rogueb...
| 082349872349872 wrote:
| > _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.
| matthewmorgan wrote:
| Really cool, reminds me of this article I once read:
| Collaborative Diffusion: Programming Antiobjects
| https://home.cs.colorado.edu/~ralex/papers/PDF/OOPSLA06antio...
___________________________________________________________________
(page generated 2023-01-17 23:01 UTC)