随机迷宫算法--简单错误
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>();//定义一个队列
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;
}
}
