Artificial Intelligence and You (AIandU)

In this series of posts, I will be attempting to answer questions posted by PaulT at ai-blog.net. The large majority of the techniques referred to in these questions are new to me, but this seems like a good way to learn. Much of the material I used was from AIGameDev.com, which is an invaluable resource for anyone trying to learn the latest and greatest in game AI.

Behavioral AI

1) What's the difference between a finite state machine (FSM) and a hierarchical finite state machine (HFSM)? Give an example of a hierarchical state machine with functionality that you could not easily replicate in a non-hierarchical FSM.

http://www.eventhelix.com/RealtimeMantra/HierarchicalStateMachine.htm
http://www.gamasutra.com/gdc2005/features/20050311/isla_01.shtml

An FSM must have specific transitions between states for specific events. For every n states added, the increase in complexity is on the order of n².

A HFSM state builds upon higher level states and the even transitions are between the hierarchical levels. So, if the HFSM followed a binary approach, the decision complexity would be below log n. HFSM allow for a modular development of states that is more maintainable and scalable.

Any hierarchical state machine that contains a large number of states (say 50+) would be hard to represent as a non-hierarchical FSM. The number of transitions would be > 2500 and any change to a high level logical representation of the states would be incredibly difficult to reflect.

2) What are some of the limitations of state machines? When is the use of state machines appropriate, and when are they insufficient to generate the kinds of behaviors you need in a game?.

Traditional state machines are not capable of running parallel or asynchronous actions. In order to transition between states, constant polling is required to check for changes in the game state or internal state of the character. Higher level models can uses asynchronous events to trigger and/or alter behaviors

HFSMs are flexible and powerful enough to use on almost any game. With several additions to a traditional HFSM system (event/triggers and parallel actions) there are few constraints remaining. As always, the amount of time available to run behaviors and limitations on memory still poses considerable problems.

3) What is a decision tree? When would you want to use one? What are its performance characteristics? How can you generate a decision tree automatically from a pre-existing data set? Is it feasible to do this at runtime, and has it been done in a commercial game before? When and why would you want to do this, and how would the data need to be organized to make this possible?

A decision tree is a structure used to determine actions based upon a given set of data. The leaf nodes in the tree represent the action to take and all other nodes represent choices (decisions). The decisions made by each of the nodes are based upon a conditional test on arbitrary data. Each time the tree is ran, it starts from the root node and continues until a leaf node is reached.

Decision trees react to dynamically changing environments. By running the whole tree every few frames, an AI character is capable of coping with changes to the environment. The main problem with this approach is that the entire tree has to be run again. If the environment is sufficiently complex (as it is in most 3D games), then the decision tree is likely deep and requires a fair amount of time to run. Also, decision trees have no method of keeping track of previous decisions (no temporal coherence), which in itself causes problems (oscillating behaviors).

Some form of evolutionary decision tree (genetic algorithms + weighted decisions or maybe a neural network...?) would be required to automatically create a decision tree. Without a hard coded tree to start from, the tree would take many generations before it could begin to make correct decisions. If there was a seed tree to use as a starting point, the “evolutionary” process would only be making minor adjustments improve what exists. For most games, starting from scratch is not practical and would result in AI that could not make the simplest of decisions. However, there are games that are tailored specifically to use such systems (Creatures, Façade, Black & White) and did so successfully. The whole point of the game would be to “evolve” a specific feature in some way and the rest of the game play would revolve around that feature. The data (or pointers to the data) would need to be stored in an array that does not require the algorithm to understand contextual information in order to access the data.

Halfway there, take a breather
4) You're developing a boss encounter in a 3D platformer game, and the boss has 15 different attacks. The game designers have asked you to make sure that the player sees as many of those 15 attacks as possible during the encounter, and that he seldom or never sees the same attack twice in a row. What are some ways you can do this? What does the attack selection algorithm look like in this case? Keep in mind that not all attacks are possible all the time -- for example, the boss has a melee attack that he can only do when the player is very close, and a bombardment attack he can only do when the player is far away.

Addressing the last statement first, a simple way to deal with the attack limitations would be to use conditional locks on any behaviors that can not be performed. The other option is if the player is far away and the boss wants to melee, the boss should reduce the distance to the player. The actual selection process could use a probalistic selector and a timer for each attack (after attack X occurs, lock it, put a timer on the lock, and unlock when time 123 is reached). The length of time that an attack is shut off for could be set according to how powerful the attack is or some other design idea.

5) In one room in your game, there's an elevator that AIs will need to use to escape from the player. In order to use the elevator, they have to walk over to a special button on the wall, press it to summon the elevator, then walk into the elevator and press another button to tell it to ascend. How would you design a system to make sure AIs can do all of these things in the proper order? If you have 3 AIs in the room, how would you design the system to make sure they can all escape in the elevator at the same time? What happens if one of them dies while they're trying to do this, and how do you make sure the other AIs don't get stuck waiting for that dead AI?

A behavior using a priority based action selector could be used to order the actions. Each action would also have a check to see if it is valid to consider. The order and checks would look something like:

1) Press button 1....................................... button 1 is not pressed
2) Enter Elevator....................................... not in elevator
3) Wait........................................................ other living AI not in elevator
4) Press button 2....................................... button 2 is not pressed

This order of precedence along with the condition checks would satisfy all of the above requirements. The behavior oriented design methodology would refer to this as a drive collection. Each of these priorities is checked every cycle, so if AI 3 dies while AI 1 & 2 are waiting, during the next check cycle, action 3 will be passed and action 4 will be taken.

6) You're in charge of implementing a stealth game similar to Thief: The Dark Project, and you need guards in your game that have imperfect vision and hearing and inhabit dimly-lit castles, and they can search the area for the player if they think there's an intruder around. How do you model the sensory systems of these guards, and how do you aggregate auditory, visual, and other kinds of stimuli in this system? How do you implement the various alert states for the guards, and why?

http://www.gamasutra.com/gdc2003/features/20030307/leonard_01.htm

Visual awareness can be imitated using a series of cones to represent the range of sight of the guard (or any actor). Separate cones can be used to represent peripheral and primary vision and given appropriate accuracy values. The auditory system would check close objects for sound output (how much noise are you making, 0-1), this would be couple with a scale that would scale the value down with distance (noiseValue * 1 / distance). Each piece of sensory data could be looked at individually, and if any piece exceeds the guards awareness threshold (how loud does a noise have to be before they take notice), then the guard changes from a patrol or guard behavior to a searching behavior. The search behavior would have a higher priority than standing guard or patrolling. So, when the guard notices a disturbance, some bit in the guards head gets flipped from idle to alert state, which allows for the search behavior to activate. They could even have various alert states with levels of awareness (0 = none, 1 = unsure of presence, 2 = sure of presence), with appropriately associated response behaviors.

7) What is planning? How is it used, and what are its advantages? Is it feasible to use planning in real-time games? If so, name any titles where planning has been used for any part of the AI. Describe the architecture of a planning-based AI system for any genre of game.

Planning in its essence is a way to determine how an AI can reach a goal (from a set of goals) using the means that are available. Planners are often designed to work under levels of uncertainty. The overall utility of the decided upon action needs to be maximized, although it may not be an optimal or “correct” decision. Limitations of time prevent searching of the entire problem space in order to find the optimal solution. Bayesian and Markovian planners are often used to deal with factors of uncertainty.

It is feasible and has been done, S.T.A.L.K.E.R. and FEAR both used a “Goal Oriented Action Planner” to plan action selection. Goal Oriented Action Planning does not constantly replan, but instead queries the world for the values it used to form the plan. It then performs replans when any of those values change. A good explanation of GOAP can be found at:
http://www.igda.org/ai/report-2004/goap.html

STRIPS and HTN are both common planning engines used for AI systems. Both planners, at there core, consist of actions, goals, conditional actions. An action may be composed of one or more actions. The network of actions and conditions forms a hierarchy, of which one path from root to goal forms a plan. The primary implementation variations are found in the process of deciding on a plan. Both of these systems are well documented and have existing implementations.
http://en.wikipedia.org/wiki/STRIPS
http://en.wikipedia.org/wiki/Hierarchical_task_network

8) You're working on a game that involves enemy wizards dueling each other. Each wizard has at least a dozen different spells at his disposal -- some of them simply inflict damage, while others will temporarily stun or immobilize an enemy, slow him, prevent him from casting spells for a brief duration, teleport the caster a short distance, or give the caster a temporary shield. A wizard can only cast one spell at a time, but each spell has a fixed cooldown (time before it can be cast again) and an associated mana cost (assume no mana regeneration). Describe some ways you might implement a competent AI system for a wizard.

Let’s summarize some of the wizard’s arsenal first. Each spell has a cooldown time, T, mana cost, M, and effect duration, D. The wizards spell list looks something like:
Stun
Slow
Silence
Teleport
Shield
Fire Attack
Ice Attack
Electric Attack
In addition to spells each wizard has standard movement as an action choice. The environment of the duel was not described; assume it is a 3D environment with not elevation changes or obstacles, basically an empty arena. Also, if both wizards are alive and run out of mana, the round is a draw. Assume that the wizard knows how much mana, MP, health, HP, the other wizard has and the location, (X,Y) of the other wizard.

As far as architecture for the AI goes, a FSM or BT could easily be used to model the wizard’s behavior. The game state is fairly simple, so the AI representation does not need much external information (enemy location, hp, and mp).

The highest level view of the wizard’s behavior should look something like:
1) Evade................................................... out of mana AND opponent hp > 0
2) Defend.................................................. own hp low AND own hp
3) Attack................................................... own hp > opponent hp
4) Idle....................................................... default

Evade would consist of a run away behavior that attempts to keep the wizard from being hit.
Defend would use defense spells (Stun, slow, silence, teleport, shield). A probalistic selector would be used to select which defensive spell to use. If a spell is already in effect, it is not selected. Attack spells will also be considered as part of defense, but only if the wizard has shield on and has stunned, silenced, or slowed the opponent.
Attack will attempt to bring the wizard into an optimum attack location and cast attack spells at the opponent. If all attack spells are in cooldown, then stun, silence, or slow is used.

End of Part 1
That wraps up the first post in this series. Hopefully I didn't butcher all of the concepts and if I did, then please comment on it. There are several more categories of questions to be covered and I am looking forward to covering them all.

Labels: AI, ai-blog.net, Behavioral AI, Decision Tree, FSM, HFSM, Paul Tozour, Planner, Q/A