Collision Detection Methods
I’ve had a few queries about collision detection recently so I decided to share some code I’ve used to detect collisions between two circles as well as rectangles vs circles.
I will be doing a tutorial on this as soon as possible, but for the moment this code could be useful.
In SLQ I am using AABB (Axis Aligned Bounding Boxes) for the collision checks. Each entity is responsible for providing its collision bounds as a CGRect. Its then a simple process of checking each entities CGRect against another using the CGRectIntersectsRect method.
Whilst this is fine for rectangles, what about if you want to use a circle as bounds for your entity. You may either have a circular shape you want bounds for, or you want to rotate your entity and not have to worry about rotating the bounding box in which case circles are useful.
There are no methods available within Cocoa Touch to check if a circle has intersected with a rectangle or if a circle has intersected with another circle. For this you need to create your own methods and the methods I use for these checks are shown below.
This first method can take a CGRect structure and a Circle structure, listed later in this post and check if they intersect. If they do then YES is returned.
static inline BOOL RectIntersectsCircle(CGRect aRect, Circle aCircle) {
float testX = aCircle.x;
float testY = aCircle.y;
if (testX < aRect.origin.x)
testX = aRect.origin.x;
if (testX > (aRect.origin.x + aRect.size.width))
testX = (aRect.origin.x + aRect.size.width);
if (testY < aRect.origin.y)
testY = aRect.origin.y;
if (testY > (aRect.origin.y + aRect.size.height))
testY = (aRect.origin.y + aRect.size.height);
return ((aCircle.x - testX) * (aCircle.x - testX) + (aCircle.y - testY) * (aCircle.y - testY)) < aCircle.radius * aCircle.radius;
}
The next method can be used to check if two circles are intersecting and again respond with YES if they are.
static inline BOOL CircleIntersectsCircle(Circle aCircle1, Circle aCircle2) {
float dx = aCircle2.x - aCircle1.x;
float dy = aCircle2.y - aCircle1.y;
float radii = aCircle1.radius + aCircle2.radius;
return ((dx * dx) + (dy * dy)) < radii * radii;
}
Both of these are designed to be quick and so don't use the expensive sqrtf function. The structure I'm using to define a circle is shown below.
typedef struct {
float x;
float y;
float radius;
} Circle;
Once I’ve finished with the book, I’ll do a proper tutorial on this stuff and show how it can be used. I’m also planning on introducing a physics engine, something like Box2D or Chipmunk to show how they can be used in general and how their more advanced collision detection can also be used.
Hope you find this useful.
Mike
17 Comments
jjack on March 5th, 2010
How do you wrap the circle struct around an object like a sprite is it like the CGRect
Thanks
mike on March 5th, 2010
Hi jjack, exactly like that. You define a circle that is large enough to encompass your sprite e.g.
Circle myCircle; myCircle->x = 50; myCircle->y = 50; myCircle->radius = 25;
The radius would of course depend on the size of your sprite :)
Mike
jjack on March 5th, 2010
But how would you update that everytime the sprite moves is there a drawInRect function for your circle
mike on March 5th, 2010
There is no need to actually draw the circle. The sprite would normally have its own position in the game world, so each time something wants to get the bounds of the sprite it can call a method in your sprites class that returns the a Circle structure.
This structure can be made using the position of your sprite at its center and a fixed radius. The method could look something like
- (Circle)circleCollisionBounds {
Circle circleBounds;
circleBounds->x = sprite.x;
circleBounds->y = sprite.y;
circleBounds->radius = 25;
return circleBounds;
}
Your each time the game updates it could loop through all your entities (sprites) and get each one to return its current circle bounds. You can then perform a check to see if that circle intersects either another circle or rectangle.
Mike
Simon on March 6th, 2010
Hi Mike,
Thanks for this. It’s always nice to see how others do things.
Simon
Scott on March 8th, 2010
Thanks Mike for the great topic.
I started a thread in the forum on my thoughts and progress on collision detection. I’ve learned a ton since then and will really enjoy hearing your thoughts on the subject.
For me, I was not able to use AABB since my player and entities were rotated and I needed the ability to have collision boundaries within a tile segment. I wanted to use a more precise method of collision detection, so I implemented OBB (Oriented Bounding Boxes). This method is very similar to AABB, but instead of every rectangle being a normalized rectangle, they are rotated in world space.
This adds some complexity to collision detection, but not as much as you might think. For example, all of my entities are moving “forward”. This mean that I really only need to test the values of their top left and right coords to any collision boundaries.
In addition, I pre-process the map on startup – recording any “non-walkable” (static collision boundaries) tiles into an array. During collision detection, I first check to see if the tile the entity is currently within my collision array. If not, I just move on. If so, I do the more CPU intensive check to see if my rotated entity quad is within a static boundary. Checking the macro before the micro really helps performance in this case.
Not to confuse the issue, but I have recently just started work on “path finding”. This is the process of having an algorithm find the quickest path from point A to point B – and avoiding any obstacles in between. I am currently implementing the A* (pronounced “A Star”) method since I think this is best suited for the game I am writing. I am seeing how this process can really augment the collision detection process as far as the entity is concerned, but that is a topic for another post.
Thanks again Mike for all you do. I would not be at the level of game development if it were not for you!
Thanks,
-Scott
A Person on March 8th, 2010
@Scott
What method of OBB collision detection did you use? I am working on a OBB collision detection system of mine own i’d love to know how you implemented yours.
Easy And Accurate 2D Collisions | iPhone and iPad SDK Development Tutorials and Programming Tips on March 8th, 2010
[...] first tutorial is from 71 Squared on Collision Detection Methods which has a some nice straightforward functions written in C that you can drop into your code for [...]
Scott on March 8th, 2010
A Person,
My OBB system is pretty basic. First of all, all my static collision boundaries on my map are created using AABB (normalized rectangles). All of my entities including my player are done with “forward moving” OBB. Basically the bounding box around all my entities is rotated in the same direction the entity is facing. I created a simple structure to hold the OBB called RotatedQuad like this:
Typedef struct {
CGPoint frontLeft;
CGPoint frontRight;
CGPoint rearRight;
CGPoint rearLeft;
} RotatedQuad;
Each entity is responsible for keeping its bounding box rotated in the correct orientation. Once I need to check for a collision, I simply just check to see if the frontLeft and/or frontRight CGPoints are within any of my static bounds. The actual collision testing is really as simple as AABB testing. Since I am only concerned with the front of each bounding box, it makes it even simpler.
To speed this up, I pre process my map on startup to save every tile location in the map to a 2D array called walkabilityArray. This array is indexed using the x and y coords of the map location. During initialization, if I find a static boundary passes anywhere within the tile, I save a value of 0 indicating that there is a boundary on the tile and further testing should be performed. If no boundary is present on the tile, I save a 1 indicating that there is nothing to check and to move on.
This really helps performance when doing collision checking. Instead of constantly checking each quad and static boundary for a collision, I first just perform a lookup in my walkabilityArray to see if I really need to do any kind of collision test. Accessing my 2D array is much faster than checking for OBB vs. AABB collisions.
I hope this helps, but if you are looking for more specifics, just let me know.
-Scott
blakeman13 on March 9th, 2010
So how would this work for like a entity such as the ghost in your tutorials and how would you remove it from the screen if a collision is detected and or introduce an explosion where the collision was detected
A Person on April 3rd, 2010
Any ideas on how the rectangle circle collision detection could be changed to work for oriented rectangles?
Tweets that mention Collision Detection Methods | 71² - The ramblings of two 30-something developers -- Topsy.com on April 19th, 2010
[...] This post was mentioned on Twitter by AQILITY. AQILITY said: On Collision Detection Methods- http://bit.ly/dA8iYX [...]
Paulw on July 26th, 2010
Hi Mike
just a quick comment to say how much I am enjoying your videos and comments. I am looking forward to your book and am going to buy it on day one.
Keep up the good work.
Paul
Chris on February 14th, 2011
Can these methods be used as well if there is a rectangle-rectangle collision detection?
I´m trying to create “solid” rectangles for a game (without using OPENGL, just regular UIIMAGES) where the rectangles cannot go through each other (when trying you should feel like hitting a wall) but can be stacked on top of each other.
any tutorial about that type of collision detection?
mike on February 14th, 2011
Hi Chris
There is no reason why these methods could not be used for that although your needs do introduce a few more complexities.
The methods as they stand just let you know when two objects intersect each other, they don’t tell you by how much the objects penetrate each other. This is important so that having identified a collision, how far back you need to move the objects so they are touching but not penetrating.
This can get complex quickly and I would suggest using a physics engine such as Box2D or Chipmunk. These can be used in an app that doesn’t use OpenGL. You would simply set up your physics world in which you create objects of the size of your UIImages. Then you step the world each game update and use the location and rotation of the object in the physics world to set the location and rotation of the UIImage before you render it.
Doing this will give you all the collision detection and resting functionality you need plus more.
It sounds complex, but once you start looking into it it’s not too bad.
Mike
Chris on February 16th, 2011
Hey again!
Couldn´t find a reply button… so I hope it´s okay that I send a new comment instead.
can I combine Box2D and Chipmunk with the code I already have created to get the collision detection to work the way I want it to work or do I need to rewrite the whole game (menu,settings etc). (isn´t there any other way to do this?) I feels like I don´t have time to learn how chipmunk or box2d works. I´m closing in on the deadline :(
fredflinstone on March 5th, 2010
thanks, this will be useful
I have started to look at Chipmunk for my game and have just been looking through some demos, a tutorial on Chipmunk would be great seen as there are not that many I can find.