Return First Position In Flood Fill That Matches Conditions

Question

I have some function, and this function's purpose is to take a grid, and search, in a flood-fill pattern, until it finds a size. Once that size is found, it should return the {x,y} object. The main issue that I'm having is that I don't know how to get it to properly return without crashing or going into an infinite loop.

function floodFillSearch(room: Room, startPosition: RoomPosition, structure: StampType, plannedPositions: RoomPosition[]): RoomPosition | undefined {
    Logger.log(`Start Position: ${startPosition.x}, ${startPosition.y}`, LogLevel.DEBUG)
    let x = startPosition.x
    let y = startPosition.y

    if (x > 49 || y > 49 || x < 0 || y < 0) { return }
    if (x + 1 > 49 || y + 1 > 49 || x - 1 < 0 || y - 1 < 0) { return }

    Logger.log(`Searching for ${structure} at ${x},${y}`, LogLevel.DEBUG)

    if (doesStampFitAtPosition(startPosition.x, startPosition.y, room, structure, plannedPositions)) {
        return new RoomPosition(startPosition.x, startPosition.y, startPosition.roomName)
    }

    let rightResult = floodFillSearch(room, new RoomPosition(startPosition.x + 1, startPosition.y, room.name), structure, plannedPositions, visited)
    let leftResult = floodFillSearch(room, new RoomPosition(startPosition.x - 1, startPosition.y, room.name), structure, plannedPositions, visited)
    let topResult = floodFillSearch(room, new RoomPosition(startPosition.x, startPosition.y + 1, room.name), structure, plannedPositions, visited)
    let bottomResult = floodFillSearch(room, new RoomPosition(startPosition.x, startPosition.y - 1, room.name), structure, plannedPositions, visited)

    if (rightResult) { return rightResult }
    if (leftResult) { return leftResult }
    if (topResult) { return topResult }
    if (bottomResult) { return bottomResult }
    return
}

Some notes, the bounds of the array are 0,0 -> 49,49. And the doesStampFitAtPosition() function checks the adjacent n size spaces and if it doesn't contain a value that's already predetermined, then it returns true, otherwise false. For example, a global color might exist, it would check if that global color, with the size of 5x5 grid, given the starting position, exists.

Notes

• The RoomPosition contains properties for x and y ultimately, I'm just trying to get the x and y position that is first found.

Update

• I have been told I'm looking for a breadth-first search.

Answer 1

To avoid that your traversal runs in circles, you need to somehow mark your cells as "visited". There are several ways to do that, for instance with a Set where you add a unique reference to a cell.

function floodSearch(startX: number, startY: number, size: number, visited: Set = new Set): {x: number, y: number} | undefined {

    if (startX > 49 || startY > 49 || startX < 0 || startY < 0) {
        return;
    }

    if (obj.lookAtArea(startX, startY, size)) {
        return {x: startX, y: startY};
    }

    if (visited.has(startX + startY*50)) {
        return; // Already visited
    }
    visited.add(startX + startY*50);

    let topResult = floodSearch(startX, startY - 1, size, visited);
    let botResult = floodSearch(startX, startY + 1, size, visited);
    let leftResult = floodSearch(startX - 1, startY, size, visited);
    let rightResult = floodSearch(startX + 1, startY, size, visited);
 
    if(topResult) return topResult;
    if(botResult) return botResult;
    if(leftResult) return leftResult;
    if(rightResult) return rightResult;
}

In the initial call you would not pass the visited argument, so it gets initialised as an empty Set.

The above is a depth-first search, and is rather memory efficient for finding a target. But if you are interested in the closest hit, then a breadth-first search is often the chosen method -- this will search all cells at a short distance, then all cells that are one step further from the source, ...etc.

The code could look like this:

function floodSearch(startX: number, startY: number, size: numberx): {x: number, y: number} | undefined {
    const queue: Set = new Set;
    queue.add(startX + startY*50);

    for (const coord of queue) {
        const x = coord % 50;
        const y = (coord - x) / 50;

        if (obj.lookAtArea(x, y, size)) {
            return {x, y};
        }

        if (y > 0) queue.add(coord - 50);
        if (x > 0) queue.add(coord - 1);
        if (y < 49) queue.add(coord + 50);
        if (x < 49) queue.add(coord + 1);
    }
}

This uses a specific behaviour of Set: when .add is called with a value that is already in the set, the set doesn't change, but if it is not in the set yet, it gets added in such a way that the for..of loop is guaranteed to visit it in a next iteration.