Creating a maze?

[grommet2481]

So im trying despritely to understand how to create a maze and find the shortest path. I would just like to first understand how to create a maze. Theres no need for it to be outputted at this stage, I just want to understand how it works. I found this program on the net. It will not compile, I know it is because cell is not part of the java libaries??? or is it? What is this cell. It seems perfect for creating a maze. Can someone show me what I need to get this program to work? or even just elabourate on this cell object. please

import java.awt.*;
import java.awt.color.*;


public class Maze {
   private int N;                 // dimension of maze
   private Cell cells[][];        // two dimensional grid of cells
   private Cell start, finish;
   private Draw draw;
   private double size;
   boolean done = false;

   Maze(int N) {
      this.N = N;
      draw = new Draw(512, 512);
      size = 512.0 / (N + 2);
      init();
      generate();
   }

   private void init() {

      // need to allocate memory for 2d array, each row, and each cell
      // individually since it's a 2d array of objects and not primitive types
      // use N+2 to leave room for one cell border around N-by-N grid
      cells = new Cell[N+2][N+2];
      for (int x = 0; x < N+2; x++)
         cells[x] = new Cell[N+2];
      for (int x = 0; x < N+2; x++)
         for (int y = 0; y < N+2; y++)
            cells[x][y] = new Cell(x * size, y * size);

      // initialize border cells as already visited
      for (int x = 0; x < N+2; x++) {
         cells[x][0].setVisited(true);
         cells[x][N+1].setVisited(true);
      }

      for (int y = 0; y < N+2; y++) {
         cells[0][y].setVisited(true);
         cells[N+1][y].setVisited(true);
      }

      // Set neighbors, ignoring border cells. (1, 1) is lower left.
      for (int x = 1; x <= N; x++) {
         for (int y = 1; y <= N; y++) {
            Cell north = cells[x][y+1];
            Cell south = cells[x][y-1];
            Cell west  = cells[x-1][y];
            Cell east  = cells[x+1][y];
            cells[x][y].setNeighbors(north, east, south, west);
         }
      }

      // set start and finish states
      start  = cells[1][1];
      finish = cells[N][1];
      draw.setColor(Color.RED);
      start.spot(draw, size);
      finish.spot(draw, size);
   }

   // generate the maze
   private void generate(Cell x) {
      x.setVisited(true);
      Cell next;
      while ((next = x.deleteRandomWall()) != null)
         generate(next);         
   }

   // generate the maze starting from the start cell
   private void generate() {
      generate(start);
      for (int x = 1; x <= N; x++)
         for (int y = 1; y <= N; y++)
            cells[x][y].setVisited(false);

      // delete some random walls
      for (int i = 0; i < N; i++) {
          int x = (int) (1 + Math.random() * N);
          int y = (int) (1 + Math.random() * N);
          cells[x][y].deleteRandomWall();
      }
   }

   // solve the maze using depth first search
   private void solve(Cell x) {
      if (done || x == null || x.isVisited()) return;
      x.setVisited(true);

      if (x == finish) done = true;

      draw.setColor(Color.BLUE);
      x.spot(draw, size);
      draw.show();
      draw.pause(30);

      solve(x.getNorth());
      solve(x.getEast());
      solve(x.getSouth());
      solve(x.getWest());

      if (done) return;

      draw.setColor(Color.GRAY);
      x.spot(draw, size);
      draw.show();
      draw.pause(30);
   }

   // solve the maze starting from the start state
   public void solve() {
      for (int x = 1; x <= N; x++)
         for (int y = 1; y <= N; y++)
            cells[x][y].setVisited(false);
      done = false;
      solve(start);
   }

   // display the maze in a window
   public void draw() {
      if (cells == null) return;
      draw.setColor(Color.BLACK);
      for (int x = 1; x <= N; x++)
         for (int y = 1; y <= N; y++)
            cells[x][y].draw(draw, size);
      draw.show();
   }



   // a test client
   public static void main(String[] args) {
      int N = Integer.parseInt(args[0]);
      Maze maze = new Maze(N);
      maze.draw();
      maze.solve();
   }

}

[VernonDozier]

http://www.derekscswebsite.com/RandomMazeJava/index.html
http://www.derekscswebsite.com/Javascript/Maze/index.html
http://www.derekscswebsite.com/Algorithms/RandomMaze/RandomMaze.html

The above are links to a random maze creation program I created, as well as a detailed explanation of the algorithm I used. It's one way to make a maze. It's not the only way.

[BestJewSinceJC]

I'll give a short explanation, but it is exceedingly difficult without simply creating a small maze, creating a stack and a queue, and walking through the small maze using this procedure:

1. From your current position, *initially the start* add the cells of the maze (that you can 'walk to' i.e. not walls) that are to the N, S, E, W or your current position to the stack/queue.
2. If you aren't at the end of the maze yet, get the next cell from the stack/queue, then repeat step 1 (using the cell you just got)

If you do a small example as I described above, you will see that the following is true:

The queue is guaranteed to find the shortest path to the goal. The stack isn't. (Now its up to you to figure out why the queue will find the shortest path, but the stack won't)