Strategies for placing random items without overlapping with other excisting items?

[mauticom]

Hi guys,

 

how do you place items(sprites) randomly on your world and ensure that they don't overlap with other already excisting items? 

Do you check every item or are there functions from the physic engines that support you with that?

 

If there are no built in functions I would do it the following way:

 

1.) create random placement of sprite

2.) check newly placed items against all excisting items in the world

2.1) No overlapping -> GREAT finish!

2.2) If it overlaps repeat step 1. (abort after X cycles to avoid endless loop and performance spikes if you place them while the game runs)

 

If you do it like this: is there are a global phaser list where I can loop through:

 

a.) all excisting sprites

b.) all visible sprites

 

???

 

Any other ideas and strategies to place items randomly?

 

Thanks and greetings from a sunny Vienna,

 

Clemens

[alex_h]

Another approach is to make list all possible placements, then select randomly from that list.

[lewster32]

I'd go with Alex's approach - it's easier to specify a bunch of 'slots' that objects could possibly be placed in, then loop through all those slots randomly deciding to either add an object or not. Those slots could maybe be null keyed sprites with a physics body, and you could check for overlap each frame and mark them as invalid slots when they're overlapped by an object, so your routine could then only choose from slots that aren't being overlapped.

 

There's no flat list of all existing/visible sprites, because the scene graph is a hierarchy. There's nothing stopping you adding to your own flat array of objects when you create them though, and use that for such management. If you do this, then you could potentially create a sprite at a random position, iterate through the array seeing if the sprite overlaps with any of them, and if it doesn't, place the sprite at that point, otherwise pick a new point and repeat. This is probably quite inefficient and could be improved with the use of a QuadTree to quickly eliminate sprites that are nowhere near.

[wayfinder]

You could try and generate possible positions from a grid that is wide enough that no two objects spawned on grid coordinates would overlap (say you have a 32 px wide object, a 32x32 grid would work). Then put all these in an array and shuffle it. That will give you a random order by simply increasing the index, without repetitions. When you reach the end of the array, shuffle again and start from the top.

var array = [];var index = 0;for (var i = 0; i < gridLinesHorizontal; i++) {    for (var j = 0; j < gridLinesVertical; j++) {        array.push(new Phaser.Point(i * gridSize, j * gridSize));    }} Phaser.Utils.shuffle(array); ......... <in your game loop>if (spawn) {    spawnAtPos(array[index]);    index++;    if (index === array.length) {        index = 0;        Phaser.Utils.shuffle(array);    }}

Edit: if, of course, you are talking about dynamically moving sprites, this will not work. In that case, you pretty much have to check all of the objects in the vicinity of your desired spawning point.

[FineRapha]

I know it's an old thread. But it was the first result on Google for me.

So, here's my approach (using tiled maps).

First, I create a layer (using Tiled) with all possible locations

  layer_item_placement = map.createLayer( 'item_placement' );
  layer_item_placement.resizeWorld();
  layer_item_placement_available = [];
  for( var i = 0 ; i < layer_item_placement.layer.data.length; i++ )
  {
    for( var j = 0 ; j < layer_item_placement.layer.data[i].length; j++ )
    {
      if(layer_item_placement.layer.data[i][j].index >= 0 )
      {
       layer_item_placement_available.push({
          x:layer_item_placement.layer.data[i][j].x * 32,
          y:layer_item_placement.layer.data[i][j].y * 32
        });
      }
    }
  }

Then I create my objects:

  for( var i = 0 ; i < 50 ; i++ )
  {
    var xy = layer_item_placement_available[ _rand( 0 , layer_item_placement_available.length - 1 ) ];
    var object = game.add.sprite( xy.x , xy.y , 'objects' , _rand( 0 , 49 )  ); // 49 == Max sprite number
    furniture.add( object );
  }

Got all objects inside the area I wanted.