Monster path finding in 4.0.5

[fizzix]

I think the approach nick outlines is probably a good starting point. We can compute a whole bunch of heatmaps each turn based off of scent and sounds. Let's try that and see how quickly the game runs, if it winds up being too slow, we can start considering optimizations.

[t4nk]

For code readability purposes, do you mean?

For readability, as an optimization (people seem to be concerned about it ) of both struct square and the heatmaps (fitting into cache), but most importantly, for ease of adding more heatmaps (Sil has 400+ of them!) and for possibility of them carrying additional information.
Something like:

struct heatmap {
    uint16_t **grids;
    /* some other stuff that might be useful... */
};

struct chunk {
    stuff; /* as currently */

    struct heatmap *heatmaps;
    int num_heatmaps;
};

That sounds sensible - how do they do it?

Pretty much like hitpoints are displayed, updated on each turn, for example:

Noise: [######..]

or just as numbers:

Noise: 4/9

[Nick]

Thanks for all the responses.

You say that, but what about lava, immobile monsters, and other such barriers?

Good point. For immobile monster place-swapping is sometimes possible; lava is an interesting one.

Does this mean that we track noisiness on a per-tile basis? Do we track noises not caused by the player?

Player noise would be generated every turn as a heat map, with the starting value dependent on stealth and possibly player action. I would start by tracking no other noises, but try to allow for that to be added later.

Sounds plausible to me. What happens if we have a monster tracking the player by noise, then they stumble onto the player's scent trail? What happens after that if the player teleports? What if the monster saw the player teleport?

Monsters (probably all?) would prioritise sound over scent, because it's more immediate. A teleported player would no longer generate sound, but scent would remain, so some monsters would just stop and some would track to where the player left from. If they saw - probably would continue scent tracking anyway, but they would be fairly close so it wouldn't make a lot of difference.

Sounds like a good start. Presumably we want to have it so that different monsters use different tracking procedures. Most monsters will use sight first, then sound, and otherwise stay put, as they don't have scent or telepathic tracking ability. Those that do have the latter abilities will rely on them. Pick thematically appropriate monsters to be able to scent-track: hounds, obviously, perhaps giants/ogres (Fee Fi Fo Fum...), etc.

This is exactly how I'm thinking of it.

As for telepathy, I would envision two types. The commonest type, which would be exemplified by monsters like the mind flayer, would be essentially identical to the current pathing. The monster always knows where the player is, but doesn't know the correct path, and so if there's no near-straight-line route, it gets hung up on a wall.

A more sophisticated telepathy, where the monster has full knowledge of the dungeon and always chooses the most efficient route, should be implemented but only made available to uniques, and particularly only to those which should thematically have it: Sauron, the Nazgul, Saruman, Osse, Arien, and perhaps one or two other such great powers that I'm forgetting. (Tunnelers like Morgoth and wall-walkers like Adunaphel can be excluded from this class, as they'll get as good of a result with just the other telepathy.) Since the set of monsters with this power is quite restricted and only one or two will likely be generated on any level at a time, we can afford to use a computationally expensive algorithm to get their movement right if necessary.

I like this a lot.

That seems good to me. I'd suggest to remove 'noise' and 'scent' from struct square, and instead introduce several 'flow maps' in struct chunk - two dimensional arrays of bytes (or uint16_t or whatever): one for player noise, recalculated on each player's turn, and one for each stair and perhaps several for other kinds of noise

For code readability purposes, do you mean?

Also, if different actions produce different amounts of noise, that should be displayed in the UI (a la Dungeon Crawl).

That sounds sensible - how do they do it?

With these pathfinding algorithms, any chance the player will get actions to (try to) confuse their trail? Dropping food or throwing stones or torches, etc?

I think not to start out with, but it's a possibility for later.

For scent based tracking, Brogue has a very good implementation that would be worth stealing.

The scent distance metric is the second one described on this page:

http://brogue.wikia.com/wiki/King's_move

Every move in Brogue, all scent weakens by 3, then you throw your scent on every tile in LoS according to this metric. If the scent is fresher than what's on that tile, it gets updated. This effectively means that monsters who track you via scent will follow along an optimal path to your new location.

You can look in the Brogue source code to see how it's implemented, and also some optimizations, for example, rather than aging all scent by 3, there's a global counter that increments by 3 every turn, and new scent adds the global counter to its value before being placed on tiles, meaning that rather than old scent being 'weakened', new scent is 'strengthened'.

I think that's pretty much how it's done in O/FA, too.

[Patashu]

For scent based tracking, Brogue has a very good implementation that would be worth stealing.

The scent distance metric is the second one described on this page:

http://brogue.wikia.com/wiki/King's_move

Every move in Brogue, all scent weakens by 3, then you throw your scent on every tile in LoS according to this metric. If the scent is fresher than what's on that tile, it gets updated. This effectively means that monsters who track you via scent will follow along an optimal path to your new location.

You can look in the Brogue source code to see how it's implemented, and also some optimizations, for example, rather than aging all scent by 3, there's a global counter that increments by 3 every turn, and new scent adds the global counter to its value before being placed on tiles, meaning that rather than old scent being 'weakened', new scent is 'strengthened'.

[bio_hazard]

With these pathfinding algorithms, any chance the player will get actions to (try to) confuse their trail? Dropping food or throwing stones or torches, etc?

[t4nk]

I think a complete rewrite of monster pathfinding is in order - a lot of the code is old, and the flow stuff in particular is hard to understand because of no-longer needed optimisations. So I've thought about how it should work in principle, and come up with this:

• Monsters should track the player by sight, sound and smell. Maybe telepathy too, but let's keep it simple for now.
• Sight: If the monster sees the player, they can head straight for them. Easy.
• Sound: Every turn, the player makes some noise, with stealthier players making less. Monsters have a threshold for noticing noise; if the noise at their grid is above that, they will follow increasing sound.
• Smell: Every turn, the player grid (and maybe nearby grids) is marked with scent, which ages off over time. A monster that cannot see or hear the player may be able to follow scent trails.

I would see this as a starting point - what do others think?

That seems good to me. I'd suggest to remove 'noise' and 'scent' from struct square, and instead introduce several 'flow maps' in struct chunk - two dimensional arrays of bytes (or uint16_t or whatever): one for player noise, recalculated on each player's turn, and one for each stair and perhaps several for other kinds of noise (perhaps teleportation should make noise? presumably teleporting stuff leaves a pocket of vacuum that collapses with a loud sound - in gameplay terms, that's a method to nerf teleportation a bit).
The maps for stairs would allow to introduce monsters patrolling between stairs, like in Sil, which is cool and good for gameplay (IMO).
The smell idea is also good, it should make corridors a little bit more dangerous (and currently smell, as implemented, does very little, pretty much nothing in practice).
Also, if different actions produce different amounts of noise, that should be displayed in the UI (a la Dungeon Crawl).

[luneya]

I think a complete rewrite of monster pathfinding is in order - a lot of the code is old, and the flow stuff in particular is hard to understand because of no-longer needed optimisations. So I've thought about how it should work in principle, and come up with this:

• Monsters should track the player by sight, sound and smell. Maybe telepathy too, but let's keep it simple for now.
• Sight: If the monster sees the player, they can head straight for them. Easy.
• Sound: Every turn, the player makes some noise, with stealthier players making less. Monsters have a threshold for noticing noise; if the noise at their grid is above that, they will follow increasing sound.
• Smell: Every turn, the player grid (and maybe nearby grids) is marked with scent, which ages off over time. A monster that cannot see or hear the player may be able to follow scent trails.

I would see this as a starting point - what do others think?

Sounds like a good start. Presumably we want to have it so that different monsters use different tracking procedures. Most monsters will use sight first, then sound, and otherwise stay put, as they don't have scent or telepathic tracking ability. Those that do have the latter abilities will rely on them. Pick thematically appropriate monsters to be able to scent-track: hounds, obviously, perhaps giants/ogres (Fee Fi Fo Fum...), etc.

As for telepathy, I would envision two types. The commonest type, which would be exemplified by monsters like the mind flayer, would be essentially identical to the current pathing. The monster always knows where the player is, but doesn't know the correct path, and so if there's no near-straight-line route, it gets hung up on a wall.

A more sophisticated telepathy, where the monster has full knowledge of the dungeon and always chooses the most efficient route, should be implemented but only made available to uniques, and particularly only to those which should thematically have it: Sauron, the Nazgul, Saruman, Osse, Arien, and perhaps one or two other such great powers that I'm forgetting. (Tunnelers like Morgoth and wall-walkers like Adunaphel can be excluded from this class, as they'll get as good of a result with just the other telepathy.) Since the set of monsters with this power is quite restricted and only one or two will likely be generated on any level at a time, we can afford to use a computationally expensive algorithm to get their movement right if necessary.

[Derakon]

Sight: If the monster sees the player, they can head straight for them. Easy.

You say that, but what about lava, immobile monsters, and other such barriers?

Sound: Every turn, the player makes some noise, with stealthier players making less. Monsters have a threshold for noticing noise; if the noise at their grid is above that, they will follow increasing sound.

Does this mean that we track noisiness on a per-tile basis? Do we track noises not caused by the player?

Smell: Every turn, the player grid (and maybe nearby grids) is marked with scent, which ages off over time. A monster that cannot see or hear the player may be able to follow scent trails.

Sounds plausible to me. What happens if we have a monster tracking the player by noise, then they stumble onto the player's scent trail? What happens after that if the player teleports? What if the monster saw the player teleport?

[Nick]

I think a complete rewrite of monster pathfinding is in order - a lot of the code is old, and the flow stuff in particular is hard to understand because of no-longer needed optimisations. So I've thought about how it should work in principle, and come up with this:

• Monsters should track the player by sight, sound and smell. Maybe telepathy too, but let's keep it simple for now.
• Sight: If the monster sees the player, they can head straight for them. Easy.
• Sound: Every turn, the player makes some noise, with stealthier players making less. Monsters have a threshold for noticing noise; if the noise at their grid is above that, they will follow increasing sound.
• Smell: Every turn, the player grid (and maybe nearby grids) is marked with scent, which ages off over time. A monster that cannot see or hear the player may be able to follow scent trails.

I would see this as a starting point - what do others think?

[Pete Mack]

In path calculation, it's not number of squares that matter, it's number of vertices and edges. As a crude first approximation, the number of vertices is bounded by the number of corner squares in the map, and the number of edges is between 3 and 4x greater. There's a concept of 'visibility graph' that is roughly the kind of graph wanted. With a visibility graph, with hallways reduced to a single node, the problem is really quite small. Note that visibility graphs are pretty easy in the special case of rooms and hallways assembled from axis-aligned grid-based rectangles.

Further, for player moves between adjacent nodes, recomputing the shortest path is much cheaper than the initial Dykstra algorithm used to compute a minimum spanning tree.

[Antoine]

Only some types of monster should be able to track the @ over great distances.

[fizzix]

And I say again, it's not nearly as slow as you people think. You know, you can actually try that. Just increase mon-play:flow-depth in constants.txt to something reasonable, like 200 (note that flow is always recalculated after player's move, see monster_swap()). The result might surprize you... (you can view the flow propagation with Ctrl+A and _)

edit: Angband's level is what, 198x66 max? Let's say 200x100, or 20000 grids. Let's even devote a uint16_t for each grid (for storing noise - scent is kind of useless, IMO) (edit: come to think of it, a byte should suffice, by anyway...). I assure you that it's entirely practical to process a 40kb array every single frame, many times over even... Angband's flow depth is so tiny (32) because it just uses it in a pretty crazy way. The gory details are in get_moves_flow() (if (found_direction) { ... }) and it's kind of insane

Yeah, we can definitely do the player map (I do think I extended that to 1024 squares or something, which certainly should be far enough). The problem really comes if you try to compute multiple paths on each turn, which you'll need to do if you want to do stuff like tracking to approximate or last known locations.

Static heat maps are much easier. They only need to be computed once, when the level forms (and then whenever the player or a monster decides to create or destroy a wall...)

[t4nk]

In the technical side of this Angband runs into a few problems. The levels tend to be very large, which is necessary in order to fit these giant vaults we have, but makes tracking problems and heat map generation more computationally intensive. If we could shrink level size by half or so, it opens up a lot of options for better tracking, wandering monsters, etc. It's a tradeoff worth considering.

And I say again, it's not nearly as slow as you people think. You know, you can actually try that. Just increase mon-play:flow-depth in constants.txt to something reasonable, like 200 (note that flow is always recalculated after player's move, see monster_swap()). The result might surprize you... (you can view the flow propagation with Ctrl+A and _)

edit: Angband's level is what, 198x66 max? Let's say 200x100, or 20000 grids. Let's even devote a uint16_t for each grid (for storing noise - scent is kind of useless, IMO) (edit: come to think of it, a byte should suffice, by anyway...). I assure you that it's entirely practical to process a 40kb array every single frame, many times over even... Angband's flow depth is so tiny (32) because it just uses it in a pretty crazy way. The gory details are in get_moves_flow() (if (found_direction) { ... }) and it's kind of insane

[fizzix]

@ derakon-- you don't have to do pathfinding for every monster. You do it to make a map starting from the player, to every room in the dungeon. (Symbolically, pinch a string network of the dungeon at the player's location, and let the rest of it hang down. Strings under tension become routes.) Then the monsters follow it in reverse.

So ideally you actually want several heat maps. One from the player, and a few more from static points in the map (steal a page from Sil's book and heatmap from each stair.) Then you can have monsters that wander around the level, as well as ones that are tracking the player.

In the original map posted, where the pit fiend could not find the path, this is essentially working as intended. The pit fiend knows where @ is, but the number of spaces between the fiend and @ is larger than the tracking distance (which is monster dependent with a hard cap at the heat map value, 256 I think). So the fiend can't actually track @. BUT the fiend is within the minimum tracking distance (as the crow flies), so it is considered active and tries to move towards @, which is why it hops up and down along that wall. If you move closer to the fiend at some point it will be able to track the player, and it will move appropriately.

Now in my ideal conception monsters would be split into different states of awareness. At one end there's asleep, and at the other end there's in LoS of the player. These work the same as currently. But I'd like two other states, aware that player is nearby, and aware that player has been seen recently (but teleported away or whatever). The first state would track almost as currently, but the second state, "aware that the player has been seen recently", would be more interesting. In this state the monster is encouraged to wander in a specific direction. (In the case where the monster was teleported, this could be the last seen location of the player, in the case where the player teleported, this could be some random far away point). Then we can add a fifth state, which is unaware of the player but wandering anyway. This is a good state for packs of hounds (if you can somehow keep them somewhat coherent.) FWIW I did try implementing this stuff upon a time, but I failed and gave up. I could never get alternate heat maps to work properly, which was an inability on my part entirely.

In the technical side of this Angband runs into a few problems. The levels tend to be very large, which is necessary in order to fit these giant vaults we have, but makes tracking problems and heat map generation more computationally intensive. If we could shrink level size by half or so, it opens up a lot of options for better tracking, wandering monsters, etc. It's a tradeoff worth considering.

[t4nk]

Bear in mind that any one-to-one pathfinding solution (where each monster calculates its own path to the player independent of other monsters) is likely to bog down even on modern computers, considering the number of monsters on the level and the size of the level. A* is a one-to-one pathfinding solution, unfortunately. The heatmaps work because they do a single pass to generate the heatmap, which all monsters can then share for their needs.

You shouldn't judge by the slowness of CPython's VM. Of course, there are limits, but generally, in C the performance of that kind of code is simply incomparable. I'm not even proposing to run A* on every single monster across the whole levels?
Example: Sil has about 400 flow tables. Consider melee2.c:4484. Yeah, I know, you haven't played Sil, but maybe you should
In any case, I going to reduce the size of levels and number of monsters, irregardless of pathfinding