Optimising a loop...

Report · May 22, 2011

I'm trying to create a random square every frame of an animation.

The trick is, this square isn't allowed to overlap any other squares currently on the stage.

I've got code that works all fine and dandy but... after a few hundered squares it slows right down.

There must be a way to optimise this, at the moment I've go a while loop telling checking the random squares position against all the others already on the page. If it doesn't intersect, it draws it and carries onto the next frame.

After a few thousand attempts, it makes the max and minimum size the square can be smaller, to give it a better chance of fitting in the gaps.

And then continues getting smaller after multiple thousand more attempts.

Here's my code...

var squares:Sprite = new Sprite; addChild(squares); var squares_arry:Array = new Array; var aSquare:Array; var attempts:int = 0; var limit:int = 1000; var maxSize:int = 80; var minSize:int = 20; aSquare = new Array(int(stage.stageWidth*Math.random()), int(stage.stageHeight*Math.random()), int(Math.random()*maxSize+minSize)); squares_arry.push(aSquare); squares.graphics.beginFill(0); squares.graphics.drawRect(aSquare[0], aSquare[1], aSquare[2], aSquare[2]); squares.graphics.endFill(); addEventListener(Event.ENTER_FRAME, drawSquare); function drawSquare(e:Event):void{ if (attempts > limit){ maxSize = Math.max(maxSize/1.3, 4); minSize = Math.max(minSize/1.6, 2); limit = limit*3; trace ("limit = " + limit + " | min = " + minSize + " | max = " + maxSize); } do{ aSquare = new Array(int(stage.stageWidth*Math.random()), int(stage.stageHeight*Math.random()), int(Math.random()*maxSize+minSize)); attempts ++; } while (! spaceClear()); squares_arry.push(aSquare); squares.graphics.beginFill(0); squares.graphics.drawRect(aSquare[0], aSquare[1], aSquare[2], aSquare[2]); squares.graphics.endFill(); } function spaceClear():Boolean{ var clr:Boolean = true; for (var i:int = 0; i<squares_arry.length; i++){ if (!checkSpot(aSquare, squares_arry)){ clr=false; break; } } if (clr) return(true); else return(false); } function checkSpot(s1, s2):Boolean{ var ss0:int = Math.abs(s1[0] - s2[0]); var ss1:int = Math.abs(s1[1] - s2[1]); if (ss0 > s1[2] && ss0 > s2[2]){ return (true); } else if (ss1 > s1[2] && ss1 > s2[2]){ return (true); } else{ return (false); } }

Report · May 22, 2011

Ok, and which is more efficient, does anyone know?

Using an arrays array, where each item is an array with a length of 3.

(so [0] would be the value for xPos, [1] would be the yPos value and [2] wuld be the size value)

Using an array where, each item has 3 names pieces of information.

(ie. xPos, yPos, size)

My original code uses the former.

Here is my code using the latter...

var squares:Sprite = new Sprite; addChild(squares); var squares_arry:Array = new Array; var aSquare:Array; var attempts:int = 0; var limit:int = 1000; var maxSize:int = 80; var minSize:int = 20; aSquare = new Array(int(stage.stageWidth*Math.random()), int(stage.stageHeight*Math.random()), int(Math.random()*maxSize+minSize)); squares_arry.push({xx: aSquare[0], yy:aSquare[1], sz:aSquare[2]}); squares.graphics.beginFill(0); squares.graphics.drawRect(aSquare[0], aSquare[1], aSquare[2], aSquare[2]); squares.graphics.endFill(); addEventListener(Event.ENTER_FRAME, drawSquare); function drawSquare(e:Event):void{ if (attempts > limit){ maxSize = Math.max(maxSize/1.3, 4); minSize = Math.max(minSize/1.6, 2); limit = limit*3; trace ("limit = " + limit + " | min = " + minSize + " | max = " + maxSize); } do{ aSquare = new Array(int(stage.stageWidth*Math.random()), int(stage.stageHeight*Math.random()), int(Math.random()*maxSize+minSize)); attempts ++; } while (! spaceClear()); squares_arry.push({xx: aSquare[0], yy:aSquare[1], sz:aSquare[2]}); squares.graphics.beginFill(0); squares.graphics.drawRect(aSquare[0], aSquare[1], aSquare[2], aSquare[2]); squares.graphics.endFill(); } function spaceClear():Boolean{ var clr:Boolean = true; for (var i:int = 0; i<squares_arry.length; i++){ if (!checkSpot(aSquare, squares_arry)){ clr=false; break; } } if (clr) return(true); else return(false); } function checkSpot(s1, s2):Boolean{ var ss0:int = Math.abs(s1[0] - s2.xx); var ss1:int = Math.abs(s1[1] - s2.yy); if (ss0 > s1[2] && ss0 > s2.sz){ return (true); } else if (ss1 > s1[2] && ss1 > s2.sz){ return (true); } else{ return (false); } }

Report · May 22, 2011

Do you want to generate squares indefinitely or there is limit of 1000? If there is a limit - remove ENTER_FRAME listener after 1000 squares are generated. If you aim at indefinite number - Flash will chock no matter what you do.

Report · May 22, 2011

Also, depending on stage dimensions, at some point you will run out of available real estate - there is not going to be enough free pixels. It feels like you need to revise the algorithm.

Report · May 22, 2011

I realise I need to revise my algorithm, I was asking if there were any ideas on how to do so

I want it to keep creating squares for as long as possible, with as little overhead as possible.

I realise it will choke at some point, but at the moment, it comes to a stand-still at around half of the stage real-estate, which seems a little early.

Like I said, pretty soon the squares being created are rather small, and Flash still often can't seem to find a space to put them in.

Did you attempt to try the code?

Here's how it publishes, with some debugging text in the top left...

http://www.x1.ltd.uk/brooks_website/flashstuff/squares/squares2.html

I'm not asking for code, just trying for suggestions of better methods to do what I'm doing, but get it to last longer... make more squares before giving up.

Thanks,

Brook.

Report · May 22, 2011

I did try your code and it crashes my player. I am pretty sure this is due to indefinite loop code falls into eventually. This simple experiment (code below) demonstrates that 1000 squares practically fill entire stage very quickly.

I realize that the main challenge is to find available space on each iteration. Frankly, although I see some ways to do that, I am not sure about which way would be most efficient yet.

var maxSide:Number = 50;
var minSide:Number = 10;
var limit:int = 1000;
var squares:Array = [];
addEventListener(Event.ENTER_FRAME, spawnSquare);

function spawnSquare(e:Event):void {
     var s:Shape = square();
     s.x = int(stage.stageWidth * Math.random());
     s.y = int(stage.stageHeight * Math.random());
     addChild(s);
     squares.push(s);
     if(squares.length >= limit) removeEventListener(Event.ENTER_FRAME, spawnSquare);     
}
          
function square():Shape {
     var side:int = minSide + (maxSide - minSide) * Math.random();
     var s:Shape = new Shape();
     s.graphics.beginFill(Math.random() * 0xFFFFFF);
     s.graphics.drawRect(0, 0, side, side);     
     return s;
}

Report · May 22, 2011

My code seems to create up to about 700 before giving up on a much larger canvas.

Here's a screen shot. Looking in the top left shows how it's taken about 13 million attempts to create only 700 squares... And it's struggling to fit squares of a maximum size of 6 pixels wide into the stage.

If you could suggest a few of the methods you're thinking of I would love to give them a try and see if they beat my idea

Thanks,

Brook.

Report · May 22, 2011

Do the squares really need to be display objects? Why not make a bitmap canvas and then use the bitmapData fillRect or draw methods.

Report · May 22, 2011

Actually... I didn't know flash could use bitmap.

I'll play around with that

But, I don't think that will help with the algorithm in this case.

... Does sounds more efficient for overall display though.

I'm quite new to flash and algorithms, but I'm enjoying what I'm learning.

Report · May 22, 2011

You should be able to make the squares in a smilar way without the overhead of thousands of display objects via fillRect:

import flash.display.Bitmap;

import flash.display.BitmapData;

import flash.geom.Rectangle;

//A white 400x400 pixel canvas

var myBitmapData:BitmapData = new BitmapData(400, 400, false, 0xFFFFFF);

var bm:Bitmap = new Bitmap(myBitmapData);

addChild(bm);

var sc:uint=0x000000;

//coordinate object

var o:Object=new Object();

o.x=100; o.y=100; o.w=30; o.h=50;

//fill a rect

myBitmapData.fillRect(new Rectangle(o.x, o.y, o.w, o.h), sc);

o.x=150; o.y=200; o.w=20; o.h=20;

//another fill

myBitmapData.fillRect(new Rectangle(o.x, o.y, o.w, o.h), sc);

There's also getPixel, which returns the color of a pixel at any x, y, so maybe you could randomly check a pixel and if it's white, check to the left and right and up and down until you hit black, which would give you a rectangle of white to add a randomly sized black fill.

Report · May 22, 2011

Using BitmapData is a great idea but the challenge to find available pixels still remains. Especially it is challenging from the perspective of randomness.

Perhaps, getColorBoundsRect() method may work.

Message was edited by: Andrei1

Report · May 22, 2011

Here is BitmapData based solution. So far it works with 1000 squares without a glitch:

var canvas:Bitmap;
var bmd:BitmapData;
var min:int = 2;
var max:int = 80;
var limit:int = 1000;
var squares:Array = [];
// declare once to lighten functions
var point:Point;
var r:Rectangle;
var tbmd:BitmapData;
var flag:Boolean = false;
var rand:int;

init();

function init():void
{
     bmd = new BitmapData(stage.stageWidth, stage.stageHeight, true, 0x00000000);
     canvas = new Bitmap(bmd);
     addChild(canvas);
     addEventListener(Event.ENTER_FRAME, drawSquare);
}

function drawSquare(e:Event):void {
     var rect:Rectangle = getTransprentRect();
     squares.push(rect);
     bmd.fillRect(rect, 0xFF000000);
     if (squares.length >= limit) {
          removeEventListener(Event.ENTER_FRAME, drawSquare);
          trace("DONE");
     }
}

function getTransprentRect():Rectangle {
     flag = false;
     while (!flag) {
          point = new Point(int(Math.random() * bmd.width), int(Math.random() * bmd.height));
          if (bmd.getPixel32(point.x, point.y) == 0) {
               rand = Math.min(min + Math.random() * (max - min), bmd.width - point.x, bmd.height - point.y);
               r = new Rectangle(point.x, point.y, rand, rand);
               tbmd = new BitmapData(r.width, r.height, true, 0x00000000);
               tbmd.copyPixels(bmd, r, new Point());
               flag = testAlpha(tbmd);
          }
     }
     return r;
}

function testAlpha(b:BitmapData):Boolean {
     var isTransparent:Boolean = true;
     var len:int = b.width * b.height;
     for (var i:int = 0; i < len; i++) {
          if (b.getPixel32(i % b.width, int(i / b.width)) > 0) {
               isTransparent = false;
               break;
          }
     }
     return isTransparent;
}

Report · May 22, 2011

Ok, I'm liking this.

I'll have a look through it properly once I get into the office.

I'll need to learn how the bitmap parts of flash work, and then I'll be trying to find a way to keep a 1 pixel line between all the squares.

Hopefully this could even give me an idea of how to get it to work better with vectors, cos that works so much faster than the shapes version.

Brook.

Report · May 23, 2011

To keep at least one pixel between them, change to the following:

function drawSquare(e:Event):void {
     var rect:Rectangle = getTransprentRect();
     rect.x++;
     rect.y++;
     rect.width -= 2;
     rect.height -= 2;
     squares.push(rect);
     bmd.fillRect(rect, 0xFF000000);
     if (squares.length >= limit) {
          removeEventListener(Event.ENTER_FRAME, drawSquare);
          trace("DONE");
     }
}

Report · May 23, 2011

If you need to use vectors instead of bitmap for display - you still can use BitmapData as a matrix. The following code draws vector circles using rectangles from BitmapData. As you see bitmap is not displayed (I commented it out) at all but BitmapData is utilized as a template. There is only one new function - drawVectorObject().


//var canvas:Bitmap;
var bmd:BitmapData;
var min:int = 2;
var max:int = 80;
var limit:int = 1200;
var squares:Array;
var point:Point;
var r:Rectangle;
var tbmd:BitmapData;
var flag:Boolean;
var rand:int;

init();

function init():void
{
     squares = [];
     bmd = new BitmapData(stage.stageWidth, stage.stageHeight, true, 0x00000000);
     // bitmapdata is not displayed
     //canvas = new Bitmap(bmd);
     //addChild(canvas);
     addEventListener(Event.ENTER_FRAME, drawSquare);
}

function drawVectorObject(rect:Rectangle):Shape {
     var s:Shape = new Shape();
     s.graphics.beginFill(Math.random() * 0xFFFFFF);
     s.graphics.drawCircle(rect.width * .5, rect.height * .5, rect.width * .5);
     addChild(s);
     s.x = rect.x;
     s.y = rect.y;
     return s;
}

function drawSquare(e:Event):void {
     var rect:Rectangle = getTransprentRect();
     rect.x++;
     rect.y++;
     rect.width -= 2;
     rect.height -= 2;
     squares.push(rect);
     bmd.fillRect(rect, 0xFF000000);
     drawVectorObject(rect);
     if (squares.length >= limit) {
          removeEventListener(Event.ENTER_FRAME, drawSquare);
          trace("DONE");
     }
}

function getTransprentRect():Rectangle {
     flag = false;
     while (!flag) {
          point = new Point(int(Math.random() * bmd.width), int(Math.random() * bmd.height));
          if (bmd.getPixel32(point.x, point.y) == 0) {
               rand = min + Math.random() * (max - min);
               rand = Math.min(rand, bmd.width - point.x, bmd.height - point.y);
               r = new Rectangle(point.x, point.y, rand, rand);
               tbmd = new BitmapData(r.width, r.height, true, 0x00000000);
               tbmd.copyPixels(bmd, r, new Point());
               flag = testAlpha(tbmd);
          }
     }
     return r;
}

function testAlpha(b:BitmapData):Boolean {
     var isTransparent:Boolean = true;
     var len:int = b.width * b.height;
     for (var i:int = 0; i < len; i++) {
          if (b.getPixel32(i % b.width, int(i / b.width)) > 0) {
               isTransparent = false;
               break;
          }
     }
     return isTransparent;
}

Report · May 22, 2011

Here is another experiment that utilizes hitTestObject method. Of course it is not a final solution but it demonstrates how squares can find empty spaces. It just maybe a step into a right direction:

var max:Number = 50;
var min:Number = 10;
var limit:int = 100;
var squares:Array;
var currentSquare:MovieClip;

squares = [];
addEventListener(Event.ENTER_FRAME, spawnSquare);
     
function spawnSquare(e:Event):void
{
     currentSquare = square();
     currentSquare.x = int(stage.stageWidth * Math.random());
     currentSquare.y = int(stage.stageHeight * Math.random());
     addChild(currentSquare);
     squares.push(currentSquare);
     removeEventListener(Event.ENTER_FRAME, spawnSquare);
     addEventListener(Event.ENTER_FRAME, findPosition);
     if(squares.length >= limit) removeEventListener(Event.ENTER_FRAME, spawnSquare);
}
          
function findPosition(e:Event):void 
{
     var hasSpace:Boolean = true;
     for each(var o:MovieClip in squares) {
          if (o != currentSquare && o.hitTestObject(currentSquare)) {
               hasSpace = false;
          }
     }
     if (hasSpace) {
          removeEventListener(Event.ENTER_FRAME, findPosition);
          addEventListener(Event.ENTER_FRAME, spawnSquare);
     }
     else {
          currentSquare.x += 1;
          currentSquare.y += 1;
     }
     if (currentSquare.x > stage.stageWidth) {
          currentSquare.x = 0;
          currentSquare.attempt++;
     }
     if (currentSquare.y > stage.stageHeight) {
          currentSquare.y = 0;
          currentSquare.attempt++;
     }
     if (currentSquare.attempt > 2 ) {
          trace(squares.indexOf(currentSquare));
          removeChild(currentSquare);
          squares.splice(squares.indexOf(currentSquare), 1);
          removeEventListener(Event.ENTER_FRAME, findPosition);
          addEventListener(Event.ENTER_FRAME, spawnSquare);
          
     }
}

function square():MovieClip {
     var side:int = min + (max - min) * Math.random();
     var s:MovieClip = new MovieClip();
     s.graphics.beginFill(Math.random() * 0xFFFFFF);
     s.graphics.drawRect(0, 0, side, side);
     s.attempt = 0;
     return s;
}