4 ms·
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 cas
by 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 agoYeah, I think you're right. Maybe I should delete my parent response.
- amitp 4y agoIt'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/