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 } });
}
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.