Monster path finding in 4.0.5

[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 have this basically working in development now. I will push it out for people to look at fairly soon, once I have made suitable changes to monster sound sensitivity and sleep counter values.

[Pete Mack]

Phase door and illumination is certainly the preferred option, or just sucking up and fighting for a strong fighter with good damage. Mage should certainly phase door before it gets to a square away, then acid bolt etc. No real threat to a priest, since they are evil, and a single Orb will send them fleeing.

[Derakon]

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

If you're dying to this monster, then you need to prepare for it. Umber Hulks are far from an impossible challenge even if you're underlevelled; you just need to play smart.

Stay out of melee with them -- scrolls of Phase Door should be standard kit for every character, and they move at normal speed, so even if you don't see them before they break down the adjacent wall, you'll still have a turn to respond.

If you do get confused, you can try to kill them in melee; they have very little health and it doesn't take much to get them to flee.

Or you can drink CSW/CCW and hope that they miss their confusing attack, giving you a chance to phase away.

If you drink Speed, then you can drink CSW/CCW and be guaranteed a turn to get away.

You can use a Staff of Teleport even when confused, so that's also a good escape option if you've found/bought one by the time Umber Hulks show up.

[Sky]

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

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

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

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

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.

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

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

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

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

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

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

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