SHARE
TWEET

Untitled

Conderoga Dec 14th, 2011 30 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.awt.Point;
  2. import java.util.ArrayList;
  3. import java.util.Collections;
  4. import java.util.LinkedList;
  5.  
  6. public class Maze {
  7.         /**
  8.          * This variable stores essentially all the data for the maze.
  9.          * A 4 x 4 maze would look like this:
  10.          *  _|_|_|_
  11.          *  _|_|_|_
  12.          *  _|_|_|_
  13.          *   | | |
  14.          *  Where an underscore represents a horizontal wall, and a pipe
  15.          *  represents a vertical wall. This variable will only use O(r*c)
  16.          *  memory. Every even number row in the variable will represent the vertical
  17.          *  walls. Since there will only be cols-1 vertical walls per row, the first
  18.          *  column on every even row should be ignored. The same thing also goes for the
  19.          *  last row's horizontal walls. There will only be a maximum of rows-1 horizontal walls
  20.          *  per column, so the last row in the variable simply should not be read.
  21.          *  Because of this, the variable is actually initialized with 2*r-1 rows.
  22.          *  
  23.          *  Basically the generate maze method will fill up this variable and the print one will
  24.          *  display it in text form.
  25.          *  
  26.          *  OMG JOSH LOOK HERE PL0x! ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~< look
  27.          *  Some useful tips for accessing from the "walls" array:
  28.          *  
  29.          *  Say you have a r x c grid that represents the blocks in the maze...
  30.          *  to get a boolean of whether or not there is a wall to its...
  31.          *  right  -> walls[2r][c+1];
  32.          *  left   -> walls[2r][c];
  33.          *  top    -> walls[2r-1][c];
  34.          *  bottom -> walls[2r+1][c];
  35.          *  
  36.          *  Of course those will go out of bounds, so you'll have to be careful
  37.          *  but that should come in handy when trying to display the maze.
  38.          */
  39.         public boolean [][] walls;
  40.  
  41.  
  42.         public Maze(int r, int c){
  43.                 walls = new boolean [(2*r)-1][c];
  44.                 for(int row= 0; row<walls.length; row++)
  45.                         for(int col = 0; col < walls[row].length; col++)
  46.                                 walls[row][col] = true;
  47.         }
  48.         /**
  49.          * This method was only used for testing the print method
  50.          * @param maze
  51.          */
  52.         public void setMaze(boolean[][] maze){
  53.                 walls = maze;
  54.         }
  55.         /**
  56.          * Be this fills the walls array by breaking walls down for the maze.
  57.          * It's complicated but I bet you can figure it out. In addition, the
  58.          * ends arrayList correctly contains the list of all endpoints (in x=r,y=c form) when
  59.          * the depth first search is complete. It is currently set to just print
  60.          * the ends afterwards however that could quickly be changed.
  61.          */
  62.         public void generateMaze(){
  63.                 if(walls==null)
  64.                         return;
  65.                 int r = (walls.length+1)/2;
  66.                 int c = walls[0].length;
  67.  
  68.  
  69.                 int[][] around = {{-1,0,0,1},
  70.                                 {0,-1,1,0}};
  71.  
  72.                 int numGrids = r*c;
  73.  
  74.                 boolean [][] visited = new boolean[r][c];
  75.                 LinkedList<Point []> pointsToVisit = new LinkedList<Point []>();
  76.                 LinkedList<Point> surrounding = new LinkedList<Point>();
  77.                 ArrayList<Point> ends = new ArrayList<Point>();
  78.  
  79.                 pointsToVisit.add(new Point [] {new Point(0,0),null});
  80.  
  81.                 while(numGrids>0){
  82.                         Point [] toCheck = pointsToVisit.removeFirst();
  83.                         if(visited[toCheck[0].x][toCheck[0].y]){
  84.  
  85.                         }
  86.                         else{
  87.                                 if(toCheck[1]!=null){
  88.                                         //update the walls array:
  89.                                         if(toCheck[1].y>toCheck[0].y){ //right vert wall
  90.                                                 walls[2*toCheck[0].x][toCheck[0].y+1] = false;
  91.                                         }
  92.                                         else if(toCheck[1].y<toCheck[0].y){ //left vert wall
  93.                                                 walls[2*toCheck[0].x][toCheck[0].y] = false;
  94.                                         }
  95.                                         else if(toCheck[1].x<toCheck[0].x){//horizontal wall above
  96.                                                 walls[2*toCheck[0].x-1][toCheck[0].y] = false;
  97.                                         }
  98.                                         else if(toCheck[1].x>toCheck[0].x){//horizontal wall below
  99.                                                 walls[2*toCheck[0].x+1][toCheck[0].y] = false;
  100.                                         }
  101.                                 }
  102.                                 visited[toCheck[0].x][toCheck[0].y] = true;
  103.                                 numGrids--;
  104.                                 for(int i = 0; i < around[0].length; i++){
  105.                                         if(toCheck[0].x+around[0][i]>=0 && toCheck[0].x+around[0][i]<r //makes sure the point to check is in bounds
  106.                                                         && toCheck[0].y+around[1][i]>=0 && toCheck[0].y+around[1][i]<c //makes sure the point to check is in bounds
  107.                                                         &&      !visited[toCheck[0].x+around[0][i]][toCheck[0].y+around[1][i]]){
  108.                                                 surrounding.add(new Point(toCheck[0].x+around[0][i],toCheck[0].y+around[1][i]));
  109.                                         }
  110.                                 }
  111.                                 if(surrounding.size()>0){
  112.                                         Collections.shuffle(surrounding);
  113.                                         pointsToVisit.addFirst(new Point [] {surrounding.removeFirst(),toCheck[0]});
  114.                                         while(!surrounding.isEmpty()){
  115.                                                 pointsToVisit.addLast(new Point [] {surrounding.removeLast(),toCheck[0]});
  116.                                         }
  117.                                 }      
  118.                                 else
  119.                                         ends.add(toCheck[0]);
  120.                         }
  121.                 }
  122.                 System.out.println(ends);
  123.         }
  124.         /**
  125.          * Please excuse the extremely shitty string concatenation everywhere.
  126.          * Run it and the code will make a lot more sense.
  127.          * @return
  128.          */
  129.         public String printMaze(){
  130.                 if(walls==null)
  131.                         return "Empty Maze";
  132.                 String out = "";
  133.                 for(int i = 0; i < walls[0].length; i++){
  134.                         out+="**";
  135.                 }
  136.                 out+="*\n";
  137.                 for(int r = 0; r < walls.length; r+=2){
  138.                         out+="*";
  139.                         if(r==walls.length-1)
  140.                                 out+=" ";
  141.                         for(int c = 0; c < walls[r].length; c++){
  142.                                 if(r!=walls.length-1){ //vertical walls
  143.                                         if(c!=0){
  144.                                                 if(walls[r][c])
  145.                                                         out+="|";
  146.                                                 else
  147.                                                         out+=" ";
  148.                                         }
  149.                                         if(walls[r+1][c])
  150.                                                 out+="_";
  151.                                         else
  152.                                                 out+=" ";
  153.                                 }
  154.                                 else{
  155.                                         if(c!=0){
  156.                                                 if(walls[r][c])
  157.                                                         out+="| ";
  158.                                                 else
  159.                                                         out+="  ";
  160.                                         }
  161.                                 }
  162.                         }
  163.                         out+="*\n";
  164.                 }
  165.                 for(int i = 0; i < walls[0].length; i++){
  166.                         out+="**";
  167.                 }
  168.                 out+="*";
  169.                 return out;
  170.         }
  171. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top