Hacker News Reader

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.

View on HN

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

Your parent comment is referring to the Dijkstra Map algorithm described in the top-level comment, not the algorithm discussed in the article.

Assuming this is calculated on every turn: Then it is a shortest path tree from the player position (the root) to all tiles.

Reply on news.ycombinator.com