Finding the largest area in a grid with the same value

27 October 2020 - 2 minute read

To challenge myself I tried to recreate the simple game called Flood It. The goal of the game is to fill/flood the board with as little moves as possible. The board gets flooded from the top left corner. With each newly selected color the area expands.

To know which blocks needed to be painted, I needed to calculate the area from the top left corner which had the same color. How can we calculate this area, you might say, using Depth First Search!

Flood It

Create the grid

First we need to make a grid that is filled with blocks. We also need to define the area to begin with, in this case it's always the first block of the grid.

createGrid(){
    for (let x = 0; x < this.size; x++) {
        for (let y = 0; y < this.size; y++) {
            this.blocks.push(new Block(x,y))             
        }      
    }
    this.area = [this.blocks[0]]
}

Find adjacent

To properly run the depth first search function we need to calculate the adjacent blocks for each block. For this game and rules it only applies to the top,left,bottom and right blocks.

getBlockAt(x,y){
    return this.blocks.find(block => block.x == x && block.y == y)
}

setAdjacent(){
    this.blocks.forEach(block => {
        let top = this.getBlockAt(block.x, block.y + 1)
        let right = this.getBlockAt(block.x + 1, block.y)
        let bottom = this.getBlockAt(block.x, block.y - 1)
        let left = this.getBlockAt(block.x - 1, block.y)
        block.adjacent = [top,right,bottom,left]
    })
}

Calculate the area

To calculate the area we need to recursively visit the adjacent blocks of each block that has the same color.

We make an array of blocks to explore, beginning with the start block.

this.start_block.visited = true;
let blockstoExplore = [this.start_block];

We will loop through all the blocksToExplore array while it isn't empty yet. We pop of a block to explore and loop through all the adjacent blocks. Since there are blocks with less than 4 adjacent blocks we check if the block is undefined so we can skip it. Then, we check if the block hasn't been visited yet and is the same color as the current selected color. If this is the case then it must certainly be in the largest area. We push it to blocksToExplore array to have a look at its adjacent blocks.

while(blockstoExplore.length){
    let popped_block = blockstoExplore.pop();

    popped_block.adjacent.forEach(block => {
        if(block == undefined) return;
        if(!block.visited && block.color == this.current_color) {
            blockstoExplore.push(block)
            this.area.push(block)
        }
        block.visited = true;
    })
}

Once we found all the blocks we will reset the visited state of the blocks for the next update. Lastly we will remove all the duplicate blocks from the area.

this.blocks.forEach(b => b.visited = false)
this.area = [...new Set(this.area)];

Now we have found the area of blocks with the same color from the top left corner using depth first search

updateArea(){
    this.start_block.visited = true;
    let blockstoExplore = [this.start_block];

    while(blockstoExplore.length){
        let popped_block = blockstoExplore.pop();

        popped_block.adjacent.forEach(block => {
            if(block == undefined) return;
            if(!block.visited && block.color == this.current_color) {
                blockstoExplore.push(block)
                this.area.push(block)
            }
            block.visited = true;
        })
    }

    this.blocks.forEach(b => b.visited = false)
    this.area = [...new Set(this.area)];
}