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:
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.
