Randomly spawning bitmaps on cnvas

I need some ideas in order to finish algorithm. I'm randomly placing objects (bitmaps) on canvas without overlapping. Time needed to finish it is my problem. When I need to spawn for example 80% of canvas it takes to long. So i was thinking : I should make some change when the bitmaps take off 50 % of canvas. I want to tell algorithm that it should generate new locations (x,y) where it is free space.

My question is : How to render new location (x,y) in place where is free space.

In summary:

Things I know :

• object location (x,y)
• 4 corners (x,y) of object
• object width, height
• canvas width, height

Any suggestions?

Thanks for ideas. Now I've got problem.

OK, thanks for ideas. I've got a problem.

Link to picture: Picture with grid

I'm incrementing number of objects in cell after each adding object to grid. In the picture there are 9 possible locations for object. Should I check 9 conditions which tells where I should increment number of objects in cell? I assume that if object is on both cells than I increment number of objects in both cells.

• Use a set of free spaces. Randomize from it and remove the item you picked. – AturSams Oct 6 '12 at 15:47

Divide your world (screen) into a grid.

If all objects are not bigger then 20x20 px, then if you divide your screen into 40x40 grid tiles, you can just:

• every time when you add an object, set grid cell's state it occupies as "taken"
• every time when you remove an object, set the cell it was on as "free"
• when adding an object randomly, place it on one of free cells.

Edit: in regards to your question:

I'm incrementing number of objects in cell after each adding object to grid. In the picture there are 9 possible locations for object. Should I check 9 conditions which tells where I should increment number of objects in cell? I assume that if object is on both cells than I increment number of objects in both cells.

Yes, you want to register one object to all grid cells it occupies. One way of doing this would be creating a grid of arrays of objects:

const NUMBER_ROWS:int = 3;
const NUMBER_COLS:int = 3;
var grid:Array = [];
//init an empty grid
for ( var row:int = 0; row < NUMBER_ROWS; row++ ) {
for ( var col:int = 0; col < NUMBER_COLS; col++ ) {
grid.push ( [] );
}
}
//create object
var object: SomeClass = new SomeClass ();
//add the object to 4 cells:
grid[0][0].push ( object );
grid[1][0].push ( object );
grid[0][1].push ( object );
grid[1][1].push ( object );

//remove the object from upper two cells (it went down)
var index:int = grid[0][0].indexOf ( object );
grid[0][0].splice ( index, 1 );
index = grid[1][0].indexOf ( object );
grid[1][0].splice ( index, 1 );

• Ok, thanks for idea. Now I've got problem. Look at the picture. In my next post. – Toystoj Oct 7 '12 at 9:37

1. Divide the canvas into many 'rectangular pieces'
2. Shuffle the order of the pieces
3. Add bitmaps based on the order of the shuffled collection

To divide the canvas into pieces, make the whole canvas your first rectangular piece, then recursively split it until each piece is small enough.

For example, starting with the canvas, do a coin toss to determine if you split it with a horizontal line or a vertical line. Randomize where that line passes. Now run the same function on the two pieces you created and the stopping condition will be that the new piece is small enough by your definition.

• Why not just a grid, where all 'rectangular pieces' have same width and height? – Markus von Broady Oct 6 '12 at 21:10