4 ms·

Basically putting a gradient field on a discretized map for rogue-like games and then doing motion planning accordingly. For example, having enemies gradient as

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/

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/