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.events.Event;
import flash.utils.Timer;
import flash.events.TimerEvent;
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.cacheAsBitmap=true;
	mc.graphics.lineStyle(1);
	mc.graphics.beginFill(Math.random()*0xFFFFFF);
	mc.graphics.drawCircle(0,0,radius);
	mc.graphics.endFill();
	mc.x = c.x;
	mc.y = c.y;
	addChild(mc);
	mcs.push(mc);
}
var t:Timer = new Timer(animationTime*1000,1500);
t.addEventListener(TimerEvent.TIMER,function(e:Event):void{
   addMC();
   arrange();
   });
addMC();
arrange();
t.start()
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;
	numMoved++;
	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)
				TweenLite.to(cur,animationTime,{x:np.x,y:np.y})
			numMoved++;
		}
		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.

One thought on “Simple Circle Packing”

  1. Hi Danny Miller, I saw this example while searching for Circle Packing methods. It clearly explains about how its happening. Do you have any example to pack the different size of circles? Thanks in advance.

Leave a Reply

Your email address will not be published. Required fields are marked *