Quickest way to test collisions

[Shatterhand]

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

I still don't understand what you're saying. Of course you will do one at a time in a loop, but this loop will be in your main game loop which should, in theory, all be executed in one frame. That's the whole point.

Right now I could have a code like this:

for f =0 to num_enemies
   for g = 0 to num_bullets
       if enemyx(f) > bulletx(g) - 8
          if enemyx(f) < bulletx(g) + 8
              if enemyy(f) > bullety(g) - 8
                 if enemyy(f) < bullety(g) + 8
                          colide()
                 endif
              endif
          endif
        endif
    next
next

This is the easiest way to do (and I am using arrays to be easier to understand ,but in Blitz you'd have a "new type" of enemy and bullet where X and Y would be, and probably would be parsing a list instead of array).

But this is very slow and if you have many bullets and many enemies, it will take a huge portion of a frame to do it.

[Shatterhand]

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

It's 4 checks when you're check one object against one object. When you are testing 8 objects against 30 (like the example I Gave) it's 960 checks. It does eat a lot of time.

If you only check one object against one object per loop your game won't work properly, missing collisions all the time.

I really think the Grid idea works great with checks against background, since it's easier to keep everything on a grid and you can probably do a whole shift in a grid when the screen moves very quickly (I guess). But with stuff that moves freely on screen to many different directions I am not sure it would help at all.

[Retro1234]

Your still trying to check them all in 1 game loop they only move what 4 pixels max per loop you won't miss anything.

Even if you check them all at once like your code above it should be quick.

[Shatterhand]

Originally Posted by Retro1234

Your still trying to check them all in 1 game loop they only move what 4 pixels max per loop you won't miss any thing.

Even if you check them all at once like your code above it should be quick.

I've made Quasarius.
[ Show youtube player ]

if I remember correctly, enemies move 2 pixels when they move, player laser moves at 8 pixels.

What I did on that game (and keep in minding I was still learning a lot of this stuff and I know it wasn't the smartest way) was first check if the laser sprite was colliding with the color of the enemy (all the enemies have a color in common). If it is, then figure out what enemy the laser is hitting.

With all 12 enemies on screen, I had to do just 48 checks. Believe it or not, THIS CAUSED a hiccup on the game. I switched to test just half of enemies at one loop then half of the enemies at the following loop. Many times I just missed the collision on the next loop because the laser had already moved past the enemy. So when the laser hits an enemy, on the next frame if its not destroyed (when it didn't detect what enemy it was hitting), the laser does not move. But the enemy still moves and sometimes I'd STILL MISS the collision because of this.

So I changed the movement of the enemies, which ended up helping gameplay. Half of enemies move in a frame, half of the other enemies move at the other frame, up until you have just 6 enemies on screen. This made the enemies move faster when you have less enemies (something that was already planned, but I wasn't going to do it this way), so I was ok with it, but I really scratched my head on how hard this was.

Of course on this game specifically I could have used a grid approach since the movement is a lot more restricted (and there was no need to check sprite collision against playfield before checking what was causing the collision, I am pretty sure this just created unnecesary extra overload), but like I said, I was still learning (and still am )

[Retro1234]

Good luck dude I'm sure Daedalus holds the key in his knowledge of Blitz

Also I would say dont move all Bullets at once move them 1 by 1 per game loop or maybe ive totally lost it

[Shatterhand]

This is a test I've made



the blue balls are just bouncing around the screen. They are 3 bitplanes 16x16 bobs, they are blitted every frame and their logic add a value to X and Y and test if they are at the border of screen (if so, invert speed), then blit it on screen. On this test I have a total 16 "blue balls"

the red on the background is time the frame takes to run its logic (plus erasing and blitting all of them on screen, with no background restoring)

the purple on background is the time I waste checking if any of the blue balls colide with *one* sprite (the ship), using the method I showed above

the yellow is how much free time I have in the frame

If I wanted to check against 6 sprites instead of just one, that purple area would be 6 times bigger. This little test alone wouldn't fit on a frame.

I am also baffled of how long it takes to process this simple logic of the enemies + blitting (I should test how much of this is just the blitting), but for now I am just thinking about how to better collision checks

This is running on Winuae, FULL ECS Cycle Exact, 68000 , Cycle Exact CPU Frequency 2X (A500). Not sure how much accurate is this though

[Retro1234]

is it not possible?

*****Main Game Loop****
For I= To Eternity

Joystick stuff
Text Stuff

Move Hero BoB

BulletX[N] BOB + 4 ; **Move Bullett***
IF BulletX[N] = Ship Then Hit
N=N+1
if N=Max Bullet N=1

Wait Blitter


Next I

[Shatterhand]

IF BulletX[N] = Ship Then Hit

You are considering collisions on 1 pixel boundaries, and that's not how it works on games. If you are going to have a hitbox it's 4 checks, not one.

And then you are considering I am testing all bullets against one single "ship", not several ones.

[E-Penguin]

You could check one sprite per frame, but rather than checking just the current position, check the sum of positions since the last check. Create a bounding box based on the vector. That would deal with collisions missed since the last check, although you might see the bullet going through the enemy in some cases.

[Shatterhand]

Originally Posted by E-Penguin

You could check one sprite per frame, but rather than checking just the current position, check the sum of positions since the last check. Create a bounding box based on the vector. That would deal with collisions missed since the last check, although you might see the bullet going through the enemy in some cases.

I thought about this. Maybe not 1 sprite per frame because it's too low, but half of them per frame. It could be good enough, though still a little heavy on the cpu.

[E-Penguin]

You could also do a bit of loop unbundling - test all sprites each iteration. It'll save a good amount of jumps and a comparison each time.

For each bob do
    If (is collision (sprite1) then... 
    Else if (is collision (sprite2) then.. 
   ... 
    Else if (is collision (sprite n) then... 
    End if 
Next

Sprites not in use would need an appropriate flag set to be ignored, but you only have the one loop to contend with.

[Daedalus]

Even coordinates can be unbundled to save some checks - there's no point comparing the Y coordinates if the X coordinates aren't within collision range, for example. Compare the short side of the hitbox first and you'll eliminate more redundant checks.

If you're actually using sprites, there's hardware collision detection available which is more or less for free on real hardware (though it's CPU-intensive to do under emulation) - it's one advantage of using sprites versus blitting.

[Shatterhand]

Originally Posted by Daedalus

Even coordinates can be unbundled to save some checks - there's no point comparing the Y coordinates if the X coordinates aren't within collision range, for example. Compare the short side of the hitbox first and you'll eliminate more redundant checks.

If you're actually using sprites, there's hardware collision detection available which is more or less for free on real hardware (though it's CPU-intensive to do under emulation) - it's one advantage of using sprites versus blitting.

All my hitboxes are perfect 16x16 squares, but of course your suggestion makes sense. If you look at my code, I first check x coordinates and only if they are correct I check y coordinates.

Sprite vs Sprite collision is great and very fast indeed. Unfortunately it's not the case here.. sprite vs Playfield collision only tells me a collision happened, not where did it happen, so you have to do the checks anyway.

Also about sprite X sprite collision, each pair of sprite channels share collision detection too. If you check sprite Channel 0 against, say, sprite 7, a collision between sprite 1 against 6 will return a positive too.

[Retro1234]

Originally Posted by Shatterhand

You are considering collisions on 1 pixel boundaries, and that's not how it works on games. If you are going to have a hitbox it's 4 checks, not one.

I thought this was so obvious I didn't write it, Sorry.

[Daedalus]

Originally Posted by Shatterhand

If you look at my code, I first check x coordinates and only if they are correct I check y coordinates.

Ugh, you're right... Sorry, I completely missed most of the comments on the second page. Time for bed I reckon

[tw1sted1981]

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.

Can you turn the division into a multiplication in this instance and get the same result? I’m assuming if cellsize is always constant it might be doable?


Sent from my iPhone using Tapatalk

[E-Penguin]

I just wrote the dullest game - random bullets bounce around the screen and if one touches the enemy, it dies.

8 bullets (sprites) vs 10 enemies (bob), seems to work fine with collision detection, under standard A500 config (winuae). 16 colours, not that you'd know from my graphics.

Granted, there's no sound or control or anything, but it seems to run fine with "everything vs everything" collision detection, and I'm not using the sprite vs playfield.

Full source attached. It could probably be optimised, I just threw this together to create a test-bench.

One question - how do I get the damned sprites to disappear once I don't want them? If I stop doing DisplaySprite they just stay where I left them...

[Shatterhand]

One question - how do I get the damned sprites to disappear once I don't want them? If I stop doing DisplaySprite they just stay where I left them...

Never figured this out either and it seems there's no way to do it without resorting to ASM (!!!)

My sprite 0 is always just a blank sprite and a draw it on the channel I want the sprite to dissapear.

[Shatterhand]

E-Penguin, just tested your code here. On my Winuae configuration its NOT running on one frame.

I really need to test this on real hardware, I don't trust winuae for those timing tests too much (Even though I know Toni does a hell out of a job with it )

[E-Penguin]

How can you tell its taking longer than a frame? I assumed because the red bar was relatively constant (not flickering between frames) it was all done before each vwait.