# Find empty position in map

## Recommended Posts

I need to find position for spawning player in 2D map. My problem is, if I generate random point on the map, there might be already player on that same position. I could loop that random until position is found without collision but it would be inefficient when map is full or would it?

##### Share on other sites

I have an idea. I made an example on Playground with Unit Tests using Jasmine because I study TDD (Test-Driven Development).

We can write a function that will get a 2D map and will return an array of empty points.

Lets define:

• 0 - empty
• p - player
• b - bar or obstacle (I thinks that "bar" and "obstacle" are synonyms in English)

For example, this is our 2D map:
p00000
bbbb00
0p000b
bbb000
p00000

We expected that a function will return an array of empty points: (0, 1), (0, 2) and so on.

We can generate a random index from the range: [0, cells.length) and use this random index to get an empty cell from cells list:

main.js

``````
/**
* Returns a random integer between min (include) and max (include)
*/
function getRandomInt(min, max)
{
return Math.floor(Math.random() * (max - min + 1)) + min;
}

function main()
{
var map = [
['p', '0'],
['0', 'p']
];

// Get empty cell list
var gameGame = new GameMap();
var emptyCells = gameGame.GetEmptyCells(map);
console.log(emptyCells); // output: [ {x: 0, y: 1}, {x: 1, y: 0} ]

// Get random cell
var index = getRandomInt(0, emptyCells.length - 1);
var cell = emptyCells[index];
console.log(cell); // output: {x: 1, y: 0}
}

GameMap.js

``````
function GameMap()
{
}

GameMap.prototype.GetEmptyCells = function(map)
{
var emptyCells = [];

for (var x = 0; x < map.length; x++)
{
var row = map[x];
for (var y = 0; y < row.length; y++)
{
if (row[y] === "0")
{
emptyCells.push({ x: x, y: y });
}
}
}

return emptyCells;
};``````

SpecRunner.html

``````<!DOCTYPE html>
<html>

<meta charset="utf-8">
<title>Jasmine Spec Runner v3.3.0</title>

<script src="https://cdnjs.cloudflare.com/ajax/libs/jasmine/3.3.0/jasmine.min.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/jasmine/3.3.0/jasmine-html.min.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/jasmine/3.3.0/boot.min.js"></script>

<!-- include source files here... -->
<script src="src/GameMap.js"></script>

<!-- include spec files here... -->
<script src="spec/GameMapSpec.js"></script>

<body>
</body>

</html>``````

GameMapSpec.js

``````describe("GameMap", function()
{
it("GetEmptyMap_ReturnsEmptyMapList", function()
{
// Arrange
var gameMap = new GameMap();
var expectedCells = [
{ x: 0, y: 1 }, { x: 0, y: 2 }, { x: 0, y: 3 }, { x: 0, y: 4 }, { x: 0, y: 5 },
{ x: 1, y: 4 }, { x: 1, y: 5 },
{ x: 2, y: 0 }, { x: 2, y: 2 }, { x: 2, y: 3 }, { x: 2, y: 4 },
{ x: 3, y: 3 }, { x: 3, y: 4 }, { x: 3, y: 5 },
{ x: 4, y: 1 }, { x: 4, y: 2 }, { x: 4, y: 3 }, { x: 4, y: 4 }, { x: 4, y: 5 },
];
var map = [
['p', '0', '0', '0', '0', '0'],
['b', 'b', 'b', 'b', '0', '0'],
['0', 'p', '0', '0', '0', 'b'],
['b', 'b', 'b', '0', '0', '0'],
['p', '0', '0', '0', '0', '0'],
];

// Act
var actualCells = gameMap.GetEmptyCells(map);

// Assert
expect(actualCells).toEqual(expectedCells);
});
});``````

##### Share on other sites

Nicely documented.  However I imagine the map to be changing, so collecting / filtering all the empty cells each search is going to be expensive (doubly so if the map array is formed by looping all Players to get their positions?).  Whereas having Players link (or delink) themselves from their respective Coordinate (as they move) and then have that Coordinate link (or delink) itself from EmptyCoordinates (as the Player links change) may be more optimal?  Whether this linking overhead is more or less optimal that the OP's "loop until random is empty" approach likely depends on size of map, population density, frequency of movement and so on.  A fourth approach may be to hold a finite set of "spawn" locations and pick the one with any Player furthest from it.

##### Share on other sites

Honestly, picking a random location is super super cheap.

Finding if that position is empty or not might involve iterating a list of entities (probably not so cheap, dependent mostly on list size) or might be a simple table lookup (super cheap).

If your map 'mostly' contains empty spaces you'll mostly have one random position and lookup assigned, maybe you'll get unlucky and end up with a few, probably still really cheap and way way simpler.

Iterating over the entire 2D map will be slower, managing another list of empty positions is more overhead (although picking one would be super cheap also).

I like the spawn point idea, could be extrapolated to finding locations equidistant from two or more entities (rather than a fixed list of spawn points, even the fixed list needs distance checks), this would all be reasonably expensive (by comparison) but quite a fun challenge to code up and good for the user—no one wants to spawn too close to an enemy (dependent on the game type of course, but usually true), which could well happen with random distribution, frequently if your map is well populated.