[SHOW] Collision Detection/Geometry Lib

[newblack]

Every time I start on a game (which is way more often than when I finish one), I always end up rewriting the game element framework, the geometrical representation of the view, the relationship between the 2, collision detection, etc.

So I wanted to write a geometry library that offers a framework that handles this, as automatically and independently as possible.

My key goals were/are:

• Make collision detection easy
• Make the framework easily usable with or without the DisplayObject hierarchy
• Make the geometry bindable to DisplayObjects and vice versa
• Automatically generate convex geometry based on DisplayObject hierarchy
• Offer simple collision detection queries for use with or without the geometry library

This is a totally lame demo, but it illustrates a few things. Here's what's going on.
I create a couple container DisplayObjects as children to each other to prove transformation working. Then I add a bitmap (a spaceship .png), and 2 shapes. 1 shape, I use the graphics api to draw a triangle, and the other a circle.

So at that point, I've done nothing at all with the library. Then I call Geometrer.createHierarchy and pass the DisplayObjectContainer that holds everything else. This method recurses over all children and populates an array with each container or shape's geometrical counterpart from the library (a triangle, a circle and the convex hull (polygon) of the spaceship graphic).

The demo is drawing all of the strokes (circle, triangle, polygon and AABBs) at the global level. Because the shapes are bound to the DisplayObjects, I'm simply updating the orientation and position of a few of these DisplayObjects each frame and the geometry binds accordingly.

The geometry is determined by drawing each DisplayObject into bitmap data, doing some analysis to find edge pixels, and the convex hull of these points. Then the points are reduced to hopefully find a neat, tidy geometry fit from the library. If not, an algorithm, tries to determine if it's a circle. Otherwise the n-dimensional convex hull is returned.

here's what the code involving the library looks like in the demo:

//maps DisplayObjects to geometrical counterparts
var map:Dictionary = new Dictionary();
			
//holds a list of all constructed shapes
var shapes:Vector.<ITransformable> = new Vector.<ITransformable>();
			
var shapeRoot:ITransformable = Geometrer.createHierarchy( base, shapes, map );

//then i can access a shape/container via the map
var myElement:ITransformable = map[ myDisplayObject ];

fp10 demo:
http://lab.generalrelativity.org/glib/hierarchy/

I'll be releasing everything under the MIT license once the collision detection is built up more. I'm curious in hearing level of interest etc. Thanks!

[Son of Bryce]

This sounds cool but I'd like a little clarification.

It looks like you can detect a collision detection with either the red or blue shapes. And if I understand correctly, this blue shape is drawn automatically dependent on the pixel data of the object. While the red one is a basic bounding box similar to a hitTestObject, based on pixel data as well.

Is that about right?

[newblack]

that's correct. so hopefully the blue shape is what makes this interesting. although, i hope that the unified way of working with geometry is what proves useful.

[Son of Bryce]

This looks great! I'm looking forward to your release of this, sounds incredibly useful.

Are you developing this for any particular project?

[newblack]

thanks!
just for the reason i've listed- i always rewrite this stuff and i think that i've a pretty harmless way of integrating serious geometry.

[rachil0]

I always end up rewriting this kind of stuff for every game too. Another lofty pursuit would be designing the whole shebang so that it can be used with various broad phase culling strategies.

Does it perform sweep tests or static tests? If it's GJK implemented in AS3, wow what a handy program

[mr_malee]

I am interested in something like this.

but more so in the broad phase. Managing many objects across a large area. I really like the idea of automatically declaring geometry, I don't think I have seen that done before

[newblack]

ha, you pretty much summed up the collision detection aspect for the long run. right now it's just a laundry-list of one off static collision queries.

[dVyper]

Weird, I'm not able to view that page with FF3 (FP10). I'll have to try with my home comp later.

[Draxus]

There's gotta be something wrong with your FP or FF installation dVyper. I've seen 3 threads here and the one on kirupa, in which something wasn't working for you but works for me with the same setup and seemingly for everyone else in the thread

[dVyper]

Very strange. It only happens in certain pages with F10 content. I'm gonna have to investigate exactly whats going on.

[dVyper]

No way - it fails on my home computer too!!! Weirdly also, (slightly related) when I view Flash movies on Newgrounds they seem to freeze after a few frames for some reason. Why meeee!?!?

[newblack]

I got a chance yesterday to implement GJK for this library. In the future I'll be adding caching, so that the algorithm can be warm-started with the previously terminating simplex when retesting shapes. And I think I can get around the 2 explicit point-finding calls (closestPointOnLine and closestPointOnTriangle) with simple dot products/half-space queries, which should make it a lot faster. I'll also add a method for finding the distance between shapes, which is a slight variation on test.

Anyway, everything works as expected (polygon/polygon, polygon/circle etc). If you've read anything about GJK, it should be extremely easy to follow along the code/comments.

 
package org.generalrelativity.glib.collisiondetection.fine
{
	
	import __AS3__.vec.Vector;
	
	import flash.display.Graphics;
	import flash.display.Shape;
	
	import org.generalrelativity.glib.Geometrer;
	import org.generalrelativity.glib.geom.shape.BaseShape;
	import org.generalrelativity.glib.math.Vector2D;
	
	
	/**
	 * Implements a separating-axis variation of the Gilbert Johnson Keerthi 
	 * algorithm for testing intersection of convex shapes. 
	 * 
	 * @see http://en.wikipedia.org/wiki/Gilbert-Johnson-Keerthi_distance_algorithm
	 * 
	 * @author Drew Cummins
	 * 
	 * @see IFineCollisionDetector
	 * */
	public class GJK implements IFineCollisionDetector
	{
	
		/**
		 * Miniscule margin for rounding error
		 * */
		private static const EPSILON:Number = 1e-8;	
		
		/**
		 * Maximum iterations allowed before algorithm terminates
		 * */
		private static const MAX_ITERATIONS:int = 25;
		
		/**
		 * Useful static Vector2D reference to origin to pass in vector math operations
		 * */
		private static const ORIGIN:Vector2D = new Vector2D( 0, 0 );
		
		
		
		public function GJK()
		{
		}
		
		
		/**
		 * Tests 2 convex shapes for intersection.
		 * 
		 * @returns true if the shapes are intersecting, false otherwise
		 * */
		public function test( shape1:BaseShape, shape2:BaseShape ) : Boolean
		{
			
			//choose a starting direction
			//should test this- but appears to converge very quickly
			var d:Vector2D = shape1.worldSpacePosition.minus( shape2.worldSpacePosition );
			
			//find max vertex on Minkowski difference
			var V:Vector2D = minkowskiSumInDirection( shape1, shape2, d );
			
			//direction points from single vertex toward origin
			d = new Vector2D( -V.x, -V.y );
			
			
			//initialize the simplex Q
			var Q:Vector.<Vector2D> = Vector.<Vector2D>( [ V ] );
			
			//ensure we don't get an infinite loop, but should never terminate
			for( var i:int = 0; i < MAX_ITERATIONS; i++ )
			{
				
				//find max vertex in support direction, d
				V = minkowskiSumInDirection( shape1, shape2, d );
				
				//if V . d < 0, V is no closer to O than the current simplex, no intersection
				if( V.dot( d ) < 0 ) return false;
				
				//add V to simplex
				Q.push( V );
				
				//update simplex, if origin exists in simplex, return true
				if( updateSimplex( Q, d ) ) 
				{
					return true;
				}
				
			}
			
			return false;
			
		}
		
		
		
		/**
		 * Updates the simplex, <code>ioQ</code> and direction, <code>ioDirection</code>.
		 * 
		 * <p>If the origin exists in (or on) the simplex, the algorithm terminates, returning true.
		 * Otherwise, the simplex is minimized to include only <i>vertices</i> on the Minkowski difference
		 * that contain the point of minimum norm from the origin (a point or line in 2D).</p>
		 * 
		 * <p>Note that both parameters bear the io prefix. This convention denotes a complex data type 
		 * (no pointers in AS3) that is updated from within the alogrithm.</p>
		 * 
		 * @param ioQ 			Simplex to update
		 * @param ioDirection 	Support direction (-[closest point to origin])
		 * */
		private function updateSimplex( ioQ:Vector.<Vector2D>, ioDirection:Vector2D ) : Boolean
		{
			
			//holds the closest point to origin on the simplex
			var P:Vector2D;
			
			//length - 1 of simplex
			var length:int = ioQ.length - 1;
			
			//if both x and y are within a very small range of the origin, shapes intersecting
			if( Math.abs( ioQ[ length ].x ) < EPSILON && 
				Math.abs( ioQ[ length ].y ) < EPSILON ) 	return true;
			
			
			//simplex is triangle (length = simplex.length - 1)
			if( length == 2 )
			{
				
				//find the closest point on the triangle to the origin
				P = Geometrer.closestPointTriangle( ORIGIN, ioQ[ 0 ], ioQ[ 1 ], ioQ[ 2 ] );
				
				//if that point is sufficiently close to the origin, the origin lies in or on
				//the triangle and the shapes are intersecting
				if( Math.abs( P.x ) < EPSILON && 
					Math.abs( P.y ) < EPSILON ) 	return true;
				
				//if the closest point to the origin is one of the triangle's vertices, we can fully represent
				//the simplex as that single point
				if( P.x == ioQ[ 2 ].x && P.y == ioQ[ 2 ].y )
				{
					
					//minimize the set to that point and remove the rest
					ioQ[ 0 ] = ioQ[ 2 ];
					ioQ.splice( 1, 2 );
					
				}
				else
				{
					
					//otherwise the point will lie on the edge [Q0, Q1], minimize to that line segment
					ioQ[ 0 ] = ioQ[ 1 ];
					ioQ[ 1 ] = ioQ[ 2 ];
					
					ioQ.pop();
					
				}
				
				//regardless of simplex dimension, the new direction will point from the closest point on
				//the simplex toward the origin
				ioDirection.x = -P.x;
				ioDirection.y = -P.y;
				
			}
			else
			{
				
				//line scenario
				
				//V is most recent addition to simplex (closest to origin on Minkowski sum)
				
				//define 2 vectors, both pointing from V, 1 to the origin, the other to the previous loop's
				//addition to the simplex. 
				var vo:Vector2D = ioQ[ 1 ].times( -1 );
				var vb:Vector2D = ioQ[ 0 ].minus( ioQ[ 1 ] );
				
				//if vo . vb is > 0, then we need to express the simplex as B and V
				
				//this should be tested as the overhead comes on top of the more likely and expensive situation
				//where we do need to represent the simplex as a segment. the less expensive case (point) can be 
				//solved identically to the segment scenario by checking for equality: P == Q1
				if( vo.dot( vb ) > 0 )
				{
					
					//find the point on line closest to the origin
					P = Geometrer.closestPointLineSegment( ORIGIN, ioQ[ 0 ], ioQ[ 1 ] );
					
					//if that point is sufficiently close to the origin, the origin lies on the line
					//and so the shapes are intersecting
					if( Math.abs( P.x ) < EPSILON && 
						Math.abs( P.y ) < EPSILON ) 	return true;
					
					//direction = -P
					ioDirection.x = -P.x;
					ioDirection.y = -P.y;
					
				}
				else
				{
					
					//recently added vertex closest point to origin on simplex
					ioQ[ 0 ] = ioQ.pop();
					
					//direction = -V
					ioDirection.x = -ioQ[ 0 ].x;
					ioDirection.y = -ioQ[ 0 ].y;
					
				}
				
				
			}
			
			//if the algorithm has come this far, no intersection is found
			return false;
			
		}
		
		
		/**
		 * Finds the maximum vertex on Minkowski sum in the given direction.
		 * 
		 * @see BaseShape#getMaxInDirection
		 * */
		private function minkowskiSumInDirection( shape1:BaseShape, shape2:BaseShape, direction:Vector2D ) : Vector2D
		{
			
			var sa:Vector2D = shape1.getMaxInDirection( direction );
			var sb:Vector2D = shape2.getMaxInDirection( direction.times( -1 ) );
			
			return sa.minus( sb );
			
		}
		
		
		
	}
}