Home > blogging, Evolutionary Computation, Projects > Collision detection in Adobe Actionscript 3 (on a large scale)

Collision detection in Adobe Actionscript 3 (on a large scale)

It’s been a few weeks since I last worked on my VisGA, but I finally got some time this weekend. I was able to derive a relatively efficient collision detection scheme for path finding. Computational efficiency is a must with VisGA as cpu time and memory allocation are the two largest concerns for wide distribution of a flex/AC3 web app. The issue with actionscript is not that there are no methods for doing collision detection. Instead collision detection on multiple objects (10-100) which must be tested for each non-deterministically generated path between point A and point B can lead to serious computational overhead given adobe’s native collision testing methods.

For standard graphics objects, Actionscript provides two primary means of testing collisions.

First is the .hitTestObject – which allows you to compare a given graphics object, testSprite, to a point, testPoint, as in:

testSprite.hitTestPoint(testPoint)

My application needs to determine whether or not a line being drawn between two points (divided into N Manhattan segments) collides with an obstacle while trying to reach the destination point using non-deterministically selected heuristic driven path finding. Each segment must be tested as it is non-deterministically built to ensure that it does not collide with any previously placed obstacles. Using hitTestPoint would require P*M tests to be made for collision where P is the number of pixels between the “from” and “to” points on the segment and M is the number of obstacles to compare against. For anything but trivial cases this balloons very quickly for even a single segment if P or M is large. Considering there are N segments and L lines where L is the number of total start-end point pairs in the population, this is an exponentially large problem – just to collision test.

A much better option is the .hitTestObject – which allows you to compare a given sprite, mySprite (the segment in question), to another graphics object, testSprite. as in:

mySprite.hitTestObject(testSprite)

Using hitTestObject, I would need to do, at minimum, N*L hitTests and then further determine where exactly the collision is using boundary comparisons, so the total complexity would be 2N*L tests. While this is better it is still not ideal – ideally I would only need to do L computations with something like hitTestALL (which unfortunately doesn’t exist and is very non-trivial to implement).

I tinkered with ways to combine obstacle sprites into a sort of master sprite – but this causes the master sprite boundary box to be the smallest box which can surround all sprites rather than an irregular boundary box that only includes the component boundary box pixels. There is a work around for this by defining a custom boundary box – but this introduces other more difficult problems – such as where to go to when there is a collision (rectangular graphics objects provides a number of helpful points).

My ultimate thesis is a) Adobe should provide better collision detection for large numbers of items and b) the best way I’ve found to implement multiple collision testing and pathfinding is a complicated interplay of hitTestObject, iterated over all objects to be tested, boundary checking based on heuristics (such as knowing where you are coming from and testing only those sides of objects which may be in the path of such a vector), and finally optimized pathfinding logical heuristics that reduces the “internal loops” that can occur using non-deterministic pathfinding techniques.

Below is the core collision testing method for an array of obstacle items and a test_line generated from a “from” and “to” point using the graphics.drawPath method. It returns all obstacles that collide with the given line, subsequent analysis of exactly where the collision occurs and the logic used for routing around it is performed by the pathfinding algorithm:

protected function obstacle_collision(from:Point,to:Point):Array{
 //checks for collision of the line formed between the two points "from" and "to" with all obstacles

 var collision_array:Array = new Array();
 var test_line:Line = new Line();
 var test_line_sprite:Sprite = new Sprite();
 test_line.commands.push(1,2);
 test_line.coords.push(from.x,from.y,to.x,to.y);
 test_line_sprite.graphics.drawPath(test_line.commands,test_line.coords);

 //iterate through all obstacles and check for collision
 for(var i:Number = 0;i < obstacles.length; i++){
       if(obstacles[i].hitTestObject(test_line_sprite)){
            collision_array.push(obstacles[i]);
       }
 }
 return collision_array;
}

Hopefully this has clarified some nuanced issues regarding large scale collision testing. In my research I couldn’t find a simpler, more efficient way to do this. If you come across something better – let me know, otherwise feel free to reuse anything here for your purposes.

Cheers!

P.S. you can see the pathfinding in action in my latest version of VisGA available at: http://personal.utulsa.edu/~matt-hale/vis-ga/GA.html

About these ads
  1. March 13, 2012 at 2:00 am

    I have had an online magazine for 3 years, and we are looking to spice up the website. We’ve used Joomla, but are now looking for something new. Is WordPress better than Joomla? We will be adding content rich items on the site: videos, etc. Any suggestions?.

    • April 4, 2012 at 12:46 am

      WordPress is pretty awesome in my opinion. A massive collection of existing plugins make it really truly extensible. Adding content is really simple as well. Although i would suggest an actual server wordpress install over the free version.

  1. April 4, 2011 at 1:53 am

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 64 other followers

%d bloggers like this: