February 28, 2011

ISSUE 7: Do you read me, HAL?

We’ll be giving the bad guys pursue, attack, flyby and flee behaviours. How do we do this without all of the bad guys behaving identically? If we’re not careful they will flock together and fall into synchronized movements. Worse, they could be predictable (not much fun for a game!). Artificial intelligence (AI) is an interesting subject. Is the solution smoke and mirrors or do we need to program something “intelligent”?

When we’re done there we will add a new ‘picture in picture’ set of cameras and tackle different screen resolutions.

1. Artificial Intelligence

Artificial intelligence (AI) is a term used often yet strangely you’ll struggle to find a good short description. The key word is ‘intelligence’ while ‘artificial’ is a bit misleading. The intention, we assume, is to indicate ‘man made’ (the term does date back to 1956!). Arguably, if a computer program exhibits intelligence there’s nothing artificial about it.

AI, Computer Intelligence, Machine Intelligence, call it what you will. The subject area is basically concerned with the science of exhibiting ‘intelligent’ behaviour computationally.

So what is intelligent behaviour?

It’s a good question and again there’s no silver bullet answer. Terms such as reasoning, planning, learning, comprehension, problem solving, abstract thought and similar are banded about often. Yet the best descriptions are in simpler terms:

making sense of our environment (inputs) and deciding what to do

We’ll take a look now at what challenges AI presents and what solutions are available. As we go through this keep the game in mind. What we are trying to achieve is effectively an autopilot for the bad guys. We want them to exhibit behaviours – pursue, attack, flyby and flee – as plausibly as possible. The first key when it comes to AI in games is simple: make it believable. Believable is a subjective term we should really suffix with “for an arcade shooter”. 🙂

The second key is knowing where to draw the line. There’s a trade off between believable (for an arcade shooter) and engineering a solution too complex. Historically, AI was generally last considered in game development. The reason? Processing power. By the time all the graphics, sound, user interactions and similar were dealt with there was little room in terms of “free CPU cycles” for AI. This has been alleviated somewhat in recent years due to the advent of the GPU and the rapid progression of processor technology (Moore’s law observes that the quantity of transistors that can be placed on a circuit has doubled approximately every two years).

Still, AI in gaming is often quite ‘crafty’. Processing power is still a concern as we continue to push the multimedia boundaries. If you’re looking for pure academic AI games are probably not for you! We will be using some very simple tricks to cause behaviours.

The field of AI is filled with problems:

  • Searching/Path Finding
  • Pattern Recognition
  • Planning
  • Learning
  • Creativity
  • Knowledge Representation
  • …and lots more!

The field of AI is equally filled with potential solutions:

  • State machines
  • Neural networks
  • Genetic algorithms/programs
  • Intelligent Agents
  • Semantic Networks
  • Expert Systems
  • Machine Learning
  • Fuzzy Logic
  • …again, lots more!

For our purposes we have opted for something called a “finite state machine” or “FSM”. We will design our FSM and then code it in Python.

2. The Finite State Machine (FSM)

Describes behaviour through a finite number of states. At any given moment the machine is in one state (it begins in the ‘start state’). The machine is fed input. The input is processed (differently depending on the state), actions performed and optionally output given.

When certain events (inputs) occur (‘transition conditions’) the machine moves from one state to another (a ‘transition’). The machine can only move to certain states depending on the state it is currently in. The states it could move to are called ‘accept states’.

To make things happen a FSM also specifies actions. Actions are specific to a particular state or transition. There are four types of action: entry (to a state), exit (of a state), input (machine stays in the same state but performs some action based on input) and transition.

Well, that’s the theory. It might not be clear at this stage. Thankfully, we can see what a FSM looks like if we represent it as a State Diagram. One is shown below (the one we will be using!) and hopefully clears up any confusion. 🙂

Finite State Machine

3. Making Behaviour Dynamic

If you look back at the state diagram you’ll notice it’s mostly static. In fact, the only ‘dynamic’ behaviour is the coin toss on the fly by (which, when we code it, means we will pick a random number and depending on the answer – fly by to the left or right of the player). Everything else is pretty rigid. So if we created an army of bad guys, they’d all do the same thing for the most part.

Queue the smoke and mirrors. It’s remarkable what a few random numbers can do. Before we go ahead and code our FSM consider the following. Whenever we create a bad guy, what if we jumble up the parameters? Easy to do and could mean:

  • Each bad guy would have a different ‘tolerance’ when height matching the player
  • Each bad guy would have a different maximum speed
  • Each bad guy attacks from a different range
  • Each bad guy flees at a different level of damage
  • Each bad guy begins to bank on a flyby at a different point
  • …etc…