Java迷宫解决方案 – 我从未如此困惑过
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Java迷宫解决方案 – 我从未如此困惑过,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含4791字,纯文字阅读大概需要7分钟。
内容图文
所以我的任务是创建一个迷宫求解器,它包含一个Queue,一个Set,一个Location对象和一个最终进入Maze对象的Cell对象.
为了快速了解我完成时我的代码基本上会做什么:
7
10
_ _ _ _ _ _ _ _ _
|_ _ _ | _ _ _ |
| _ _| | | _ | |
| | | |_| | | |_| |
|_ _|_ _ _| |_ | |
| _ | | _ _| |_|
| |_ _| _| |_ |
|_ _ _ _|_ _|_ _ _| |
进入:
@ _ _ _ _ _ _ _ _ _
|@ @ @ @| _ _ _ |
| _ _|@| |@ @ @| |
| | |@|_|@| |@|_| |
|_ _|_ @ @ @| |@ @| |
| _ | | _ _|@|_|
| |_ _| _| |_ @ @|
|_ _ _ _|_ _|_ _ _|@|
@
到目前为止,我所做的一切都非常好,但是当我在我的Maze对象中实际编码findPath()方法时,我的代码会生成一个无效的路径.当我接收文件来读取迷宫时,我将该迷宫转换为多维字符数组,然后我将该字符数组转换为多维数组的单元格,并将每个单元格的边界映射到北,南,东和西布尔值.
现在要实际弄清楚如何在迷宫中导航,我在Maze的findPath()方法中试过但实际上有些失败了.
@ @ @ @ . . . . . .
. . . @ . . . . . .
. @ @ @ . . . . . .
. @ @ @ @ . . . . .
. . @ @ @ . . . . .
. @ @ @ @ . . . . .
. . . . . . . . . .
首先,为了说明我应该实现的目标,让我看一看我的需求文档:
The algorithm operates according to the following pseudo-code:
* Visit the starting Location.
* Add this Location to the set.
* Enqueue the Location in the queue.
while (ArrayQueue<E> != empty( ))
{
Dequeue a Location(next) from the queue
For each neighbor of Location(next) which has
not yet been placed in the set, repeat:
* Visit the neighbor of Location(next).
* Add the neighbor of Location(next) to the Set.
* Enqueue the neighbor of Location(next)in the Queue.
}
我几乎肯定我已经正确地使用了他的算法,但是我无法弄清楚我做错了什么来获得我遇到的路径.我最头疼的是Maze对象的findPath()方法,我在下面已经介绍过了.我想我最大的问题是我做错了什么?我已经在这几天了,只是想不出来.任何帮助表示赞赏.我的代码如下:
我的迷宫的findpath方法
public void findPath()
{
Location startLocation = new Location(0, 0);
theMaze[startLocation.getRow()][startLocation.getColumn()].setVisited(true);
Location endLocation = new Location(6, 9);
Location cursor;
locationQueue.enqueue(startLocation);
locationSet.enter(startLocation);
while(!locationQueue.isEmpty())
{
cursor = locationQueue.dequeue();
if(cursor == endLocation)
break;
for(int i = 0; i < 4; i++)
{
Location temp = cursor.getLoc(i);
if(theMaze[cursor.getRow()][cursor.getColumn()].validDirection(i) && (!locationSet.isElement(temp)) && !(theMaze[temp.getRow()][temp.getColumn()].isVisited()))
{
cursor = cursor.getLoc(i);
theMaze[cursor.getRow()][cursor.getColumn()].setVisited(true);
if(theMaze[cursor.getColumn()][cursor.getColumn()].getPathAmount() < 2)
{
cursor = startLocation;
continue;
}
locationSet.enter(cursor);
locationQueue.enqueue(cursor);
}
}
}
for(int i = 0; i < locationSet.size(); i++)
{
System.out.println("Row " + locationSet.get(i).getRow() + " Column " + locationSet.get(i).getColumn());
theMaze[locationSet.get(i).getRow()][locationSet.get(i).getColumn()].setPath();
}
for(int i = 0; i < theMaze.length; i++)
{
for(int j = 0; j < theMaze[i].length; j++)
{
System.out.print(theMaze[i][j].toString());
}
System.out.print("\n");
}
}
编辑:我的问题是与迷宫对象而不是其他类,所以我基本上清理.
解决方法:
你的基本算法是有缺陷的.您只需将单元格添加到路径中,但如果它们变成死角则不要删除它们.
这种问题最适合递归算法.
function findExit(gameMap, listOfVisitedCells, currentCell, solution)
listOfVisitedCells.add(currentCell);
for each gameMap.NeighbourOf(currentCell)
if neighbour not in listOfVisitedCells
solution.add(neighbour)
if (gameMap.isExit(neighbour)) {
return true;
}
if (findExit(gameMap, listOfVisitedCells, currentCell, solution)) {
return true;
}
solution.remove(neighbour);
}
}
// No neighbours of the current cell got to find the exit.
return false;
}
当然,这将探索地图深度优先,所以如果有几条路径是有效的,你不能保证找到最短的路径(使用Djikstra的算法).
更新:从审查您的代码:
很难在心理上调试如此多的代码行,并且SO无法与您选择的调试器共度时间,观察程序的实际状态与预期状态等等.不要期待太多,因为有限的代码量,SO更适合于具体的问题(“我希望这段代码可以做到这一点,但它没有,为什么”).
无论如何,这让我感到奇怪:
Location temp = cursor.getLoc(i);
if(theMaze[cursor.getRow()][cursor.getColumn()].validDirection(i) && (!locationSet.isElement(temp)) && !(theMaze[temp.getRow()][temp.getColumn()].isVisited()))
{
cursor = cursor.getLoc(i); <-- Why are you overwritting the current
<-- location when you have still not checked
<-- all the posible directions?
theMaze[cursor.getRow()][cursor.getColumn()].setVisited(true);
if(theMaze[cursor.getColumn()][cursor.getColumn()].getPathAmount() < 2)
{
cursor = startLocation;
continue;
}
locationSet.enter(cursor);
locationQueue.enqueue(cursor);
}
我敢打赌,这是不正确的.当然,可能隐藏了另一个问题,如果你自己调试它来找到不能按预期工作的片段(然后,如果需要,在SO中寻求帮助),它会更好(并提供更多经验).
内容总结
以上是互联网集市为您收集整理的Java迷宫解决方案 – 我从未如此困惑过全部内容,希望文章能够帮你解决Java迷宫解决方案 – 我从未如此困惑过所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。