Game AI Patterns

How do you go about making your enemies and NPCs act intelligently? It’s a tough question, and you can go about as deep as you like. Personally, though, I think there a few simpler options which will serve most cases. Let’s take a look!

Finite State Machines

It’s difficult to imagine a more intuitive way to approach game AI than with a finite state machine. At it’s simplest a FSM is a collection of cases, e.g.

if (alive) hunt player
else give up the ghost

In the past I’ve written about patterns for decomposing finite state machines, which is useful to avoid coding a huge number of if/else statements. If you’re writing your game’s AI then the best way to start is to write down the different conceptual states the object will have. For instance, a tank warfare game might have the following states:

1. Seeking enemy
2. Attacking enemy

The next step is to write down the conditions which connect the different states. Continuing with the tank example it might be as follows:

1. seeking => attacking when you can see the target
2. attacking => seeking when you cannot see the target

Easy, right? Naturally, you can get pretty complex behavior by creating more states and transitions. Try it out!

A* Intelligently

Many AI problems are actually pathfinding problems. Sometimes the paths are literal paths from point A on the map to point B, other times they are paths through a network of possible choices. In all cases the A* pathfinding algorithm can help. A* describes a way to find the shortest path from your current position in the graph to the target, but it’s especially useful for AI when you start to get creative with it.

At the heart of the A* algorithm is the notion of “weight”. Each possible move is weighed against the others and then the best is picked. In the context of game AI you can influence how A* plots its path by tweaking the weighted values along the graph. Want your enemies to avoid running into minefields? No problem, tweak A* to favor moving through “safe” nodes. You can read more about this in my presentation on the grid data structure.

Raycasting Your Way

Sometimes you don’t have a graph to traverse. (Though I strongly encourage you to re-think whether that’s actually the case — why can’t you use the grid data structure to create a graph?) In those cases you can turn to ray casting to answer the different physical queries for your AI.

One approach, which I used in Forte, is to cast three rays from your object — left, right, forwards — and then determine which way to move based on the results. Ray casting is also a natural way to determine whether an object can “see” a second object. This means you can use ray casting to create AI driven entities which respond to changes in their line of sight.

Conclusion

So there you have several tools for developing AI, which one should you use? Most likely the answer is all three. In my experience, finite state machines generally act as the foundation for the AI and different states will employ ray casting and A* in different ways to accomplish the desired behavior. I hope this was useful and look forward to seeing what smart things your game entities do in the future!

Related posts:

1. Game Design: Decoding State Machines
2. Physical Queries for the Math Challenged: Ray Casting
3. Game Design Patterns