java - Find Shortest Path in a Maze with Recursive Algorithm -

i made little recursive algorithm find solution maze in following format

###s### ##___## ##_#_## #__#_## #e___## 

where '#' represents wall, , '_' represents open space (free move through). 's' represents start location, 'e' represents end location.

my algorithm works fine, i'm wondering how modify work shortest path.

/**  * findpath()  *   * @param location - point search  * @return true when maze solution found, false otherwise  */ private boolean findpath(point location) {     // have reached end point, , solved maze     if (location.equals(maze.getendcoords())) {         system.out.println("found path length: " + pathlength);         maze.setmazearray(mazearray);         return true;     }      arraylist<point> possiblemoves = new arraylist<point>();     // move right     possiblemoves.add(new point(location.x + 1, location.y));     // down move     possiblemoves.add(new point(location.x, location.y - 1));     // move left     possiblemoves.add(new point(location.x - 1, location.y));     // move     possiblemoves.add(new point(location.x, location.y + 1));      (point potentialmove : possiblemoves) {         if (spaceisfree(potentialmove)) {             // move free space             mazearray[potentialmove.x][potentialmove.y] = currentpathchar;             // increment path characters alphabet             if (currentpathchar == 'z')                 currentpathchar = 'a';             else                 currentpathchar++;             // increment path length             pathlength++;              // find next path traverse             if (findpath(potentialmove)) {                 return true;             }              // backtrack, route doesn't lead end             mazearray[potentialmove.x][potentialmove.y] = maze.space_char;             if (currentpathchar == 'a')                 currentpathchar = 'z';             else                 currentpathchar--;             // decrease path length             pathlength--;         }     }      // previous space needs make move     // return false if maze cannot solved.     return false; } 

in first block find path , break out. char[][] array path written on set well, later printed out result.

it works well, i'm wondering best way modify not break out after finds first successful path, keep going until finds shortest possible path.

i tried doing this, modifying findpath() method , adding shortestpath , hasfoundpath variable. first indicating length of shortest path found far, , hasfoundpath variable indicating whether or not have found path.

    // have reached end point, , solved maze     if (location.equals(maze.getendcoords())) {         system.out.println("found path length: " + pathlength);         // path shorter previous?         if (hasfoundpath && pathlength < shortestpathlength) {             maze.setmazearray(mazearray);             shortestpathlength = pathlength;         } else if (!hasfoundpath) {             hasfoundpath = true;             maze.setmazearray(mazearray);             shortestpathlength = pathlength;                     }         //return true;     } 

but haven't been able set mazearray correct values of shortest path may find.

any guidance appreciated :) thanks

spaceisfree() method makes sure up/left/down/right coordinates valid before moving them. makes sure char '_' or 'e' , isn't out of bounds.

your code appears perform depth-first search (dfs). find shortest path want switch breadth-first search (bfs). it's not can adding few variables existing code. require rewriting algorithm.

one way convert dfs bfs rid of recursion , switch using explicit stack keep track of nodes you've visited far. each iteration of search loop, (1) pop node off stack; (2) check if node solution; , (3) push each of children onto stack. in pseudo code, looks like:

depth-first search

stack.push(startnode)  while not stack.isempty:     node = stack.pop()      if node solution:         return     else:         stack.pushall(node.children) 

if switch stack queue implicitly become bfs, , bfs naturally find shortest path(s).

breadth-first serarch

queue.add(startnode)  while not queue.isempty:     node = queue.remove()      if node solution:         return     else:         queue.addall(node.children) 

a couple of additional notes:

1. the above algorithms suitable trees: mazes don't have loops. if mazes have loops you'll need make sure don't revisit nodes you've seen. in case, you'll need add logic keep track of visited nodes , avoid adding them onto stack/queue second time.

2. as written, these algorithms find target node don't remember path got them there. adding exercise reader.