4 ms·
Not really - a shortest path algorithm outputs a single path between a start and an end point. This gives you a value (distance to player) for every square on
by xsmasher 7y ago
Not really - a shortest path algorithm outputs a single path between a start and an end point.
This gives you a value (distance to player) for every square on the board; you can do a lot of things with that data, like choose between multiple "best steps" based on some other preference, or choose "best steps" for a large number of monsters efficiently.
- fwip 7y agoNo, it doesn't give you a distance-to-player for every square on the board. It is closer to giving you an ordered list of 'most recent player positions' - notably, the point directly in front of the player is not necessarily in this list. These positions contain "time since player was here," which is not a distance to player. (It could be thought of as a maximum bound on distance-to-player, I suppose). If the player's route is not straight, some squares with "fresher scent" may be physically more distant from the player than squares with less fresh scent.
- eindiran 7y agoYour parent comment is referring to the Dijkstra Map algorithm described in the top-level comment, not the algorithm discussed in the article.
- zetalemur 7y agoAssuming this is calculated on every turn: Then it is a shortest path tree from the player position (the root) to all tiles.