[Rich516516]

I had to make both types of maze traversal programs using java, I found the recursion form was much easier, now im trying to do the maze traversal using stacks, ive tried modifying my switch states, tried modifying my location class to contain a variable to tell how many times that location has been checked and I just cannot get it to work properly, it either goes around in a circle and fills my stack, or it will empty to stack before its done. Heres the code for my location class

package PartA;

public class Location{
  
  public int popped,state,x,y=0;
  char item;
 
  public Location(Map maze,char[][] map, int inx, int iny){
    
    x=inx;
    y=iny;
    if (x>=0 && x<maze.width && y>=0 && y<maze.height){
    item=map[x][y];
    }   
  }
  
  
}

Heres the actual maze class, the map class is functioning properly as I use the same one in the recursion program.

 package PartA;

import Collections.*;

public class Maze{
  char[][] maze;
  Map map;
  Location loc;
  Stack<Location> locStack;
  int c;
  int startx,starty,x,y;
  
  public Maze(){
    map=new Map();
    locStack=new ConStack<Location>(1000);
    map.drawMap();
    map.printMap();
    startx=map.startx;
    starty=map.starty;

    System.out.println("Starting position ("+startx+","+starty+")");
    loc=new Location(map,map.map,startx,starty);
    locStack.push(loc);

    while (locStack!=null){
      loc=locStack.pop();
      loc.state++;
      x=loc.x;
      y=loc.y;
      map.printMap();
      switch (loc.state){
        case 0:
          locStack.push(loc);
          if (x>=0 && x<map.width && y>=0 && y<map.height){
          loc=new Location(map,map.map,x+1,y);
          loc.state++;
          locStack.push(loc);
          }
        case 1:
          locStack.push(loc);
          if (x>=0 && x<map.width && y>=0 && y<map.height){
          loc=new Location(map,map.map,x,y+1);
          loc.state++;
          locStack.push(loc);
          }
        case 2:
          locStack.push(loc);
          if (x>=0 && x<map.width && y>=0 && y<map.height){
          loc=new Location(map,map.map,x-1,y);
          loc.state++;
          locStack.push(loc);
          }
        case 3:
          locStack.push(loc);
          if (x>=0 && x<map.width && y>=0 && y<map.height){
          loc=new Location(map,map.map,x,y-1);
          loc.state++;
          locStack.push(loc);
          }
        case 4:
          loc=locStack.pop();
          if (x>=0 && x<map.width && y>=0 && y<map.height && loc.item!='#'){
          map.map[loc.x][loc.y]='.';
          }
    }
  }
map.printMap();
  }
  
   
  public static void main ( String[] args ) { new Maze(); };
}

Heres an example of a maze in which im trying to solve is in the attachments

Its stored in a 2d char array and starts at location 1,1 and has to reach E using stacks, and backtracking functions and marks the proper path with * and position tried but failed with .

Thanks for your help in advance, not looking for code but more of help on how to reach a solution, examples of code would be helpful but not needed as I want to learn and not just think I understand.

Attached File(s)

•  maze1.txt (114bytes)
  Number of downloads: 135

[macosxnerd101]

If you treat your Maze as a Tree, you can apply a depth-first traversal. If you model recursions using Tree diagrams, they will be evaluated in a depth-first manner on the call stack. I cover the Iterator pattern with Trees in my tutorial, if you want to check it out. Also, you might also want to check out this tutorial for more overview on recursion, stacks, and trees.

Hope this helps some.

[Rich516516]

That helped me understand the stacks better, thanks, but still having the problem of it going in a circle because it goes back, mostly because backtracking can be done but only 4 times before that location is canceled and that's the part im having problems with.

[Rich516516]

Also heres my pseudo code if that helps all in which im trying to get in java

push start position onto the stack
while stack is not empty and top item on the stack isnt E (exit)
considering top stack postion
if theres another direction possible
make another choice in direction form the position on the top of the stack
push the new position onto the stack
else
pop the current position

[macosxnerd101]

You could do one of two things. First, store a List<Location> to track Locations you have already visited (pushed onto the Stack). Basically, if a path doesn't pan out, you have that location stored so you won't revisit it later beyond the backtracking. The other thing I did was use my StackMap snippet to store a Node (for you this would be a Location), as well as the index. That way, I knew where in the Tree I was and could better determine which child Node to visit next.

[Rich516516]

macosxnerd101, on 07 April 2011 - 08:21 PM, said:

You could do one of two things. First, store a List<Location> to track Locations you have already visited (pushed onto the Stack). Basically, if a path doesn't pan out, you have that location stored so you won't revisit it later beyond the backtracking. The other thing I did was use my StackMap snippet to store a Node (for you this would be a Location), as well as the index. That way, I knew where in the Tree I was and could better determine which child Node to visit next.

I used the first option and it worked great, thanks a lot , now I know why we use recursion, much simpler to code, but also depending on what though the run time can be very long, or even stack over flow, but for this simple problem recursion definitely work better

[macosxnerd101]

Glad I could help!