求助：实现广度优先洪水填充搜索并返回首个匹配位置

问题背景 #

需要实现一个函数，以广度优先的洪水填充模式在0,0至49,49的网格中搜索，找到能容纳指定size结构的首个RoomPosition类型位置并返回。现有代码存在崩溃或无限循环问题，无法正常返回结果。

原问题代码 #

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
}

补充说明：doesStampFitAtPosition函数用于检查起始位置的相邻n size区域是否符合预设条件，返回布尔值。需采用广度优先搜索实现。

问题分析 #

• 搜索模式错误：原代码采用递归式深度优先搜索，不符合广度优先的要求，且递归深度过大时会触发栈溢出崩溃。
• 无已访问记录：未标记已遍历的坐标，导致重复访问同一位置，引发无限循环。
• 边界判断错误：提前排除了网格边缘的合法位置（比如x=49时直接返回，但该位置可能完全符合结构放置条件）。
• 未定义变量：递归调用时传入了未声明的visited参数，直接导致运行报错。

修复后的代码 #

function floodFillSearch(room: Room, startPosition: RoomPosition, structure: StampType, plannedPositions: RoomPosition[]): RoomPosition | undefined {
    // 初始化队列，存储待搜索的位置
    const queue: RoomPosition[] = [startPosition];
    // 记录已访问的坐标，避免重复遍历
    const visited = new Set<string>();
    // 标记起始位置为已访问
    visited.add(`${startPosition.x},${startPosition.y}`);

    // 定义四个方向的偏移量
    const directions = [
        { x: 1, y: 0 },   // 右
        { x: -1, y: 0 },  // 左
        { x: 0, y: 1 },   // 上
        { x: 0, y: -1 }   // 下
    ];

    while (queue.length > 0) {
        const currentPos = queue.shift()!;
        const x = currentPos.x;
        const y = currentPos.y;

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

        // 检查当前位置是否能放置结构
        if (doesStampFitAtPosition(x, y, room, structure, plannedPositions)) {
            return new RoomPosition(x, y, room.name);
        }

        // 遍历四个方向
        for (const dir of directions) {
            const newX = x + dir.x;
            const newY = y + dir.y;
            // 检查新坐标是否在网格范围内
            if (newX >= 0 && newX <= 49 && newY >= 0 && newY <= 49) {
                const key = `${newX},${newY}`;
                // 未访问过的位置加入队列
                if (!visited.has(key)) {
                    visited.add(key);
                    queue.push(new RoomPosition(newX, newY, room.name));
                }
            }
        }
    }

    // 遍历完所有位置都没找到，返回undefined
    return undefined;
}

修复说明 #

• 改用队列实现BFS：通过队列按顺序遍历每个位置，保证广度优先的搜索顺序，避免递归栈溢出。
• 添加已访问集合：用字符串格式的坐标作为键，记录已遍历的位置，彻底解决无限循环问题。
• 修正边界判断：仅排除网格外的坐标，保留边缘合法位置的搜索资格。
• 移除无效递归参数：删除原代码中未定义的visited参数，改用局部集合管理访问状态。

内容的提问来源于stack exchange，提问作者xTwisteDx