Quickest way to test collisions

[Shatterhand]

What's the quickest way to test collisions between objects?

Using DoColl/PColl is incredibly fast if you poke one sprite against 1 single bitplane. This is great if you don't have to test what collided with what (example: every enemy has an outline drawn with color 1, if touches player, player dies. You don't need to know what touched the player, you just need to know an enemy touched it and now he's dead ). Preliminary tests I made indicate this is faster than comparing a Word with a Word 5 times.

Now if you have a space ship that can shoot up to 8 bullets at the same time on screen, and you have 30 enemies on screen, each one will die if hit by one of the bulelts.... what's the fastest way to do that test?

I am really scratching my head trying to figure out a fast way, anything I try seems to be slow as hell. (I am badly used to work with super fast CPUs, coding for a 7mhz one is very challenging ). If anyone can could come up with ideas (if possibly ,please, with examples ), I'll be very grateful.

[MickGyver]

This thread discusses bounding box collision methods, maybe it can help:

http://eab.abime.net/showthread.php?t=91067

Interesting question, I will follow this thread.

[E-Penguin]

I've been pondering the same thing. Comparing everything with everything else is O(n²) - exponential computing cost. Probably there's some optimisation to be done by first filtering by general area (if all the bullets are in the left and all the enemies are on the right there can't be a collision).

I wonder whether some sort of binary search would speed it up, at the cost of maintaining the enemy list in a sorted order?

[Shatterhand]

Originally Posted by MickGyver

This thread discusses bounding box collision methods, maybe it can help:

http://eab.abime.net/showthread.php?t=91067

Interesting question, I will follow this thread.

This thread had LOTS of considerations I had never even thought about, like using pointers

So far I've been trying to check collisions using the same method Daedalus suggested that, with 4 ifs. Problem is, 8 bullets * 30 enemies * 4 ifs = 960 possible checks. It's a shitload of stuff to check on the worst case scenario, this alone will take a whole frame.

I guess I'll post there to see if I can get any help. Thank you for point me out for that thread.

[Shatterhand]

Originally Posted by E-Penguin

I wonder whether some sort of binary search would speed it up, at the cost of maintaining the enemy list in a sorted order?

If all enemies can be at any X or Y without actually have one side of the screen more used than the other, I have the feeling that the time you will take sorting it will not compensate for what you may gain with a binary search.


I was thinking about trying to use some kind of grid structure... my screen is 320x256. I divide this maybe ine 10x8 32 pixels cells. Bullet check collisions only against enemies on the surrounding cells it is right now. But I just can't wrap my mind on how to make something like this work anyway.

[Dan]

well, then each bullet shall have grid position coordinates px,py

The enemy ship has, as well, px,py Grid - coordinates.


So when you save the coordinates for each bullet, you check if bullets px/py coordinate are near ship px,py , something like pseudo code:

if abs(bulletPX(x)-EShip_px(x))<=2 and Abs(BulletPY(y)-EShip_Py(x))<=2 then 
check for colision
endif

you should see what works better <=2 or <=1 , depending on the grid size.

[Shatterhand]

I'm already doing 2 checks there, before I move to the other 4 checks. Ok, this may halve the overload, but still seems to be a lot, isn't it? And it's 2 more checks for each grid check that is "validated"

Well, I can do just one grid check on the Y axis first and only if this one is valid, I go for the X axis check. This may give me up to 50% less overload.

EDIT: Also I can't think of any way of keeping the grid position without doing a division ( px = x / cellsize) , and from what I hear, divisions are slow as hell.

[Retro1234]

Can't you just do
If Bullet X,Y = Player X,Y Then Hit ?

[Dan]

Originally Posted by Shatterhand

I'm already doing 2 checks there, before I move to the other 4 checks. Ok, this may halve the overload, but still seems to be a lot, isn't it? And it's 2 more checks for each grid check that is "validated"

Well, I can do just one grid check on the Y axis first and only if this one is valid, I go for the X axis check. This may give me up to 50% less overload.

EDIT: Also I can't think of any way of keeping the grid position without doing a division ( px = x / cellsize) , and from what I hear, divisions are slow as hell.

Yeah. On the today's PC this wouldn't be a prob, but on the amiga ...

[Retro1234]

If your going to have to increase your Bullet X,Y anyway you might a well just add an If it's hardly cpu intensive.

But Blitz probably has some kind of Bob collision check anyway.

Most Amiga games probably use blocking anyway for the Map the Enimies everything.

[Shatterhand]

Originally Posted by Retro1234

Can't you just do
If Bullet X,Y = Player X,Y Then Hit ?

This would work great if both bullet and player were just 1 pixel big

[Retro1234]

If bullet X+0 or If Bullet X+16 or If Bullet Y+0 etc etc

[E-Penguin]

Originally Posted by Shatterhand

If all enemies can be at any X or Y without actually have one side of the screen more used than the other, I have the feeling that the time you will take sorting it will not compensate for what you may gain with a binary search.

I dunno... You would avoid having to check every bullet against every enemy. Let's assume you maintain a list L sorted on x position containing enemies...

Pseudo code :

 
For each bullet b do
    Enemy e = BinarySearch(L, bullet.x) 

   If e != null then 
       CheckBounds(e, bullet)
    End if
Next

Let's assume your BinarySearch function returns a valid enemy pointer from list L if the x is within some distance of the enemy's x. If that is valid then do a bounds check. That way you're not comparing everything with everything else. The code complexity then approaches O(n) which is a vast improvement. You would probably need to also repeat this until no more enemies are found for that X.

Assuming blitz's list sort function is something sensible, it's quick to sort an already sorted (or mostly sorted) set.

[Shatterhand]

Originally Posted by Retro1234

If your going to have to increase your Bullet X,Y anyway you might a well just add an If it's hardly cpu intensive.

it's 1 if on the best case scenario, 4 ifs on the worst case scenario. 8 bullets * 30 enemies * 4 ifs = 960 ifs. *it is* CPU intensive from the tests I've made.

But Blitz probably has some kind of Bob collision check anyway.

It does have sprite against sprite collision which works great and it's pretty fast. It has sprite against playfield collision which is fast enough if you use it smartly, but it only tells you a collision happened, not where it happened, so it's not useful if you need to know what collided with what. All the other collision functions are basically pretty ways to do the classic 4 IFs structure to check if 2 rectangles are touching each other.

Most Amiga games probably use blocking anyway for the Map the Enimies everything.

[/quote]

I have no idea of what you meant here.

[Retro1234]

Ok but a grid could work well like you say that way you don't won't have to check them all however I assume most Games know exactly where on screen everything is at all times incase Bullet hits wall etc

I don't know enough about Blitz can you not do If Baddy BOB 1 collide and IF Bullet 6 BOB collide.

[Dan]

Or you divide the Main Loop into 2 sections/part.

The First section/part does the movement
The Second section/part does the collision check

something like

a=1
;main loop
do
 a=-a
  if a=1 
    PlayerMovement()
    Enemymovement()
    Playerbullets()
    Enemybullets()
  else
    CollisionCheck() 
  endif

flip ; or whatever the blitz uses to redraw the screen.
loop

Sadly i'm familiar only with the PC's version of Blitzbasic ...

[Shatterhand]

Assuming blitz's list sort function is something sensible, it's quick to sort an already sorted (or mostly sorted) set.

There's a sort command on Blitz and I have no idea of how to use it, as any way I try to write it gives me a Syntax Error, and the manual is just extremely vague about (even citing something like "we will work out on this function at a later version")

I probably have to write a sort method myself.

[Retro1234]

And don't check them all at once check them 1 by 1 in your loop

If Bullet X[N]+0 or BulletX[N]+16 = Ship[N]+0 or Ship[N]+16 then = Hit
N=N+1
Loop

So 30.checks after 30 Loop etc

[E-Penguin]

Originally Posted by Retro1234

And don't check them all at once check them 1 by 1 in your loop

If Bullet X[N]+0 or BulletX[N]+16 = Ship[N]+0 or Ship[N]+16 then = Hit
N=N+1
Loop

So 30.checks after 30 Loop etc

You'd need nested loops, which gives exponential running times. The cpu will be mostly checking things that are nowhere near each other. There must be a better way.

[Retro1234]

Yeah it's a bit of a waste but 4 checks or up to 15 maybe max per Game Loop is hardly CPU intensive I think a ZX80 could do it.