日期:2014-05-20  浏览次数:20770 次

随机迷宫算法--简单错误
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;
}
}


不知道出错在哪里,有时候可以生成 却有时候又不能生成,大家帮忙看看~~~谢谢~

------解决方案--------------------
你这样搜索的思想就是错误的,你现在使用是在一个点上取四个随机数来决定下一步的方向,但你不能保证这几个随机数是否相同。假是在迷宫入口处即(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>();//定义一个队列