recursion - Maze solving algorithm Java (Recursive) -
i've got stuck on homework assignment due end of week.
for stupid reason recursive traverser not stopping when hits end of maze ('e'), keeps on going.
here reader:
public class mainprog { public static void main(string[] args) { // name of file open. scanner reader = new scanner(system.in); // reading system.in system.out.println("enter name of textfile read ( add .txt): "); string filename = reader.next(); char temp; // reference 1 line @ time string line = null; int count = 1; int heightcounter = 0; try { // filereader reads text files in default encoding. filereader filereader = new filereader(filename); // wrap filereader in bufferedreader. bufferedreader bufferedreader = new bufferedreader(filereader); int height = 0, width = 0, startx = 0, starty = 0, endx = 0, endy= 0; char [][] maze = null; while((line = bufferedreader.readline()) != null) { system.out.println(line); switch (count) { case (1): height = integer.parseint(line.substring(0, line.indexof(' '))); width = integer.parseint((line.substring(line.indexof(' ')+1))); maze = new char [height][width]; break; case (2): temp = line.charat(0); starty = character.getnumericvalue(temp); temp = line.charat(2); startx = character.getnumericvalue(temp); break; case (3): endy = integer.parseint(line.substring(0, line.indexof(' '))); endx = integer.parseint((line.substring(line.indexof(' ')+1))); break; default: int counter = 0; (int iterator = 0; iterator < line.length(); iterator++){ if(line.charat(iterator) != ' '){ maze[heightcounter][counter] = line.charat(iterator); counter++; } } heightcounter++; break; } count++; } maze[starty][startx] = 's'; maze[endy][endx] = 'e'; mazecreator ma = new mazecreator(maze); ma.start(starty, startx); system.out.println(ma.result); // close files. bufferedreader.close(); system.out.println("height: " + height + " width: " + width); system.out.println("starty: " + starty + " startx: " + startx); system.out.println("endy: " + endy + " endx: " + endx); system.out.println(ma.result); } catch(filenotfoundexception ex) { system.out.println( "unable open file '" + filename + "'"); } catch(ioexception ex) { system.out.println( "error reading file '" + filename + "'"); // or this: // ex.printstacktrace(); } } } and here maze class:
package com.todai.first.project.testmaze; public class mazecreator { char [][] maze; char path = 'x'; char visited = 'y'; string result = ""; int starty, startx; public mazecreator (char[][] maze){ this.maze = maze; } public void start (int starty, int startx) { this.starty = starty; this.startx = startx; traverse(starty, startx); } private boolean isvalid (int row, int col){ boolean valid = false; if (row >= 0 && row < maze.length && col >= 0 && col < maze[row].length){ if (maze[row][col] == '0' || maze[row][col] == 'e' || maze[row][col] == path) { valid = true; } } return valid; } private boolean traverse (int row, int col) { system.out.println("i'm here: \t" + row +","+ col + "\t :: " + maze[row][col]); if (maze[row][col] == 'e'){ system.out.println("i won!"); result = mazetostring(); return true; } else{ if (maze[row][col] == path){ maze[row][col] = visited; } else { maze[row][col] = path; } if (isvalid(row+1, col)){ traverse(row+1, col); } if (isvalid(row-1, col)){ traverse(row-1, col); } if (isvalid(row, col+1)){ traverse(row, col+1); } if (isvalid(row-1, col-1)){ traverse(row, col-1); } return false; } } private string mazetostring(){ stringbuilder sb = new stringbuilder(); (int i=0; i< this.maze.length; i++) { (int j=0; j < this.maze[i].length; j++) { if (maze[i][j] == '1') { maze[i][j] = '#'; } sb.append(maze[i][j]); } sb.append("\n"); } maze[starty][startx] = 's'; return sb.tostring(); } } here output console (eclipse):
enter name of textfile read ( add .txt): small.txt 6 5 1 1 4 3 1 1 1 1 1 1 0 0 0 1 1 0 1 0 1 1 0 1 0 1 1 0 1 0 1 1 1 1 1 1 i'm here: 1,1 :: s i'm here: 2,1 :: 0 i'm here: 3,1 :: 0 i'm here: 4,1 :: 0 i'm here: 3,1 :: x i'm here: 4,1 :: x i'm here: 2,1 :: x i'm here: 1,1 :: x i'm here: 1,2 :: 0 i'm here: 1,3 :: 0 i'm here: 2,3 :: 0 i'm here: 3,3 :: 0 i'm here: 4,3 :: e won! i'm here: 2,3 :: x i'm here: 3,3 :: x i'm here: 4,3 :: e won! i'm here: 1,3 :: x i'm here: 2,2 :: # i'm here: 1,2 :: x i'm here: 2,2 :: x ##### #sxx# #y#y# #y#y# #y#e# ##### height: 6 width: 5 starty: 1 startx: 1 endy: 4 endx: 3 ##### #sxx# #y#y# #y#y# #y#e# ##### as guys can see keeps on recursively calling iteself after having found 'e'.
any clues?
after print i won!, return true, non of recursive calls check return value, of course don't stop. change calls check return value:
if (isvalid(row+1, col)) { if (traverse(row+1, col)) return true; } 
Comments
Post a Comment