Boundary Collision Detection
The first type of collision test we’ll examine uses the boundaries of two rectangles for the test condition. Also called “bounding box” collision detection, this technique is simple and fast, which makes it ideal in situations in which a lot of objects are interacting on the screen at once. Not as precise as the radial technique (coming up next), boundary collision detection does return adequate results for a high-speed arcade game. Interestingly, this is also useful in a graphical user interface (GUI), comparing the boundary of the mouse cursor with GUI objects for highlighting and selection purposes. On the WP7, however, we can’t actually track mouse movement because a “mouse” does not even exist on Windows Phone, only touch points.
XNA provides a useful struct called Rectangle. Among the many methods in this struct is Intersects(), which accepts a single parameter—another Rectangle. The return value of Intersects() is just a bool (true/false). The trick to using Rectangle.Intersects() effectively is creating a bounding rectangle around a sprite at its current location on the screen, taking into account the sprite’s width and height. When we get into animation a couple of hours from now, we’ll have to adapt this code to take into account the width and height of individual frames. In the meantime, we can use the width and height of the whole texture since we’re just working with simple static sprite images at this point. Figure 10.1 illustrates the boundary around a sprite image.
As you can see in this illustration, boundary collision does not require that the image have an equal width and height, since the bounding rectangle can handle a nonuniform aspect ratio. However, it is usually better to store game artwork in square images for best results.
Accounting for Pivot
Remember that Sprite.position references the pivot point of the object, also known as the origin. Normally, the origin is at the center of the sprite. If the origin is changed from the center of the sprite, the boundary will return an incorrect result! Therefore, if you change the origin, it’s up to you to take that into account when calculating boundaries. The Sprite class does not account for such changes. The calculation for the boundary might be done like so at this point:
[code]
int halfw = image.Width / 2;
int halfh = image.Height / 2;
return new Rectangle(
(int)position.X – halfw,
(int)position.Y – halfh,
image.Width,
image.Height);
[/code]
Accounting for Scaling
That should work nicely, all things being equal. But another important factor that must be considered is scaling. Has the scale been changed from 1.0, or full image size? If so, that will affect the boundary of the sprite, and we have to account for that or else false results will come back while the game is running, causing a sprite to collide when it clearly did not touch another sprite (due to scaling errors). When the boundary is calculated, not only the origin must be accounted for, but the scaling as well, which adds a bit of complexity to the Boundary() method. Not to worry, though—it’s calculated by the method for us. Here is a new version that takes into account the scaling factor:
[code]
int halfw = (int)( (float)(image.Width / 2) * scaleV.X );
int halfh = (int)( (float)(image.Height / 2) * scaleV.Y );
return new Rectangle(
(int)position.X – halfw,
(int)position.Y – halfh,
halfw * 2,
halfh * 2);
[/code]
What is happening in this code is that the width and height are each divided by two, and the scaling is multiplied by these halfw and halfh values to arrive at scaled dimensions, which are then multiplied by two to get the full width and height when returning the Rectangle.
Sprite Class Changes
To simplify the code, we can add a new method to the Sprite class that will return the boundary of a sprite at its current location on the screen. While we’re at it, it’s time to give Sprite a new home in its own source code file. The new file will be called Sprite.cs. The namespace is a consideration, because the class needs a home. I propose just calling it GameLibrary, and in any program that uses Sprite, a simple using statement will import it.
The new version of this class includes the Boundary() method discussed earlier. An additional new method is also needed for debugging purposes. Every class has the capability to override the ToString() method and return any string value. We can override ToString() and have it return information about the sprite. This string can be logged to a text file if desired, but it is easier to just print it on the screen. The code in ToString() is quite messy due to all the formatting codes used, but the result looks nice when printed. It can be very helpful to add a ToString() to a custom class for this purpose, for quick debugging. For example, it is helpful to see the position and boundary of a sprite to verify whether collision is working correctly. See the demo coming up shortly to see an example of this in action. Our Sprite class, the source code for which is shown in Listing 10.1, sure has grown since its humble beginning!
LISTING 10.1 Revised source code for the Sprite class.
[code]
public class Sprite
{
private ContentManager p_content;
private SpriteBatch p_spriteBatch;
public Texture2D image;
public Vector2 position;
public Vector2 velocityLinear;
public Color color;
public float rotation;
public float velocityAngular;
public Vector2 scaleV;
public Vector2 origin;
public bool alive;
public bool visible;
public Sprite(ContentManager content, SpriteBatch spriteBatch)
{
p_content = content;
p_spriteBatch = spriteBatch;
image = null;
position = Vector2.Zero;
velocityLinear = Vector2.Zero;
color = Color.White;
rotation = 0.0f;
velocityAngular = 0.0f;
scaleV = new Vector2(1.0f);
origin = Vector2.Zero;
alive = true;
visible = true;
}
public float scale
{
get { return scaleV.X; }
set
{
scaleV.X = value;
scaleV.Y = value;
}
}
public bool Load(string assetName)
{
try
{
image = p_content.Load<Texture2D>(assetName);
origin = new Vector2(image.Width / 2, image.Height / 2);
}
catch (Exception) { return false; }
return true;
}
public void Draw()
{
p_spriteBatch.Draw(image, position, null, color, rotation,
origin, scaleV, SpriteEffects.None, 0.0f);
}
public void Move()
{
position += velocityLinear;
}
public void Rotate()
{
rotation += velocityAngular;
if (rotation > Math.PI * 2)
rotation -= (float)Math.PI * 2;
else if (rotation < 0.0f)
rotation = (float)Math.PI * 2 – rotation;
}
public Rectangle Boundary()
{
int halfw = (int)( (float)(image.Width / 2) * scaleV.X );
int halfh = (int)( (float)(image.Height / 2) * scaleV.Y );
return new Rectangle(
(int)position.X – halfw,
(int)position.Y – halfh,
halfw * 2,
halfh * 2);
}
public override string ToString()
{
string s = “Texture {W:” + image.Width.ToString() +
“ H:” + image.Height.ToString() + “}n” +
“Position {X:” + position.X.ToString(“N2”) + “ Y:” +
position.Y.ToString(“N2”) + “}n” +
“Lin Vel “ + velocityLinear.ToString() + “n” +
“Ang Vel {“ + velocityAngular.ToString(“N2”) + “}n” +
“Scaling “ + scaleV.ToString() + “n” +
“Rotation “ + rotation.ToString() + “n” +
“Pivot “ + origin.ToString() + “n”;
Rectangle B = Boundary();
s += “Boundary {X:” + B.X.ToString() + “ Y:” +
B.Y.ToString() + “ W:” + B.Width.ToString() +
“ H:” + B.Height.ToString() + “}n”;
return s;
}
}
[/code]
Boundary Collision Demo
Let’s put the new Sprite method to use in an example. This example has four asteroids moving across the screen, and our spaceship pilot must cross the asteroid belt without getting hit by an asteroid. This example is automated—there’s no user input. So just watch it run this time. The source code is found within Listing 10.2, while Figure 10.2 shows a screenshot of the program running. When the ship collides with an asteroid, it simply stops until the asteroid goes on by. But to give the ship more survivability, additional intelligence code has to be added.
When the demo is completed later in the hour, it will also have dodging capability. If an asteroid is directly above or below the ship when a “grazing” collision occurs, the ship can simply stop to avoid being destroyed. But if an asteroid is coming from the left or right, destruction is imminent! When this happens, the pilot has to use emergency thrusters to quickly move forward to get out of the way of the asteroid. This is also automated, so again, just watch it run, as input is ignored. We’ll start by just having the ship stop when a collision occurs, and add the capability to speed up in the section coming up on collision response.
Note that the using statements are included here just to show that GameLibrary must be included (the namespace containing the Sprite class), but they will again be omitted in future listings.
LISTING 10.2 Source code for the boundary collision demo program.
[code]
using System;
using System.Collections.Generic;
using System.Linq;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Audio;
using Microsoft.Xna.Framework.Content;
using Microsoft.Xna.Framework.GamerServices;
using Microsoft.Xna.Framework.Graphics;
using Microsoft.Xna.Framework.Input;
using Microsoft.Xna.Framework.Input.Touch;
using Microsoft.Xna.Framework.Media;
using GameLibrary;
namespace Bounding_Box_Collision
{
public class Game1 : Microsoft.Xna.Framework.Game
{
GraphicsDeviceManager graphics;
SpriteBatch spriteBatch;
Random rand;
Viewport screen;
SpriteFont font;
Sprite[] asteroids;
Sprite ship;
const float SHIP_VEL = -1.5f;
int collisions = 0;
int escapes = 0;
public Game1()
{
graphics = new GraphicsDeviceManager(this);
Content.RootDirectory = “Content”;
TargetElapsedTime = TimeSpan.FromTicks(333333);
}
protected override void Initialize()
{
base.Initialize();
}
protected override void LoadContent()
{
spriteBatch = new SpriteBatch(GraphicsDevice);
screen = GraphicsDevice.Viewport;
rand = new Random();
font = Content.Load<SpriteFont>(“WascoSans”);
//create asteroids
asteroids = new Sprite[4];
for (int n=0; n<4; n++)
{
asteroids[n] = new Sprite(Content, spriteBatch);
asteroids[n].Load(“asteroid”);
asteroids[n].position.Y = (n+1) * 90;
asteroids[n].position.X = (float)rand.Next(0, 760);
int factor = rand.Next(2, 12);
asteroids[n].velocityLinear.X = (float)
((double)factor * rand.NextDouble());
}
//create ship
ship = new Sprite(Content, spriteBatch);
ship.Load(“ship”);
ship.position = new Vector2(390, screen.Height);
ship.scale = 0.2f;
ship.velocityLinear.Y = SHIP_VEL;
}
protected override void Update(GameTime gameTime)
{
if (GamePad.GetState(PlayerIndex.One).Buttons.Back ==
ButtonState.Pressed)
this.Exit();
//move asteroids
foreach (Sprite ast in asteroids)
{
ast.Move();
if (ast.position.X < 0 – ast.image.Width)
ast.position.X = screen.Width;
else if (ast.position.X > screen.Width)
ast.position.X = 0 – ast.image.Width;
}
//move ship
ship.Move();
if (ship.position.Y < 0)
{
ship.position.Y = screen.Height;
escapes++;
}
//look for collision
int hit = 0;
foreach (Sprite ast in asteroids)
{
if (BoundaryCollision(ship.Boundary(), ast.Boundary()))
{
//oh no, asteroid collision is imminent!
EvasiveManeuver(ast);
collisions++;
hit++;
break;
}
//if no collision, resume course
if (hit == 0)
ship.velocityLinear.Y = SHIP_VEL;
}
base.Update(gameTime);
}
protected override void Draw(GameTime gameTime)
{
GraphicsDevice.Clear(Color.CornflowerBlue);
spriteBatch.Begin();
foreach (Sprite ast in asteroids)
ast.Draw();
ship.Draw();
string text = “Collisions:” + collisions.ToString();
spriteBatch.DrawString(font, text, new Vector2(600, 0),
Color.White);
text = “Escapes:” + escapes.ToString();
spriteBatch.DrawString(font, text, new Vector2(600, 25),
Color.White);
spriteBatch.DrawString(font, ship.ToString(), new Vector2(0, 0),
Color.White);
spriteBatch.End();
base.Draw(gameTime);
}
void EvasiveManeuver(Sprite ast)
{
//for now, just stop the ship
ship.velocityLinear.Y = 0.0f;
}
bool BoundaryCollision(Rectangle A, Rectangle B)
{
return A.Intersects(B);
}
}
}
[/code]
Radial Collision Detection
The term “radial” refers to rays or radii (plural for radius), implying that this form of collision detection uses the radii of objects. Another common term is “distance” or “spherical” collision testing. In some cases, a bounding sphere is used to perform 3D collision testing of meshes in a rendered scene, the 3D version of a bounding circle. (Likewise, a bounding cube represents the 3D version of rectangular boundary collision testing.) Although radial collision can be done with an image that has an unbalanced aspect ratio (of width to height), best results will be had when the image has uniform dimensions. The first figure here, Figure 10.3, shows how a bounding circle will not correspond to the image’s width and height correctly, and this radius would have to be set manually.
But if the image’s width and height are uniform, as illustrated in Figure 10.4, then the width or height of the image can be used for the radius, simplifying everything. The beauty of radial collision testing is that only a single float is needed—the radius, along with a method to calculate the distance between two objects. This illustration also shows the importance of reducing the amount of empty space in an image. The transparent background pixels in this illustration (the area within the box) should be as close to the edges of the visible pixels of the shuttle as possible to improve collision results. The radius and distance factors will never be perfect, so reducing the overall radii of both sprites is often necessary. I have found in testing that 80% produces good results. Due to the shape of some images, reducing the radius by 50% might even be helpful, especially in a high-speed arcade-style game in which the velocity would exceed the collision error anyway.
Here is a method that will be helpful when radial collision detection is being used:
[code]
bool RadialCollision(Vector2 A, Vector2 B, float radius1, float radius2)
{
double diffX = A.X – B.X;
double diffY = A.Y – B.Y;
double dist = Math.Sqrt(Math.Pow(diffX, 2) + Math.Pow(diffY, 2));
return (dist < radius1 + radius2);
}
[/code]
An overload with Sprite properties will make using the method even more useful in a game:
[code]
bool RadialCollision(Sprite A, Sprite B)
{
float radius1 = A.image.Width / 2;
float radius2 = B.image.Width / 2;
return RadialCollision(A.position, B.position, radius1, radius2);
}
[/code]
To test radial collision, just make a change to the Boundary Collision program so that RadialCollision() is called instead of BoundaryCollision() in the program’s Update() method.
Assessing the Damage
We now have two algorithms to test for sprite collisions: boundary and radial. Detecting collisions is the first half of the overall collision-handling code in a game. The second half involves responding to the collision event in a meaningful way.
There are as many ways to respond to the collision are there are games in the computer networks of the world—that is, there is no fixed “right” or “wrong” way to do this; it’s a matter of gameplay. I will share one rather generic way to respond to collision events by figuring out where the offending sprite is located in relation to the main sprite.
First, we already know that a collision occurred, so this is post-collision response, not predictive response. The question is not whether a collision occurred, but where the offending sprite is located. Remember that the center of a sprite represents its position. So if we create four virtual boxes around our main sprite, and then use those to test for collision with the offender, we can get a general idea of where it is located: above, below, left, or right, as Figure 10.5 shows.
There will be cases in which the offender is within two of these virtual boxes at the same time, but we aren’t concerned with perfect results, just a general result that is “good enough” for a game. If you are doing a slow-paced game in which pixel-perfect collision is important, it would be vital to write more precise collision response code, perhaps a combination of boundary and radial collision values hand-coded for each sprite’s unique artwork. It might even be helpful to separate appendages into separate sprites and move them in relation to the main body, then perform collision testing on each item of the overall “game object.” Figure 10.6 shows a screenshot of the new boundary collision example, which now has some collision-avoidance intelligence built in. The source code for the program is contained in Listing 10.3.
LISTING 10.3 Source code for the new boundary collision program with collision-avoidance A.I.
[code]
public class Game1 : Microsoft.Xna.Framework.Game
{
GraphicsDeviceManager graphics;
SpriteBatch spriteBatch;
Random rand;
Viewport screen;
SpriteFont font;
Sprite[] asteroids;
Sprite ship;
int collisions = 0;
int escapes = 0;
int kills = 0;
int hit = 0;
const float SHIP_VEL = 1.5f;
const float SHIP_ACCEL = 0.2f;
const float ESCAPE_VEL = 2.5f;
public Game1()
{
graphics = new GraphicsDeviceManager(this);
Content.RootDirectory = “Content”;
TargetElapsedTime = TimeSpan.FromTicks(333333);
}
protected override void Initialize()
{
base.Initialize();
}
protected override void LoadContent()
{
spriteBatch = new SpriteBatch(GraphicsDevice);
screen = GraphicsDevice.Viewport;
rand = new Random();
font = Content.Load<SpriteFont>(“WascoSans”);
//create asteroids
asteroids = new Sprite[4];
for (int n=0; n<4; n++)
{
asteroids[n] = new Sprite(Content, spriteBatch);
asteroids[n].Load(“asteroid”);
asteroids[n].position.Y = (n+1) * 90;
asteroids[n].position.X = (float)rand.Next(0, 760);
int factor = rand.Next(2, 12);
asteroids[n].velocityLinear.X = (float)
((double)factor * rand.NextDouble());
}
//create ship
ship = new Sprite(Content, spriteBatch);
ship.Load(“ship”);
ship.position = new Vector2(390, screen.Height);
ship.scale = 0.2f;
ship.velocityLinear.Y = -SHIP_VEL;
}
protected override void Update(GameTime gameTime)
{
if (GamePad.GetState(PlayerIndex.One).Buttons.Back ==
ButtonState.Pressed)
this.Exit();
//move asteroids
foreach (Sprite ast in asteroids)
{
ast.Move();
if (ast.position.X < 0 – ast.image.Width)
ast.position.X = screen.Width;
else if (ast.position.X > screen.Width)
ast.position.X = 0 – ast.image.Width;
}
//move ship
ship.Move();
if (ship.position.Y < 0)
{
ship.position.Y = screen.Height;
escapes++;
}
//look for collision
foreach (Sprite ast in asteroids)
{
if (RadialCollision(ship, ast))
{
//oh no, asteroid collision is imminent!
EvasiveManeuver(ast);
collisions++;
hit++;
}
}
//accelerate
if (ship.velocityLinear.Y >= -SHIP_VEL)
{
ship.velocityLinear.Y -= SHIP_ACCEL;
if (ship.velocityLinear.Y < -SHIP_VEL)
ship.velocityLinear.Y = -SHIP_VEL;
}
else if (ship.velocityLinear.Y < SHIP_VEL)
{
ship.velocityLinear.Y += SHIP_ACCEL;
if (ship.velocityLinear.Y > SHIP_VEL)
ship.velocityLinear.Y = SHIP_VEL;
}
base.Update(gameTime);
}
protected override void Draw(GameTime gameTime)
{
GraphicsDevice.Clear(Color.Black);
spriteBatch.Begin();
foreach (Sprite ast in asteroids)
{
ast.Draw();
ast.color = Color.White;
}
ship.Draw();
string text = “Intersections:” + collisions.ToString();
spriteBatch.DrawString(font, text, new Vector2(600, 0), Color.White);
text = “Kills:” + kills.ToString();
spriteBatch.DrawString(font, text, new Vector2(600, 25), Color.White);
text = “Escapes:” + escapes.ToString();
spriteBatch.DrawString(font, text, new Vector2(600, 50), Color.White);
float survival = 100.0f – (100.0f / ((float)collisions
/ (float)kills));
text = “Survival:” + survival.ToString(“N2”) + “%”;
spriteBatch.DrawString(font, text, new Vector2(600, 75), Color.White);
spriteBatch.DrawString(font, ship.ToString(), new Vector2(0, 0),
Color.White);
spriteBatch.End();
base.Draw(gameTime);
}
void EvasiveManeuver(Sprite ast)
{
ast.color = Color.Red;
//shortcuts for ship
int SW = (int)(float)(ship.image.Width * ship.scale);
int SH = (int)(float)(ship.image.Height * ship.scale);
int SX = (int)ship.position.X – SW/2;
int SY = (int)ship.position.Y – SH/2;
//create boundary boxes around the ship
Rectangle[] boxes = new Rectangle[4];
boxes[0] = ship.Boundary(); //upper
boxes[0].Y -= SH;
boxes[1] = ship.Boundary(); //lower
boxes[1].Y += SH;
boxes[2] = ship.Boundary(); //left
boxes[2].X -= SW;
boxes[3] = ship.Boundary(); //right
boxes[3].X += SW;
if (boxes[0].Intersects(ast.Boundary()))
ship.velocityLinear.Y = SHIP_VEL * ESCAPE_VEL;
else if (boxes[1].Intersects(ast.Boundary()))
ship.velocityLinear.Y = -SHIP_VEL * ESCAPE_VEL;
else if (boxes[2].Intersects(ast.Boundary()))
ship.velocityLinear.Y = -SHIP_VEL * ESCAPE_VEL;
else if (boxes[3].Intersects(ast.Boundary()))
ship.velocityLinear.Y = -SHIP_VEL * ESCAPE_VEL;
//check for a “kill,” intersection with small inner box
Rectangle kill = ship.Boundary();
int shrinkh = kill.Width / 4;
int shrinkv = kill.Height / 4;
kill.Inflate(-shrinkh, -shrinkv);
if (kill.Intersects(ast.Boundary()))
kills++;
}
bool BoundaryCollision(Rectangle A, Rectangle B)
{
return A.Intersects(B);
}
bool RadialCollision(Sprite A, Sprite B)
{
float radius1 = A.image.Width / 2;
float radius2 = B.image.Width / 2;
return RadialCollision(A.position, B.position, radius1, radius2);
}
bool RadialCollision(Vector2 A, Vector2 B, float radius1, float radius2)
{
double diffX = A.X – B.X;
double diffY = A.Y – B.Y;
double dist = Math.Sqrt(Math.Pow(diffX, 2) + Math.Pow(diffY, 2));
return (dist < radius1 + radius2);
}
}
[/code]
This is perhaps our longest sample program so far, even taking into account that that Sprite class is now found in a different source code file. Game A.I. is a challenging subject. By studying the way the algorithm responds to asteroid collisions, you could use this technique for any number of game scenarios to improve gameplay and/or increase the difficulty by making your A.I. sprites more intelligent.
We learned about collision detection via boundary and radial collision methods, and used these algorithms to study collision response in gameplay code. When a collision algorithm is available, it really opens up our ability to make a game for the first time. As we saw in the final example of this hour, the level of response to collisions can be basic or advanced, rudimentary or quite intelligent, as the spaceship in this example demonstrated.