Monday, April 14, 2008

Look Around and Listen (The Problem With State Machines)

At the last Game Developer Conference I attended a talk about enemy design in Naughty Dog's latest game Uncharted. Having not played the game, one statement really struck me. An adversary's average lifetime after being activated was measured in seconds. Most of their animation budget was devoted to deaths.

Good game design (as with many things) is all about capitalizing on your strengths and hiding your weaknesses.

This week I did a bit more work on my thief-like/rogue-like hybrid. The thief, not being homicidally inclined, is incapable of killing the guards. The longer they live (as with anybody) the more likely they are to do something stupid.

At first, guards could only see, and all they cared about was seeing the thief. They had a simple state machine, like this:

When a guard spotted the thief he would leave his patrol state and enter a brief “look” state. This gives the player one turn in which to get back into hiding. If they don't, the guard gives chase. (This may turn out to make the game too easy; if so I may need to do something additional, like having a guard go instantly to chase if they are in a state of alert.) When the guard lost sight of the thief he would enter a “search” state which consisted simply of moving to the last place he saw the thief. After a timeout, the guard would return to his patrol.

To add the sense of hearing, the first thing I did was to simply include it in the “Can I see the thief?” calculations. The obvious problem was that a guard would hear the player and say “What's that I see?” or something similar.

One solution would be to implement some sort of memory regarding whether the guard has seen and/or heard the thief in the current “interaction”. I thought it might be interesting to make the guard behave more aggressively based on a sighting than on hearing, so I opted to just add more states to my state machine. It wound up looking like this:

Investigate is the state in which a guard moves to the point where he last heard the thief. Search is moving to the point where he last saw the thief. Distinguishing between these allows the guard to say different things when he gives up and returns to patrol (“Where'd he go?” versus “The noises have stopped,” for instance). Chase is like search except that the thief is in sight. I can't remember if I really need it, but I think I'm using it to stop updating the last-seen position one turn after the thief goes out of sight (to simulate being able to see which direction he moved to get out of sight).

This is obviously getting kind of crazy, though. The next thing I'm working on is for guards to be able to alert other nearby guards. Currently I'm putting alerted guards into the search state and setting the last-seen position to the position of the guard who called out. This causes the alerted guard to move toward the guy making noise. If he doesn't spot the thief in the process, he'll eventually give up and return to patrol. Of course, inherent in the search state is the idea that he saw the thief at some point, so he might say something to that effect when he gives up, which makes him look odd.

State machines are nice when they have a handful of states; they help you to think about all the transitions and to encapsulate all state into single nodes. I find that they don't scale very well as the complexity and number of states grows, though. I don't feel like I've got a great solution to this yet.

No comments: