广度优先搜索:找不到路径，二维数组中边框的最短路径 [英] Breadth First Search: Can't find path, shortest path to border in 2D-Array
问题描述
我尝试编写一个圆点"游戏.游戏的基本思路是，您必须先将蓝点包围，然后再逃脱.对于每个放置的障碍物(橙色的点)，蓝色的点(玩家")向边界移动一步.如果您直到他在边界上之前都没有圈出蓝点，您就输了，游戏会重新开始.
因此，我必须在2D UIButton数组上进行 呼吸优先搜索 ，以找到从playerButton到边框的最短路径.
问题:
它通常找不到边界的路径(在控制台中打印找不到路径！"并重新启动)，即使蓝色点可能有到达边界的路径/该点也没有用橙色圆点圈起来.它也不是走的最短的路径，有时圆点只会循环起来.下来，起来，下来，...这很容易取胜.
我的项目:
最好的办法是，您可以
如有疑问，请询问.
感谢您的帮助！
SwiftHobby
您在 findDirection() func中具有以下代码块:
让otheryQueue = otherQueue< Pair>()让对= Pair()var PossibleNeighbours = findPossibleNeighbours(btn:btnArr [playerX] [playerY]，blockedArr:blockedArr)//返回给定点的所有可能邻居的数组print(String(possibleNeighbours.description)+"possibeNeighs starting")//possibleNeighbours.shuffle()//重要提示:取消注释以使其更加随机对于可能的邻居中的邻居{if(isOnBorder(point:neighbour)){打印(蓝点在边界上")返回邻居}pair.setPair(firstValue:邻居，secondValue:邻居)otheryQueue.enqueue(key:对)blockedArr [getXFromString(string:neighbour)] [getYFromString(string:neighbour)] = true}//开始搜索while(！otheryQueue.isEmpty){... 要调试，我在开始搜索"之前添加了此代码:
var p = otheryQueue.first而p！= nil {print("first"，p?data.first，"second"，p?data.second)p = p?.next}//开始搜索while(！otheryQueue.isEmpty){... 如果我先点击任意灰色点(例如 0 0 )，则我在控制台中得到的输出为:
按钮0 0轻按["4 3"，"5 4"，"4 5"，"3 5"，"3 4"，"3 3"] possibe第一可选("3 3")第二可选("3 3")第一可选("3 3")第二可选("3 3")第一可选("3 3")第二可选("3 3")第一可选("3 3")第二可选("3 3")第一可选("3 3")第二可选("3 3")第一可选("3 3")第二可选("3 3") (如果我先在 3 3 上点击，输出将全部为"3 4").
您的代码仅创建一个 pair 对象，然后每次通过循环修改其值.
您可能想在每次要 .enqueue 对象时创建一个 new pair 对象:
表示可能的邻居中的邻居{if(isOnBorder(point:neighbour)){打印(蓝点在边界上")返回邻居}//添加此行让对= Pair()pair.setPair(firstValue:邻居，secondValue:邻居)otheryQueue.enqueue(key:对)blockedArr [getXFromString(string:neighbour)] [getYFromString(string:neighbour)] = true} 现在，当我第一次点击 0 0 时，我的控制台输出是:
按钮0 0轻按["4 3"，"5 4"，"4 5"，"3 5"，"3 4"，"3 3"] possibe第一可选("4 3")第二可选("4 3")第一可选("5 4")第二可选("5 4")第一可选("4 5")第二可选("4 5")第一可选("3 5")，第二可选("3 5")第一可选("3 4")第二可选("3 4")第一可选("3 3")第二可选("3 3") 您可能想在下一个块(搜索块)中做同样的事情:
//开始搜索while(！otheryQueue.isEmpty){让pointPair = otheryQueue.dequeue()让按钮= btnArr [getXFromString(string:(pointPair?.getFirst())！)] [getYFromString(string:(pointPair?.getFirst())！)]PossibleNeighbours = findPossibleNeighbours(btn:按钮，blockedArr:blockedArr)对于可能的邻居中的邻居{如果isOnBorder(point:neighbour){返回(pointPair?.getSecond())！}//添加此行让对= Pair()pair.setPair(firstValue:邻居，secondValue:(pointPair?.getSecond())！)otheryQueue.enqueue(key:对)blockedArr [getXFromString(string:neighbour)] [getYFromString(string:neighbour)] = true}} I try programming a "Circle the dot" game. The basic game idea is that you have to surround the blue dot before it escapes. With every placed obstacle (orange colored dot), the blue dot ("player") moves one step to the border. If you haven't circled the blue dot until he's on the border, you lost and the game restarts.
Therefor I have to do a Breath First Search over a 2D-Array of UIButtons to find the shortest path from the playerButton to the border.
The problem:
It often doesn't find a path to the border (prints "No path found!" in the console and restarts) EVEN THOUGH there is a possible path for the blue dot to the border/ the dot isn't circled by orange dots. It also doesn't go the shortest path, sometimes the dot just loops up. down, up, down,... which makes it pretty easy to win.
My project:
The best thing would be if you can just download my project (all together 300 lines of code) here.Then you can test the problem with those patterns: (click in the given sequence on the labeled buttons/ dots)
Finds no possible path, but there are many: (1,2) -> (0,3) -> (1,4)
Finds no possible path, but there is one: (2,2) -> (1,3) -> (2,4) -> (2,5) -> (3,5) -> (4,4) -> (3,3)
Loops Up/Down/Up/...: (3,4) -> (2,3) -> (2,2) -> (1,1) -> (1,0) -> (3,4) -> (3,5) -> (4,6) -> (4,7) -> (5,8)
Important: There are infinite possible ways to see those problems, the 3 patterns are only to find the problem quicker and you don't have to play it multiple times until an issue appears. ALSO, you have to let line 94 (possibleNeighbours.shuffle()) uncommented, as this would randomize the patterns.
If you don't want to download my whole project you can take a look at my breadth-first-search method, which return the next x and y coordinates the blue dot has to move to:
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
}
Here is a screenshot of the game view, to help understand what I mean with (1,2), (0,3), blue dot and so on:
If there are questions please ask.
Thanks for any help!!
SwiftHobby
You have this block of code inside your 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){
...
To debug, I added this immediately before the "Start the search":
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){
...
If I start by tapping on any gray dot, such as 0 0, the output I get in console is:
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")
(if I tap first on 3 3 the output will be all "3 4").
Your code is creating only one pair object, and then modifying its values each time through the loop.
You probably want to create a new pair object each time you want to .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
}
Now my console output when first tapping on 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")
You likely want to do the same thing in the next block (the search block):
// 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
}
}
这篇关于广度优先搜索:找不到路径，二维数组中边框的最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
