New module - rigz.collision

BlitzMax Forums/BlitzMax Programming/New module - rigz.collision

Pete Rigz

(Posted 2010) [#1]

I've added a new module to my slowly growing collection - rigz.collision. As well as being able to check for collisions between boxes, circles lines and polys, (plus you can do ray casting), you can also use quadtrees for spatial partitioning.

To get it you can either grab from SVN here: http://subversion.assembla.com/svn/timelinefx-module - checkout into rigz.mod

or download here: http://www.rigzsoft.co.uk/files/rigz.mod.zip (this is compiled for windows, so if you download on the Mac just makemods to recompile it)

Lot's of people can take some credit for this module as I learnt a lot from various tutorials and source code here and on the internet. The whole thing is fully documented with examples, but I'd say it's still a beta at the moment as I'm sure they'll be a few bugs/quirks about :)

Here's a copy and paste of the overview from the docs:

Collision Module with quadtrees for spatial partitioning of boundaries

This module provides a way to check for collisions between boxes, circles, lines and polygons 
(referred to as boundaries throughout to documentation). The option of using a quadtree is also
there to speed up collision checking between large numbers of objects.

Thanks to matibee, Leadwerks and Oddball from the Blitzmax forums, plus the authors of various sites (see docs for links)

The aim of this module was to try as much as possible to combine ease of use with performance. In terms of performance 
it uses a collision checking technique called separating axis theorem, which is quite a common and fast approach to
collision detection, as well as providing an easy way to find out about each collision that happens in order to 
calculate things such as overlap prevention, and rebound vector calculation.

For an example as to how easy the module is to use, to calculate a collision between 2 objects, you can simply use CheckCollisions like so: 

local result:tlCollisionResult=CheckCollisions(SourceObject, TargetObject)

Where source and target objects can be either a tlBox, tlCircle, tlLine or tlPolygon. Once the check is done the results 
of the collision are returned in a tlCollisionResult where you can find out a number of things about the nature of the 
collision. To prevent 2 objects from overlapping you can simply do: 

PreventOverlap(result)

and if a collision occurred then the 2 objects will be separated. See PreventOverlap for more info and an example

Quadtrees are also simple to use, see tlQuadtree for more info and an example.

All boundaries can be placed on one or more layers (up to 32) to help you organise collisions more easily. You can
use the constants tlLAYER_1, tlLAYER_2.. etc. up to 32 or tlLAYER_ALL to place a boundary on all layers. To set a layer 
you can either do it on creation of a boundary ie., with CreateBox, or you can use SetBoundaryLayer. Use GetBoundaryLayer 
to find out the layer of a boudnary.

It's might be worth noting, that whilst function wrappers for most types have been created for extra convienience, you can 
still access the those methods directly in a more OO approach if you wish. Peruse the documentation for the specific methods etc.

Not much in the way of a screen shot but here's an example of using a quadtree to draw a maze (Thanks to impixi from the blitz forums for the TDungeon code in archives found here:
http://www.blitzbasic.com/codearcs/codearcs.php?code=1891 ) and prevent a player from overlapping the walls. Thanks to the quadtree, culling off screen tiles and only checking for collisions in the immediate vicinity is easy and fast.

slenkar

(Posted 2010) [#2]

thanks, very generous

BlitzSupport

(Posted 2010) [#3]

Some good-looking stuff in this module -- thanks!

ErikT

(Posted 2010) [#4]

Thanks a lot, seems like a super-great module!

matibee

(Posted 2010) [#5]

Hi Pete,

I thought I should re-visit http://www.blitzbasic.com/Community/posts.php?topic=85634 one day and polish it up a bit now that I know BMax better, then I saw this and thought I needn't bother now. However I just noticed this today;

Thanks to matibee, Leadwerks and Oddball from the Blitzmax forums, plus the authors of various sites (see docs for links)

Nice one :D

For the latest samples based on my code try; http://www.blitzmonkeys.com/index.php?topic=188.0

Pete Rigz

(Posted 2010) [#6]

Hi matibee, yes I saw your samples on blitzmonkeys, I didn't have any kind of collision response at that point so it was a useful reference, as was the quadtree stuff :)

slenkar

(Posted 2010) [#7]

that platformer example is pro

Htbaa

(Posted 2010) [#8]

I thought I had already replied to this topic. Maybe it was somewhere else?

Anyway, nice module. I can use this :-).

The Caffeine Kid

(Posted 2010) [#9]

I wish I had seen this a week ago. I've been going half mad trying to do some circle/line-segment intersection code. I'm rubbish at math and it took me about a whole day of gibbering before I got something working.

Good stuff! :)

Imphenzia

(Posted 2010) [#10]

This is great :) I'm playing with this module now and it's very easy to implement.

I do have a question though: I create a poly for a midhandled bitmap object, but they don't align with eachother - is centering handled differently?
EDIT: Not a problem anymore!! I had the coordinates wrong :)

Also FYI: drawing the bounding box with a poly doesn't take into consideration the offsetX and offsetY passed along with the poly.draw method.

Pete Rigz

(Posted 2010) [#11]

Glad you like it! The handle of the polygon is set to the middle by averaging all the vertices automatically, but I see you've solved that anyway :)

I have fixed the offset problem and committed the changes via SVN if you can use that? Otherwise I'll upload a new downloadable version soon.

Imphenzia

(Posted 2010) [#12]

I'll grab the SVN version no probs! I also had some issues when scaling the polygon differently in X and Y even though scaling the bitmap the same amount. I'll dig into this further though, could be me again :)

By the way - have you done any performance testing with this system, i.e. how does it compare to the native bitmap collisions?

Pete Rigz

(Posted 2010) [#13]

Hmm, yeh I seem to have muddled the matrices a bit there! I committed a fix on SVN.

I didn't do any direct tests, but then there's no kind of quadtree implementation for the bitmap collisions so it's hard to compare, on top of the other features such as preventing overlap. The main performance test is the maze example (screenshot above) where it's testing for a collision with 30 odd thousand sections of wall (and doing off-screen culling). Using a quadtree means only the immediate sections of wall are tested so each check is under 1ms.

Imphenzia

(Posted 2010) [#14]

I'm still playing around with this and loving it =)

My next observations are:

I) If I fire a bullet with a collision poly into another collision poly it will quite often end up inside the target poly if the angle is quite shallow. When this happens the bullet will bounce around inside the target poly like crazy. I've tried using a circle for the bullet instead with same result. Finally I've also tried making sure that the target is stationary and nonrotating and with high update frequency 100hz, same issue.

2) When you do GetReboundVector, what is the best way to have both objects rebound off eachother if they are both moving?

Pete Rigz

(Posted 2010) [#15]

Do you have any example code of the first problem? This could be a problem called tunnelling where fast moving objects can miss their collision or end up inside stuff, but when you say it happens when the angle is shallow I'd it might be something else.

As for the 2 objects bouncing off each other currently nothing is really implemented yet for this. For that I'd need to introduce mass to objects to correctly calculate that, which I might do at some point, it shouldn't be too hard to implement given that so much of the ground work is done already. But there's only so far I'd want to take it in that direction before you may as well just use a physics engine like box 2d. I'll probably stop at a snooker balls bouncing off each other and leave it there :) The closest you can get at the moment would be something like

object1.velocity=GetReboundVector(collisionresult,object1.velocity)
object2.velocity=GetReboundVector(collisionresult,object2.velocity)

But that won't work if the 2 objects are travelling in similar directions, some kind of physics calculation would be needed to do it properly.

Thanks for putting it through its paces!

Imphenzia

(Posted 2010) [#16]

It must be a combination of the code I use where I have my own little 2D physics with the collision system because if I only use more or less the poly coordinates the problem isn't too frequent.

This example code will demonstrate how some objects slides around the boundary of a target which commonly happens in my little game as well in addition to them actually landing inside the target:

SuperStrict

Import rigz.collision
Import rigz.vector

Graphics 800, 600

Global target:TObj= TObj.Create(300,300,[0.0,120.0,12.0,28.0,42.0,2.0,82.0,0.0,111.0,11.0,133.0,3.0,182.0,12.0,197.0,52.0,189.0,103.0,153.0,130.0,99.0,152.0,82.0,154.0,75.0,161.0,35.0,157.0,10.0,142.0])

While Not KeyDown(KEY_ESCAPE)
	Cls
	Local bullet:TObj = TObj.Create(10,Rand(230,350),[20.0,3.0,25.0,2.0,25.0,5.0,20.0,4.0])
	bullet.setVelocity(Rnd(5,15),Rnd(-1.0,4.0))
	TObj.update()
	TObj.draw()	
	DrawText "Objects: " + CountList(TObj.LObjects),10,10
	DrawText "Press space to rotate target",10,25
	Flip 1
Wend


Type TObj
	Global LObjects:TList = CreateList()
	Field link:TLink
	Field x:Float
	Field y:Float
	Field angle:Float
	Field velocity:tlVector2 = CreateVector2(0,0)
	Field poly:tlPolygon
	
	Function Create:TObj(x:Float, y:Float, verts:Float[])
		Local obj:TObj = New TObj
		obj.x = x
		obj.y = y
		obj.poly = CreatePolygon(x,y,verts)
		obj.link = LObjects.AddLast(obj)
		Return obj
	End Function
	
	Method setVelocity(x:Float, y:Float)
		Self.velocity.x = x
		Self.velocity.y = y
	End Method
	
	Method setAngle(angle:Float)
		Self.angle = angle
		Self.poly.setAngle(angle)
	End Method
	
	Function update()
		For Local obj:TObj = EachIn LObjects
			obj.x:+obj.velocity.x
			obj.y:+obj.velocity.y
			obj.poly.setPosition(obj.x,obj.y)
					
			If obj <> target Then
				Local result:tlCollisionResult = CheckCollision(obj.poly, target.poly)				
				If Not result = Null Then
					PreventOverlap(result)
					obj.velocity = GetReboundVector(result,obj.velocity)
					obj.poly.setAngle(ATan2(obj.velocity.y, obj.velocity.x))
				End If
			Else
				If KeyDown(KEY_SPACE) obj.setAngle(obj.angle+1)
			End If

			If obj.x > GraphicsWidth() Or obj.x < 0 Or obj.y >  GraphicsHeight() Or obj.y < 0 RemoveLink obj.link
		Next
	End Function
	
	Function draw()
		For Local obj:TObj = EachIn LObjects
			obj.poly.draw()
		Next
	End Function
End Type

Pete Rigz

(Posted 2010) [#17]

Ha! how strange is that? Thanks for the sample, it's actually quite a simple solution.

When the system prevents an overlap, it will move the tlPolygon so that it no longer overlaps, therefore you need to update your tObj to reflect this as well. This was essentially causing the result of the overlap prevention to be ignored so on the odd occasion a bullet started to skate round the edge :)

I've updated the documentation to highlight this a bit more. Here's what I put in your sample to fix it:

			If obj <> target Then
				Local result:tlCollisionResult = CheckCollision(obj.poly, target.poly)				
				If Not result = Null Then
					PreventOverlap(result)
					obj.velocity = GetReboundVector(result, obj.velocity)
					obj.poly.setAngle(ATan2(obj.velocity.y, obj.velocity.x))
					obj.x = obj.poly.GetWorldX()
					obj.y = obj.poly.GetWorldY()
				End If
			Else
				If KeyDown(KEY_SPACE) obj.setAngle(obj.angle+1)
			End If