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.

E.g.:

{0,0,0,0,0,0}
{0,1,1,0,0,0}
{0,1,1,0,0,1}
{1,1,0,1,0,1}
{0,0,0,1,0,1}
{0,0,1,1,1,1}

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:

{0,0,0,0,0,0}
{0,1,1,0,0,0}
{0,1,1,0,0,2}
{1,1,0,2,0,2}
{0,0,0,2,0,2}
{0,0,2,2,2,2}

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]
                else
                    tileAbove = nil
                end

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

                --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
                    end
                else
                    if tileBehind.val > tileAbove.val then
                        ng = obj.changeObjNums(ng, x, y, objNum, tileAbove.val)
                        objNum = tileAbove.val
                    else
                        objNum = tileAbove.val
                    end
                end

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

--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
            end
        end
    end
    return grid
end

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.