Let’s say you have a 2D grid with distinct, arbitrary shapes on it (polygons of any sort), and you’d like to isolate the distinct shapes. For example, this 2D grid could represent a game’s map with a system of different shaped buildings. If your player is on top of one building, the game logic requires the application to distinguish the isolated shapes for pathfinding purposes etc.



You can see two distinct shapes on this grid, one on the top left, the other in the bottom right (we ignore touching diagonals).

To isolate the shapes, iterate the grid left-to-right, top-to-bottom. For each cell (xi, yi) that has a value vi where i > 0, check the cell directly above i.e. (xi, yi-1), and directly behind i.e. (xi-1, yi), where i-1 > 0. If either of these has a value vi where i > 0, assign (xi, yi) the value vi. If they don’t, this cell must be part of a new shape. Assign (xi, yi) the value vi+1.

The output will be:


As mentioned, this algorithm ignores touching diagonals. In the example, if we considered (xi, yi) and (x4, y4) to be touching, then there’d just be a single shape on this grid.

Here’s an implementation in Lua:

-- og is "old gird"
-- ng is "new grid"
local function createPolyObjects (og)
    local objNum = 0
    local ng = {}
    for y = 1, #og, 1 do
        ng[y] = {}
        for x = 1, #og[y], 1 do
            local tile = {}
            tile.val = og[y][x];
            tile.x = x
            tile.y = y
            if tile.val == 1 then
                --Tile above
                local tileAbove = {}
                tileAbove.x = x
                tileAbove.y = y-1
                if tileAbove.y > 0 then
                    tileAbove.val = ng[tileAbove.y][tileAbove.x]
                    tileAbove = nil

                --Tile behind
                local tileBehind = {}
                tileBehind.x = x-1
                tileBehind.y = y
                if tileBehind.x > 0 then
                    tileBehind.val = ng[tileBehind.y][tileBehind.x]
                    tileBehind = nil

                --Determine the correct objNum to assign
                if tileAbove == nil or tileAbove.val == 0 then
                    if tileBehind == nil or tileBehind.val == 0 then
                        objNum = objNum + 1
                    if tileBehind.val > tileAbove.val then
                        ng = obj.changeObjNums(ng, x, y, objNum, tileAbove.val)
                        objNum = tileAbove.val
                        objNum = tileAbove.val

                --Populate ng
                ng[y][x] = objNum
                ng[y][x] = 0
    obj.max = objNum
    return ng

--Helper function:
--Changes the "object number" used on the grid
local function changeObjNums (grid, x, y, oldNum, newNum)
    for j = y, 1, -1 do
        for i = x, 1, -1 do
            if grid[j][i] == oldNum then
                grid[j][i] = newNum
    return grid

This code is part of my Lua Grid Tools repo on Bitbucket.

Next I’ll explain how to break up the polygons into distinct rectangles. This is useful if you’re aiming to add each shape to Box2D, as convex shapes cannot be used in Box2D. Check that out here.