广度优先搜索：找不到路径，二维数组中到边界的最短路径

我尝试编写一个“绕点”游戏。基本的游戏理念是，你必须在蓝点逃脱之前包围它。每放置一个障碍物（橙色点），蓝色点（“玩家”）就会向边界移动一步。如果你在他到达边界之前没有圈出蓝点，那么你就输了，游戏将重新开始。

因此我必须做一个对 UIButton 的 2D 数组进行呼吸优先搜索找到从playerButton到边界的最短路径。

问题：

它通常找不到通往边界的路径（在控制台中打印“未找到路径！”并重新启动），即使蓝点可能有通往边界的路径/该点没有被橙色点包围。它也不会走最短路径，有时该点只是循环。下、上、下……这使得获胜变得非常容易。

我的项目：

最好的事情是如果你可以下载我的项目 https://www.dropbox.com/s/mtl410wzrg3elwg/dot%202%202.zip?dl=0（总共300行代码）here https://www.dropbox.com/s/mtl410wzrg3elwg/dot%202%202.zip?dl=0然后您可以使用这些模式测试问题：（在给定的序列中单击标记的按钮/点）

1. 找不到可能的路径，但有很多条：(1,2) -> (0,3) -> (1,4)

2. 找不到可能的路径，但有一条： (2,2) -> (1,3) -> (2,4) -> (2,5) -> (3,5) -> (4,4) -> (3,3)

3. 向上/向下/向上/...循环：(3,4) -> (2,3) -> (2,2) -> (1,1) -> (1,0) -> (3,4) ) -> (3,5) -> (4,6) -> (4,7) -> (5,8)

重要提示：查看这些问题的方法有无数种，这 3 种模式只是为了更快地找到问题，并且您不必多次播放直到出现问题。另外，你必须让第 94 行（possibleNeighbours.shuffle()）未注释，因为这会使模式随机化。

如果您不想下载我的整个项目，您可以查看我的广度优先搜索方法，该方法返回蓝点必须移动到的下一个 x 和 y 坐标：

    func findDirection()->String{
    var blockedArr:  [[Bool]] = [[false, false, false, false, false, false, false, false, false],
                                 [false, false, false, false, false, false, false, false, false],
                                 [false, false, false, false, false, false, false, false, false],
                                 [false, false, false, false, false, false, false, false, false],
                                 [false, false, false, false, false, false, false, false, false],
                                 [false, false, false, false, false, false, false, false, false],
                                 [false, false, false, false, false, false, false, false, false],
                                 [false, false, false, false, false, false, false, false, false],
                                 [false, false, false, false, false, false, false, false, false]] // Can do it like this as its always 9X9
    
    for btnline in btnArr{ //Block all dots which are already occupied
        for btn in btnline{
            if(btn.backgroundColor != defaultColor){
                blockedArr[getX(btn: btn)][getY(btn: btn)] = true
            }
        }
    }
    
    let otheryQueue = otherQueue<Pair>()
    let pair = Pair()
    var possibleNeighbours = findPossibleNeighbours(btn: btnArr[playerX][playerY], blockedArr: blockedArr) //returns array of all possible neighbours of given dot
    print(String(possibleNeighbours.description) + " possibeNeighs beginning" )
   //possibleNeighbours.shuffle() //IMPORTANT: Uncomment this to make it more random
    
    for neighbour in possibleNeighbours{
        if(isOnBorder(point: neighbour)){
            print("Blue dot is on border")
            return neighbour
        }
        pair.setPair(firstValue: neighbour, secondValue: neighbour)
        otheryQueue.enqueue(key: pair)
        blockedArr[getXFromString(string: neighbour)][getYFromString(string: neighbour)] = true
    }
    
    // Start the search
    while(!otheryQueue.isEmpty){
        let pointPair = otheryQueue.dequeue()
        let button = btnArr[getXFromString(string: (pointPair?.getFirst())!)][getYFromString(string: (pointPair?.getFirst())!)]
        possibleNeighbours = findPossibleNeighbours(btn: button, blockedArr: blockedArr)
        for neighbour in possibleNeighbours{
            if isOnBorder(point: neighbour){
                return (pointPair?.getSecond())!
            }
            pair.setPair(firstValue: neighbour, secondValue: (pointPair?.getSecond())!)
            otheryQueue.enqueue(key: pair)
            blockedArr[getXFromString(string: neighbour)][getYFromString(string: neighbour)] = true
        }
    }
    print("No path found!")
    return "-1 -1" //return (-1, -1) position if NO PATH FOUND
}

这是游戏视图的屏幕截图，有助于理解 (1,2)、(0,3)、蓝点等的含义：

如果有问题请提问。

谢谢你的帮助！！

斯威夫特爱好

你的里面有这段代码findDirection() func:

    let otheryQueue = otherQueue<Pair>()
    let pair = Pair()
    var possibleNeighbours = findPossibleNeighbours(btn: btnArr[playerX][playerY], blockedArr: blockedArr) //returns array of all possible neighbours of given dot
    print(String(possibleNeighbours.description) + " possibeNeighs beginning" )
   //possibleNeighbours.shuffle() //IMPORTANT: Uncomment this to make it more random
    
    for neighbour in possibleNeighbours{
        if(isOnBorder(point: neighbour)){
            print("Blue dot is on border")
            return neighbour
        }
        pair.setPair(firstValue: neighbour, secondValue: neighbour)
        otheryQueue.enqueue(key: pair)
        blockedArr[getXFromString(string: neighbour)][getYFromString(string: neighbour)] = true
    }

    // Start the search
    while(!otheryQueue.isEmpty){
       ...

为了调试，我在“开始搜索”之前添加了以下内容：

    var p = otheryQueue.first
    while p != nil {
        print("first", p?.data.first, "second", p?.data.second)
        p = p?.next
    }
    
    // Start the search
    while(!otheryQueue.isEmpty){
       ...

如果我首先点击任何灰点，例如0 0，我在控制台中得到的输出是：

Button 0 0 tapped
["4 3", "5 4", "4 5", "3 5", "3 4", "3 3"] possibeNeighs beginning
first Optional("3 3") second Optional("3 3")
first Optional("3 3") second Optional("3 3")
first Optional("3 3") second Optional("3 3")
first Optional("3 3") second Optional("3 3")
first Optional("3 3") second Optional("3 3")
first Optional("3 3") second Optional("3 3")

（如果我先点击3 3输出将全部为“3 4”）。

您的代码仅创建一个pair对象，然后每次通过循环修改其值。

您可能想创建一个new pair每次你想要的时候都反对.enqueue it:

    for neighbour in possibleNeighbours{
        if(isOnBorder(point: neighbour)){
            print("Blue dot is on border")
            return neighbour
        }
        
        // add this line
        let pair = Pair()
        
        pair.setPair(firstValue: neighbour, secondValue: neighbour)
        otheryQueue.enqueue(key: pair)
        blockedArr[getXFromString(string: neighbour)][getYFromString(string: neighbour)] = true
    }

现在我第一次点击时控制台输出0 0 is:

Button 0 0 tapped
["4 3", "5 4", "4 5", "3 5", "3 4", "3 3"] possibeNeighs beginning
first Optional("4 3") second Optional("4 3")
first Optional("5 4") second Optional("5 4")
first Optional("4 5") second Optional("4 5")
first Optional("3 5") second Optional("3 5")
first Optional("3 4") second Optional("3 4")
first Optional("3 3") second Optional("3 3")

您可能想在下一个块（搜索块）中执行相同的操作：

    // Start the search
    while(!otheryQueue.isEmpty){
        let pointPair = otheryQueue.dequeue()
        let button = btnArr[getXFromString(string: (pointPair?.getFirst())!)][getYFromString(string: (pointPair?.getFirst())!)]
        possibleNeighbours = findPossibleNeighbours(btn: button, blockedArr: blockedArr)
        for neighbour in possibleNeighbours{
            if isOnBorder(point: neighbour){
                return (pointPair?.getSecond())!
            }
            
            // add this line
            let pair = Pair()
            
            pair.setPair(firstValue: neighbour, secondValue: (pointPair?.getSecond())!)
            otheryQueue.enqueue(key: pair)
            blockedArr[getXFromString(string: neighbour)][getYFromString(string: neighbour)] = true
        }
    }