depth first search - Java: Trouble randomizing a DFS run to build a maze -
i'm having trouble randomizing visit node neighbors, whole graph (a mxn array, in test 4x4) visited, don't i'm doing wrong here.
import java.util.arraylist; class ij { int i; int j; ij (int i,int j){ = 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]; (int i=0; i<m; i++) (int j=0;j<n;j++){ adjacencymatrix[i][j]=-1; //mark vertices 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 has returned null "); return null; } string gowhere (boolean northvalid, boolean southvalid, boolean eastvalid, boolean westvalid, int i, int j){ //border cases //left lower corner, north , east 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, south , east 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 llegado retornar null"); return null; } void dfs(int i, int j){ // i,j identifies 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 vertex unvisited adjacencymatrix[i][j]=0; //mark vertex visited ij ij = new ij(i,j); orderofvisits.add(ij); //add vertex visit list system.out.println("visit i,j: " + +" " +j); //boolean wentnorth = false; //boolean wentsouth=false; //boolean wenteast = false; //boolean wentwest = false; // if (where!=null) (int rows=i; rows<m; rows++) (int cols=j; cols<n; cols++){ //normal dfs string = 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 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 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 even though i'm validating position of next move (via booleans southvalid, eastvalid, etc.)
i have suggestion change gowhere method, since directions directions equally weighted when comes choosing way 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 think can rid of other direction finder methods. think there bugs still in there or j outside matrix boundary, think method change might remove complications. see note above returning "south" in "northoreast" method.
also, consider using constants directions. prevent typos , compiler 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 problem setting valid booleans. instead of:
if (!(inorth<0)) northvalid=true; try:
northvalid = (inorth >= 0); there's not problem in north case, it's little confusing testing false if less else.
when you're comparing m or n, using > indicate being invalid. think south, example if invalid if it's >= m. or do:
southvalid = (isouth < m);
Comments
Post a Comment