Collision detection?

Game Play & Game Design
#1

I was thinking about making a simple 2D car game, seen from above where you drive a car around a track, and there will be people walking around that will get smacked if the car hits them.

Now i wonder whats the best way (in your opinion) to handle the collision detection between the car and the people (also the edges of the track etc.
I can think of two ways, making the whole game a huge array and check if some part of the car is in the same array as another object.

Or in some way store the coordinates of each object and simply check if the coordinates of the car is the same as another object.

I Could really use some hints.

Thanks.

#2

I think you should try to test on intersecting intervals. To speed your code up, I suggest you use some kind of 2-dimensional tree to store your objects in. (If time-complexity is an issue for you)

#3

Ok, i think i understand, but i could use a brief explanation.

#4

thinking about a good collision detection is thinking about the game restrictions itself. most tips tuning
your detection base on looking for things that cant happen. for example, can your car drive around in one
screen, or is the world/street moved while your car has a relative fix position?
do you want to allow any type of street or is it enough to have a straight street, a 90° curve and two, three
more types? do you need real round slopes, or is it enough to have a kind of polygon street?

#5

True.
I was thinking of making the entire track/street or whatever fit in one screen, no scolling in other words. Dont need too many different types of street.

I do understand that its difficult to say what i should use for collisiondetection when i cant really specify my game requierment.
But i was curious about different methods that i havent thought about.
And was hoping i could get some examples and get some ideas what to use.

#6

For static enviromnets (or semi static) then tile-based works great. Dead easy to look up which tiles you’re over, and then performing collision based on pre-fabbed tile types is quite simple too. For dynamic objects you can just use the position and some kind of bounding shape and check against all of them each frame. If you’ve got really huge worlds or tons of dynamic objects some kind of spatial tree (like a quad tree) could be used to speed things up, but I think you’ll find that’s a waste of time.

#7

Thanks for the answer.
I think i got an idea how to do it.
Worst case scenario is it doesnt work and thats not the end of the world :slight_smile:

#8

Two different methods I have used in tile-based collision detection:

  1. Check the tole locations of the top left, top right, bottom left and bottom right corners of an object, and see if they match those for a different object. Use a Rectangle object as bounds to match up against any resulting colliding objects to make sure that there isn’t a tile-wide gap between them.

  2. Use a total of four Rectangle objects per item (one for up, down, left, right) and check in a 3x3 tile sized grid around the object for collisions with that object’s four bounds objects.

Make sense?

#9

yes, makes alot of sense :slight_smile:
thanks.

#10

Hey, I was just wondering about something similar to this.

I’ve been developing a small pong-like game with paddles and a ball.
I need to detect collisions between the ball and the paddles for the game to work, and I origionally did this using bounding boxes on each element.
That worked fine, until the ball started moving faster. Because the check only happens at certain points in time, it was possible for the ball to pass completly through a paddle without it being detected.

I ended up solving this by plotting a line from the balls old position, to the balls new position, and checking for intersections with that.
I was just wondering if that is the common way to solve that, or is there something better?

-Munkii

#11

it would be simpler in that instance to just check if the paddle has gone higher than the top paddle or lower than the bottom paddle (assuming the paddles are on the top and bottom)

EDIT: u would have to check that the paddle intersects with the ball vertically aswell

#12

The line plot sounds like a good idea. I haven’t had this problem myself, but I probably would have done something similar or perhaps had fringe cases to check if the ball goes past the paddle’s X position, how long ago the last timestep was. So pretty much like this:

#13

When you use discrete tiles and a game object is always exactly on one tile in the center, you can just check collisions on tiles.
If you use tiles to build your map, but free positions for objects, so that a object can be on the border of a tile and might cover multiple tiles, you need something else.

Collision in space is usually either rectangular collision test or circular collision test first. For a bounding rectangle you use the minx, miny and maxx, maxy coordinates of each object and check if two objects overlap. For a bounding circle you need a center coordinate and a radius for each object. The distance between two objects centers must be greater than the sum of their radi. Use pythagoras. Do not us sqare root, better use the square of the radi

mindistance = radius1 + radius2
xdistance = (x1 - x2) * (x1 - x2)
ydistance = (y1 - y2) * (y1 - y2)
if( (xdistance + ydistance) < (mindistance * mindistance) )
{
collision
} else
{
no collision
}

this is based on Pythagoras a^2 + b^2 = c^2
It is cheaper to use c^2 than to calculate the square root of (a^2 + b^2)

If you have a one screen game and few objects, you can just check each object against each other.
On greater areas, you would divide the area into sectors. You can either use tiles, or groups of 5x5 tiles for example as “sector” und you check all objects of a sector against all other objects in the same sector and against the neighbour sectors.
If you make a vertical or horizontal scroller, you can sort objects by x or y coordinate and check an object against all other objects up to 100 pixels away or such. Depends on your greatest object.

Modern games use trees for this. Quadtrees or Octrees, which iteratively divide the whole map in equal parts.

-JAW