Find empty position in map

canvasman · December 20, 2018

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?

8Observer8 · January 8, 2019

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}
}
window.onload = main;

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>

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

    <link rel="shortcut icon" type="image/png" href="https://cdnjs.cloudflare.com/ajax/libs/jasmine/2.0.0/jasmine_favicon.png">
    <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/jasmine/3.3.0/jasmine.min.css">

    <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>

</head>

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

b10b · January 8, 2019

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.

mattstyles · January 9, 2019

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.

ShrewdPixel · January 30, 2019

Iterating over a list of entities and calculating whether you are within a certain range of them would be very expensive computationally if you did it with pure math calculations.

So if you go that route, I'd do it with logic instead.

For instance, you can define what radius you want to be the minimum by defining a constant, like:

const personalSpace = 20;

If it's a 2D radius, this would apply to both the x and y axis. Then you can use 4 true/false checks to see if there is any overlap:

if ( !(localplayer.x - localplayer.personalSpace > otherPlayer.x + otherPlayer.personalSpace || 
        localplayer.x + localplayer.personalSpace < otherPlayer.x - otherPlayer.personalSpace || 
        localplayer.y - localplayer.personalSpace > otherPlayer.y + otherPlayer.personalSpace || 
        localplayer.y + localplayer.personalSpace < otherPlayer.y - otherPlayer.personalSpace) )  {
    spawnPlayer();
} else {
    findNewSpawn();
}

The preceding Javascript snippet is basically saying this: Is it above it? Below it? To the Left of it? To the right of it? If it's any of those, then PersonalSpace doesn't overlap and we're good to go. Otherwise, if they all fail, then there is overlap of personal space and try again. The same concept works in 3D(Six true/false checks instead of 4).

Using true/false logic is much less expensive on performance than pure math calculations, and should be used whenever possible to save processor cycles.

I hope I've understood what you were going for and that my response is helpful. Good Luck with your game!

Sign In

Find empty position in map

Recommended Posts

canvasman

Link to comment

Share on other sites

8Observer8

Link to comment

Share on other sites

b10b

Link to comment

Share on other sites

mattstyles

Link to comment

Share on other sites

ShrewdPixel

Link to comment

Share on other sites

Join the conversation

Recently Browsing 0 members

Browse

Activity