dcsimg
A Flash Developer Resource Site

Results 1 to 13 of 13

Thread: [SHOW] Collision Detection/Geometry Lib

  1. #1
    Senior Member
    Join Date
    May 2006
    Location
    Manhattan
    Posts
    246

    [SHOW] Collision Detection/Geometry Lib

    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:
    Code:
    //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!

  2. #2
    When you know are. Son of Bryce's Avatar
    Join Date
    Aug 2002
    Location
    Los Angeles
    Posts
    839
    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?

  3. #3
    Senior Member
    Join Date
    May 2006
    Location
    Manhattan
    Posts
    246
    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.

  4. #4
    When you know are. Son of Bryce's Avatar
    Join Date
    Aug 2002
    Location
    Los Angeles
    Posts
    839
    This looks great! I'm looking forward to your release of this, sounds incredibly useful.

    Are you developing this for any particular project?

  5. #5
    Senior Member
    Join Date
    May 2006
    Location
    Manhattan
    Posts
    246
    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.

  6. #6
    Senior Member rachil0's Avatar
    Join Date
    Jul 2007
    Location
    Columbus, OH.
    Posts
    465
    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

  7. #7
    M.D. mr_malee's Avatar
    Join Date
    Dec 2002
    Location
    Shelter
    Posts
    4,140
    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

    lather yourself up with soap - soap arcade

  8. #8
    Senior Member
    Join Date
    May 2006
    Location
    Manhattan
    Posts
    246
    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.

  9. #9
    Developer dVyper's Avatar
    Join Date
    Oct 2008
    Location
    UK
    Posts
    168
    Weird, I'm not able to view that page with FF3 (FP10). I'll have to try with my home comp later.

  10. #10
    Senior Member Draxus's Avatar
    Join Date
    Sep 2007
    Location
    Florida
    Posts
    123
    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

  11. #11
    Developer dVyper's Avatar
    Join Date
    Oct 2008
    Location
    UK
    Posts
    168
    Very strange. It only happens in certain pages with F10 content. I'm gonna have to investigate exactly whats going on.

  12. #12
    Developer dVyper's Avatar
    Join Date
    Oct 2008
    Location
    UK
    Posts
    168
    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!?!?

  13. #13
    Senior Member
    Join Date
    May 2006
    Location
    Manhattan
    Posts
    246
    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.

    Code:
     
    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 );
    			
    		}
    		
    		
    		
    	}
    }

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  




Click Here to Expand Forum to Full Width

HTML5 Development Center