Monster path finding in 4.0.5

[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.

[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

[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.

[bio_hazard]

Maybe variant territory, but what about localization based on use of magic? This would be thematic. The footprint would be based on the number of mana used in the spell, and only "wizardy" monsters would pay attention to this gradient.

[Carnivean]

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 monster would have to be fairly dumb to just head straight into a wall, thinking it to be the quickest route to the player. Even a dog in a yard will run side to side seeking an exit. If there is an exit from the room, then there should be an intelligence based chance of the monster using it.

[luneya]

A monster would have to be fairly dumb to just head straight into a wall, thinking it to be the quickest route to the player. Even a dog in a yard will run side to side seeking an exit. If there is an exit from the room, then there should be an intelligence based chance of the monster using it.

Most of the monsters with this sort of telepathy will likely be wall-walkers like the various ghosts, so it's not stupid. For the rest, it seems fair to postulate that some monsters are dumber than dogs

More seriously, an animal that hunts primarily by telepathy is probably weak in the more physical senses, perhaps even completely blind. Or it might be so telepathically locked-in that it doesn't think to look around the room for alternate exits, or that it's not willing to walk directly away from its prey on the off-chance that it'll find another route (even though it sees a door across the room, it doesn't know how the hallway curves). Any of these would justify a behavior exactly like the current pathfinding.

We could, of course, create a new pathfinding algorithm with slightly different behavior if that seems more appropriate, but why go to the effort of doing that when we already have something that's known to work and does almost exactly what we want?

[Pete Mack]

If you want PASS_WALL and KILL_WALL monsters to path-find correctly, you need a different heat map when there are internal permawalls (vaults) present, alternatively, use whenever one of them does run into a permawall, let them proceed towards a vault entrance, then use the regular heat map inside the vault. The latter is not efficient, but they will eventually get to the player.

[Sky]

A small point but relevant to this thread: does every mob in the game have perfect infravision?

I just went with the old "the computer can, the player can't" that was the norm in videogames in the 80s and 90s. But since we are moving to buff the AI, how about we stop having mobs that see you while they are in full darkness.

.. not to mention, it would finally give some use to all those staves of darkness we squelch...

[AnonymousHero]

But since we are moving to buff the AI, how about we stop having mobs that see you while they are in full darkness.

I think you mean "while @ is in full darkness"? I mean, I can see a lamppost (for example) perfectly well even if I'm in the dark...

(Sounds like a good idea, btw.)

[Pete Mack]

Well yes. Bottom line, you need multiple Dijkstra flow maps, as I and others have mentioned before.
One for passwall/killwall (technically only needed on levels with vaults), one for ordinary monsters, one for fire immune monsters (technically only for levels with lava), and optionally a 'flow by smell' map for stupid (animal) monsters.

My recommendation is to treat all KILL_WALL/PASS_WALL monsters as immune to lava.

A monster would have to be fairly dumb to just head straight into a wall, thinking it to be the quickest route to the player. Even a dog in a yard will run side to side seeking an exit. If there is an exit from the room, then there should be an intelligence based chance of the monster using it.

[Derakon]

A small point but relevant to this thread: does every mob in the game have perfect infravision?

Every monster in the game currently has perfect telepathy, which is an even stronger claim.

I'm not opposed, conceptually, to changing this, so long as it introduces compelling gameplay changes. It's a substantial increase in complexity. Sil makes it work by having light be a major gameplay factor, but I'd be surprised if we could easily transplant Sil's mechanics to Angband.

[Sky]

the humber hulk's kill wall ability is a bit too strong. it's supposed to dig, but it just ignores it. maybe give it tunneling and let him dig, i.e., move slower?

[Derakon]

the humber hulk's kill wall ability is a bit too strong. it's supposed to dig, but it just ignores it. maybe give it tunneling and let him dig, i.e., move slower?

What fun would that be?

[Pete Mack]

Correct. It'd be too easy to escape. I do miss the 'grinding noises' that used to be associated with KILL_WALL monsters.

What fun would that be?

[Sky]

because he tunnels AND causes confusion. do you know how many @s i have lost to that stupid thing?