随机迷宫算法--简单错误

Question

package test;import java.util.Random;
import java.util.Vector;
public class randomMaze1 {

public randomMaze1() {

}

//生成随机地图
public void generation(int map[][]) {
int i, j;
int s[] = new int[4]; for (i = 1; i <= 20; i++)
for (j = 1; j <= 20; j++)
map[i][j] = 3;//3为不可行走,四周为0  Vector<Node> list = new Vector<Node>();//定义一个队列
Node one;
one = new Node(1, 1);
list.add(one);

for(int k=0;k<4;k++){
s[k]=k;
} while (list.size() != 0) {

one = (Node) list.elementAt(0);//取出节点的坐标
i = one.i;
j = one.j;
map[i][j] = 5;//当前节点位置



for (int x = 0; x < 4; x++) {//使上下左右节点 随机顺序加入队列

this.randArray(s);

if (s[x]==0&&i + 1 < 21 && map[i + 1][j] == 3&&around(i+1,j,map)) {
one = new Node(i + 1, j);
list.add(one);
map[i + 1][j] = -1;//即将被访问
}
else if (s[x]==1&&i - 1 >= 1 && map[i - 1][j] == 3&&around(i-1,j,map)) {
one = new Node(i - 1, j);
list.add(one);
map[i - 1][j] = -1;
}
else if (s[x]==2&&j - 1 >= 1 && map[i][j - 1] == 3&&around(i,j-1,map)) {
one = new Node(i, j - 1);
list.add(one);
map[i][j - 1] = -1;
}
else if (s[x]==3&&j + 1 < 21 && map[i][j + 1] == 3&&around(i,j+1,map)) {
one = new Node(i, j + 1);
list.add(one);
map[i][j + 1] = -1;
}
}
map[i][j] = 4;
list.remove(0);
} }
public boolean around(int i,int j,int map[][]){//判断将压入队列节点的四周 是否存在将访问节点和已访问节点
if(i+1<=20){
if(map[i+1][j]==4||map[i+1][j]==-1) return false;
}
if(j+1<=20){
if(map[i][j+1]==4||map[i][j+1]==-1) return false;
}
if(i-1>=0){
if(map[i-1][j]==4||map[i-1][j]==-1) return false;
}
if(j-1>=0){
if(map[i][j-1]==4||map[i][j-1]==-1) return false;
}
return true;
}

public void randArray(int[] s) {//打乱数组顺序
int i, x, y;
for (i = 0; i < 4; i++)
s[i] = i; Random rand = new Random();
for (i = 0; i <= rand.nextInt(15) + 5; i++) {
x = rand.nextInt(4);
y = rand.nextInt(4);
if (x != y) {
s[x] = s[x] + s[y];
s[y] = s[x] - s[y];
s[x] = s[x] - s[y];
}
} }

public static  void main(String[] args){
int s[][]=new int[22][22];
randomMaze1 ran= new randomMaze1();
ran.generation(s);
for(int i=0;i<=21;i++){
for(int j=0;j<=21;j++)
System.out.print(s[i][j]+" ");
System.out.println();
}

}}class Node {//坐标节点类
public int i, j; public Node(int i, int j) {
this.i = i;
this.j = j;
}
}
不知道出错在哪里,有时候可以生成 却有时候又不能生成,大家帮忙看看~~~谢谢~

Answer 1

你这样搜索的思想就是错误的,你现在使用是在一个点上取四个随机数来决定下一步的方向,但你不能保证这几个随机数是否相同。假是在迷宫入口处即（1，1）点处取的随机数都为1或都为2，带个迷宫就只会打一个4。
你可以换一种思考方式，既然你不能决定随机数的取值，但你可以设置两个队列，即入口和出口各设一个队例，各两个队列使用相同的随机数同时“探路”。下面是修改后的程序：
import java.util.Random; 
import java.util.Vector; 
public class randomMaze1 { public randomMaze1() { } //生成随机地图 
public void generation(int map[][]) { 
int i, j,u,v; 
int s[] = new int[4]; for (i = 1; i  <= 20; i++) 
for (j = 1; j  <= 20; j++) 
map[i][j] = 3;//3为不可行走,四周为0  Vector <Node> list = new Vector <Node>();//定义一个队列 
Vector <Node> list2= new Vector <Node>();
Node one; 
Node two;
one = new Node(1, 1);
two = new Node(20,20);
list.add(one); 
list2.add(two);for(int k=0;k <4;k++){ 
s[k]=k; 
} while (list.size() != 0||list2.size()!=0) { i=0;j=0;
u=0;v=0;
for (int x = 0; x  < 4; x++) {//使上下左右节点 随机顺序加入队列 this.randArray(s); 
if(list.size()!=0){
one = (Node) list.elementAt(0);//取出节点的坐标
i = one.i; 
j = one.j; 
map[i][j] = 5;//当前节点位置 
if (s[x]==0&&i + 1  < 21 && map[i + 1][j] == 3&&around(i+1,j,map)) { 
one = new Node(i + 1, j); 
list.add(one); 
map[i + 1][j] = -1;//即将被访问 
} 
else if (s[x]==1&&i - 1 >= 1 && map[i - 1][j] == 3&&around(i-1,j,map)) { 
one = new Node(i - 1, j); 
list.add(one); 
map[i - 1][j] = -1; } 
else if (s[x]==2&&j - 1 >= 1 && map[i][j - 1] == 3&&around(i,j-1,map)) { 
one = new Node(i, j - 1); 
list.add(one); 
map[i][j - 1] = -1; } 
else if (s[x]==3&&j + 1  < 21 && map[i][j + 1] == 3&&around(i,j+1,map)) { 
one = new Node(i, j + 1); 
list.add(one); 
map[i][j + 1] = -1; }} 
if(list2.size()!=0){two = (Node) list2.elementAt(0);u = two.i;
v = two.j;
map[u][v] = 5;//当前节点位置 
if (s[x]==0&&u + 1  < 21 && map[u + 1][v] == 3&&around(u+1,v,map)) { 
one = new Node(u + 1, v); 
list.add(one); 
map[u + 1][v] = -1;//即将被访问 
} 
else if (s[x]==1&&u - 1 >= 1 && map[u - 1][v] == 3&&around(u-1,v,map)) { 
one = new Node(u - 1, v); 
list.add(one); 
map[u - 1][v] = -1; } 
else if (s[x]==2&&v - 1 >= 1 && map[u][v - 1] == 3&&around(u,v-1,map)) { 
one = new Node(u, v - 1); 
list.add(one); 
map[u][v - 1] = -1; } 
else if (s[x]==3&&v + 1  < 21 && map[u][v + 1] == 3&&around(u,v+1,map)) { 
one = new Node(u, v + 1); 
list.add(one); 
map[u][v + 1] = -1; } 
}
} 
if(list.size()!=0){
map[i][j] = 4; 
list.remove(0); }
if(list2.size()!=0){
map[u][v] = 4;
list2.remove(0);
}
}} 
public boolean around(int i,int j,int map[][]){//判断将压入队列节点的四周 是否存在将访问节点和已访问节点 
if(i+1 <=20){ 
if(map[i+1][j]==4 ||map[i+1][j]==-1) return false; 
} 
if(j+1 <=20){ 
if(map[i][j+1]==4 ||map[i][j+1]==-1) return false; 
} 
if(i-1>=0){ 
if(map[i-1][j]==4 ||map[i-1][j]==-1) return false; 
} 
if(j-1>=0){ 
if(map[i][j-1]==4 ||map[i][j-1]==-1) return false; 
} 
return true; 
} public void randArray(int[] s) {//打乱数组顺序 
int i, x, y; 
for (i = 0; i  < 4; i++) 
s[i] = i; Random rand = new Random(); 
for (i = 0; i  <= rand.nextInt(15) + 5; i++) { 
x = rand.nextInt(4); 
y = rand.nextInt(4); 
if (x != y) { 
s[x] = s[x] + s[y]; 
s[y] = s[x] - s[y]; 
s[x] = s[x] - s[y]; 
} 
} } public static  void main(String[] args){ 
int s[][]=new int[22][22]; 
randomMaze1 ran= new randomMaze1(); 
ran.generation(s); 
for(int i=0;i <=21;i++){ 
for(int j=0;j <=21;j++) 
System.out.print(s[i][j]+" "); 
System.out.println(); 
} } } class Node {//坐标节点类 
public int i, j; public Node(int i, int j) { 
this.i = i; 
this.j = j; 
} 
}