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.

CodePudding user response：

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.