3 ms·
So basically just a shortest path algorithm starting from the player to all other tiles?
by Jaxan 7y ago
So basically just a shortest path algorithm starting from the player to all other tiles?
- masklinn 7y agoSounds like that's what the base layer is yes, though the additional layers are interesting.
- fwip 7y agoNot exactly - a shortest path algorithm would lead to the monsters "anticipating" the player coming around the obstacle and cutting them off. The algorithm is summarized in the article as: "When an enemy enters the Chase state it tries to raycast to the player and if nothing is in the way - chase em! If something is in the way, it goes through the scent trail in order and tries to raycast to each scent until it can see one, then - chase it!" With complex geometry, this will frequently lead to a non-optimal route, and is probably more fun to play against.
- xsmasher 7y agoNot 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.