Friday 19 October 2007

Unangband monster AI - part two (What is worth doing?)

Part one of this article is here.

I want to expand on that idea of 'if the player can't see it, its not worth doing', which R. Dan Henry, current maintainer of Gumband is a big exponent of. There's a great article on artificial intelligence in F.E.A.R. called 'Three States and a Plan: The A.I. of F.E.A.R.' which anyone who is serious about artificial intelligence development for games should read. While the technical details are interesting, the key point worth making is that player's don't want realistic AI in games. They want AI that tells them what their opponents are thinking.

A player in a game will be frustrated if while they're hiding in a vent, an opponent rolls a grenade in and kills them without warning. That would be the realistic AI option, but that development effort ends up with the unintended result that the player just thinks the game is hard, not that the enemies are smart. What the player instead wants, is to hear the enemy say 'Gordan Freeman is hiding in the vents. I'm using a grenade.' That's not realistic at all. In a movie, you'd cut away to show the enemy soldiers signalling with their hands (and it'd still be exaggerated). But because the player can't see this, the AI actions have to be telegraphed to them. And audio dialog is used in a FPS engine to do this.

One of the most effective AI actions in F.E.A.R. is when the player has killed all but one of their enemies and they hear the radio message 'Man down, I need support. Calling for reinforcements.' broadcast by the last remaining survivor.

The equivalent AI action is: do nothing at all. No additional backup arrives. The designers didn't need to worry about developing this code. The player perception is that the backup is coming, so they have an incentive to hunt down the last survivor. And the designers know that there are more soldiers around the next corner, which the player will perceive as the reinforcements arriving a little to late. It may sound like a cheap trick, but it is a huge saving in development cycles and CPU time.

So what does Unangband do?

I try to find cheap answers, as opposed to smart answers. I'm not going to exhaustively catalog them here, more give you tasters of the various techniques I use. A lot of developers equate Artificial Intelligence in gaming with computer science AI, in particular, route finding or path finding. These are more the domain of operations research, which concerns itself with finding the best solution. AI should be more about finding a 'good-enough' solution: for local agents using limited information. The local agents, in the Unangband case, are monsters, and where possible, I strengthen the use of local information, rather than global solutions.

The Unangband monster structure contains the following 'local AI state' which is inherited from the 4GAI:

  1. A target (x,y) which the monster is heading towards.
  2. A minimum range that the monster wants to stay away from the target.
  3. A best range, that the monster wants to ideally be at.
  4. A set of flags which contain some AI state information: in particular, did the player attacked me the last turn.
  5. A set of smart flags indicating what resistances the monster has learned about the player.
Other than adding a few flags in 4, I did not expand at all on the existing monster AI structures. In return, I've been able to add the following additional behaviours:
  1. Monsters talk to each other, conveying information about the player position, resistances or lack of resistances.
  2. Monsters wake up their fellows nearby when they are under attack.
  3. Archers will share ammunition with each other, so that each monster in the group will usually have ammunition available.
  4. Monsters will eat when they are hungry, to help them recover from injuries.
  5. If a group of monsters is fighting the player and the player can be flanked, some will sneak off and take the back route to the player.
  6. Added friendly monsters, which intelligently move around the player and get out of their way, and attack targets, all done without adding a single 'order a monster to do something' command.
  7. When fighting another group of monsters, archers and spell casters will stay at the back while warriors will move up and form a front line.
  8. Faster monsters like wolves will attack isolated enemies, and the edges of the front line, dashing in for a bite and then retreating back.
That I've been able to achieve all of that is firstly a testament to the 4GAI code. I was amazed how readily I could add friendly monsters, despite Leon's opinion to the contrary. The concept of minimum range and best range is brilliant, and most of the formation code relies on this idea. But its also shows that you don't have to write particularly intelligent or deep code if you rely on using local agents 'naturally' and stick to local information. In the rest of today's article, I'm going to discuss point 1, and in follow up articles how I achieved the rest.

There are AI routines which already exists in the Angband code that allow the monster to learn about a player resistance, and then base the spell to cast on the information available. For instance, a vampire with several different elemental bolt spells might try the strongest fire bolt first, and, learning that the player resists fire, switch to lightning, then cold, and so on as additional resistances are learned. 4GAI provides much of the improvements to the code to allow this natural progression to occur, including adding monsters that rely on this.

In Unangband, if a monster learns about a player resistance, it tells all the other monsters around it. The player sees a message similar to 'The goblin wizard casts a fire bolt. The goblin says "The player is resistant to fire"'. Other information gets conveyed the same way, such as if the player is doing cheap exploits like hack-and-back or pillar dancing, the detection routines which come from improvements in the NPPAngband code. Pillar dancing may be seen as cheating by the august fellows of Rogue Basin (And I think John Harris would disagree), but in NPPAngband, monsters notice you doing it to them, and in Unangband, they tell everyone else around them as well, so the advantage of doing so is lessened.

The information communicated includes a state change on the listening monsters so that the talker knows not to provide redundant information if someone nearby has already mentioned it. This state change already exists in the monster structure, either being the player resistance flag, or other local information (such as am I awake?). And there's some nice gloss to requiring that the player speaks orc, to understand what those Uruk are saying, and so on.

The talkers will wake up monsters near them, which lessens the ability of super-stealthy characters to wake up and fight one monster in a room at a time, which always feels unrealistic to me in Angband. Of course, to counter this, if you manage to stun or cut a monster badly enough, it loses its ability to talk, so a backstab with a blade or blunt weapon becomes more worthwhile. And if you go around beating up the townsfolk, they run away, and tell everyone around them to run (or turn the tables on you if the listener happens to be a battle-scarred veteran), because they don't clear the particular 'I've been attacked' state flag, and pass it on.

There's nothing complicated about the code used to add monsters speaking. In fact it turns out that the problematic code that in the latest version causing monsters to randomly note you have incorrect resistances was me trying to be too clever, and simplifying the code was the correct fix. The incidental effects greatly improve the player perception of the AI. And, it makes a 'hidden' feature that has been in Angband for a long time: the fact that monsters learn about your resistances, a lot more obvious to the player.

In part three, I'll discuss other local monster interactions.

No comments: