title: Problems with maze generation using a non-recursive backtracking algorithm
body: <p>I'm working on a game for Android where the explorable areas will be randomly generated. Right now I'm just trying to get the maze generated (with some ASCII art output so I can see it), and I've been at it for about 4-5 days now but I'm just stumped.</p>
  
  <p>I'm trying to use the "depth-first search" algorithm, and all the examples I could find use recursive backtracking. Since this is for Android and phones are relatively wimpy, the recursion quickly leads to a call stack overflow, which is why I'm trying to write my own algorithm using a stack for backtracking.</p>
  
  <p>I came up with this solution, using a MazeGenerator class and a MazeCell class.</p>
  
  <p>MazeGenerator:</p>
  
  <pre><code>package com.zarokima.mistwalkers.explore;
  
  import java.util.Random;
  import java.util.Stack;
  import org.anddev.andengine.util.path.Direction;
  import android.graphics.Point;
  
  public class MazeGenerator
  {
  private int x, y; // the dimensions of the maze
  private MazeCell[][] maze;
  private Random rand = new Random();
  private Stack&lt;MazeCell&gt; stack;
  
  public MazeGenerator(int x, int y)
  {
      this.x = x;
      this.y = y;
      generateMaze();
  }
  
  public void setSeed(long seed)
  {
      rand.setSeed(seed);
  }
  
  public void setSize(int x, int y)
  {
      this.x = x;
      this.y = y;
  }
  
  public String outputMazeText()
  {
      String output = new String();
      for (int i = 0; i &lt; y; i++)
      {
          // draw the north edge
          for (int k = 0; k &lt; x; k++)
          {
              output += maze[k][i].hasNeighbor(Direction.UP) ? "+   " : "+---";
          }
          output += "+\n";
          // draw the west edge
          for (int k = 0; k &lt; x; k++)
          {
              output += maze[k][i].hasNeighbor(Direction.LEFT) ? "    " : "|   ";
          }
          output += "|\n";
      }
      // draw the bottom line
      for (int k = 0; k &lt; x; k++)
      {
          output += "+---";
      }
      output += "+\n";
  
      return output;
  }
  
  public void generateMaze()
  {
      maze = new MazeCell[x][y];
      for (int i = 0; i &lt; x; i++)
      {
          for (int k = 0; k &lt; y; k++)
          {
              maze[i][k] = new MazeCell(i, k);
          }
      }
  
      MazeCell.setBounds(x, y);
  
      stack = new Stack&lt;MazeCell&gt;();
      stack.push(maze[0][0]);
      maze[0][0].setInMaze(true);
  
      while (!stack.isEmpty())
      {
          MazeCell currentCell = stack.peek();
  
          Direction[] possibleDirections = currentCell.getUncheckedDirections();
  
          if (possibleDirections.length == 0)
          {
              stack.pop();
              continue;
          }
  
          int dint = rand.nextInt(possibleDirections.length);
          Direction direction = possibleDirections[dint];
  
          MazeCell nextCell = null;
          Point position = currentCell.getPosition();
  
          switch (direction)
          {
              case UP:
                  nextCell = maze[position.x][position.y - 1];
                  break;
              case DOWN:
                  nextCell = maze[position.x][position.y + 1];
                  break;
              case LEFT:
                  nextCell = maze[position.x - 1][position.y];
                  break;
              case RIGHT:
                  nextCell = maze[position.x + 1][position.y];
                  break;
          }
  
          currentCell.setNeighbor(nextCell, direction);
  
          stack.push(nextCell);
      }
  }
  }
  </code></pre>
  
  <p>MazeCell:</p>
  
  <pre><code>package com.zarokima.mistwalkers.explore;
  
  import java.util.ArrayList;
  import org.anddev.andengine.util.path.Direction;
  import android.graphics.Point;
  
  public class MazeCell
  {   
  private MazeCell[] neighbors;
  private boolean[] checked;
  private boolean inMaze = false;
  private Point position;
  private static boolean setNeighbor = true; //whether the next call of SetNeighbor() should also call for the new neighbor
  private static int xMax = 10, yMax = 10; //exclusive boundary for position
  private int mapIndex; //will be used when maze generation is working properly
  
  public MazeCell(int x, int y)
  {
      position = new Point(x,y);
      neighbors = new MazeCell[4];
      checked = new boolean[4];
      for(int i = 0; i &lt; neighbors.length; i++)
      {
          neighbors[i] = null;
      }
  }
  
  public Point getPosition()
  {
      return position;
  }
  
  public void setInMaze(boolean b)
  {
      inMaze = b;
  }
  
  public static void setBounds(int x, int y)
  {
      xMax = x;
      yMax = y;
  }
  
  public void setNeighbor(MazeCell c, Direction d)
  {
      checked[d.ordinal()] = true;
      switch(d)
      {
          case UP:
              if(!c.hasNeighbor(Direction.DOWN) &amp;&amp; !c.isInMaze());
              {
                  if(setNeighbor)
                  {
                      setNeighbor = false;
                      c.setNeighbor(this, Direction.DOWN);
                  }
                  neighbors[d.ordinal()] = c;
              }
              break;
          case DOWN:
              if(!c.hasNeighbor(Direction.UP) &amp;&amp; !c.isInMaze())
              {
                  if(setNeighbor)
                  {
                      setNeighbor = false;
                      c.setNeighbor(this, Direction.UP);
                  }
                  neighbors[d.ordinal()] = c;
              }
              break;
          case LEFT:
              if(!c.hasNeighbor(Direction.RIGHT) &amp;&amp; !c.isInMaze())
              {
                  if(setNeighbor)
                  {
                      setNeighbor = false;
                      c.setNeighbor(this, Direction.RIGHT);
                  }
                  neighbors[d.ordinal()] = c;
              }
              break;
          case RIGHT:
              if(!c.hasNeighbor(Direction.LEFT) &amp;&amp; !c.isInMaze())
              {
                  if(setNeighbor)
                  {
                      setNeighbor = false;
                      c.setNeighbor(this, Direction.LEFT);
                  }
                  neighbors[d.ordinal()] = c;
              }
              break;
  
      }
      setNeighbor = true;
      inMaze = true;
  }
  
  public void setDirectionChecked(Direction d, boolean b)
  {
      checked[d.ordinal()] = b;
  }
  
  public boolean hasNeighbor(Direction d)
  {
      return (neighbors[d.ordinal()] != null);
  }
  
  public MazeCell getNeighbor(Direction d)
  {
      return neighbors[d.ordinal()];
  }
  
  public boolean isInMaze()
  {
      return inMaze;
  }
  
  public Direction[] getUncheckedDirections()
  {
      ArrayList&lt;Direction&gt; al = new ArrayList&lt;Direction&gt;();
  
      for(Direction d : Direction.values())
      {
          //boundary cases
          switch(d)
          {
              case UP:
                  if(position.y == 0)
                      continue;
                  break;
              case DOWN:
                  if(position.y == yMax-1)
                      continue;
                  break;
              case LEFT:
                  if(position.x == 0)
                      continue;
                  break;
              case RIGHT:
                  if(position.x == xMax-1)
                      continue;
                  break;
          }
          if(checked[d.ordinal()] == false)
              al.add(d);
      }
  
      Direction[] d = new Direction[al.size()];
      for(int i = 0; i &lt; d.length; i++)
          d[i] = al.get(i);
  
      return d;
  }
  }
  </code></pre>
  
  <p>This produces results that look like <a href="http://dl.dropbox.com/u/2437386/Screenshot_2012-02-08-23-33-29.jpg" rel="nofollow">this</a></p>
  
  <p>Notice how every cell always connects to its up and down neighbors. I have not been able to figure out what is wrong here.</p>
  
  <p>Although the checks in MazeCell's setNeighbor function seem like they should be enough, I added a few more just to see what would happen. Here is the second generateMaze() method:</p>
  
  <pre><code>public void generateMaze()
  {
      maze = new MazeCell[x][y];
      for (int i = 0; i &lt; x; i++)
      {
          for (int k = 0; k &lt; y; k++)
          {
              maze[i][k] = new MazeCell(i, k);
          }
      }
  
      MazeCell.setBounds(x, y);
  
      stack = new Stack&lt;MazeCell&gt;();
      stack.push(maze[0][0]);
      maze[0][0].setInMaze(true);
  
      while (!stack.isEmpty())
      {
          MazeCell currentCell = stack.peek();
  
          Direction[] possibleDirections = currentCell.getUncheckedDirections();
  
          if (possibleDirections.length == 0)
          {
              stack.pop();
              continue;
          }
  
          int dint = rand.nextInt(possibleDirections.length);
          Direction direction = possibleDirections[dint];
          currentCell.setDirectionChecked(direction, true);
  
          MazeCell nextCell = null;
          Point position = currentCell.getPosition();
  
          switch (direction)
          {
              case UP:
                  nextCell = maze[position.x][position.y - 1];
                  break;
              case DOWN:
                  nextCell = maze[position.x][position.y + 1];
                  break;
              case LEFT:
                  nextCell = maze[position.x - 1][position.y];
                  break;
              case RIGHT:
                  nextCell = maze[position.x + 1][position.y];
                  break;
          }
  
          if (!nextCell.isInMaze())
          {
              currentCell.setNeighbor(nextCell, direction);
  
              stack.push(nextCell);
          }
      }
  </code></pre>
  
  <p>And it produces results like <a href="http://dl.dropbox.com/u/2437386/Screenshot_2012-02-09-22-23-44.jpg" rel="nofollow">this</a></p>
  
  <p>Notice how segments are all broken up.</p>
  
  <p>I've played around with it a <em>lot</em> more than just what is mentioned here, but nothing that shows any real improvement -- most end up just looking like the second picture. Any help?</p>