
function grid2d(w: number, h: number, val: any): any[][]
{
    var result: any[][] = [];
    for(var i = 0; i < w; i++)
    {
        result[i] = [];
        for(var j = 0; j < h; j++)
        {
            result[i][j] = val;
        }
    }
    return result;
}


function getIslands(map: GameMap)
{
    var L0 = map.h;
    var L1 = map.w;
    var islandNumbers = grid2d(L0, L1, null);
    var prevident = []
    var nextIslandNumber = 0;
    var i, j;

    function interior(t: TileType) {
        return t !== TileType.Wall && t !== TileType.Barrier;
    }

    // find islands
    let grid = map.grid;
    for(i = 0; i < L0; i++)
    {
        for(j = 0; j < L1; j++)
        {
            let t = map.grid[i][j].t;
            if(interior(t))
            {
                var above = (j > 0 && interior(grid[i][j - 1].t));
                var left = (i > 0 && interior(grid[i - 1][j].t));
                if(above && left)
                {
                    var n1 = islandNumbers[i][j-1];
                    while(typeof prevident[n1] !== 'undefined') n1 = prevident[n1];
                    var n2 = islandNumbers[i-1][j];
                    while(typeof prevident[n2] !== 'undefined') n2 = prevident[n2];
                    if(n1 < n2) prevident[n2] = n1;
                    if(n2 < n1) prevident[n1] = n2;
                    islandNumbers[i][j] = Math.min(n1, n2);
                }
                else if(above)
                {
                    islandNumbers[i][j] = islandNumbers[i][j - 1];
                }
                else if(left)
                {
                    islandNumbers[i][j] = islandNumbers[i - 1][j];
                }
                else
                {
                    islandNumbers[i][j] = nextIslandNumber;
                    nextIslandNumber++;
                }
            }
        }
    }
    // map island numbers to consecutive numbers
    var remap = [];
    var nextRemap = 0;
    for(var k = 0; k < nextIslandNumber; k++)
    {
        if(typeof prevident[k] === 'undefined')
        {
            remap[k] = nextRemap;
            nextRemap++;
        }
    }
    // renumber the grid
    for(i = 0; i < L0; i++)
    {
        for(j = 0; j < L1; j++)
        {
            if(interior(grid[i][j].t))
            {
                var n = islandNumbers[i][j];
                while(typeof prevident[n] !== 'undefined') n = prevident[n];
                islandNumbers[i][j] = remap[n];
            }
        }
    }
    
    // set the data
    return islandNumbers;
}

