返回符合条件的洪水填充中的第一个位置

Question

我有一些函数，这个函数的目的是获取网格，并以洪水填充模式进行搜索，直到找到

size

。一旦找到该大小，它应该返回

{x,y}

对象。我遇到的主要问题是我不知道如何让它正确返回而不崩溃或进入无限循环。

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
}

一些注意事项，数组的边界是

0,0 -> 49,49

。

doesStampFitAtPosition()

函数检查相邻的

n size

空间，如果它不包含已经预先确定的值，则返回 true，否则返回 false。例如，可能存在全局颜色，它将检查在给定起始位置的情况下大小为

5x5 grid

的全局颜色是否存在。

注释

• 最终，

  RoomPosition

  包含

  x

  和

  y

  的属性，我只是想获取首先找到的

  x

  和

  y

  位置。

更新

• 我被告知我正在寻找广度优先搜索。

Answer 1

为了避免遍历循环，您需要以某种方式将单元格标记为“已访问”。有多种方法可以做到这一点，例如使用 Set，您可以在其中添加对单元格的唯一引用。

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;
}

在初始调用中，您不会传递

visited

参数，因此它被初始化为空 Set。

上面是深度优先搜索，对于寻找目标来说内存效率相当高。但是，如果您对“最近”命中感兴趣，那么通常会选择广度优先搜索方法——这将搜索短距离内的所有单元格，然后搜索距离源更远一步的所有单元格，...等等 代码可能如下所示：

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);
    }
}

这使用了 Set 的特定行为：当使用集合中已有的值调用 

.add

时，集合不会更改，但如果它尚未在集合中，则会以以下方式添加：

for..of

循环保证在下一次迭代中访问它。