Collision detection

[geldo79]

Hi,

It's been a year or so since I stopped coding for my spacewar-like Amiga game. Now i started again and did some optimitations, and i think i am not so far away from producing a first kind of a playable version. I think the only technical problem i still have is to find a proper way of collision detection. In principle i have a 'working' solution, but it is too slow. The problem is that my bobs and sprites move really fast. The collision between the sprites (spaceships) and bobs (laser cannon shots) have to be detected. Also the collision between the sprites. I tried to determine if an intersection between the vector of the bobs and the sprites exists, and in principle that works. But i wonder i someone can give hints for a faster collision detection. To just use bounding boxes could be difficult, because the bobs and sprites have dimensions of 16x16 pixels, but can move up to ca. 32 pixels per frame. The boxes would have to be very big. Any ideas?

Greetings Christian

[mcgeezer]

Can you not use the inbuilt hardware tondo the detection? Clxcon?

Geezer

[roondar]

One option I once experimented with is doing multiple collision checks per frame so that you can guarantee that the objects motion is accurately captured using smaller bounding boxes.

Essentially, I'd cut up the large motion in several smaller steps for the purposes of collision but not for the purposes of drawing the screen. This works, but of course has a drawback in that collisions take (much) more CPU time to handle.

[defor]

Does it mean that you need something usually called CCD -- Continuous Collision Detection because of fast moving objects? Possibly the simplest is the collision detection between two moving circles which reduces down to finding a line-circle intersection. However even that requires a square-root :-( You need it to compute a time of collision (= a distance along the line). If you don't need that info then you don't have to sqrt. I'm afraid that finding (exact) time of collision between any other type of objects is even more time-consuming. Maybe you can speed up sqrt by some pre-computed table? Or you would be fine with squared values? Alternatively you can try to sample the space by checking box-box (or possibly a faster circle-circle) intersection along a line as @roondar suggests. It really depends on how precise results you need. If all you need is just a simple overlap test then it is simple to compute how many samples (overlap tests) you need between two objects of some dimensions and their relative(!) velocity.

[geldo79]

Thanks for your replies. I could optimize my method a bit, and I made a mistake in my distance calculation. I wanted to calculate the collsion detection only if the objects are close enough for a collision. Because of my mistake, it was calculated for every Bob...and that was too much for the CPU to do it during the vertical blanking. Now everything runs smoothly again....:-)

It's an intersection calculation between the movement vector of the Bob (laser cannon) and two lines drawn horizonatlly and vertically over the spaceship (sprite). In combination with simple bounding box, it works very good even for very fast moving objects.