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
14 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
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.