XNA & Game A.I – Where to begin

July 8, 2009 at 8:40 pm (A.I, XNA) (, , , , )

I’ve been thinking a lot about writing some articles on using A.I in games with XNA but I just don’t know where to begin. I have to start somewhere so let’s get to it.

As previously mentioned I’ve been writing an A.I library for use with XNA games. It’s called Brains and it consists of a few building blocks to get you quickly up and running with an A.I prototype and just as simple to implement right into your game. It’s currently only in 2D but would not require too much modification to support 3D.

The Brains library is built up of a world map, an A.I agent and a behavior tree implementation.

The Map

A world map is made up of a grid. In it’s simplest form a world map could look like this

image

It would be made up of 1 grid which is 16 GridCells and have 4 columns and 4 rows of GridCells.

A more complex world might have over 100×100 GridCells in it’s map. Brains can split this into a cluster for you which will greatly increase the speed of path finding and other A.I techniques. As a simple sample we could have a map made up of 8×8 cells and have a cluster of 4 grids.

image image

image image

In the real world they wouldn’t have a gap in between, this is just to represent that they are separate grids in a map cluster.

When loading a world map you simply specify the width and height of the map in world coordinates, pixels for example, the cell size to split the world into again in world coordinates and if you have a large world you can decide to create a cluster by specifying the rows and columns to split the bigger world into. In this example that would look something like this.

World.SetupMap(1280,1280,160,2,2);

You can also load a world map by loading from a texture. In the current implementation it will assume 1 pixel of the image to be 1 GridCell. Here is a blown up example of one of the demos in the source code.

image

Brains will set any pixel that is black, to be a blocked type of GridCell, and any other colour to be an empty GridCell. The red and green pixels are loaded and annotated on the grid for your use but are not used internally in the engine. This makes it super easy to knock up a quick map to test out.

The Agent

A Brains A.I world also contains a list of Agent types. This type is used to provide autonomous behaviors to your game. An Agent stores some simple positioning properties such as Position, Radius and the Cells the Agent is currently in. It also stores the desired orientation and the desired position of an Agent for use with a Locomotion controller.

An Agent can store a set of feelers which can be used by your behaviors to poke data around the world.

The last defining feature of an Agent is it’s RootBehavior property. This is an IBehavior type which can be any type of behavior built into Brains, or your own custom implementation.

You can inherit from the Agent type to give you that extra flexibility when creating your autonomous characters.

Locomotion Controller

The Locomotion Controller is what controls the movement of an Agent. This is isolated from the Agent so that you can extend and implement the default implementation to get your characters moving how you want them to. There are 2 types of LocomotionController implemented in Brains. The basic movement controller which moves the agent from its current position to its desired position, and rotates it to face the desired rotation. The other Locomotion Controller is the LocomotionSteering which will allow you to make use of the famous Steering Behaviors For Autonomous Characters by Craig Reynolds. My version isn’t quite finished yet as I’m working on a better group design but the basic steering behaviors are working at the moment.

Behaviors

Brains contains some built in behaviors to form the basis of any combination of behaviors you may ever need to build. You can of course ignore these and implement your own.

With the Brains building blocks you can quickly build very complex behaviour trees without writing a ton of spaghetti code.

A Behavior Tree is made up of smaller blocks of hierarchical logic and built to recursively go down the tree until it finds a behavior to run. A simple representation of a Behavior Tree can be shown like this.

image

The circles represent a behavior and the lines show how the behavior breaks down into active actions an Agent may take based on decisions further up the tree. The Behavior tree is a much larger the subject than the scope of this post though so I will brush over the behavior building blocks built right into Brains.

Sequence Behavior

The Sequence Behavior has a set of sub behaviors which will run the first item in the list until it is successful, it will then move onto the next behavior in it’s sub behaviours in sequence. If a behavior fails it will fail the whole sequence.

Selector Behavior

The Selector Behavior also has a set of sub behaviors which it will run in sequence until it finds a success and then complete as a success itself.

Random Behavior

This Behavior randomly selects one of its child behaviors to run.

ParallelBehavior

This is a very primitive implementation of a Behavior which will run multiple behaviors at the same time. This raises a lot of complications with access to current data so will currently prove troublesome if the parallel is not a simple one.

Condition Behavior

Used to provide conditions before running other sub behaviors

Task Behavior

This is the behavior which would contain your A.I logic code. You would generally inherit from this to provide the specific game A.I logic.

Combining these set of components with your own and your imagination you can create extremely complex A.I decision making agents with great ease. With the added bonus of a Behavior Tree designer provided with the source code it’s even easier to let you just put on your game designer hat or give the ability to a game designer to create a better game A.I

Brains also contains a few Task Behaviors for pathfinding around the world. You can also extend upon these to provide more flexible pathfinding.

They are:

Find Path Behavior

Finds a path from 1 GridCell to another.

Follow Path Behavior

Follows a provided path.

GoTo Behavior

This behavior combines the FindPath and FollowPath behaviors.

FollowRouteBehavior

This Behavior takes a series of GridCells. It will pathfind from one GridCell to the next and cycle once it’s complete. This makes use of the GoTo Behavior.

 

That’s a brief roundup of what Brains has to offer. It’s still unfinished and will continue to get development done to it. I want to tidy up some of the API exposure I’m not happy about yet (a few dirty hacks) and then I’ll post the source code for you to have a play with and give me some feedback.

Credits

The majority of my A.I reading has been from the AIGameDev web site. I’ve learned so much from there, I highly recommend it.

Some other helpful sites are of course the XNA Creators Club Online

A few other XNA A.I related projects have also been a great source of inspiration. Most notably Simple AI Engine for XNA and SharpSteer

About these ads

3 Comments

  1. CatalinZima said,

    Nice post. I was familiar with the concepts, but it will be nice to use a library instead of rolling my own.
    It will be interesting to see how it behaves in action :)

  2. Petr said,

    This year I had on college subject about A.I. , but this article is much more interesting and learn me much more than our professor. A waste a lot of time listening his classes :(
    Great work, very nice article

  3. Asa said,

    I saw the graphic on Ziggyware and got excited someone was going the Champandard route. I can’t wait to see your Brains!

    Are you planning on using Decorators (timer, lookup, etc)?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: