#flipcode

#flipcode

#flipcode - Creating Real Artificial Intelligence

News
Wiki
Forum
Links
#flipcode@home
#flipcode
Articles

Forum

Technical
Gallery
Development
Folding@home
General news
Community

Resources

Physics wiki
Mathematics wiki

My Account

Creating Real Artificial Intelligence

By Richard Garand

Introduction

Welcome to the first article in a new Flipcode exclusive series. These articles are based on my experience making a space combat game for fun (you can see the game here). Since I was working on my own, I had to do everything from modelling to sound editing. I also came up with my own ways of doing basic components such as artificial intelligence, which will be the subject of this article. At first I thought it was something complex that was beyond my resources, but after thinking about it I built my way up from very primitive system to something that could actually fight back.

When you�re learning how to make games, there are many valuable resources on the internet. When it comes to 3D graphics you can find thousands of articles and sites that will explain everything from rasterizing to advanced pixel shader effects. For other subjects like AI, there are less articles and they only focus on limited areas � in this case, anyone can tell you how to do A* pathfinding, but if you go beyond that you�re mostly on your own. In addition, many free tools that you can use to create content for your engine are poorly explained. This series of articles will show you how to do things like creating intelligent opponents and making your own 3D models. For now, let�s talk AI.

The goal of my system is making the AI follow pre-set rules; we add �modes� to the AI so that it can switch between different rules. To make the system more powerful, we then allow the AI to re-use other rules. With these three ideas, the biggest challenge is not making your AI too smart! With a little creativity you can come up with rules for anything from a Quake clone to a strategy game. After introducing the prerequisites I�ll show you how to create the rules and states; explain how you can build rules based on other, more fundamental rules; and give an example of how I turned my ideas into working code.

Since my game is written in C# I�ll use that in my examples, but I�ll keep it simple so you only need basic object-oriented design concepts to understand it. My goal isn�t to give you source files that you can download and compile. Instead I�ll guide you through the conceptual system so you can understand it better and adapt it to your needs. If you aren�t familiar with C#, all objects are passed as references so you can think of every function parameter (except numbers) as a pointer.

The State Machine

There are many tools you can use to give yourself an enemy (or a friend) without needing other players. Advanced systems like neural networks are promising, but they are very complex and can be processor-intensive. A Finite State Machine is a much simpler way to give your characters a few rules to follow. Many people like to explain state machines using transition diagrams annotated with input and output in a strict format. That�s a waste of time though. Just think of the AI operating in different modes and you�ll save yourself a lot of boring abstract theory. We�ll put aside the state machine for a bit though, and start by creating a basic container class for the AI.

The I in AI

When I approached this problem, I knew the best way to start was by creating a class that could be attached to a game object and called periodically to make decisions. It all starts with the AIController class, which has the following two public functions:

public AIController(Ship controlled, Game game)

public virtual void Update(float elapsedTime)

When the class is created, it saves references to the object it�s controlling and the game class (so it can access things outside the object�s properties). I use the Ship class since that�s the base class of everything that can have AI. Now you can give your object class a controller property that�s called to let the AI �think�. Then, you just need to create a few subclasses for different situations and attach them to the right objects, and you have AI. It�s that simple � thanks for coming out, and we�ll see you next week at the same time!

Going Around in Squares

Just kidding, I�ll give you a few more details of how to do this. As I mentioned, the key to making this work is sub-classes. To start with, we�ll bring back my first AI controller that makes something go around in a square pattern (assuming there�s enough open space). First create a class called SquarePatrol that inherits from AIController. Add a private float variable called elapsed to the class, and set it to 0 in the constructor. Now, override the virtual Update function with the following code:

  public override void Update(float elapsedTime)
  {
      elapsed += elapsedTime;
      if (elapsed > 5.0f)
      {
          elapsed -= 5.0f;
          controlled.Turn(90);
      }
  }

As you can see, the code is very simple. It keeps track of how much time has passed, and every 5 seconds turns the controlled ship 90 degrees. I don�t actually use a function called Turn, so you�ll have to fill in your own code suitable for the kind of game you�re making.

Plugging In

Now that you have a basic AI object, you need a way to use it. This involves two steps. First you need to create AI objects and set them as the controller for selected objects when you set up the level. How you choose the objects is completely up to you. Then, as you probably guessed by now, you have to keep calling the Update function.

For now you can do it every frame, but as it grows more complex you might want to call it less often. You can call it anywhere you want, but a good place to do it is right before you move all the objects; that way any changes will take effect immediately. Go through your list of objects, and, if they have a controller, call its Update function with the time since the last frame. Now fire up your game � it lives! Take a few minutes to stare in amazement and congratulate yourself before moving on.

Computing Across State Borders

Let�s turn the class into a state machine now. You already know you can have different classes for different rules, but sometimes creating a new class is overkill. In that case, you can simply add states to an existing class. To demonstrate this I�ll add a new state to the SquarePatrol class. Our goal now is to have the fighter go in a straight line as fast as possible when it�s attacked. This also demonstrates another way to expand your AI system: by adding external events.

To start with, we�ll add a few things to the class:

A virtual void function called OnDamage() (with no parameters) in the AIController class that does nothing
An enumeration in SquarePatrol called Modes with the values Patrol and Evade
A Modes member variable called mode that�s initialized to Modes.Patrol
A float member variable in SquarePatrol called timeSinceAttack
An implementation of OnDamage in SquarePatrol

Now rewrite the update function like this:

  public override void Update(float elapsedTime)
  {
      if (mode == Modes.Patrol)
      {
          elapsed += elapsedTime;
          if (elapsed > 5.0f)
          {
              elapsed -= 5.0f;
              controlled.Turn(90);
          }
      }
      else
      {
          timeSinceAttack += elapsedTime;
          if (timeSinceAttack > 15.0f)
          {
              mode = Modes.Patrol;
              controlled.speed = 50;
          }
      }
  }

And don�t forget the AI�s reaction to an attack (again, this goes in SquarePatrol):


  public override void OnDamage()
  {
      mode = Modes.Evade;
      timeSinceAttack = 0;
      controlled.speed = 100;
  }

The new event requires another call to the AI in addition to the Update function. Every time an object is damaged by a shot, check if it has a controller and call the OnDamage function. Now you have a basic intelligence that can operate in either patrol or evasion mode. By combining several AI classes and several states within each class, you get virtually unlimited options.

Building Blocks

By now you�re probably starting to imagine the possibilities when you replace the Update function with some more complex code. This would be a good time to blow your mind again by introducing a new idea: attaching controllers to other controllers.

If you write out a full description of what you want your AI to do you�ll notice that you repeat yourself a lot. For my game I might want ships to turn to face some other object for various reasons. In an action game, an AI controller might want to just �follow something� without having all the code in that controller. If these were simple one-off actions you could just make a function, but they require continuous changes� in fact, they�re a lot like the AI controllers we already have.

Now you might be thinking that you�d like to attach controllers to the AI in the same way you attach them to objects. In the following paragraphs I�ll tell you how to do just that. First we have to make some additions to the AIController class:

public void AddPrimitive(AIController primitive)

public void RemovePrimitive(AIController primitive)

The implementations are simple; as the names imply, they just maintain a list of primitive controllers in the class. To allow a primitive to remove itself from the parent when it�s finished, you have to create a member variable in AIController called parent and, in AddPrimitive, do primitive.parent = this. Another useful addition you can make is to have functions that store the current list of primitives as an element in a stack, so you can have whole collections of actions that change as you switch states. This lets you temporary use different actions and then go back to the previous mode.

Once you have the management functions implemented, change the AIController�s Update function so that it calls the Update function for all the primitives in the list. Now that you�re doing this, any derived class will have to call the base class Update function to make this happen.

It�s Like The Painting Always Looks At You!

Now let�s try this out to see how it works. The first step is to create a primitive controller to use; the following pseudo-code class will always turn to face a target:

  class FaceTarget : AIController
  {
      public FaceTarget(Ship controlled, Game game, GameObject target)
      {
          // store parameters in member variables of the same name
      }

      public override void Update(float elapsedTime)
      {
          Vector direction = target.Position �  controlled.Position;
          float angle = controlled.ForwardDirection.AngleWith(direction);
          if (angle > controlled.TurnRate * elapsedTime)
              angle = controlled.TurnRate * elapsedTime;
          if (angle < -controlled.TurnRate * elapsedTime)
              angle = -controlled.TurnRate * elapsedTime;
          controlled.Turn(angle);
      }
  }

The actual math for doing this in space is complicated, but you can see that every time the controller is updated it turns towards the target. Now, somewhere in another AI class you can call AddPrimitive(new FaceTarget(controlled, game, target)) to set off an ongoing process that will turn the ship towards its target at the same time as the AI�s other actions.

Call On Me

There�s two ways you might want to use one of these primitive controllers: a single shot controller that knows when it�s done, or an ongoing process that you terminate at the time of your choice. In the first case, the controller can simply do its thing and then call parent.RemovePrimitive(this). And example of this is a controller that smoothly turns to another direction. For the second kind, the parent controller should keep a reference to it and remove it when it�s no longer needed. Don�t forget to delete objects when you�re done with them in C++.

I Need Guns� Lots of Guns

Now you have a few ideas about creating AI classes with rules, using states to make the rules more complex, and using primitive classes to make rules based on other rules. It�s time for something more fun: an example! Chances are you won�t be able to use this directly in your game but I�ll explain how I used the concepts above to add space combat to my space combat game.

For this example I�ll focus on the fighters. For the first mission I came up with, they had to play two roles: attacking a larger ship and fighting amongst each other. Since you�ve already seen enough code I�ll just explain the ideas. Hopefully this will show you how to come up with your own rules. Keep in mind that getting the AI can take a few tries. As you test your code you�ll have to come up with new rules to stop it from doing the wrong things.

That�s No Moon!

I started by having the fighters attack a large ship with a BombingRun controller. The plan is for a fighter to turn in towards the target target, fly towards it while firing, and put in some distance when it gets too close; once it gets far enough it starts over. This means the controller needs two modes: Attack and Distance.

In this case the code to face the target is in the main controller. Every time it�s updated in Attack mode it check if it�s facing the place it wants to aim at and turns towards it, limiting the turn to the fighter�s turn rate. The angle between the new direction and the direction it wants to shoot is still saved in a variable, and if it�s less than 5 degrees the controller tries to fire the fighter�s weapons. This uses another function that checks if the weapons are ready before firing. Note that if you want to implement a similar function you might need to lead the target by shooting at a point ahead of it instead of the target itself; the math is beyond this article but you can get help with it in the forums.

For the next step we introduce a primitive controller. When the fighter is 5 seconds from hitting the target, a new controller is added that makes it do a 180 degree turn over a few seconds. After adding the controller the fighter changes to Distance mode so it won�t try to turn back and attack. When the turn controller is done its job it deletes itself and the fighter simply flies away from the target. The Distance mode is much simpler. It just checks if the fighter is outside the weapons range, and when it is switches back to Attack mode; this gives it a little room to turn around and get the maximum time to attack as it flies back.

Dogfights

The other main controller is the Dogfight controller. The fighter selects a target, chases it while firing, and repeats once the target blows up. The first part is simple; if the controller doesn�t have a target it scans through the game�s list of ships for enemy fighters. Each one has a member variable that says how many ships are targeting it, so the fighter can choose one that no one else is going after and set it as the target.

After a target is located, it follows the familiar routine of turning towards it and firing if the angle and range are within the limits. This is one place where you can reduce the intelligence if it�s too smart: introduce some random variations in the turn and the top gun becomes a training target. Once again a leading point is calculated to give the shots a better chance of being at the right place when they get there.

The fighter also has some rules for speed. If it�s more or less behind the target it sets the speed to stay within a certain range but not get too close. If it�s not behind the target it goes a bit slower than the target to minimize the turn radius. These rules have to be tuned very carefully; if two fighters are targeting each other making them go slower than the other one will just stop them both. Getting all these little details right is one of the harder parts of using this AI system, and my speed rules still aren�t perfect.

The Decider

There�s one more controller that ties everything together: the Fighter controller. After all, what better place to decide which AI to use than in the AI code? This controller simply creates one of the two other controllers as a primitive and keeps it until the fighter�s goals change (the game notifies it with an event function). It then removes the current controller and creates a new one. When I load up a fighter, I simply attach a new Fighter controller and let it go do its thing.

This is only a simple system and my game already has much more advanced rules. However, it shows you how I went from a general idea to specific rules and an implementation using all the features of the system. Since I didn�t plan this all out before writing the code it could be simplified by creating some new primitives; see if you can figure out the best way to code these rules.

Conclusion

This should give you some ideas about how to create AI for your game. All you have to do now is come up with rules and create the appropriate classes. With the features I describe there may be several ways to make a change; you�ll have to decide which one is easiest. If you have any questions or can�t figure out how to do your AI check out the forums on this site, or drop in to #flipcode on irc.enterthegame.com. If there are enough questions about how to apply this system I�ll write another article explaining some of the more advanced uses. Future articles in this series will focus on 3D modelling with Blender.

Richard Garand is a freelance programmer currently specializing in web applications. His website is at http://www.richard-garand.com/.