Fast collision detection

BlitzMax Forums/BlitzMax Beginners Area/Fast collision detection

Farflame

(Posted 2009) [#1]

Which is the 'fast' version of the collision commands? They all say 'pixel accurate collision' in the text, even the CollideRect command and they all seem quite slow. Is there a fast one, or should I make my own function?

therevills

(Posted 2009) [#2]

What I sometimes do is use a fast RectOverlap first then use ImagesCollide:

Function RectsOverlap%(x0, y0, w0, h0, x2, y2, w2, h2)
	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

Also have you had a look at the CollideImage command which adds images to a collision layer?

_Skully

(Posted 2009) [#3]

I use "feelers" that are relative points around the image and test the pixelmap for collisions on those points... seems quite fast

Farflame

(Posted 2009) [#4]

Thanks, looks good :)

therevills

(Posted 2009) [#5]

test the pixelmap for collisions on those points

@Skully, how do you do that? Are you talking about pixmaps?

_Skully

(Posted 2009) [#6]

This is what I am doing...

If PixelNonAlpha(LockImage(i,,,False),x,y)
      ' ...
End iF

Function PixelNonAlpha:Int(p:TPixmap,x:Int,y:Int)
	If ((ReadPixel(p,x,y) Shr 24) & %11111111)>0 Return True
End Function

x,y are points relative to the image centre.. so for an actor I might have a bunch of points depending on the size of the image that surround it. Rather than testing pixel per pixel I test those points which also gives me a collision normal (relative to the image centre) when it finds a non-alpha pixel.

BTW: This is not the way to do it if your colliding with single pixel wide barriers though, since there is error for skipping over the barrier if movement is too fast

_Skully

(Posted 2009) [#7]

BTW: You can also rotate those points around the image along with the global rotation by doing a simple sin/cos calculation (use an array of sin/cos values for speed)

therevills

(Posted 2009) [#8]

Interesting....

Wouldnt your background image always give you a nonalpha colour?

_Skully

(Posted 2009) [#9]

I'm using a multi-level tile system.. collision layer is only one layer (on top of the background)

therevills

(Posted 2009) [#10]

Of course! Doh!

Ive been thinking in the lines of Worms/Lemmings recently and thought that what you were doing...

Normally when I do muti-level tile system I store the collision layer in an array and check the cell, if you dont mind how do you use your PixelNonAlpha with your collision layer?

_Skully

(Posted 2009) [#11]

Do you mean you are storing the images equivalent pixelmap in an array and checking that? That would possibly be faster... maybe I'll test that.

What I have found is that a reading from a pixelmap is fast... since there is no requirement to send the pixelmap back across the bus (as in a write lock) to the gfx card. At one point I had integrated Nate the Great's verlets and used this method to check for verlet collisions against the map and I was running over 400 verlets on my laptop (flowing water)

Here's the actual function that handles collisions:

	Function PixelCollides:Int(T:MapTile,x:Int,y:Int)
		Local tl:TileLayer=t.Layers[1]
		If tl
			Local i:TImage
			If tl.ModifiedImage
				i=tl.ModifiedImage
			ElseIf tl.TileSet
				i=tl.TileSet.Image
				x:+tl.ImageX*currentlevel.TileSizeX
				y:+tl.ImageY*currentlevel.TileSizeY
			EndIf
			If i Return PixelNonAlpha(LockImage(i,,,False),x,y)
		EndIf
	End Function

ImaginaryHuman

(Posted 2009) [#12]

Do you really need to lock image for every single pixel you test? You should probably be doing that once for multiple tests.

_Skully

(Posted 2009) [#13]

A lockimage (read only) just passes the images pixelmap

I don't think it does anything else... in fact I'm not even sure why they call it lockimage, other than for a setting a write-lock flag

Also, the map is made of bits and pieces of many tilesets (as many as the map builder wishes) and to anticipate whether we are on the same image as last time or not... not sure which is quicker.. just getting the pixelmap or testing if we are on the same one or not...