Developer's diary

Hi,

I'm about to implement a new monster movement AI system in my Angband variant
Unangband, and was wondering if people were interested in a 'development diary'
of the work I'm doing.

The problem: Unangband has a complex terrain system (hundreds of terrain
types), including ice, water, lava, acid, pools of oil that can be set alight,
chasms, giant spider webs, rubble, rope bridges and so on. At the moment, I use
an adaptation of Leon Merrick's 4GAI from Oangband/Sangband for monster
movement, but it doesn't correctly handle pathfinding over the variety of
different terrain. I need something that can cope with dynamic terrain, and
various combinations of movement. I've had a look at the NPPAngband 4.5GAI
monster movement system, but it doesn't quite do what I want. So in the
Unangband tradition I'll be writing my own.

Since its probably harder to describe the details of the terrain system, I'll
instead describe some 'usage cases' that I want the new monster movement system
to handle.

Example 1: The player is crossing a bridge over a chasm. A group of orcs is
moving through a corridor at the end of the bridge, and see the player through
one of the windows from the corridor into the chasm. The orc warriors rush to
the end of the corridor and start climbing onto the bridge. Meanwhile, the orc
archers start to shoot at the player through the windows.

#.#
#o#
#o'
#.#
#oooxxxx@xxxx

FYI x is the bridge character in Unangband.

Example 2: The player is at the edge of a lake, swarming with naga. One type
of naga uses the water to its advantage, swimming underwater for cover and
popping out to cast spells at the player, while staying at a distance. If the
player enters the lake, another type of naga swarms forward, attacking the
player with their poisonous bite. This type had hidden under the water until
the player could be attacked.

Example 3: A group of giant spiders, which leave a trail of webs behind them,
swarm into a chasm to attack the player, who is on the other side. The giant
spiders crawl around the edge of the chasm toward the player. Their trails of
webs allow grow to form a spider web that fills the chasm. This allows further
spiders to crawl directly to the player over the webs.

Example 4: The player flees from a group of monsters and enters a room filled
with cupboards. The monsters follow into the room. Suspicious that the player
may be hiding in the cupboards, the monsters open then all. Meanwhile, the
player has cast an invisibility spell and used the delay to flee.

Example 5: A monster has yet to encounter the player. He wanders through the
dungeon corridors, getting to a room, and then choosing an exit from the room
to explore further. His path is predictable, so that the player can detect him
using detect monster spells. Because this monster is too much danger for the
player to handle at this stage, the player is able to use this information to
avoid the monster, while still exploring all the locations that the monster
frequents.

Regards,

Andrew

On 2006-09-08 17:26:44, Andrew Doull <andrewdoull RemoveThis @gmail.com> wrote:

> Hi,
>
> I'm about to implement a new monster movement AI system in my Angband variant
> Unangband, and was wondering if people were interested in a 'development diary'
> of the work I'm doing.
>
> The problem: Unangband has a complex terrain system (hundreds of terrain
> types), including ice, water, lava, acid, pools of oil that can be set alight,
> chasms, giant spider webs, rubble, rope bridges and so on.

My initial problem, is that monster movement at the moment in Unangband works
okay for normal terrain, but breaks down for mixtures of terrain. I want to be
able to handle the case where a monster has to swim through acid, and then open
a closed door in order to navigate the shortest path to the player. A monster
which has only one of these abilities will have to find a longer path.

One option is to compute pathfinding for each monster. But dungeons in Unangband
can have lots of monsters. So I want to look at alternatives.

I suspect I am going to have some kind of array of path costs to get to the
player, for each x,y location, and for each 'combination' of monster
abilitiess.

If we use numbers for costs, an example might be:
############
#65432123456#
#54321@12345#
######1######
######2######
where numbers indicate the cumulative cost to get to the player. The algorithm
for monster movement then becomes pick the adjacent location with the lowest
cost for any array where it have the correct 'combination' of monster
abilities.

This is fine for moving towards the player, but for the reverse: fleeing from
the player, this breaks down. If we pick locations for higher costs, we don't
necessarily get a safe path away from the player. In the above example, the
monster will end up in a dead end that isn't safe rather than fleeing down the
corridor directly below the player.

Note that it might be possible to mark dead ends in such a way we can still use
this algorithm. If we define a dead end as a location where there is no higher
cost adjacent, below a 'certain cutoff' (e.g. far enough away from the player to
be safe). Then the 'sixes' in the above example will be marked as dead ends. We
then spread the dead ends by ignoring anything we've already marked as a dead
end and re-applying the algorithm until we have a settled state. In the above
example, assuming the corrirdor below the player is not a dead end, then
everything except the corridor is marked as a dead end. Then reverse the sign
on the dead end locations.

The movement algorithm then becomes:

1. When moving towards the player, pick the adjacent location with the lowest
ABS(cost).
2. When moving away from the player, pick the adjacent location with the
highest cost.

This may not still be correct, as it encourages monster fleeing past the player
to always run adjacent to them. We also should bias monsters to either
left-handedness or right-handedness when choosing from multiple locations of
equal cost.

Regards,

Andrew