我正在尝试创建某种没有鬼的 PacMan 模拟，它由 6x10 的矩阵表示。我已经实现了 BFS 的一个变体，我在两个正在搜索的节点之间递归调用算法，它给了我令人满意的结果。然而，我真正想做的是在每次吃豆人运动后打印迷宫的状态，吃豆人用“2”表示，盒子用“3”表示，墙壁用“1”表示，自由方式用“0”表示。我试图将每个节点的符号更改为“2”，对于每个新动作，然后将其父节点符号更改为“0”，但这并没有按预期工作，它给了我一些奇怪的结果。
我想我知道问题出在哪里，尽管我仍然没有设法解决它。所以，对于每个探索过的节点，我将它放入一个列表中（本可以做得更高效，这只是第一次运行），问题是它不会访问已经访问过的节点，所以它无法打印 PacMan 运动的每一步。我已经尝试在检查节点标志之前更改它们是否已经被探索过，尽管效果不佳。
我想这听起来相当令人困惑，所以我将尝试绘制一些我希望它看起来如何的步骤。
这是一个起始迷宫：
1 1 1 1 1 1 1 1 1 1
2 0 0 3 1 0 0 0 3 1
1 3 1 1 1 3 1 1 0 1
1 0 1 0 3 0 1 1 3 1
1 3 0 3 1 3 0 1 0 1
1 1 1 1 1 1 0 3 0 1
这就是解决方案的样子：
1 1 1 1 1 1 1 1 1 1
0 0 0 0 1 0 0 0 0 1
1 0 1 1 1 2 1 1 0 1
1 0 1 0 0 0 1 1 0 1
1 0 0 0 1 0 0 1 0 1
1 1 1 1 1 1 0 0 0 1
现在，我希望它为 pacman 采取的每一步打印一个新的迷宫：
1 1 1 1 1 1 1 1 1 1///////1 1 1 1 1 1 1 1 1 1//////1 1 1 1 1 1 1 1 1 1
0 2 0 3 1 0 0 0 3 1///////0 0 2 3 1 0 0 0 3 1//////0 0 0 2 1 0 0 0 3 1
1 3 1 1 1 3 1 1 0 1///////1 3 1 1 1 3 1 1 0 1//////1 3 1 1 1 3 1 1 0 1
1 0 1 0 3 0 1 1 3 1/////// 。
1 3 0 3 1 3 0 1 0 1/////// 。
1 1 1 1 1 1 0 3 0 1///////
/////////
1 1 1 1 1 1 1 1 1 1
0 0 2 0 1 0 0 0 3 1
1 3 1 1 1 3 1 1 0 1
依此类推，抱歉图片混乱，我只写了前 3 行。
这是一个函数和所有相关函数的代码，也是完整源代码的链接。我也发表了一些评论，并阻止了我尝试过的最后一件事。任何建议都可以。谢谢。
源代码：http ://www.speedyshare.com/DkXgQ/BreadthFirstSearch.rar
public static boolean breadthFirstSearch(Node root, Node[][] mazeGrid, int boxCounter) {
root.setSign("0");
toExplore.add(root);
int[] x_coord = { 0, 1, 0, -1};
int[] y_coord = {1, 0, -1, 0 };
while(!toExplore.isEmpty()) {
Node node = toExplore.poll();
explored.add(node);
//for moving!!!!!
/*if(node.getParent() != null) {
node.getParent().setSign("0");
}
node.setSign("2");*/
for(int i = 0; i < 4; i++) {
//new coordinates
int x = node.getX_coord() + x_coord[i];
int y = node.getY_coord() + y_coord[i];
if(x >= 0 && y >=0 && x < 6 && y < 10) {
Node child = maze[x][y];
//show moving steps!!!!!
/*System.out.println("\nStep : \n");
for(int xx = 0; xx < 6; xx++) {
for(int j = 0; j < 10; j++) {
System.out.print(maze[xx][j].getSign() + " ");
}
System.out.print("\n");
}*/
//is current node explored?
if(!isExplored(child) && !child.getSign().equals("1")) {
//save parent for the shortest path between root and node being searched for
child.setParent(node);
//have we found a box?
if(child.getSign().equals("3")) {
System.out.println("Node number " + boxCounter + " has been found : " +
child.getX_coord() + " , " + child.getY_coord());
//counter for rest of the existing boxes
boxCounter--;
Node temp = child;
printPath(temp);
//this is used for path printing between two nodes, and not from the main root and last node being found
temp.setParent(null);
//just jumping from box to box, so I can print where the last position on the maze is
child.setSign("2");
if(boxCounter != 0) {
//if there are more boxes on the maze, recursion
breadthFirstSearch(child, mazeGrid, boxCounter);
}
return true;
}
if(child.getSign().equals("0")) {
//new node to explore
toExplore.add(child);
}
}
}
}
}
System.out.println("Node not found!");
return false;
}
public static void printPath(Node child) {
while(child.getParent() != null) {
path.add(0, child);
child = child.getParent();
}
System.out.println("Shortest path : ");
for(Node n: path) {
System.out.println(n.getX_coord() + " - " + n.getY_coord());
}
path.clear();
}
public static boolean isExplored(Node node) {
for(Node n : explored) {
if(n.getX_coord() == node.getX_coord() && n.getY_coord() == node.getY_coord()) {
return true;
}
}
return false;
}