Jump to content


Check out our Community Blogs

Register and join over 40,000 other developers!


Recent Status Updates

View All Updates

Photo
- - - - -

Maze Tutorial

linked list setpreferredsize

  • Please log in to reply
11 replies to this topic

#1 mr mike

mr mike

    CC Resident

  • Just Joined
  • PipPipPipPip
  • 89 posts

Posted 20 May 2011 - 07:54 AM

LETS THINK ABOUT A MAZE
A Maze can be thought of a series of rooms that has four walls that are either opened exposing the next room or are blocking the view of the next room. In short a room(Vertex) has four walls(edges) that are either there or not(boolean). The openings are determined by sets.

LET'S BEGIN
First we will create a room class. The variables that will be needed initially are four walls, a thought of a matrix(x and y), an adjacency list, a room name consisting of a number(ie. 0, 1, 2, 3,...,n), and a pointer to the previous room.

Room Class
import java.util.*;
public class Room{
   // represent four walls
   public Wall north, east, south, west; // the wall class will be created next
   public int x, y; // represent the row and column of the maze
   public List<Room> adj; // adjacency list using linked list
   public int roomName; // for this the room will be a number
   public Room prev; // last room pointer

   // now we code the constructer 
   public Room(int x, int y){
      this.x = x;// row
      this.y = y;// column
      adj = new LinkedList<Room>();
      prev = null;// we have not progressed, so prev is nothing
      roomName = 0;// we will use the concept of arrays start 0
   }// end of constructor

   // we have to increment the room name so lets do it
   public int getRoomName(){
      return roomName++;
   }// end of getRoomName()

}// end of 
Wall Class
public class Wall{
   
   public Room currentRoom, nextRoom;// room in now, next room 
   public boolean isGone = false;// is the wall there

   // Two constructors will be created
   // which will account for walls with or 
   // without neighbors

   // with a neighbor 
   public Wall(Room a, Room b){
      currentRoom = a;
      nextRoom = b;
   }

   // without a neighbor
   public Wall(Room r){
      currentRoom = r;
      nextRoom = null;
   }
}// end of Wall class
I will explain how disjoint sets work in a future tut, but a quick explanation:
Disjoint sets are sets whose intersect is the null set. We will use this notion to join the sets or room names and create the maze by unionizing the rooms.

JoinRoom class
public class JoinRoom{
   private int[] set; // this is an array to store a set of rooms
   public JoinRoom(int elem){
      set = new int[e];
      // initialize every element in the set
      for(int i = 0; i < set.length; i++){
         set[i] = -1;
      }
   }// end of constructor

   // find using compression
   public int find(int r){
      if(set[r] < 0){
         return r;
      } else {
         return set[r] = find(set[r]);
      }
  }// end of find

  public void unionRooms(int roomA, int roomB){
      if(set[roomB] < set[roomA]){
          set[roomA] = roomB;
      } else {
         if(set[roomA] == set[roomB]){
            set[roomA]--;
         }
         set[roomB] = roomA;
     }
 }// end of union rooms

}// end of joinRoom class
NOW WE CREATE OUR MAIN CLASS TO GENERATE THE MAZE

We will create the class and have it extend JPanel for our artwork. We have to think of private variables that will be needed.
public class Maze extends JPanel{
    // the maze can be seen as a matrix of squares so well use a multidimensional array of the room 
    // class
    private Room[][] rooms;// the maze can be seen as a matrix of squares so well use
    private ArrayList<Wall> walls; // List of walls
    private Random rand;// We are going to have to randomize the rooms chosen to unionize
    private int height;// users desired height of matrix 
    private int width;// users desired width of matrix
    private int num;// we will have to increment a few times so lets just use num as an incrementor
    private JoinRooms ds;// we are going to join rooms so well label the variable ds for disjoint set

    // we are going to need variables for our panel 
    private int x_cord; // x-axis rep
    private int y_cord;// y-axis rep
    private int roomSize;
    private int randomWall;

}// end of class

Now we need the constructor. We want the constructor to take height and width of the matrix. We also want the constructor to initialize our multidimensional room array and our arraylist of walls(the bottom right will always be the exit). We will also call the generate the random maze which will initialize the maze to be a matrix of squares. Finally we will set the size of our panel.

    public Maze(int height, int width) {
        this.height = height;
        this.width = width;
        rooms = new Room[height][width];
        walls = new ArrayList<Wall>((height - 1) * (width - 1));
        generateRandomMaze();
        setPreferredSize(new Dimension(800, 700));
   }

To generate the random maze we will first have to create a initial multidimensional array of rooms with the walls intact except for the top left and bottom right room. We will now initialize our JoinRooms class to be essentialy a array of rooms. We also have to initialize our random room generator and use our incrementer(num) to decrement.

   private void generateRandomMaze() {
        generateInitialRooms();// see next method
        ds = new JoinRoom(width * height);
        rand = new Random(); // here is the random room generator
        num = width * height;

        while (num > 1) {
           // when we pick a random wall we want to avoid the borders getting eliminated
            randomWall = rand.nextInt(walls.size());
            Wall temp = walls.get(randomWall);
            // we will pick two rooms randomly 
            int roomA = temp.currentRoom.y + temp.currentRoom.x * width;
            int roomB = temp.nextRoom.y + temp.nextRoom.x * width;

            // check roomA and roomB to see if they are already members 
            if (ds.find(roomA) != ds.find(roomB)) {
                walls.remove(randomWall);
                ds.unionRooms(ds.find(roomA), ds.find(roomB));
                temp.isGone = true;
                temp.currentRoom.adj.add(temp.nextRoom);
                temp.nextRoom.adj.add(temp.currentRoom);
                num--;
            }// end of if
        }// end of while
    }


     // name the room to display
    private int roomNumber = 0;
    /**
     * Sets the grid of rooms to be initially boxes
     * This is self explanitory, we are only creating an reverse L for all
     * The rooms and there is an L for the border
     */
    private void generateInitialRooms() {
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                // create north walls
                rooms[i][j] = new Room(i, j);
                if (i == 0) {
                    rooms[i][j].north = new Wall(rooms[i][j]);
                } else {
                    rooms[i][j].north = new Wall(rooms[i - 1][j], rooms[i][j]);
                    walls.add(rooms[i][j].north);
                }
                if (i == height - 1) {
                    rooms[i][j].south = new Wall(rooms[i][j]);
                }
                if (j == 0) {
                    rooms[i][j].west = new Wall(rooms[i][j]);
                } else {
                    rooms[i][j].west = new Wall(rooms[i][j - 1], rooms[i][j]);
                    walls.add(rooms[i][j].west);
                }
                if (j == width - 1) {
                    rooms[i][j].east = new Wall(rooms[i][j]);
                }
                rooms[i][j].roomName = roomNumber++;// we will name the rooms
            }
        }
        // initalize entrance and exit
        rooms[0][0].west.isGone = true;// you can replace .west.isGone with .north.isGone
        // this is just saying the roomName for top left is 0 
        rooms[0][0].roomName = 0;
        // we will remove the south wall of the last room
        rooms[height - 1][width - 1].south.isGone = true;
        // this is just saying the roomName for bottom right is the last element in the mxn room matrix
        rooms[height - 1][width - 1].roomName = (height * width);
    }

Voila, the initialization and the maze is joined with only one path from start to finish lets display it on our panel(I like to call this my art canvas).

   // The code will display the maze
   // I urge you to play with the variable 
   // values to see how this portion of the 
   // code works and changes
   public void paintComponent(Graphics g) {
        x_cord = 40;
        y_cord = 40;
        // could have taken height as well as width
        // just need something to base the roomsize
        roomSize = (width - x_cord) / width + 7;

        // temp variables used for painting
        int x = x_cord;
        int y = y_cord;

        for (int i = 0; i <= height - 1; i++) {
            for (int j = 0; j <= width - 1; j++) {
                if (!(rooms[i][j].north.isGone)) {
                    g.drawLine(x, y, x + roomSize, y);
                }//end of north if
                // west wall not there draw the line
                if (rooms[i][j].west.isGone == false) {
                    g.drawLine(x, y, x, y + roomSize);
                }// end of west if
                if ((i == height - 1) && rooms[i][j].south.isGone == false) {
                    g.drawLine(x, y + roomSize, x + roomSize,
                            y + roomSize);
                }// end of south if
                if ((j == width - 1) && rooms[i][j].east.isGone == false) {
                    g.drawLine(x + roomSize, y, x + roomSize,
                            y + roomSize);
                }// end of east if
                x += roomSize;// change the horizontal
            }// end of inner for loop
            x = x_cord;
            y += roomSize;
        }// end of outer for loop
   }

Finally, we can create the main method for our code. This should be very clear and doesnt need detail(If not ask in comments).
   public static void main(String[] args) {
        // we will use the scanner for userInput
        Scanner userInput = new Scanner(System.in);
        int m, n;// these are variables for the size of maze (m x n)
        System.out.print("Enter the size of your maze: ");
        // store the input
        m = userInput.nextInt();
        n = userInput.nextInt();
        // use JFrame to put the created panel on
        JFrame frame = new JFrame();
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.setSize(500, 800);
        frame.getContentPane().add(new Maze(m, n));
        frame.pack();
        frame.setVisible(true);
    }// end of main

Here is the complete code from our main class
import java.awt.Dimension;
import java.awt.Graphics;
import java.util.ArrayList;
import java.util.Random;
import java.util.Scanner;

import javax.swing.JFrame;
import javax.swing.JPanel;


public class Maze extends JPanel {

    private Room[][] rooms;// m x n matrix of rooms
    private ArrayList<Wall> walls; // List of walls
    private Random rand;// for random wall
    private int height;// height of matrix
    private int width;// width of matrix
    private int num;// incrementor
    private JoinRoom ds;// union paths

    // paint methods //
    private int x_cord; // x-axis rep
    private int y_cord;// y-axis rep
    private int roomSize;
    private int randomWall;
	
    public Maze(int height, int width) {
        this.height = height;
        this.width = width;
        rooms = new Room[height][width];
        walls = new ArrayList<Wall>((height - 1) * (width - 1));
        generateRandomMaze();
        setPreferredSize(new Dimension(800, 700));
   }
    private void generateRandomMaze() {
        generateInitialRooms();// see next method
        ds = new JoinRoom(width * height);
        rand = new Random(); // here is the random room generator
        num = width * height;

        while (num > 1) {
           // when we pick a random wall we want to avoid the borders getting eliminated
            randomWall = rand.nextInt(walls.size());
            Wall temp = walls.get(randomWall);
            // we will pick two rooms randomly 
            int roomA = temp.currentRoom.y + temp.currentRoom.x * width;
            int roomB = temp.nextRoom.y + temp.nextRoom.x * width;

            // check roomA and roomB to see if they are already members 
            if (ds.find(roomA) != ds.find(roomB)) {
                walls.remove(randomWall);
                ds.unionRooms(ds.find(roomA), ds.find(roomB));
                temp.isGone = true;
                temp.currentRoom.adj.add(temp.nextRoom);
                temp.nextRoom.adj.add(temp.currentRoom);
                num--;
            }// end of if
        }// end of while
    }

     // name the room to display
    private int roomNumber = 0;
    /**
     * Sets the grid of rooms to be initially boxes
     * This is self explanitory, we are only creating an reverse L for all
     * The rooms and there is an L for the border
     */
    private void generateInitialRooms() {
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                // create north walls
                rooms[i][j] = new Room(i, j);
                if (i == 0) {
                    rooms[i][j].north = new Wall(rooms[i][j]);
                } else {
                    rooms[i][j].north = new Wall(rooms[i - 1][j], rooms[i][j]);
                    walls.add(rooms[i][j].north);
                }
                if (i == height - 1) {
                    rooms[i][j].south = new Wall(rooms[i][j]);
                }
                if (j == 0) {
                    rooms[i][j].west = new Wall(rooms[i][j]);
                } else {
                    rooms[i][j].west = new Wall(rooms[i][j - 1], rooms[i][j]);
                    walls.add(rooms[i][j].west);
                }
                if (j == width - 1) {
                    rooms[i][j].east = new Wall(rooms[i][j]);
                }
                rooms[i][j].roomName = roomNumber++;// we will name the rooms
            }
        }
        // initalize entrance and exit
        rooms[0][0].west.isGone = true;// you can replace .west.isGone with .north.isGone
        // this is just saying the roomName for top left is 0 
        rooms[0][0].roomName = 0;
        // we will remove the south wall of the last room
        rooms[height - 1][width - 1].south.isGone = true;
        // this is just saying the roomName for bottom right is the last element in the mxn room matrix
        rooms[height - 1][width - 1].roomName = (height * width);
    }
	
	 public void paintComponent(Graphics g) {
        x_cord = 40;
        y_cord = 40;
        // could have taken height as well as width
        // just need something to base the roomsize
        roomSize = (width - x_cord) / width + 7;

        // temp variables used for painting
        int x = x_cord;
        int y = y_cord;

        for (int i = 0; i <= height - 1; i++) {
            for (int j = 0; j <= width - 1; j++) {
                if (!(rooms[i][j].north.isGone)) {
                    g.drawLine(x, y, x + roomSize, y);
                }//end of north if
                // west wall not there draw the line
                if (rooms[i][j].west.isGone == false) {
                    g.drawLine(x, y, x, y + roomSize);
                }// end of west if
                if ((i == height - 1) && rooms[i][j].south.isGone == false) {
                    g.drawLine(x, y + roomSize, x + roomSize,
                            y + roomSize);
                }// end of south if
                if ((j == width - 1) && rooms[i][j].east.isGone == false) {
                    g.drawLine(x + roomSize, y, x + roomSize,
                            y + roomSize);
                }// end of east if
                x += roomSize;// change the horizontal
            }// end of inner for loop
            x = x_cord;
            y += roomSize;
        }// end of outer for loop
   }
   
   public static void main(String[] args) {
        // we will use the scanner for userInput
        Scanner userInput = new Scanner(System.in);
        int m, n;// these are variables for the size of maze (m x n)
        System.out.print("Enter the size of your maze: ");
        // store the input
        m = userInput.nextInt();
        n = userInput.nextInt();
        // use JFrame to put the created panel on
        JFrame frame = new JFrame();
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.setSize(500, 800);
        frame.getContentPane().add(new Maze(m, n));
        frame.pack();
        frame.setVisible(true);
    }// end of main
}// END OF CLASS 

That concludes the tutorial on maze creation. Enjoy.

Optional things you should try with this maze program:
1. Print the maze to a txt file
2. Accept a text file to generate maze
3. Display the solution to the maze(hint: add dijkstra(), leftHand(), or anotherAlgorithm(search for path) and dont forget to modify paintComponent() method when solved

Edited by mr mike, 23 May 2011 - 05:30 PM.
leathalwire pointed out a typo

  • 4

#2 lethalwire

lethalwire

    while(false){ ... }

  • Senior Member
  • PipPipPipPipPipPip
  • 766 posts
  • Programming Language:C, Java, PHP, JavaScript
  • Learning:PHP

Posted 23 May 2011 - 04:00 PM

Great tutorial! I can see how everything would work in theory but I can't quite fully compile this yet! :(

            int roomA = temp.[B]here[/B].y + temp.[B]here[/B].x * width;
            int roomB = temp.next.y + temp.next.x * width;

I can't find the here,next variables inside of the Wall class.
I'm sure you meant currentRoom and nextRoom though. :)

I enjoyed this tutorial. Especially because I'm currently learning about the disjoint data set structure and how it can be used in problems like this.
+1 for you.
Thanks.
  • 0

#3 mr mike

mr mike

    CC Resident

  • Just Joined
  • PipPipPipPip
  • 89 posts

Posted 23 May 2011 - 04:12 PM

@ lethalwire
Sorry typo
Thanks for bringing this to my attention, ill fix it and glad you enjoyed this tutorial.

Edited by mr mike, 23 May 2011 - 05:28 PM.

  • 0

#4 charlote

charlote

    CC Regular

  • Member
  • PipPipPip
  • 37 posts

Posted 12 December 2011 - 01:58 AM

It is a great tutorial. Unfortunately, I couldn't compile it. I ended up getting "room cannot be resolved to a type" and "wall cannot be resolved to a type" errors. Any suggestions as to why do I get those errors. I did try to figure out.. But couldn't correct it.
Thanks,
Charlotte
  • 0

#5 wim DC

wim DC

    Roar

  • Expert Member
  • PipPipPipPipPipPipPipPip
  • 2681 posts
  • Programming Language:Java, JavaScript, PL/SQL
  • Learning:Python

Posted 12 December 2011 - 02:05 AM

Either you did not create the Room and Wall class, or else you need to import them as you may have put those in a package.
  • 1

#6 Ziegfred

Ziegfred

    CC Lurker

  • New Member
  • Pip
  • 3 posts
  • Learning:Java, C++

Posted 01 October 2012 - 05:33 AM

not yet updated?
  • 0

#7 VNFox

VNFox

    CC Devotee

  • Senior Member
  • PipPipPipPipPipPip
  • 648 posts
  • Programming Language:C#, PHP
  • Learning:Assembly

Posted 01 October 2012 - 08:47 AM

wow that's a lot of work +1. Looks good.
  • 0

www.pickmike.com
I don't just develop software. I find solutions to your business needs.


#8 maher

maher

    CC Newcomer

  • Member
  • PipPip
  • 15 posts
  • Location:India
  • Programming Language:C, C++, (Visual) Basic
  • Learning:Java, PHP, JavaScript

Posted 05 October 2012 - 06:11 PM

this is extraordinary. good job friend.
  • 0

#9 charvie5

charvie5

    CC Newcomer

  • Member
  • PipPip
  • 11 posts
  • Programming Language:C, Java, Python, Bash

Posted 21 February 2013 - 08:58 AM

Hi, I'm not sure if this post will still be viewed by the author....but ill give it a shot..

 

I have implemented a maze application using this implementation. I have a navigator which is just a small green square (the navigator can move using key adapter) and is only allowed to move when the current cell's wall is down (e.g. if he wants to go right, it will check if the east wall is down, and if it is he can move)

 

However, I am encountering a problem by which it seems that some walls that are not shown in the gui seem to be up (i.e he cant move where he should).

 

I think this might be down to that fact that, in the generateRandomMaze() method, when the temp wall's isGone is set to true, the adjacent wall is still up and so he can't move.

 

I might be totally wrong but I am just wondering if anyone could enlighten me into what my problem might be?

 

I could post my code for the movement of the navigator if necessary.

 

Thanks


  • 0

#10 Ritwik I the programmer

Ritwik I the programmer

    CC Addict

  • Advanced Member
  • PipPipPipPipPip
  • 244 posts
  • Programming Language:Java
  • Learning:Java, C++, Python

Posted 21 February 2013 - 09:11 AM

charvie5, you could PM the author of the tutorial or start a separate thread on this topic. To get proper help, you will need to post your code as well.


  • 1

I can believe, but why should I?


#11 charvie5

charvie5

    CC Newcomer

  • Member
  • PipPip
  • 11 posts
  • Programming Language:C, Java, Python, Bash

Posted 21 February 2013 - 09:23 AM

Thanks Ritwik.

 

I have created a seperate thread.


Edited by Roger, 21 February 2013 - 09:58 AM.
added link

  • 0

#12 maerivera08

maerivera08

    CC Lurker

  • Just Joined
  • Pip
  • 1 posts

Posted 10 February 2014 - 08:14 AM

how can i change the size of the grids?i want to change it because it is too small.tnx! :biggrin:


  • 0





Also tagged with one or more of these keywords: linked list, setpreferredsize

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download