CODEWITHSUNDEEP
javamaze
vsasv
vsasv

Reputation: 870

Making a Maze in Java?

My question is how would I be able to create a randomly generated maze in Java? I know the main outline of the DFS way of creating the maze but I am having a hard time implementing it. In my program, the maze is held in a 2D array and adding 1 to the array yields an array out of bounds exception. How would I avoid that? I do not want to make a very complex maze, just a simple maze. Although I have began to create the code, I am not sure how to make it work.

The pseudocode for the DFS Method is:

create a CellStack (LIFO) to hold a list of cell locations  
set TotalCells = number of cells in grid  
choose a cell at random and call it CurrentCell  
set VisitedCells = 1  

while VisitedCells < TotalCells 
find all neighbors of CurrentCell with all walls intact   
      if one or more found 
          choose one at random  
          knock down the wall between it and CurrentCell  
          push CurrentCell location on the CellStack  
          make the new cell CurrentCell  
          add 1 to VisitedCells
      else 
          pop the most recent cell entry off the CellStack  
          make it CurrentCell
      endIf
    endWhile

I am not understanding how you can find out if your neighbors have their walls intact and how to destroy them. Can anyone give me some insight into this program. Much appreciated.

Upvotes: 1

Views: 2862

Answers (1)

chubbsondubs
chubbsondubs

Reputation: 38706

https://www.google.com/search?ix=seb&sourceid=chrome&ie=UTF-8&q=maze+generation+algorithm

There is plenty of literature out there that helps you do this. Rehashing it here isn't going to do it justice.

For the two questions you asked. Your algorithm sounds like its brittle in that it relies on a fixed size of the array. If it's not designed that way then you'll have to grab a debugger and found out why it's going outside the length of the array (array.length). As for the 2nd question you'll use simple indexing to look at neighboring cells.

  • Cell to the left maze[row][col-1]
  • Cell to the right maze[row][col+1]
  • Cell above maze[row-1][col]
  • Cell below maze[row+1][col]

Of course you'll have to prevent going outside the boundaries of the array as row,col are on the edge of the maze.

To tell if a wall is here:

Cell cell = maze[row][col];
if( cell.isWall() ) ...

Upvotes: 3

Related Questions