Physical Queries for the Math Challenged: Collision Detection and Response
Following developing Forte I thought I would share some of the challenges I encountered and more importantly how I overcame them. I am what you might call a design nut more than a number wonk, so some aspects of game programming are more challenging for me. Specifically, I ran into trouble when I needed to implement collision detection and ray casting for my tile based game. If you find yourself needing a collision detection scheme to fit your game or just want a way to easily support ray casting then you've come to the right spot. In this post I'm going to cover the basics of implementing such a system without needing to delve into complex vector math or kinematics.
I'm not going to leave out the hard stuff, I'm simply going to elaborate on an approach which avoids the tricky stuff and still works. Of course, there's a catch, which is that you've got to follow a number of constraints imposed by this system. To help reduce this burden I've tried to make it possible to implement more advanced functionality down the road without having to change existing code. This post will deal with the basic data structure underlying everything and how to perform collision detection with it. Please stay tuned for my next post on performing various queries using ray casting. Finally, for those of you who want the full source code at hand when you read you will find the full source code for the grid system described here attached below.
High Level Overview
Before I can tell you about the constraints and implementation of the framework I need to outline what the overall picture plan is. Following the lead documented by the N tutorial we are going to construct a grid which divides the screen into some number of cells. The goal is to place each game object into a single cell. Following this we simply check a cell and its neighbors when checking for collisions and walk across cells when ray casting.
Constraints
Without further ado here are the constraints. Whether they're too onerous is up for you to decide. Personally, I think it's worth working under these restrictions in exchange for ease of development.
- Each game object must be equal to or smaller than the size of a cell.
- Game objects can not exist outside of the grid.
- The "loose" system described here can lead to errors with ray casting.
- Very fast moving objects pose a problem.
- Only very simple collision response is possible.
Constructing the Grid
First off we need to divide the physical space into a grid. This is straightforward given you've got a tilemap. The size of a cell is equal to the size of a tile and the grid's dimensions are equal to the tilemap's dimensions. If you aren't using a tilemap then simply decide what dimensions fit for you. Please keep constraint 1 in mind when determining the size of the cells!
Once the grid is in place it's very simple to place game objects in the correct cell. The great thing about this is it greatly reduces the number of tests you need to perform for intersections. Now you only need to check for collisions against objects in the same cell.
/* Calculate which column and row the body falls under. */
private Cell getTargetCell(Body subject) {
return point2cell(subject.getCenterX(), subject.getCenterY());
}
/* Calculate which column and row the point falls under. */
private Cell point2cell(float x, float y) {
int column = (int) Math.floor(x / cellWidth);
int row = (int) Math.floor(y / cellHeight);
Cell target = cells[column][row];
return target;
}
One gotcha is that an object may occupy more than one cell. If you follow the first constraint then at most you'll need to check three neighboring cells for collisions. Don't worry, I'll show you how to do this, too.
/* Check each corner to see whether it is in a neighboring cell. */
protected Iterable<Cell> neighbors(Cell c, Body b) {
Set<Cell> neighbors = new HashSet<Cell>();
/*
* Adjust the dimensions to fit inside a cell. This is for objects equal
* to the size of a cell.
*/
float width = b.getWidth() - 1;
float height = b.getHeight() - 1;
Cell topLeft = point2cell(b.getX(), b.getY());
if (!c.equals(topLeft)) {
neighbors.add(topLeft);
}
Cell topRight = point2cell(b.getX() + width, b.getY());
if (!c.equals(topRight)) {
neighbors.add(topRight);
}
Cell bottomLeft = point2cell(b.getX(), b.getY() + height);
if (!c.equals(bottomLeft)) {
neighbors.add(bottomLeft);
}
Cell bottomRight = point2cell(b.getX() + width, b.getY() + height);
if (!c.equals(bottomRight)) {
neighbors.add(bottomRight);
}
return neighbors;
}
Also, don't forget to update the grid at a regular frequency. I simply cleared each cell and then repartitioned the list of bodies being tracked like so:
/**
* Clear each cell of its bodies so that we can repartition the physical
* space.
*/
private void clearCells(Cell[][] cells) {
for (int x = 0; x < cells.length; x++) {
for (int y = 0; y < cells[x].length; y++) {
cells[x][y].clear();
}
}
}
/**
* Divide the bodies up by their position and place them into the
* appropriate cell.
*/
private void partitionBodies(Iterable<Body> bodies) {
for (Body subject : bodies) {
Cell target = getTargetCell(subject);
target.add(subject);
}
}
Performing Collision Detection
Now that we have the grid set up we can start to make it work for us. The first thing to do is check for intersections. This answers the question "Am I touching another body?". However, in order to effectively respond to a collision we want more than a simple yes/no response. In Forte I used basic information about the two bodies in order to correctly respond to collisions. First we need to determine when a collision occurs; as I alluded we need to check the bodies in the same cell against each other...
/* Check each body for collisions. */
public void update() {
LinkedList<Body> obstacles = new LinkedList<Body>(bodies);
for (Body subject : bodies) {
obstacles.remove(); /* Pop off the current body */
collider.testAndAlert(subject, obstacles);
/* Check against neighbors */
for (Cell neighbor : grid.neighbors(this, subject)) {
collider.testAndAlert(subject,neighbor.bodies);
}
}
}
/*
* Test whether the subject intersects with any obstacles and alert the
* parties if so.
*/
public void testAndAlert(Body subject, Iterable<Body> obstacles) {
for (Body obstacle : obstacles) {
if (!subject.equals(obstacle) && intersecting(subject, obstacle)) {
Contact event = getContact(subject, obstacle);
subject.collide(obstacle, event);
obstacle.collide(subject, event);
}
}
}
Intersecting first checks the bounding spheres around the bodies. This was done due to the implementation of the Shape class at my disposal. It may make more sense to simply use AABBs instead. Really, it doesn't matter much. Do whatever is easiest given your situation. If you're interested in using bounding boxes feel free to lift this implementation.
/* Check the bounding spheres of the two bodies. */
private boolean checkBounds(Body one, Body two) {
float x = (float) Math.pow(one.getCenterX() - two.getCenterX(), 2);
float y = (float) Math.pow(one.getCenterY() - two.getCenterY(), 2);
float r = (float) Math.pow(one.shape.getBoundingCircleRadius()
+ two.shape.getBoundingCircleRadius(), 2);
return ((x + y) <= r);
}
If the bounding spheres intersect then the primitive shapes are checked themselves like so. If you haven't got a nice shape class to do this work for you then you've got some hard work cut out for you, but then again maybe that's a signal it's time to switch languages?
/* Check whether the shapes intersect. */
private boolean checkPrimitives(Body one, Body two) {
return one.shape.intersects(two.shape);
}
Alright, at this point we know that an intersection has occurred, so the next step is to respond. For my purposes I wanted the two objects to move out of intersection. Since I didn't want to struggle to find the normal to the collision, the point of collision, and other relevant but tricky things I implemented an approach using the relative position of the intersecting bodies. Please note that how to respond is very much specific to your game, so treat what I'm about to show you as a starting point...
/* Move the tank out of intersection with the obstacle. */
public void collide(Body obstacle, Contact event) {
/* Amount to move in the x and y direction. */
float ddx = 0;
float ddy = 0;
/* If my top is above this one and I'm moving down. */
if (getY() < obstacle.getY() && dy > 0) {
ddy -= dy;
/* If my bottom is below this one and I'm moving up. */
} else if (getY() + getHeight() > obstacle.getY() + obstacle.getHeight() && dy < 0) {
ddy -= dy;
/* If my left side is right of this one and I'm moving right. */
} else if (getX() < obstacle.getX() && dx > 0) {
ddx -= dx;
} else if (getX() + getWidth() > obstacle.getX() + obstacle.getWidth() && dx < 0) {
ddx -= dx;
}
/* Move the body back according to its speed. */
ddx -= dx;
ddy -= dy;
setX(getX() + ddx);
setY(getY() + ddy);
}
Alright, it's worth explaining this; No matter what happens I move the body back to its previous position according to its velocity. Additionally, I would like the body to slide along objects instead of just sticking. For instance, imagine that the player is moving his tank along a wall. To achieve this I find where the obstacle is relative to the current body and modify my position accordingly.
Further Work
Alright, well we've got the grid implemented and collision detection and response up and running. That said there are still some areas for improvement. Most notable is ray casting which I have left for my next post. With ray casting in place we will have all the tools necessary to start making games with complex AI. Here are some other areas for improvement:
- Add A* pathfinding on top of the grid.
- Improve the collision detection to return additional information such as collision normal.
- Optimize for performance at various points throughout the grid.
Thanks for reading and let me know if you found this helpful or have any questions!
Resources
Please feel free to use, modify, and distribute the following code however you like. I would greatly appreciate any meaningful feedback and contributions! Beware, though, that the code is not particularly cleaned up and is distributed as is with no guarantees whatsoever.
- Crash source code (Written in Java and requires the Slick library to compile)
- Tutorial on ray casting. The next article in the series!
There are currently no comments.
Leave a Reply