Java learning maze solver

Question

I have been working on some code to guide a 'robot' through a maze with multiple dead ends and 1 correct path to the goal like this:

I have used a stack to record the direction the robot is facing the first time it reaches a square with 3 or 4 possible exits and if all adjacent squares have already been visited, used pop() to make the robot return from the direction it first came from (opposite to direction arrived). At the end of the run the stack contains the direction arrived at all squares on the route to the target. Following the opposite directions of the stack would take the robot from the goal back to the start point. I am struggling to find out how to use this stack so that on the next run the robot will take the optimal path to reach the goal.

Some of my code:

private int pollRun = 0; // Incremented after each pass
private int explorerMode; // 1 = explore, 0 = backtrack

public void exploreControl(IRobot robot) {

  byte exits = nonwallExits(robot);
  int direction;

  switch (exits) { //passes control to respective method
    case 1: direction = deadEnd(robot);   break;
    case 2: direction = corridor(robot); break;
    case 3: direction = junction(robot); break;
    default: direction = crossroads(robot); break;
  }

  if (exits == 1) {explorerMode = 0;}

  robot.face(direction); 

  pollRun++;

}

public void backtrackControl(IRobot robot) {

  byte exits = nonwallExits(robot);
  int direction = IRobot.CENTRE;

  switch (exits) { //passes control to respective method
    case 1: direction = deadEnd(robot);   break;
    case 2: direction = corridor(robot); break;
    default: direction = junction(robot); break; // do nothing
  }

  if (exits > 2) {
    if (passageExits(robot) > 0){
      exploreControl(robot);
      explorerMode = 1;
      pollRun++;
      return;
    } else {
      robot.setHeading(st.pop());
      robot.face(IRobot.BEHIND);
      pollRun++;
      return;
    }

  }

    robot.face(direction); 

  pollRun++;

}

public void optimal(IRobot robot) {

  byte exits = nonwallExits(robot);
  int direction;
  int heading;

  for(int i = 0; i < st.size(); i++) {
    stNew.push(st.pop());
  }

  if (exits < 3) {

    switch (exits) { //passes control to respective method
      case 1: direction = deadEnd(robot);   break;
      default: direction = corridor(robot); break;
    }

    robot.face(direction);

  } else {
    robot.setHeading(stNew.pop());
  }

}

public void controlRobot(IRobot robot) {

  if ((robot.getRuns() == 0) && (pollRun == 0)) {
    robotData = new RobotData(); //reset the data store
    explorerMode = 1;
  }

  if (robot.getRuns() = 1) {
    optimal(robot);
    return;
  }

  if (robot.getRuns() <= 0 && (nonwallExits(robot) >= 3)
      && (beenbeforeExits(robot) <= 0)) {
    st.push(robot.getHeading());
  }

  if (explorerMode == 1) {
    exploreControl(robot);
  } else {backtrackControl(robot);}

}

The optimal method shows my attempt at solving it, however all it does is cause the robot to head straight at every junction

For example this maze,

enter image description here

Would leave me with the stack: EAST, EAST, SOUTH, SOUTH, EAST, SOUTH, SOUTH, EAST, EAST, SOUTH, SOUTH, EAST, EAST, EAST, SOUTH, EAST, SOUTH

I don't think a stack is the right approach. To find the optimal solution, you'll want to construct a complete graph of the maze then do a breadth first search. — Mason Bryant
That is one of the possible solutions to the problem but I have been told that it is much simpler to use stacks. — Shiftz
If you build a complete graph of the maze it makes it an unreal scenario, you need to assume the maze graph will be unknown to him, think of a physical robot on a maze trying to find the exit, it sounds more like in a real scenario you would use depth search and walk the possible paths recording the discovered paths along the way. — guilhebl
I have answered a similar question before, which only use stack. Dunno if it helps: stackoverflow.com/a/22187419/395202 — Adrian Shum

sprinter sprinter · Accepted Answer · 2014-12-04T23:54:45

It is true that this problem can be solved using a stack and an exhaustive search of the maze. There are more efficient methods but this one will work.

It's fairly difficult to know how your code is intended to function because you've only given a part of it. However in general these sorts of exhaustive searches make heavy use of recursion - which is a very common use case for stacks. I assume yours does the same though I can't see that code in the sample you've provided.

Here is some sample psuedo code for an exhaustive 'depth first' search. This code will end up with all possible solutions rather than just one. You should have a method that looks something like this in your code.

void findPath(Stack currentPath) {
    if (currentPath.peek() == goal) {
        solutions.add(currentPath);
    } else {
        for (Position next: currentPath.openPositions()) {
            currentPath.push(next);
            findPath(currentPath);
            currentPath.pop();
        }
    }
}

The 'openPositions' method needs to explicitly stop any doubling back by looking at the current path - in other words it shouldn't return any positions that are already in the currentPath stack or you will end up with infinite recursion.

Because this finds all possible solutions you would then need to find the one with the shortest length as the optimal path. In your case it seems the mazes only have one path so you can exit as soon as you have found a path.

A final note: you've tried to mix the task of setting the direction the robot needs to turn with the task of finding a path through the maze. I recommend keeping these separate. Use the algorithm above to find a path (or a more efficient one such as a*) and then once you have paths walk through it to determine the list of directions for the robot.

Java learning maze solver

1 Answers