Phil Peron Flash Platform Developer and Game Development Hobbyist

Polygon Collision and the Separating Axis Theorem in ActionScript

I’ve been spending quite a bit of time on my latest game project which, like many other games, requires collision detection. Knowing that using brute force for broad-phase detection wasn’t an option, I implemented a spatial hash to partition the world’s game objects into manageable groups. At this point, I was ready to tackle the narrow-phase portion and immediately sought to use a form of pixel-perfect collision I’ve grown to understand and use fairly well. Unfortunately, this type of detection is inappropriate for a lot of things and an avatar moving along a tile-based set is one of them. It can be fairly costly and is better suited for boolean-based tests. After trying to force this algorithm to do something it shouldn’t, I finally settled down and visited a form of collision I had known about for a while but had not the need to implement…until now.

I’m not going to explain how the Separating Axis Theorem (SAT) works. There are plenty of resources available for that. Instead, I’m simply going to share with you the code that drives it and how you can use it in your own game.

Before we dive in, there’s something you should be aware of:

This code exists because it’s easier for me to prototype new things in ActionScript. That being said, there are certainly opportunities to improve performance and structure but I’m not interested in doing that here. I’ll address those issues and share the result when I port it over to my target platform in C#.

I’ve taken time to try and make things as easy as possible to use. I’m assuming you’re reading this because you need to leverage this functionality and want things to “just work”.

Here it is:

// create a vector of points that express the first polygon.
var points1:Vector.<Point> = new Vector.<Point>();
points1.push(new Point(0, 0));
points1.push(new Point(50, 0));
points1.push(new Point(50, 50));
points1.push(new Point(0, 50));

// create the first polygon, adjust it's registration point and move it.
var polygon1:Polygon = new Polygon(points);
polygon1.offset = new Vector2D(polygon1.center.x, polygon1.center.y);
polygon1.translate(new Vector2D(50, 50));

// create a vector of points that express the second polygon.
var points2:Vector.<Point> = new Vector.<Point>();
points2.push(new Point(0, 0));
points2.push(new Point(100, 0));
points2.push(new Point(100, 100));
points2.push(new Point(0, 100));

// create the second polygon, adjust it's registration point and move it.
var polygon2:Polygon = new Polygon(points);
polygon2.offset = new Vector2D(polygon2.center.x, polygon2.center.y);
polygon2.translate(new Vector2D(200, 200));

At this point, there are two polygons ready to shake, rattle or roll. When you’d like to see whether or not they’re colliding, use the following:

// define a container to hold a translation vector that can be altered by the collision.
var collisionResponseTranslation:Vector2D = new Vector2D();

// finally, discover whether or not a collision has occurred.
if(polygon1.isCollidingWith(polygon2, collisionResponseTranslation))
    polygon1.translate(collisionResponseTranslation);

That’s it! Here’s a demo that illustrates things a little better:

Please keep in mind that this will only work for convex polygons. My game doesn’t merit getting as complex as the folks at Metanet did with N so until it that time, it’s pretty much complete.

You’ll find the demo and library source, here.

Good luck and happy coding!