javascriptloopsrecursiongame-developmentcallstack

Random placement of items on canvas without overlap


I'm trying to randomly place a number of items (sprites) onto a canvas element without any overlap. I'm using a seeded random number so that I can get consistent placement. However I'm running into a few issues. Firstly I very quickly reach a maximum call stack size with my recursive logic to avoid any collisions (Anywhere from merely 15 entities), so I don't know if there's a way I can optimise this. Secondly, when it does run successfully, my entities all have a tendency to be along the top and left side of my canvas, hence why there's probably a large amount of collisions.

Can anyone see any issues with this? I've tried just using Math.random() instead of myrng() to see if that is the issue but I get the same result.

//80 is the width of a single sprite
const getLocation = () => {
    let x = Math.floor(myrng() * (canvas.width - 80));
    let y = Math.floor(myrng() * (canvas.height - 80));

    x = x < 0 ? 0 : x;
    y = y < 0 ? 0 : y;

    const overlap = entities.some((entity) => {
      return (x - entity.position.x < 80 || y - entity.position.y < 80);
    });

    if (!overlap) {
      return [x, y];
    } else {
      return getLocation();
    }
  };

myrng() is the seeded random number generator from the following package https://www.npmjs.com/package/seedrandom

I call this before I begin calling my update method.

for (let i = 0; i < 15; i++) {
      const [x, y] = getLocation();
      entities.push({ position: { x, y } });
    }

Solution

  • The overlap calculation appears to be incorrect. Try

    const overlap = entities.some((entity) => {
          return Math.abs(x - entity.position.x) < 80 
              && Math.abs(y - entity.position.y) < 80);
        });
    

    The reasoning being that if either of the x or y values of two entities are not within 80px of each other they do not overlap.

    Running out of stack space could be a consequence of recursively calling getLocation when there is no canvas space of 80 x 80 px unoccupied on the canvas. More design is needed but checking that some existing entity differs from every other entity by not less than 80px in both the x and y direction is probably necessary. If there is no solution remaining, recursions should pop an entity of the entiies array before the recursive call.