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

Question

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

因此，我必须在 UIButtons 的二维数组上进行 Breath First Search 以找到从 playerButton 到边界.

问题：

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

我的项目：

如果你能 download my project (all together 300 lines of code) here 最好。然后你可以用这些模式测试问题：（按给定的顺序点击标记的按钮/点）

找不到可能的路径，但是有很多：(1,2) -> (0,3) -> (1,4)
找不到可能的路径，但有一个：(2,2) -> (1,3) -> (2,4) -> (2,5) -> (3 ,5) -> (4,4) -> (3,3)
循环 Up/Down/Up/...: (3,4) -> (2,3) -> (2,2) -> (1,1) -> ( 1,0) -> (3,4) -> (3,5) -> (4,6) -> (4,7) -> (5,8)

重要提示：有无数种可能的方法来查看这些问题，这 3 种模式只是为了更快地找到问题，您不必多次尝试直到问题出现。此外，您必须取消注释第 94 行 (possibleNeighbours.shuffle())，因为这会使模式随机化。

如果你不想下载我的整个项目，你可以看看我的广度优先搜索方法，return 蓝点必须移动到下一个 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)、蓝点等的含义：

有问题请追问

感谢您的帮助！！

SwiftHobby

Answer 1

你的 findDirection() 函数中有这段代码：

    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 对象，然后每次循环都修改它的值。

您可能想在每次要 .enqueue 对象时创建一个 new pair 对象：

    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 时的控制台输出是：

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

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

Breadth First Search: Can't find path, shortest path to border in 2D-Array

algorithm

xcode

breadth-first-search

ios

swift