Faster Collisions

BlitzMax Forums/BlitzMax Programming/Faster Collisions

WERDNA(Posted 2010) [#1]
I've noticed the ImagesCollide command, and Especially the
ImagesCollide2 command are pretty darn slow if you have a bunch
of Objects controlled by a For Loop colliding with something.

Is there something that is still relatively close to pixel perfect, but
much more efficient?

What about the CollideImage command, which I 'think' I understand,
but does seem mildly confusing.

Also between the following two scenarios, which would be quicker?

Scenario #1: Bullets and Ships. Both objects are controlled by a
For Eachin loop, and a second For loop testing for collisions between
bullets, and ships, is run inside the bullet loop.

Scenario #2: Global Bullets and Ships. All enemy ships\bullets that
might possibly appear within the game, are declared before hand
as Globals(I.e, Global Bullet1:Bullet = new Bullet, Global Bullet2:Bullet = new Bullet, etc),
and then seperate collision checks are run between each bullet and
enemy. Although a seemingly noob way to set things up, I'm just
wondering what the benefits of this might be. And then everytime
an enemy ship 'died' I would just hold that particular object in reserve
until I needed a new enemy ship to spawn, and simply change it's
stats.

Thanks,

W E R D N A


ima747(Posted 2010) [#2]
You could minimize the number of things you're testing collisions for with some pre-logic along the lines of if object 1 too far from object 2 don't bother, etc. I thing the collision routines do bounding box checking ahead of the pixel detection but if not you could add that as well... IMO simplest method is just to use he expensive routines less frequently, rather than trying to find an alternative as they're already pretty darn good as is.

Depending on the type of game, etc etc. it might be practical to have region groupings where you split the screen or game world into a grid essentially and track what's in what area and only compare collisions for things that are in the same and possibly adjacent areas depending on how you set it up, to handle collisions near edges...


ima747(Posted 2010) [#3]
Another thought: if you could represent your graphics with a vector collision map there might be faster vector collision math...

and the obvious if you can declare their collisions by a circle you just need the distance and the 2 radiuses (radi-i?) to see if they overlap...


skidracer(Posted 2010) [#4]
Using layers with the ResetCollisions/CollideImage commands is an order of magnitude faster than multiple calls to the ImagesCollide commands.

Unfortunately the CollideImage example code only touches on how to best utilize the system.

The following tutorial may be useful even if it incorrectly attributes Mark as the author of BlitzMax's collision system:

http://www.2dgamecreators.com/tutorials/gameprogramming/collision/T2%20Collision.html

Last edited 2010


Czar Flavius(Posted 2010) [#5]
I have never used the built-in collisions!

I just do this

	Method collides:Int(size, location:TVec2)
		size = Max(size, get_size())/2
		Return (location.x + size >= _position.x - size ..
			And location.x - size <= _position.x + size ..
			And location.y + size >= _position.y - size ..
			And location.y - size <= _position.y + size)
	End Method


Where get_size() gives the size of the current object. It does square checking, which isn't pixel perfect, but usually it doesn't matter. Make the size slightly smaller than the object's actual size, and it's harder to notice. In fact it can look better - the bullet will explode slightly into the image, and not just on the outskirts, adding a small bit of depth to the effect.

Last edited 2010


therevills(Posted 2010) [#6]
Sometimes I do this:

if RectsOverlap (x1,y1,w1,h1,x2,y2,w2,h2)
	if ImagesCollide (image1,x1,y1,image2,x2,y2)
		'BOOM!
	end if
end if

...

Function RectsOverlap:Int(x0:Float, y0:Float, w0:Float, h0:Float, x2:Float, y2:Float, w2:Float, h2:Float)
	If x0 > (x2 + w2) Or (x0 + w0) < x2 Then Return False
	If y0 > (y2 + h2) Or (y0 + h0) < y2 Then Return False
	Return True
End Function



So you get the fast rectsOverlap, if that is true then do the pixel perfect command..

Last edited 2010


Jesse(Posted 2010) [#7]
SHMUPS rarely do pixel perfect collision. Most use bounding box detection for collision. it's used on the player ship as well. the box is usually smaller then the image and the player bounding box is a lot smaller than the image itself. Ultimately it is up to the game designer to decide which size bounding box is best for the game. Some instances the object will have more than one bounding box. depending on the shape of the object.
An alternative is to use polygon collision which is faster than pixel perfect collision but still slower than bounding box collision. even Polygon collision is often used along with bounding box collision for speed.

and it really isn't that important to use pixel perfect collision. Realize that most bullet collision move so fast that it won't matter where along the object the bullet hit as long as it hit: disapear the bullet, disappear the ship and create the explosion/effect and that is all there is to it.

Last edited 2010


matibee(Posted 2010) [#8]
Use this or the Pete Rigz module here.


WERDNA(Posted 2010) [#9]
You could minimize the number of things you're testing collisions for with some pre-logic along the lines of if object 1 too far from object 2 don't bother, etc.

I'm already using this one :)

Using layers with the ResetCollisions/CollideImage commands is an order of magnitude faster than multiple calls to the ImagesCollide commands.

Unfortunately the CollideImage example code only touches on how to best utilize the system.

The following tutorial may be useful even if it incorrectly attributes Mark as the author of BlitzMax's collision system:

http://www.2dgamecreators.com/tutorials/gameprogramming/collision/T2%20Collision.html

Thanks skidracer. I'll definitely give this a read. I figured that CollideImage was
faster, but wasn't fully sure how to use it to it's best potential.

Method collides:Int(size, location:TVec2)
size = Max(size, get_size())/2
Return (location.x + size >= _position.x - size ..
And location.x - size <= _position.x + size ..
And location.y + size >= _position.y - size ..
And location.y - size <= _position.y + size)
End Method

Wow Czar this will be perfect!
I did something similar in my RoboAttack3D came, albeit, without the size variable,
so I think this should work out great :)


Lol, Jesse and therevills, both of you have been answering an aweful lot of my questions
lately, and always with good advice to. Major thanks to the both of you ^_^
Although at this point, I think Czar's option
will be the very best ;)

Tis simple, and I like simple, above all other options, as long as it works.

@Matibee
Awesome suggestion. I'll try Czar's first, and see how well that serves my purposes,
but if I want something else, I'll give yours(Or one of the numerous other options ;) a shot.

Thanks a bundle everyone.

This is what I really love about the blitz community. Sure we might fight sometimes,
and some of us(puki) are a tad weird, but there is no better place to come for expert
advice about how to bring out the full potential of the blitz languages.

W E R D N A


Richard Betson(Posted 2010) [#10]
I am using this example as a basis for collision in Phoenix SS. Works good.

http://www.blitzmax.com/codearcs/codearcs.php?code=998

L8r


ImaginaryHuman(Posted 2010) [#11]
You want to at least use some kind of spatial partitioning/acceleration structure even if it's just a grid of rectangles. As objects move and change which cell they're in you detach it from the linked list of the cell it was in and attach it to the linked list of the new cell. Then when you do collision tests you only have to tests against the items in the surrounding cells that are close enough to have a likely collision. This will massively speed up your collision tests. Then perhaps if you find that two items will likely collide, use ImagesCollide or similar to do the pixel-perfect.


Chroma(Posted 2010) [#12]
Nice one Czar. Reminds me that I need to put some collision commands into my sprite module!


WERDNA since your game is a vertical scrolling game you could probably eliminate a lot from the collistion checking by doing a

If bullet.x>ship.x (ship is eliminated, check next ship)

Something along those lines.

Last edited 2010


shinkiro1(Posted 2010) [#13]
Tile your Area in Sections (ex in 4)
Ex: You have 100 Objects which could collide with each other.
100 * 100 = 10000 Checks

When tiling throw 4:
100/4 = 25
(25 * 25) = 625 Check in 1 Area
625 * 4 = 2500 Checks

Although, an Object can be in Multiple Areas too, then the number would be a little higher.
But it helps a lot ;D

Also when 1 of your Objects has checked against each other, remove it from the Checklist. This will cut the number of checks in half (around in half).


Chroma(Posted 2010) [#14]
Good idea shinkiro1. That reminds me of that SceneGraph thing that JoshK did awhile back. That could probably be used and as I recall, his code was lightning fast. I think the thread named was "Let's talk about scenegraphs".

Another idea that just hit me is split the checks up into 2 cycles or even 4 using multiple lists. And when you're making enemies just alternate the list you assign them to. Enemy1 goes to list 1, enemy2 to list 2, enemy3 to list 1, etc etc.

colCheck :+ 1

If colCheck = 4 colCheck = 1

Select colCheck
   Case 1 CheckCollision(player,EnemyList1)
   Case 2 CheckCollision(player,EnemyList2)
   Case 3 CheckCollision(player,EnemyList3)
   Case 4 CheckCollision(player,EnemyList4)
End Select


If you split them up into 4 lists that's all enemy collisions checked every 4 cycles. Which if your logic is set to 100fps, all enemies are checked every .04 seconds.

So let's say you have 1000 objects on screen needing collision checking. You'd be doing 250 collision checks a cycle instead of 1000. In a shooter, I don't think the loss of precision would even be noticeable.

Last edited 2010


dynaman(Posted 2010) [#15]
ImaginaryHuman had the best idea. If each area is exactly the size of the largest sized item then you just need to check with each item in 9 areas (the one it is in and all those in the 8 adjacent areas).

Every time an object is moved you would need to update a list of what is in each area, removing it from the one it was in and adding it to the one it enters. Unless you have a LOT of objects a simple array would probably suffice for it instead though.


WERDNA(Posted 2010) [#16]
WERDNA since your game is a vertical scrolling game you could probably eliminate a lot from the collistion checking by doing a

If bullet.x>ship.x (ship is eliminated, check next ship)

Something along those lines.

I already have that in there :)

I still haven't had a chance yet, with Christmas coming up and everything to try some
of these ideas out. Hopefully I'll have some time this morning.


Thanks everyone!

This will all help out tremendously.


W E R D N A