Java:将DFS运行随机化以建立迷宫的麻烦 [英] Java: Trouble randomizing a DFS run to build a maze
本文介绍了Java:将DFS运行随机化以建立迷宫的麻烦的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我在随机化从节点到其邻居的访问时遇到麻烦，很少访问整个图(在此测试中为4x4的MxN数组)，在这里我没有做错什么.
I'm having trouble randomizing the visit from a node to its neighbors, rarely is the whole graph (a MxN array, in this test 4x4) visited, I don't get what I'm doing wrong here.
import java.util.ArrayList;
class IJ {
int i;
int j;
IJ (int i,int j){
i = this.i;
j= this.j;
}
}
class Graph {
int M;
int N;
int adjacencyMatrix[][];
ArrayList <IJ> orderOfVisits;
Graph(int M,int N){
this.M=M;
this.N=N;
adjacencyMatrix=new int[M][N];
for (int i=0; i<M; i++)
for (int j=0;j<N;j++){
adjacencyMatrix[i][j]=-1; //mark all vertices as not visited
}
orderOfVisits = new ArrayList<IJ>();
}
String northOrEast () {
double lottery = Math.random();
if (lottery>0.5D) {return "north";}
else {return "south";}
}
String southOrEastOrNorth() {
double lottery=Math.random();
if (lottery<=0.33D){
return "south";
}
else if ((lottery > 0.33D) && (lottery <= 0.66D)) {
return "east";
}
else if(lottery > 0.66D)
{
return "north";
}
System.out.println("method sEn has returned null ");
return null;
}
String southOrEast(){
double lottery = Math.random();
if (lottery>0.5D) {return "south";}
else {return "east";}
}
String southOrEastOrWest() {
double lottery=Math.random();
if (lottery<=0.33D){
return "south";
}
else if ((lottery > 0.33D) && (lottery <= 0.66D)) {
return "east";
}
else if(lottery > 0.66D)
{
return "west";
}
System.out.println("method sEw has returned null ");
return null;
}
String southOrWest(){
double lottery = Math.random();
if (lottery>0.5D) {return "south";}
else {return "west";}
}
String southOrNorthOrWest() {
double lottery=Math.random();
if (lottery<=0.33D){
return "south";
}
else if ((lottery > 0.33D) && (lottery <= 0.66D)) {
return "north";
}
else if(lottery > 0.66D)
{
return "west";
}
System.out.println("method sNw has returned null ");
return null;
}
String northOrWest(){
double lottery = Math.random();
if (lottery>0.5D) {return "north";}
else {return "west";}
}
String eastOrNorthOrWest() {
double lottery=Math.random();
if (lottery<=0.33D){
return "east";
}
else if ((lottery > 0.33D) && (lottery <= 0.66D)) {
return "north";
}
else if(lottery > 0.66D)
{
return "west";
}
System.out.println("method eNw has returned null ");
return null;
}
String any() {
double lottery=Math.random();
if (lottery<=0.25D){
return "east";
}
else if ((lottery > 0.25D) && (lottery <= 0.50D)) {
return "north";
}
else if ((lottery > 0.5D) && (lottery <= 0.75D)) {
return "south";
}
else if(lottery > 0.75D)
{
return "west";
}
System.out.println("method any has returned null ");
return null;
}
String goWhere (boolean northValid, boolean southValid, boolean eastValid, boolean westValid, int i, int j){
//border cases
//left lower corner, only north and east are valid
if ((northValid==true) && (southValid==false) &&(eastValid==true) && (westValid==false))
{return northOrEast();}
//left border:
if ((northValid==true) && (southValid==true) && (eastValid==true) && (westValid==false))
{return southOrEastOrNorth();}
//upper left corner, only south and east are valid
if ((northValid==false) && (southValid==true) && (eastValid==true) && (westValid==false))
{return southOrEast();}
//upper border
if ((northValid==false) && (southValid==true) && (eastValid==true) && (westValid==true))
{return southOrEastOrWest();}
//upper right corner
if ((northValid==false) && (southValid==true) && (eastValid==false) && (westValid==true))
{return southOrWest();}
//right border
if ((northValid==true) && (southValid==true) && (eastValid==false) && (westValid==true))
{return southOrNorthOrWest();}
//lower right corner
if ((northValid==true) && (southValid==false) && (eastValid==false) && (westValid==true))
{return northOrWest();}
//bottom border
if ((northValid==true) && (southValid==false) && (eastValid==true) && (westValid==true))
{return eastOrNorthOrWest();}
//middle
if ((northValid==true) && (southValid==true) && (eastValid==true) && (westValid==true))
{return any();}
System.out.println("go where a llegado a retornar null");
return null;
}
void DFS(int i, int j){ // i,j identifies the vertex
boolean northValid= false;
boolean southValid= false;
boolean eastValid = false;
boolean westValid = false;
int iNorth, jNorth;
int iSouth, jSouth;
int iEast, jEast;
int iWest, jWest;
iNorth=i-1;
if (!(iNorth<0)) northValid=true;
iSouth=i+1;
if(!((iSouth)>=M)) southValid=true;
jEast=j+1;
if(!((jEast)>=N)) eastValid=true;
jWest= j-1;
if (!(jWest<0)) westValid=true;
if (adjacencyMatrix[i][j]==-1){ //if the vertex is unvisited
adjacencyMatrix[i][j]=0; //mark the vertex as visited
IJ ij = new IJ(i,j);
orderOfVisits.add(ij); //add the vertex to the visit list
System.out.println("Visit i,j: " + i +" " +j);
//boolean wentNorth = false;
//boolean wentSouth=false;
//boolean wentEast = false;
//boolean wentWest = false;
// if (where!=null)
for (int rows=i; rows<M; rows++)
for (int cols=j; cols<N; cols++){
//normal DFS
String where = goWhere(northValid, southValid, eastValid, westValid, i,j);
if (where.equals("north"))
{
DFS(iNorth,j);
//wentNorth=true;
}
if (where.equals("south")){
DFS(iSouth,j);
}
if(where.equals("east")){
DFS(i, jEast);
}
if (where.equals("west")){
DFS(i,jWest);
}
// if(northValid)
// {
// DFS(iNorth,j);
// }
//
// if(southValid){
// DFS(iSouth,j);
// }
//
// if(eastValid){
// DFS(i, jEast);
// }
//
// if(westValid){
// DFS(i,jWest);
// }
}
}
// boolean southValid;
// int iSouth, jSouth;
// iSouth=i+1; jSouth=j;
// if (iSouth>=M){
// southValid=false;
// }
// else {
// southValid=true;
// }
//
// boolean southUnvisited;
// if ((southValid)&&
// (adjacencyMatrix[iSouth][jSouth]==-1)){
// southUnvisited=true;
// }
// else{
// southUnvisited=false;
// }
//
//
// boolean northValid;
// int iNorth, jNorth;
// iNorth=i-1; jNorth=j;
//
// if(iNorth<0){
// northValid=false;
// }
//
// else{
// northValid=true;
// }
//
// boolean northUnvisited;
// if ((northValid)
// &&(adjacencyMatrix[iNorth][jNorth]==-1)){
// northUnvisited=true;
// }
// else {
// northUnvisited=false;
// }
//
// boolean westValid;
// int iWest, jWest;
// iWest =i; jWest=j-1;
// if (jWest<0){
// westValid=false;
// }
// else {
// westValid=true;
// }
//
// boolean westUnvisited;
//
//
// if ((westValid)&&(adjacencyMatrix[iWest][jWest]==-1))
// {
// westUnvisited=true;
// }
// else {
// westUnvisited=false;
// }
//
//
//
// boolean eastValid;
// int iEast, jEast;
// iEast=i; jEast=j+1;
// if (jEast<0){
// eastValid=false;
// }
// else{
// eastValid=true;
// }
//
// boolean eastUnvisited;
// if (eastValid&&
// (adjacencyMatrix[iEast][jEast]==-1)){
// eastUnvisited=true;
// }
// else {
// eastUnvisited=false;
// }
//
// double lottery = Math.random();
//
//
//
// boolean canVisitNorth=northUnvisited&&northValid;
// boolean canVisitSouth=southUnvisited&&southValid;
// boolean canVisitEast=eastUnvisited&&eastValid;
// boolean canVisitWest=westUnvisited&&westValid;
//
// if (lottery>0.75D)
// {
//
// if(canVisitNorth)
// DFS(iNorth, jNorth);
//
// else if(canVisitSouth)
// DFS(iSouth, jSouth);
//
// else if(canVisitEast)
// DFS(iEast, jEast);
//
// else if(canVisitWest)
// DFS(iWest, jWest);
//
// }
//
// else if(lottery < 0.25D)
// {
//
// if(canVisitSouth)
// DFS(iSouth, jSouth);
//
// else if(canVisitNorth)
// DFS(iNorth, jNorth);
//
// else if(canVisitEast)
// DFS(iEast, jEast);
//
// else if(canVisitWest)
// DFS(iWest, jWest);
//
//
// }
//
// else if((lottery >= 0.25D)&&
// (lottery<0.5D))
// {
// if(canVisitEast)
// DFS(iEast, jEast);
//
// else if(canVisitSouth)
// DFS(iSouth, jSouth);
//
// else if(canVisitNorth)
// DFS(iNorth, jNorth);
//
// else if(canVisitWest)
// DFS(iWest, jWest);
//
//
// }
//
// else if((lottery >= 0.5D)&&
// (lottery<0.75D))
// {
//
// if(canVisitWest)
// DFS(iWest, jWest);
//
// else if(canVisitEast)
// DFS(iEast, jEast);
//
// else if(canVisitSouth)
// DFS(iSouth, jSouth);
//
// else if(canVisitNorth)
// DFS(iNorth, jNorth);
//
//
// }
} //end DFS
//
}
public class Main {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
Graph theGraph = new Graph(3,3);
theGraph.DFS(0,0);
}
}
这段代码给我的输出是:
this code is giving me output like:
Visit i,j: 0 0
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 3
Visit i,j: 1 0
Visit i,j: 2 0
即使我正在验证下一步动作的位置(通过布尔值southValid，eastValid等)
even though I'm validating the position of the next move (via the booleans southValid, eastValid, etc.)
推荐答案
我建议更改您的goWhere方法，因为在选择走哪条路时，所有方向的权重均相等.
I have a suggestion to change your goWhere method, since all directions all directions are equally weighted when it comes to choosing which way to go.
String goWhere (boolean northValid, boolean southValid, boolean eastValid, boolean westValid){
java.util.Random r = new java.util.Random();
ArrayList<String> valids = new ArrayList<String>();
if(northValid) { valids.add("north"); }
if(southValid) { valids.add("south");}
if(eastValid) { valids.add("east"); }
if(westValid) { valids.add("west"); }
if (valids.size() > 1) {
int rand = r.nextInt(valids.size());
return valids.get(rand);
} else { return null; }
}
我认为您可以摆脱其他测向仪方法.我认为在i或j不在矩阵边界处仍存在一些错误，但是我认为这种方法更改可能会消除一些复杂性.请参阅上面有关在您的"northOrEast"方法中返回南"的注释.
I think you can get rid of the other direction finder methods. I think there are some bugs still in there where i or j is outside the matrix boundary, but I think this method change might remove some complications. See my note above about returning "south" in your "northOrEast" method.
另外，请考虑使用常量作为方向.这将有助于防止错别字，并且编译器将其捕获.
Also, consider using constants for your directions. It will help prevent typos and the compiler will catch it.
public static final int NORTH = 0;
public static final int SOUTH = 1;
public static final int EAST = 2;
public static final int WEST = 3;
然后，执行以下操作，而不是进行字符串比较:
Then, instead of doing string comparisons, do:
if (Graph.EAST == where) { ... }
我认为设置您的有效布尔值存在问题. 代替:
I think there is a problem setting your valid booleans. Instead of:
if (!(iNorth<0)) northValid=true;
尝试:
northValid = (iNorth >= 0);
在North情况下不一定存在问题，但是如果某项小于其他项，则对于false的测试会有些混乱.
There's not necessarily a problem in the North case, but it's a little confusing testing for false if something is less than something else.
与M或N进行比较时，您使用>表示无效.我认为是South，例如，如果> = M，则无效.或者只是这样做:
When you're comparing to M or N, you are using > to indicate it being invalid. I think South, for example if invalid if it's >= M. Or just do:
southValid = (iSouth < M);
这篇关于Java:将DFS运行随机化以建立迷宫的麻烦的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
