Collision detection methods

[tentons]

I'm curious about what sorts of 2d collision detection you guys employ.

I do a sector test to reduce the number of tests to objects that are within a certain proximity, then bounding circle, then bounding box. My current game doesn't need extreme accuracy, so this should work out.

[Nemesis]

The most accurate 2D solution would of course be a pixel-by-pixel check on the bounding box overlaps.

I'm working on a 3D shoot-em-up however and hence I also had to come up with an adequate solution. Every entity has a bounding sphere. Within the bounding sphere of an entity, a number of "collision spheres" define a very approximate bounding shape. Obviously, the more spheres used, the better. For most cases, 2-6 spheres are more than enough.

The following is a screenshot illistrating the collision spheres in the custom game editor:
http://colinvella.no-ip.com/perihelion/021.jpg

[Rod Hyde]

I'm curious about what sorts of 2d collision detection you guys employ.

I do a sector test to reduce the number of tests to objects that are within a certain proximity, then bounding circle, then bounding box. My current game doesn't need extreme accuracy, so this should work out.

Pixel-perfect collision detection doesn't need to check pixel-by-pixel. For each sprite, I pre-calculate the runs of non-transparent pixels on each row. In my current game I actually save this along with the sprite data, but it would be just as simple to calculate it when the sprite bitmaps are first loaded.

In the game itself, once the "shallow" collision detection has determined the need for a more detailed check, I simply determine the area where the two sprites overlap, then check if the runs of data overlap.

This is the code in Python.

def test_collision(self, other):
"""Pixel perfect collision detection.

Works on the premise that most sprites are opaque in the middle and
therefore have a small number of relatively long runs of opaque
pixels per row.
"""
cd1 = self.get_collision_data()
cd2 = other.get_collision_data()
l1, t1, r1, b1 = self.bounding_rect
l2, t2, r2, b2 = other.bounding_rect
start = min(t1, t2)
stop = 1 + min(b1, b2)
dx = l1 - l2 # difference in x coordinates
for y in range(start, stop):
r1 = y - t1 # row number in first shape
r2 = y - t2 # row number in second shape
if cd1.has_key(r1) and cd2.has_key(r2):
for run1 in cd1[r1]:
min1, max1 = run1
min1 += dx
max1 += dx
for run2 in cd2[r2]:
min2, max2 = run2
if max1 >= min2 and min1 <= max2:
return True
return False

[Nemesis]

Rod Hyde, good technique!

But does it handle hollow sprites? i.e. can you have more than one run per row?

(edit) I didn't bother to look at your code snippet... the answer is no.. duh.. silly me!

[Rod Hyde]

Rod Hyde, good technique!

But does it handle hollow sprites? i.e. can you have more than one run per row?

(edit) I didn't bother to look at your code snippet... the answer is no.. duh.. silly me!

Yes, it should handle hollow sprites as there can be several runs per row. Each row of collision data is a list of pairs of x coordinates, ie, the minimum and maximum x coordinate of each run.

To generate the collision data, I hacked up a Python script. The bit that does the work is shown below. My assumption in the following code is that black pixels are transparent.

def make_collision_data(image_file):
"""Generates dimension and collision data from the given bitmap file.

Returns a tuple consisting of the bitmap's width, its height and a
dictionary, indexed by row, containing lists of "run" tuples, where a run
tuple is a (start, end) pair indicating non-transparent data.
"""
import Image
im = Image.open(image_file)
width, height = im.size
run_dict = {}
for y in range(height):
in_run = False
run_list = []
for x in range(width):
pixel = im.getpixel((x, y))
if pixel != (0, 0, 0) and pixel != 0: # deals with both 24-bit and 8-bit data
if not in_run:
in_run = True
run_start = x
elif in_run:
in_run = False
run_list.append((run_start, x-1))
if in_run: run_list.append((run_start, width-1))
if len(run_list) > 0:
run_dict[y] = run_list
return (width, height, run_dict)

I am just amazed that I never thought of doing this 12 years ago when I was really into programming in 2d.

--- Rod

[MirekCz]

Pretty nice method.

To get a very fast, all-cases collision detection you can do the following stuff:

1.create a 1bpp masks which tells pixel trasnaprent(0) or opaque(1)
2.If initial bounding-box or similar test is passed you make detailed test

you simply take the mask values of objects from the same line on screen, shift them to put them in their position, AND them, if result is >0 you have got a collision. If you're sprite width is larger then 32pixels or higher then 1 you have to repeat the xor

some ascii art now

sprite 1 mask
0001111000
sprite 2 mask
0011001100

here's how sprite are drawn on screen (1-sprite 1, 2-sprite 2, 3-both sprites)
1113333333222 (so sprite 2 is moved 3 pixels to right from sprite 1)

so you need to do
sprite1 mask AND (sprite 2 mask >>3)
so you get
*****0001111000
AND**0000011001 (sprite2 was shifted 3 to right)
------------------------
result*0000011000 - collision detected

//* is just a dummy char

This system works great, althrought it is a bit problematic to implement well in practice for all cases(simply needs time to write it well and fix eventual bugs). The good point is little memory need and very fast test time, especially for sprites <=32 pixels wide.

[Nemesis]

@MirekCz,
Your method is definitely better than pixel-pixel checking but I think Rod Hyde's solution is more efficient as it is independen of sprite width, provided there aren't too many hollow sections.. but that is unlikely.

@Rod Hyde
I wouldn't have thought about that solution either.. although it is reminiscent of the (name off the top of my head - correct me if wrong) span-line floodfill algorithm.

[tentons]

@Rod Hyde: That's a cool technique! I'm really interested in knowing how (natively) compiled Python performs. Have you done any benchmarking with your collision algorithm?

@Nemesis: I'm resisting the urge to do a 3d game because I have a learning curve to face, but also because there are plenty of ideas where 3d adds nothing except more art requirements. But eventually I'll take the leap.

[Nemesis]

That's true.. there's little point in going 3D if you can satisfy the gameplay requirements in 2D. I'm still very much in love with 2D actually but I decided to give 3D a go anyway. My game Perihelion offers classic shoot-em-up gameplay but in 3D so in essence you're given an extra dimension to dodge enemy fire, fly through structures etc.