I’ve moved
It’s about time I got a real domain name for this thing. Please update your book marks to the new blog at http://www.conkerjo.com/
Please Mind the dust while I work with the new theme š
The Week in Code by Björn
Bjƶrn (or boki) has written his 7th instalment of The Week in Code. Hit the RSS button and maybe heāll feel obliged to keep it up and add some more. Iām in there 2 weeks on the trot by the way š
BRAINS – XNA A.I Library – Source Code
As mentioned in a previous post I have been working on an A.I library for use with XNA games. I have attached the latest source code to this post as well as the location to the SVN which I will be continuing to update.
If you do try it out and find any issues you would like to have fixed, please let me know and Iāll happily respond to requests. If anyone would like to contribute in the form of a patch or just contribute in the form of ideas and feedback, Itās all welcome.
Brains is only about 2 weeks old since I started the clean new project and itās still very much a work in progress so there are still lots of features I could add to this middleware component to make it more useful.
In the project is the main BRAINSFramework along with the debug AIRendering project. A Gamestatemanagement library for setting up a new game quickly and the AIDemos. There is also a very primitive Behavior tree designer which Iām currently working on making more friendly and feature rich.
I will be writing more comprehensive documentation in due course along with some articles to accompany the BRAINS library.
XNA & Game A.I – Where to begin
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
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.
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.
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.
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
XNA & Game A.I
Over the past few weeks I have been developing an A.I middleware library for use with XNA games. Iāve spent a lot of this time in google searching for A.I articles and samples. Itās a force of habit to append XNA to the end of my code related searches and I wasnāt finding the information I needed to get the inspiration for my A.I library. I did figure out how to use google eventually and found lots of good, general A.I articles and samples. Most samples are c++ but itās more about the concepts of A.I I was looking for than the samples.
At some point in the very near future I will be releasing the source code to this library along with a sandbox for you to see how to use it and to play around with it. One thing Iām struggling with is deciding what small chunks of A.I I should demonstrate. If you have some ideas of what you would like from an A.I sandbox please comment on this post and we can discuss.
In the meantime, here is a bunch of links Iāve been reading over the past few weeks relating A.I and some XNA specific ones I did find.
Other
- A.I Game Dev (Lots of amazing stuff here, too much to list)
- Ziggyware A.I Articles
- Gamedev.net A.I
Its not swine flu & WordPress
Despite the rumor of swine flu, I actually just have a fairly nasty bout of regular flu. Im doing ok now and am on the mend. So that’s the health sorted, but I wanted to test out this fairly useless looking word press application for the iPhone out. Sure enough, it’s fairly useless except for the short message and we have twitter for that.
I’m working on some A.I and hope to write some posts or/and articles on the subject soon. Stay tuned.
Spatial Hashing For Teh Win!!!
It totally worked. Sometimes when theory is followed by practice, things go wrong. But my previous blog post experiment has worked an absolute treat. I spent the afternoon implementing it into SBARG. Hereās a screenshot of the result.
WIN!!!!!
Spatial hashing implementation for fast 2D collisions
This is a sample prototype I wrote to fix a performance limitation with collision checking in SBARG. So what is spatial hashing? Here is a good 1 liner I will borrow from the source material i used.
āSpatial hashing is a process by which a 3D or 2D domain space is projected into a 1D hash table.ā Optimization of Large-Scale, Real-Time Simulations by Spatial Hashing
So why do we need it?
Well, for me it was a problem in my collision code and my A.I code which was trying to find nearby objects to check collisions for. Due to my brute force nature if I had 10 monsters in the world there would be 10*10 = 100 collision checks in every update. Now ramp the number up to 100 to be a bit excessive and we end up with 100*100=10,000 collision checks. This makes the cpu cry like a little baby as Iām sure you can imagine. To rectify this we need to reduce the amount of collision checks we need to do in the first place. This is where spatial hashing comes in handy.
Imagine the game world in a flat 2d grid. 100 by 100 pixels and each cell was 25 by 25 pixels. Now number the cells from left to right, top to bottom 0 onwards. You will end up with something like this. The orange circles are the game objects, in my case, monsters.
Each cell is a bucket of game objects and a unique hash id. If we imagine the bucket as a list of 16 buckets, 0-15 cells and placed the game objects in that bucket. It might look something like this.
This is our 1D grid mentioned in the introduction.
Itās a simple premise really, any item in bucket 3 for example, cannot possibly collide with something in bucket 9. This reduces the amount of times we need to cycle the nearby objects but also dramatically reduce the amount of times we need to check if a collision is happening.
Ok, so the above implementation is fine as long as a game object only ever exists in 1 bucket. But what if it crosses a line and exists in more than 1 bucket. To resolve this I imagined a box around each game object, and I calculated the hash id for each corner of the box. I then populate a List<GameObject> going through each bucket the game object is in. Sounds simple ?
Let me show you some of this theory in code.
First we need a game object. For this sample all we need is a position and a radius.
public class GameObject
{
public Vector2 Position { get; set; }
public float Radius { get; set; }
}We create a new class to store the grid data in including the buckets. Iām terrible at naming classes so I called it SpatialManager. I gave this class a Setup method which takes a full scenewidth, height and a cellsize. In our example this would be 100,100,25
public void Setup(int scenewidth, int sceneheight, int cellsize)
{
We can work out how many buckets we need by first calculating the rows and cols then simply create a new Dictionary of buckets to the tune of Rows*Cols. I also store these variables passed in for future use.
Cols= scenewidth / cellsize;
Rows= sceneheight / cellsize;
Buckets = new Dictionary<int , list><gameobject>(Cols * Rows);
for (int i = 0; i < Cols*Rows; i++)
{
Buckets.Add(i, new List());
}
SceneWidth = scenewidth;
SceneHeight = sceneheight;
CellSize = cellsize;
}
Each update, we need to clear out the buckets and re calculate the buckets each game object are in. I created a method called ClearBuckets to start fresh.
internal void ClearBuckets()
{
Buckets.Clear();
for (int i = 0; i < Cols * Rows; i++)
{
Buckets.Add(i, new List());
}
}We now need a method to register a game object into the buckets it sits in.
internal void RegisterObject(GameObject obj)
{
List cellIds= GetIdForObj(obj);
foreach (var item in cellIds)
{
Buckets[item].Add(obj);
}
}
As you can see, the code retrieves a list of cellids to add the game object to.
In the GetIdForObj method it calculates the cell id for each corner of the game object.
If we were just checking the position of the game object the calculation would be.
float width = SceneWidth / CellSize; // 100 / 25
int hashid=(int)(
(Math.Floor(position.X / CellSize)) +
(Math.Floor(position.Y / CellSize)) * width);
We need to do this for each corner and add our game to each bucket.
The GetIdForObj method looks like this.
private List GetIdForObj(GameObject obj)
{
List bucketsObjIsIn = new List();
Vector2 min = new Vector2(
obj.Position.X - (obj.Radius),
obj.Position.Y - (obj.Radius));
Vector2 max = new Vector2(
obj.Position.X + (obj.Radius),
obj.Position.Y + (obj.Radius));
float width = SceneWidth / CellSize;
//TopLeft
AddBucket(min,width,bucketsObjIsIn);
//TopRight
AddBucket(new Vector2(max.X, min.Y), width, bucketsObjIsIn);
//BottomRight
AddBucket(new Vector2(max.X, max.Y), width, bucketsObjIsIn);
//BottomLeft
AddBucket(new Vector2(min.X, max.Y), width, bucketsObjIsIn);
return bucketsObjIsIn;
}
And here is the AddBucket method which uses the calculation described above and adds it to the list of bucket id’s to add to.
private void AddBucket(Vector2 vector,float width,List buckettoaddto)
{
int cellPosition = (int)(
(Math.Floor(vector.X / CellSize)) +
(Math.Floor(vector.Y / CellSize)) *
width
);
if(!buckettoaddto.Contains(cellPosition))
buckettoaddto.Add(cellPosition);
}
Now that we have our grid of buckets. It’s a very simple retrieval process. I added a method to get the nearby objects of a given object. This uses the GetIdForObj method and populates a list of GameObject’s and returns once complete. This is the key part to this solution, you only now need to check items which are actually nearby and not items the other side of the theoretical world.
internal List GetNearby(GameObject obj)
{
List objects = new List();
List bucketIds = GetIdForObj(obj);
foreach (var item in bucketIds)
{
objects.AddRange(Buckets[item]);
}
return objects;
}
So thatās it. Now you can do your normal collision checking by retrieving nearby GameObjects. And hereās a screenshot to prove it.
Iāve placed my mouse over one of the GameObjects and itās highlighted all nearby items. Notice how they cross over cells. This is because the item i hover over is on the line and exists in multiple cells. Also notice the amount of checks it has to do. For brute force it has to do 250,000 bounding box collision checks. For spatial hashing, it checks only 4840 times. Wicked.
And what would a sample be without source code?
Enjoy
Simply RenderTargets
Somebody in the #xna IRC channel just asked how to use RenderTargets to only draw a portion of the screen. Hereās my answer.
I guessed from his brief description he might have a game scene which didn’t look like this
And the result he wanted, was something almost like ā¦ this ?
What you see here is the game scene drawn, with a triangle portion visible and the rest not so much. My favourite way to achieve this is to use 2 RenderTargets, A VERY simple Effect(shader) and good old SpriteBatch. So what do we use all this for?
First we need to draw the game scene. There is a way around this but to make things easier to understand we will draw this to a RenderTarget. Simply put, a RenderTarget is an imaginary āscreenā to draw to which you can specify the size of. Then once done, you can use the texture like any normal Texture2D you might load from the Content Pipeline.
To draw the scene we first want to set the correct RenderTarget, then use spritebatch just like you would to draw any other sprite. Like this.
GraphicsDevice.SetRenderTarget(0, _gameRT);
//Clear the RT screen
GraphicsDevice.Clear(Color.Black);
spriteBatch.Begin();
//Draw the game
spriteBatch.Draw(
_gameBackground,
Vector2.Zero,
Color.White);
spriteBatch.End();
Simple uh?
Now we need to create another RenderTarget, and Draw a triangle to it. This will never be displayed in the final scene. Although with the RenderTarget it allows you to if you so desire, maybe for debugging purposes?
GraphicsDevice.SetRenderTarget(0, _lightRT);
//Clears the screen transparent.
GraphicsDevice.Clear(Color.TransparentBlack);
spriteBatch.Begin();
spriteBatch.Draw(
_triangle,
Vector2.Zero,
Color.White);
spriteBatch.End();
This code is almost identical to the last except we draw the _triangle Texture which looks like this.
And we use the color transparent black.
The final thing we need to do now is draw it to the scene.
If we just draw the triangle on top of the game scene you will see the game scene with a white triangle on top. This isnt what we want. So we use a shader to take the game scene, and change the alpha channel corresponding to the white triangle. Wherever there is a solid non transparent color pixel, this will be set to a fully non transparent pixel in the game result, however, a transparent pixel in the triangle image will result in a completely transparent pixel in the final result. Resulting in you not being able to see that pixel. The final result is like this.
The shader code is very simple. It is a pixel shader which takes a AlphaTexture parameter which is the texture taken from the triangle RT. It takes the alpha from that texture, and sets the coresponding pixel on the final image to be the same.
float4 PixelShader(float2 texCoord: TEXCOORD0) : COLOR
{
float4 Color = tex2D(ScreenS, texCoord);
float alphaLayerAlpha = tex2D(AlphaSampler, texCoord).a;
Color.a=alphaLayerAlpha;
return Color;
}
Cool?
To use this we just create a new Effect variable and load it in LoadContent. Call Begin/End in the appropriate places, set the parametar and hey presto. A RESULT!!!
_myEffect.Parameters["AlphaTexture"].SetValue(_lightRT.GetTexture());
spriteBatch.Begin(SpriteBlendMode.AlphaBlend, SpriteSortMode.Immediate, SaveStateMode.None);
_myEffect.Begin();
_myEffect.CurrentTechnique.Passes[0].Begin();
spriteBatch.Draw(_gameRT.GetTexture(),
Vector2.Zero,
Color.White);
_myEffect.CurrentTechnique.Passes[0].End();
_myEffect.End();
spriteBatch.End();
To get a better grasp of the code you can download the sample project here.
As I said, Someone in IRC literally just asked. So I knocked this up. Apologies for the rushed post š BACK TO SBARG!!!
XBox Live Community Games Listings
A community created (Nick Gravelyn) website has existed for some time which set out to emulate the functionality of the Xbox Marketplace but until very recently, it kind of sucked to look at. The information was there, but it was a fairly dull and average affair. But now, wow. Take a look for yourself. Itās almost like a direct copy of the Xbox Marketplace but it has 2 major benefits. Itās not slow, so you can go to it today, and read it today, and the other is user ratings. Go check it out for yourself, oh a third thing, the Box Art Collage is pretty sweet too, oh, and Random Game, i could go on but hereās the link. Iām going to find some new games to play š
Congratulations to Nick Gravelyn & Scott Wendt & Bjƶrn Graf for getting this out without too much of a hiccup, I can see why Nick was so excited to get it out now. Great work with the new site.
The mind of Conkerjo 