Unangband monster AI - part three (Emergence)

In part two, I mentioned that monsters were woken up as a side-effect of the monster talking code. Consider, for a moment, an AI system that only relied on monsters talking to each other, and did not implement any path or route finding algorithms. You could do this as simply as having monsters saying one of two things:

1. The player is not here
2. The player is here

The behaviours you'd then implement in a system would be:

1. If the player is here, stay where we are.
2. If the player is not here, move somewhere else.
3. Move away from positions you can hear a monster saying that the player is not, and towards positions that you can hear a monster saying the player is.

The emergent properties of that system would be that monsters would quickly move towards the player location, without having to rely on an explicit route finding algorithm.

In Unangband, such a property emerged from another AI flag I had implemented, without me even intending to do so. The flag in question is the wonderfully named MFLAG_PUSH, which I added to fix a problem I introduced modifying the 4GAI.

In Angband, particularly powerful monsters can push past weaker ones, swapping positions. The 4GAI expands on the numbers of monsters that do this, and in Unangband, I basically allow every monster to push past another. However, this can result in a deadlock situation. Consider two monsters that are running down a corridor. If the one in front is moving before the one behind, no problems occur. However, if the one behind moves first, it'll swap positions with the first. Then the first one, which is now behind, will swap positions again. The two monsters will end up effectively running in place, swapping positions and never going anywhere.

To avoid this situation, I added the MFLAG_PUSH flag, to which was set on both monsters, when one pushes past the other. And when a monster has MFLAG_PUSH set, it becomes unpushable, until the start of its next move, at which point it is cleared. The flag is set on both monsters to prevent either getting 'free moves' by being pushed around by multiple monsters: originally I did this to prevent a monster that must swim being pushed beyond the edge of water (which requires two consecutive pushes), but it equally applied to stop a powerful monster getting multiple moves against the player.

And something interesting happened. Consider the interaction of a group of monsters moving at the approximately the same speed towards the player, one behind the other. However, the monsters are moving in a larger area, like a room. At some point, the front monster will end up with the MFLAG_PUSH flag, because he'll be slightly faster than the others and pushed his way to the front. However, because he's not twice as fast, so the monster behind will get a turn first before he can move again. The monster behind clears the push flag, and considers which squares he can move into. The immediately front one is blocked, by a monster with an MFLAG_PUSH set. However, the two immediately diagonally to either side are clear. Since all Angband variants don't increase the movement cost of diagonal moves, the monster will choose to move into one of the diagonals.

And the monsters behind him will take the same approach. What emerges, is that the group of monsters naturally spread out to a wide front taking up the available width of the open area, or their group size, whichever is smaller. And it so happens, that a wide front is the smartest group for most monsters to form.

Its important to note that this occurred accidentally, without any concept of formations or other AI tricks programmed in, and is a single bit-flag setting in the monster structure. The route finding required for this formation is completely local: a simple 'can I move into the adjacent grid' test. And the emergent property is impressive, resulting in a complex looking front on the playing field.

If you look hard at the concept of using local information to guide the monster AI, suddenly a number of other useful strategies make themselves apparent. I've already discussed the monster talking above; but here's a few more:

1. Monsters should hang around dead bodies, but not too close.
2. Monsters should hang around injured fellows, but again, not too close.
3. Monsters should aggressively search, if they find a dead body (This is straight out of Metal Gear Solid: of course, remember to mark the body as having been found, otherwise the monster will keep going into high alert mode every time they trip over the same corpse).
4. Monsters should share resources they don't need with each other.
   

Point 4 is a subtle one. It's not monsters should ask for resources they need. That behaviour is too complicated, and requires all sorts of smart AI assessment. Consider the resource of ammunition. Unangband has added ammunition on top of the 4GAI, to balance monster archery. And monsters do quickly run out of ammunition, if they're given half a chance to shoot at the player. At this point, they could either do a complicated search algorithm to try to find out which of their compatriots has ammunition, or just advance on the player and try to attack in melee.

And advancing, as I've noted previously, is a lot more interesting for the player. However, the monsters directly behind the archer, if any are there, may possibly have the ammunition that the monster needs. And they're not doing anything, so they should be sharing ammunition with anything they push into. Consider it a game economy of ammunition sinks, and ammunition providers. You want the providers to share freely with the sinks. The sinks will naturally be greedy without even trying.

I've implemented (approximately) the following algorithm:

1. If the monster I walk into and I use the same ammunition, average the amount between us.
2. If I have ammunition that the monster needs, give him half my inventory, including the ammunition.
3. Otherwise, give him all of my inventory.

And the result, of a simple sharing routine, is that everyone in a group quickly ends up with approximately the same ammunition. As it gets used up, the individuals in the group ensure that overall, each has the same amount. Again, the rules are only local, not global.

I'm in the process of adding a second emergent property to the same MFLAG_PUSH flag. The MFLAG_PUSH is another way of saying 'don't walk through me'. And when you think about it, the time you don't want that the most, is when you are doing useful work. The most useful work a monster can do, is successfully attack the player. By adding an MFLAG_PUSH to the monster when they've successfully attacked the player, a number of other useful emergent properties occur. And I'll talk about those in part four.

[Edit: Actually I won't. I end up introducing the allied monster AI in part four, because it's hard to talk about the effectiveness of AI, without having a playable demonstration, and showing off the ally AI is the easiest way of doing this. Basically, as pointed out in the comments, you don't want to have ranged attacks being marked as 'useful work' because you can have archers blocking melee monsters in corridors, but you do want melee monsters to be marked as doing useful work, for other reasons].