Thursday, 8 November 2007

Unangband monster AI - part five (Complications)

In part four, I discussed how the Angband targetting system is used by the allied monster AI to implicitly take commands from the player. To reiterate, when the monster AI is not able to find a nearby enemy monster, the ally will instead move towards the location that the player has targetted, with a number of variations. I deliberately built the allied AI system this way so that the player would not have to learn additional commands in order to order his troops around. I then hinted that there was one additional command that needed to be implemented. And if you've been reading comments elsewhere on the Unangband home page, you'll know what this is.

If you've played with the Unangband allied AI, you will have seen that the majority of your troops actions are dictated out of the more general monster AI routine. I adapted the min_range and best_range algorithms slightly, but was able to get approximately the same behaviour in terms of troop movements as the 4GAI already does for enemy monsters. And otherwise, the AI routines are the same. With a target found, allied archers will shoot and allied warriors will melee. Allied river orcs will hide in water, allied wolves will harass the enemy and so on. The flexible 4GAI monster system works perfectly in this regard, honouring all the monster flags that Angband implements. Hopefully, your minions will survive the first couple of fights, loot the bodies of the dead (or eat them, if they are so inclined), and with their spoils, follow you on to further battles.

And that's the problem. If the allied monster has the TAKE_ITEM flag, which means they pick up whatever items are in the grid that they move into. And they will. Archers will strip the ammunition off of the enemy and re-use it. The (very limited) monster use an object routine I've implemented means that food and corpses will be consumed by some types of your allies to recover wounds. And you'll have no way of getting anything that your allies pick up off of them, unless you kill them, or have them killed.

It's even worse for your summoned allies. Due to the summoning veil implementation I discussed elsewhere, minions you summon will leave your service and disappear after a timeout period. And they'll take everything they picked up with them. That's an easy fix - just have the monster drop everything when they leave. But the more general case will be problematic.

So I'm going to have to do a 'interact with allies' command. This will allow you to get equipment from them, give stuff to them, dismiss them from your service and perhaps a few other house-keeping chores (such as targetting them with spells you'd otherwise only cast on yourself, such as healing). In fact, it should be generic enough to make a general 'talk to monsters' command - so you can always try to buy your equipment back from the thieves who stole it as opposed to kill them. Or buy that rope from an orc standing on the other side of a chasm ('No, throw me the idol').

In the long run, I'll have to implement a more sophisticated orders system. If I ended up implementing battles using a turned based tactical system, you'll want to be able to select only part of your forces and give them an order, as opposed to all of them. Or have an orcish warg rider convey your orders to a unit elsewhere on the battlefield.

Speaking of warg riders, and wolves in general, I fudged things when I said that the flexible 4GAI monster system works perfectly in implementing the monster abilities. And it stood out when I created a werewolf player character and had him appear at the Battle of Five Armies with his wolf cousins. Because they got demolished, repeatedly.

Wolves are a dangerous opponent to the player character, because they move quickly, which means that they attack twice as often. But it also means that the player can get surrounded by them much more easily and attacked from all eight sides. If a player is half way across a room and a door bursts open and wargs attack, he cannot outrun them back to the safety of a single-width corridor. The much-maligned Kheldon Jones pack AI implements exactly this test: it determines how many blank squares are around a player and only has pack monsters advance to attack if there are sufficient squares free to make the player 'vulnerable' (It's maligned because it breaks the 'monsters must advance to stay interesting' paradigm).

But in a large battle-situation, with tens of opponents on either side, the wolf speed advantage gets eroded to just being able to attack faster. And this is not enough to withstand similar level monsters, who will have more attributes scaled up to make them equivalently dangerous to the player. For instance, orcs will hit harder, and have more hit points, than wolves, as they get deeper in the dungeon (It's worth noting that Unangband uses a reasonably sophisticated monster power algorithm to determine relative monster strengths, as opposed to determining monster level 'by hand').

I initially thought 'Ah - hack and back'. This is the traditional tactic to use when you have a speed advantage - where you attack, then step away before the enemy can respond in kind. And the hack and back algorithm is a 'tweak' to the monster minimum and best range, which increases the best range slightly if the monster is next to its target, and the target will get to act before the monster's next turn. Because I neglected to remove the diagnostics for this from the wip7a release, you may have seen the occasional 'backing' message while you were playing to indicate this decision had been made.

But hack and back is not nearly enough. It's a brief advantage only, and the wolves continued to get cut down without mercy. They simply didn't have the space to use hack and back tactics and tended to back themselves into a group around the player and get killed.

The Kheldon Jones pack AI concept came to the rescue. I added a 'vulnerability' weighting to the target selection routine, used if the monster is faster than the target. If this is the case, and the target has more than 4 unoccupied grids surrounding it, the target will be treated as closer than targets without this vulnerability, for the purpose of which enemy the monster will target. Now, when you appear on the battlefield with wolf allies, the wolves will attack the two ends of the advancing enemy front, splitting into two groups and harassing isolated individuals, where they are able to use the same tactics which were so effective against the player.

This concept of reweighting the target selection routine for specific monster behaviour could also be used for traditional racial enemies, so that your allies attack more distant targets if they have a particular hatred of them. It probably should be used in the instance of monsters that are vulnerable or nearly invulnerable to certain types of attacks, so that they are encouraged to fight those enemies which can hurt them the most (Currently ghosts and skeletons, immune to blunt and edged weapons respectively, also 'under-perform'). It shouldn't be abused to much though, as 'closest enemy' is a useful concept to retain.

I've covered the main innovations of the Unangband monster AI. Stick with me, as I attempt to wrap up in part six.


David said...

I'm just a little confused. You say "It probably should be used in the instance of monsters that are vulnerable or nearly invulnerable to certain types of attacks, so that they are encouraged to fight those enemies which can hurt them the most (Currently ghosts and skeletons, immune to blunt and edged weapons respectively, also 'under-perform')."

Why wouldn't the allied monster take advantage of intrinsic resistances? Specifically, kill monsters that can't hurt them but could hurt their own allies and the player character?

Andrew Doull said...

For your two questions, yes, allied monsters benefit from intrinsic resistances. But no, they do not specifically kill monsters that can't hurt them. In fact, you want the opposite behaviour: you want them to target the monsters that can hurt them.

Consider a ghost, which is immune to blunt weapons, taking on a group of monsters which has a mix of blunt and edged weapons. If the ghost targets the blunt weapon users in the group, they will quickly be killed by the edged weapon users.

The reason being is the emergent behaviour of the system at the moment, favours the sword wielding enemies (as the mace users get killed off). So the group composition quickly changes to favour the monsters that are most effective against ghosts.

You'll see, if you get ghostly allies (pick a vampire or werewolf and get ghost bats or ghostly wolves), the ghosts get killed very quickly.

So instead, you want your ghosts to target edged weapon users preferentially, even though these monsters are most effective against ghosts. This will change the balance of the enemies to blunt weapon users, which means that the ghosts overall will become more effective against the group.

Only the player has the 'overall' picture of the battle situation. So certainly giving him the capacity to split forces is appropriate - (ghosts, target the slingers, skeletons, target the archers) - because the individual monster AI is probably not going to get smart enough to figure out what allies he is fighting alongside and make the 'correct' decision.

I do take account of resistances for individual allies when they are picking which spell to use, but this does't help if you have a mix of allies with different resistances.

Ideally, if you say had fire and ice elementals as allies, you'd want your ice elementals to take on enemies resistant to fire, and your fire elementals to take on enemies resistant to cold. This requires a more complex 'pick an target' function and one I'm unlikely to implement.