Category Archives: Algorithms

Simple Circle Packing

I am working on a new game which is was in need of an algorithm to pack characters as close together without touching. Here is a demo of my algorithm:

Get Adobe Flash player

And the code (uses TweenLite)

import flash.display.MovieClip;
import flash.geom.Point;
import flash.utils.Timer;
import com.greensock.TweenLite;

var mcs:Array = [];
var radius:Number = 5;
var c:Point = new Point(stage.stageWidth / 2,stage.stageHeight / 2);
var animationTime:Number = .5;

function addMC(e:Event= null)
	var mc:MovieClip = new MovieClip();
	mc.x = c.x;
	mc.y = c.y;
var t:Timer = new Timer(animationTime*1000,1500);
function arrange()
	var curDistanceAwayFromCenter:Number = radius * 2;
	var numMoved = 0;
	var n:Number = mcs.length;
	// Place the very first circle in the center, as the algorithm won't work for n==1
	mcs[0].x = c.x;
	mcs[0].y = c.y;
	while (numMoved < n)
		/*R*SIN(180/n) = r
		SIN(180/n) = r/R;
		ARCSIN(r/R) = 180/n
		n = 180/ARCSIN(r/R)
		var numberToFit:int = Math.PI/Math.asin(radius/curDistanceAwayFromCenter);
		if (numberToFit > mcs.length-numMoved)
			numberToFit = mcs.length - numMoved;
		for (var j:int = 0; j < numberToFit; j++)
			var cur:MovieClip = mcs[numMoved];
			// ang to center
			var ang:Number = Math.PI * 2 * j / numberToFit;
			var np:Point = new Point();
			np.x = c.x + Math.cos(ang) * curDistanceAwayFromCenter;
			np.y = c.y + Math.sin(ang) * curDistanceAwayFromCenter;
			// this if improves performance a tiny bit, would probably be way more performant if we detected if this was in the "last" circle, if not then we don't need to loop through it anymore
			if (np.x !== cur.x || np.y !== cur.y),animationTime,{x:np.x,y:np.y})
		curDistanceAwayFromCenter +=  radius * 2;


Note that this doesn’t pack circles optimally in a space. That is a much harder problem. I was looking for a solution that would “cluster” the characters.

Auto create polygon AS3

Made a Flash on Wonderfl the other day.

My friend studying for his PhD at Georgia Tech in architecture called me regarding a problem. He said,

“I need to program something to create a polygon from points. Right now, the points are not being drawn in the right order so lines are being overlapped. How do I have the program draw them in the right order?”

So I came up with a theory of how to do it. The idea is that you find the average point between the points, and from that point you find the arc tangent to each of the points and order the points based on their angle to the center. This idea would only work in 2D, but I’m sure there is a general way to do it for all dimensions.

Here is the code written in actionscript. You can click to add a point and ctrl+click to delete a point. I put it on wonderfl because I am thinking some people could fork some more interesting things from it.

Auto create Polygon – wonderfl build flash online

Superfast Base64 Actionscript Library

So I was using this Base64 Actionscript class for Base64 encoding/decoding a byte array while working on my cofounded project The Base64 class is by Jean-Philippe Auclair, and according to his own benchmarks, runs about 700% faster than Adobe’s own Base64. He has a nice explanation of how he made some improvements, and considering it was high up on Google’s search results for Base64, I started using it.

That is until I came across another Base64 Actionscript library over at Valentin Simonov’s blog.

BlooDHounD’s Crypt class turns out to be even faster than Jean’s class – about 17 times faster. The code for BlooDHounD’s class is unavailable (only a SWC is given). I imagine the library was written in C/C++ and exported to a SWC using Adobe Alchemy considering the speed improvements (alchemy applications can run way faster than AS3 native code).


For my experimental digital art class at Georgia Tech, I created this toy I call SoundPen. It’s a very basic version obviously (although I think some cool things could come from this idea).

The basic idea is to create music by clicking your mouse and placing balls that will bounce of the screen. There are 3 different types of balls (click and press either A, S, or D).

I used Jeff Swartz’s algorithm to change pitch of the sounds from the vertical balls. The more left the ball is on the screen the lower the pitch while the more right on the screen the higher the pitch.

Please be careful when using. If you place too many balls your computer might slow down rapidly. If you want to remove the last ball just press the backspace.

There are probably ways I could have fixed that problem (for example, using lower level PixelBender capabilities to process the sound); however, I don’t think it matters too much. You don’t want to put too many balls anyway because you’ll just hear noise.

(Be sure you have Flash 10!)

Picture of Pictures

For my Experimental Digital Media class at Georgia Tech.

Click here to view
(Must have Flash Player 10)

The Internet has provided a new means of data expression. I decided to play with the idea of machine aesthetics by developing an application that creates images of images.

I first saw this effect a long time ago on a poster advertisement for the Truman show. I always wondered how they made the effect of compiling images together to form, when looked at a certain distance, an image.  The program I made this week creates the effect by downloading Flickr images.

The algorithm is very straightforward (I also mention some ideas for expansion on the Flash). Basically the program downloads Flickr images either by the most recent, based on a search term, or from a username’s public photos via the as3flickrlib. While downloading, the application calculates and caches each photos average RGB color average (the main reason why my algorithm is fast). The program, based on the user’s supplied number of rows and columns, calculates the average RGB color of each divided cell and finds the image with the average color that has the closest 3D distance to the cell’s average color. The effect is pretty cool. I offer the ability to have a very high resolution (which basically expands the original image before running the algorithm to near the max of Flash Player 10’s bitmapData’s limit). The picture effect is  best seen with the highest resolution.

Lastly, thanks to Flash Player 10, saving images is added. I use the JPGEncoder from as3corelib. Unfortunately, the JPGEncoder was too slow as its algorithm is synchronous. Upon Googling “Asynchronous JPG Encoder,” I found a cool Asynchrnous JPG Encoder class by While I have crtiticisms on the class’s asynchronous technique choice, the class does what it says it does.

Anyway, if there is enough support, I may release the class as open source on Google Code. I think there are a lot of ways to alter the algorithm to produce different kinds of image results.

Jacobi Algorithm in AS3

Recently, my “Calculus for Computer Science” teacher assigned the following problem.

So to complete this assignment, I decided to use Actionscript 3 and Flash. A friend of mine and I at Georgia Tech are developing a complex open source matrix library called as3matrix, and we were planning on implementing Jacobi to find eigenvectors of a MxM matrix anyway, so we decided to just apply it to our library.

The Jacobi algorithm is pretty straight forward. It’s impossible to use a formula to find the eigenvalues of a matrix larger than 5×5 because there is no equation solver for equations to that degree. So let’s say you have an 6×6 matrix. To find the eigenvectors, the Jacobi algorithm creates a smaller 2×2 matrix inside that matrix, diagonlizes that, then reapplies it to the matrix.

So what the program I turned in does, is generates a random 5×5 matrix. The program then begins to diagnolize the Matrix using the Jacobi algorithm. Then the program attempts to try diagnolizing the Matrix using the Jacobi method but this time ignoring sorting to solve the 2×2. Obviously, sorting is much faster since it ensures the 2×2 can be diagnolized (since the corner entries will be the largest absolute value of the matrix).

So anyway, here’s how the process works in our as3Matrix library. The jacobi() method computes one interation, while diagonalize() continues the jacobi method until the Off (the sum of the square of off-diagonal elements) is less than 1e-10.

First, take the matrix A. Find the i,j element in the matrix that have the largest absolute value. Create a 2×2 matrix from the i,j elements where a = i,i ; b = i,j ; c = j,i ; d = j,j . This step was probably the hardest part because I kept mixing up the i’s and j’s! Quite annoying when you accidently flip them…

Next, take that 2×2 matrix and diagonalize it. The formula for the eigenvalues that the library uses for 2×2 matrices is:

var L1:Number = ( (a+d)/2 ) + Math.sqrt( 4*b*c + ((a-d)*(a-d)))/2;
var L2:Number = ( (a+d)/2 ) – Math.sqrt( 4*b*c + ((a-d)*(a-d)))/2;

For the eigenvectors, I use a nice trick found by Harvard professor Oliver Knill. I then normalize (which is something Oliver’s page fails to mention) the eigenvectors. Combining the eigenvectors to {u1,u2}, I now have my matrix U.I take that matrix and embed it into the identity (of size of the original, original matrix).  I call that matrix G. Then D is Transpose(G)*A*G.

Then outside of the method I check if the Off(D) is < 1e-10. If so, then I consider the Matrix diagonalized!

Here are the results of Jacobi (with sorting) vs Theoretical Bound and Jacobi (without sorting) vs Theoretical Bound. Since AS3 doesn’t have an LN function, I just used the change of base formula (log(X)/log(2)). I hard coded log(2) to optimize the code.

A couple of random 5×5 matrix sample:

After running 100 random 5×5 symmetric matrics through the Jacobi algorithms, these were the average number of iterations for each:

Average Sorting = 25.11
Average no Sorting = 102.94

Sorting is clearly the best method.

Anyway, you can browse/download the as3matrix library here. Check out the in the trunk.