English Amiga Board


Go Back   English Amiga Board > Coders > Coders. Language > Coders. Blitz Basic

 
 
Thread Tools
Old 03 June 2018, 07:29   #1
Shatterhand
Warhasneverbeensomuchfun

Shatterhand's Avatar
 
Join Date: Jun 2001
Location: Rio de Janeiro / Brazil
Age: 35
Posts: 2,947
Quickest way to test collisions

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.
Shatterhand is offline  
AdSense AdSense  
Old 03 June 2018, 10:24   #2
MickGyver
Registered User

MickGyver's Avatar
 
Join Date: Oct 2008
Location: Finland
Posts: 264
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.
MickGyver is offline  
Old 03 June 2018, 17:22   #3
E-Penguin
Banana

 
Join Date: Jul 2016
Location: Darmstadt
Posts: 590
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?
E-Penguin is offline  
Old 03 June 2018, 17:37   #4
Shatterhand
Warhasneverbeensomuchfun

Shatterhand's Avatar
 
Join Date: Jun 2001
Location: Rio de Janeiro / Brazil
Age: 35
Posts: 2,947
Quote:
Originally Posted by MickGyver View Post
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 is offline  
Old 03 June 2018, 17:41   #5
Shatterhand
Warhasneverbeensomuchfun

Shatterhand's Avatar
 
Join Date: Jun 2001
Location: Rio de Janeiro / Brazil
Age: 35
Posts: 2,947
Quote:
Originally Posted by E-Penguin View Post

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.
Shatterhand is offline  
Old 03 June 2018, 19:17   #6
Dan
Registered User
Dan's Avatar
 
Join Date: Nov 2004
Location: Germany
Posts: 396
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:
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.

Last edited by Dan; 03 June 2018 at 19:26.
Dan is offline  
Old 03 June 2018, 19:22   #7
Shatterhand
Warhasneverbeensomuchfun

Shatterhand's Avatar
 
Join Date: Jun 2001
Location: Rio de Janeiro / Brazil
Age: 35
Posts: 2,947
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.
Shatterhand is offline  
Old 03 June 2018, 19:27   #8
Retro1234
Bo Bo

Retro1234's Avatar
 
Join Date: Jun 2006
Location: 5150
Posts: 3,912
Can't you just do
If Bullet X,Y = Player X,Y Then Hit ?
Retro1234 is offline  
Old 03 June 2018, 19:29   #9
Dan
Registered User
Dan's Avatar
 
Join Date: Nov 2004
Location: Germany
Posts: 396
Quote:
Originally Posted by Shatterhand View Post
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 ...
Dan is offline  
Old 03 June 2018, 19:32   #10
Retro1234
Bo Bo

Retro1234's Avatar
 
Join Date: Jun 2006
Location: 5150
Posts: 3,912
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.
Retro1234 is offline  
Old 03 June 2018, 19:32   #11
Shatterhand
Warhasneverbeensomuchfun

Shatterhand's Avatar
 
Join Date: Jun 2001
Location: Rio de Janeiro / Brazil
Age: 35
Posts: 2,947
Quote:
Originally Posted by Retro1234 View Post
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
Shatterhand is offline  
Old 03 June 2018, 19:34   #12
Retro1234
Bo Bo

Retro1234's Avatar
 
Join Date: Jun 2006
Location: 5150
Posts: 3,912
If bullet X+0 or If Bullet X+16 or If Bullet Y+0 etc etc
Retro1234 is offline  
Old 03 June 2018, 19:34   #13
E-Penguin
Banana

 
Join Date: Jul 2016
Location: Darmstadt
Posts: 590
Quote:
Originally Posted by Shatterhand View Post
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 :
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.
E-Penguin is offline  
Old 03 June 2018, 19:38   #14
Shatterhand
Warhasneverbeensomuchfun

Shatterhand's Avatar
 
Join Date: Jun 2001
Location: Rio de Janeiro / Brazil
Age: 35
Posts: 2,947
Quote:
Originally Posted by Retro1234 View Post
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.

Quote:
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.

Quote:
Most Amiga games probably use blocking anyway for the Map the Enimies everything.
[/quote]

I have no idea of what you meant here.
Shatterhand is offline  
Old 03 June 2018, 19:38   #15
Retro1234
Bo Bo

Retro1234's Avatar
 
Join Date: Jun 2006
Location: 5150
Posts: 3,912
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.
Retro1234 is offline  
Old 03 June 2018, 19:40   #16
Dan
Registered User
Dan's Avatar
 
Join Date: Nov 2004
Location: Germany
Posts: 396
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

Code:
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 ...

Last edited by Dan; 03 June 2018 at 19:47.
Dan is offline  
Old 03 June 2018, 19:40   #17
Shatterhand
Warhasneverbeensomuchfun

Shatterhand's Avatar
 
Join Date: Jun 2001
Location: Rio de Janeiro / Brazil
Age: 35
Posts: 2,947
Quote:
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.
Shatterhand is offline  
Old 03 June 2018, 19:47   #18
Retro1234
Bo Bo

Retro1234's Avatar
 
Join Date: Jun 2006
Location: 5150
Posts: 3,912
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
Retro1234 is offline  
Old 03 June 2018, 19:56   #19
E-Penguin
Banana

 
Join Date: Jul 2016
Location: Darmstadt
Posts: 590
Quote:
Originally Posted by Retro1234 View Post
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.
E-Penguin is offline  
Old 03 June 2018, 20:02   #20
Retro1234
Bo Bo

Retro1234's Avatar
 
Join Date: Jun 2006
Location: 5150
Posts: 3,912
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.
Retro1234 is offline  
AdSense AdSense  
 


Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools

Similar Threads
Thread Thread Starter Forum Replies Last Post
SetCol/DoColl-How to test collisions with different sprites against different colors? Shatterhand Coders. Blitz Basic 1 12 January 2017 18:51
Quickest code.... Galahad/FLT Coders. Asm / Hardware 10 01 January 2017 17:23
[REQ:ASM] Sprite collisions basics jman Coders. Tutorials 5 03 September 2011 00:07
What is the quickest way Doc Mindie support.WinUAE 6 17 October 2007 21:15
Disable Sprite Collisions DeAdLy_cOoKiE Retrogaming General Discussion 4 24 March 2006 17:56

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT +2. The time now is 20:43.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2018, vBulletin Solutions Inc.
Page generated in 0.10060 seconds with 15 queries