SAT for Monkey

Monkey Forums/User Modules/SAT for Monkey

FelipeA

(Posted 2014) [#1]

Hello everyone,

I want to share with you this module I just released which is based on SAT.js, a library I've been using for a while. I wanted to have a cross-platform solution for this and I didn't want to depend on a engine to handle my collisions.

It's still a work in progress but I think this version is pretty stable.

Here is the link for the repo:

https://github.com/ilovepixel/sat-monkey

Here are some examples of how to use it:

Circle to Circle test
Result

Strict

Import mojo
Import sat

Class CircleToCircle Extends App
	Field circle1:Circle
	Field circle2:Circle
	Field response:Response
	Method OnCreate:Int()
		circle1 = New Circle(New Vector(160, 120), 30)
		circle2 = New Circle(New Vector(30, 30), 10)
		response = New Response()
		SetUpdateRate(60)
		Return 0
	End
	
	Method OnUpdate:Int()
		circle1.position.Copy(MouseX(), MouseY())
		If (SAT.TestCircleCircle(circle1, circle2, response))
			circle2.position.Add(response.overlapV)
		Endif
		response.Clear()
		Return 0
	End
	
	Method OnRender:Int()
		Cls()
		circle1.DebugDraw()
		circle2.DebugDraw()
		Return 0
	End
End

Function Main:Int ()
	New CircleToCircle()
	Return 0
End

Circle to Polygon test
Result

Strict

Import mojo
Import sat

Class CircleToPolygon Extends App
	Field circle:Circle
	Field polygon:Polygon
	Field response:Response
	Method OnCreate:Int()
		polygon = New Polygon(New Vector(160, 120), New VecStack([
			New Vector(0,0), New Vector(60, 0), New Vector(100, 40), New Vector(60, 80), New Vector(0, 80)]))
		circle = New Circle(New Vector(300, 300), 20)
		response = New Response()
		polygon.Translate(-30, -40)
		SetUpdateRate(60)
		Return 0
	End
	
	Method OnUpdate:Int()
		circle.position.Copy(MouseX(), MouseY())
		polygon.Rotate(1)
		If (SAT.TestCirclePolygon(circle, polygon, response))
			polygon.position.Add(response.overlapV)
		Endif
		response.Clear()
		Return 0
	End
	
	Method OnRender:Int()
		Cls()
		circle.DebugDraw()
		polygon.DebugDraw()
		Return 0
	End
End

Function Main:Int ()
	New CircleToPolygon()
	Return 0
End

Polygon to Polygon test
Result

Strict

Import mojo
Import sat

Class PolygonToPolygon Extends App
	Field polygon1:Polygon
	Field polygon2:Polygon
	Field response:Response
	Method OnCreate:Int()
		polygon1 = New Polygon(New Vector(160, 120), New VecStack([
			New Vector(0,0), New Vector(60, 0), New Vector(100, 40), New Vector(60, 80), New Vector(0, 80)]))
		polygon2 = New Polygon(New Vector(10, 10), New VecStack([
			New Vector(0, 0), New Vector(30, 0), New Vector(30, 30), New Vector(0, 30)]))
		response = New Response()
		polygon2.Translate(-15, -15)
		SetUpdateRate(60)
		Return 0
	End
	
	Method OnUpdate:Int()
		polygon2.position.Copy(MouseX(), MouseY())
		If (SAT.TestPolygonPolygon(polygon2, polygon1, response))
			polygon1.position.Add(response.overlapV)
		Endif
		polygon2.Rotate(1)
		response.Clear()
		Return 0
	End
	
	Method OnRender:Int()
		Cls()
		polygon1.DebugDraw()
		polygon2.DebugDraw()
		Return 0
	End
End

Function Main:Int ()
	New PolygonToPolygon()
	Return 0
End

Cheers,
Felipe

Raph	(Posted 2014) [#2]

Nice!

ziggy

(Posted 2014) [#3]

Yes, this looks very nice!

FelipeA

(Posted 2014) [#4]

Thanks!
I've added a new demo
It can be viewed here: http://dev.shin.cl/sat-monkey/demo/

I am also working on building a quadtree module that could be used with this module.

AdamRedwoods

(Posted 2014) [#5]

nice job. even though monkey box2d is excellent, i think this community needs a good collision module when you don't need all the extras.
i'll be interested in seeing the benchmarks.

SLotman

(Posted 2014) [#6]

Hmmm...? All your demos just appear to me as a black screen in Firefox :(

Ran it on Chrome... whoa! Very nice!! Downloading it now :)

FelipeA

(Posted 2014) [#7]

@SLotman In what version of firefox did you test the demos?

Raz	(Posted 2014) [#8]

Crumbs, that's impressive stuff!

SLotman

(Posted 2014) [#9]

@ilovepixel: Firefox 27.0.1

AdamRedwoods

(Posted 2014) [#10]

@ilovepixel: Firefox 27.0.1

27.0.1 is what i have and worked ok here.

Sammy

(Posted 2014) [#11]

FF worked OK for me too?

Nice work Felipe, well done!

FelipeA

(Posted 2014) [#12]

Thanks!

As I mentioned before I started working on a quadtree module that could go along with the SAT module. Here is what I got so far. Sadly is not performant enough to be released but it's working as expected. Now comes the optimization!

http://dev.shin.cl/sat-monkey/quadtree/

Cheers

Sammy

(Posted 2014) [#13]

Again, very nice work, this should make much larger amounts of bodies to co-exist in the play-field without it killing the frame-rate. A feature that SAT.js does not provide IIRC?

FelipeA

(Posted 2014) [#14]

@Sammy Yes this would help a lot. The current SAT.js implementation doesn't have this and I've also added getting the bounding box of polygons and circles which helps a bit with the quad tree implementation. I don't want to force the use of this so it will be kept inside the module directory but it will be up to the developer to use it or not.
Here is a more evident comparison of the use of quadtrees with the sat module:
http://dev.shin.cl/sat-monkey/quadtree/compare/
Just press space to turn on and off the quadtree.
I think I am almost done with it, so I could be able tu push it to the repo very soon.

FelipeA

(Posted 2014) [#15]

Update!

I've added the QuadTree implementation to the SAT module. You can compare performance between using it and not in this link:
http://dev.shin.cl/sat-monkey/quadtree/compare/

The source for this example can be found on the example folder.

Cheers,
Felipe

Sammy

(Posted 2014) [#16]

The QuadTree is making a big difference to the processing speed, 30-40% quicker with the QuadTree on on my setup. Well done again, Felipe! :)

Raz	(Posted 2014) [#17]

That's really chuffin cool :)

Raz	(Posted 2014) [#18]

ilovepixel: If you don't mind, I'm wondering what you would suggest as the most elegant way is to manage interactions between objects.

I've got a class TActiveObject which all in game items extend. These items have a Polygon field and I'd like to use a Quadtree to check for overlaps and then have the objects response based on the object types using a method ReactToObject(ob:TActiveObject) (e.g. Bullet is overlapping Enemy, destroy Bullet, reduce enemy health by 1)

Quadtree code I'd like to use

Local t:Polygon
			For Local i:Int = 0 To pool.Length() - 1
				t = pool.Get(i)
				quadTree.Insert(t)
				returnObjects = quadTree.Retrieve(t)
				For Local j:Int = 0 To returnObjects.Length() - 1
					p = Polygon(returnObjects.Get(j))
					If (t <> p And SAT.TestPolygonPolygon(t, p, response))
						If (p <> poly1) p.position.Add(response.overlapV)
						If (t <> poly1) t.position.Sub(response.overlapV)
					Endif
					response.Clear()
				Next
				
				t.DebugDraw()
				response.Clear()
			Next

I hope that makes some sense! :)

Ta
-Chris

Example of TActiveObject class

Class TActiveObject

  Method ReactToObject:Void(ob:TActiveObject)

    Select ob.type
    Case OB_COIN
      ReactToCoin(Coin(ob))
    Case OB_BULLET
      ReactToBullet(Bullet(ob))
    End

  End

End

FelipeA

(Posted 2014) [#19]

What you could do is implementing iSAT into TActiveObject

That would make it look like:

Class TActiveObject Implements iSAT

  Method ReactToObject:Void(ob:TActiveObject)

    Select ob.type
    Case OB_COIN
      ReactToCoin(Coin(ob))
    Case OB_BULLET
      ReactToBullet(Bullet(ob))
    End

  End

  Method GetBounds:Box ()
  	Return Self.polygon.GetBounds() ' Or the name of the polygon field
  End

  Method DebugDraw:Void ()
  	' You can do nothing here if you want
  End

  Method GetPosition:Vector ()
    Return Self.polygon.GetPosition()
  End

  Method SetPosition:Void (x:Float, y:Float)
   	Self.polygon.SetPosition(x, y)
  End

  Method SetPosition:Void (vec:Vector)
  	Self.polygon.SetPosition(vec)
  End

  Method GetType:Int ()
  	Return POLYGON ' it could also be 0 which is the id for polygon
  End

End

Then what you can do in pseudo - code is something like this:

Main Game Loop
	QuadTree.Clear() <-- Allways Clear the Quadtree before adding again
	Loop Through all TActiveObjects
		QuadTree.Insert( TActiveObjects[i] ) <-- It will accept only Objects which implement iSAT
	End Loop
End Main Game Loop

----

ObjectX:TActiveObject <-- The one you one to test
On ObjectX Update
	ObjectsOnQuadrant:iSAT = QuadTree.Retrieve( ObjectX )
	If ObjectX is Active
		Loop Through ObjectsOnQuadrant
			If TActiveObject( ObjectsOnQuadrant[i] ) <> ObjectX <-- Check they are not the same
				If SAT.TestPolygonPolygon ( ObjectX.polygon, TActiveObject(ObejectOnQuadrant[i]).polygon )
					ObjectX.ReactToObject( ObjectsOnQuadrant[i] )
				End If
			End If
		End Loop
	End If
End ObjectX Update

I hope this helps :)

Cheers,
Felipe

Raz	(Posted 2014) [#20]

That more than helps, thank you very much :)