So far I got an DFS maze algorithm that gets me and perfect maze with one path exactly. I was wondering how I could get more than one path to my end with little change. Should I just randomly remove walls? But the thing is that I do not want just empty squares with no walls at all...
Here's my algorithm so far:
private void computeMaze(){
Random random = new Random();
Stack<Block> stack = new Stack<Block>(); //Stack
Block current = blocks[0][0]; //First cell is the current cell
current.setVisited(true); //Mark as accessed
//Create a count; first cell has been accessed, if no unvisited cells left == 0
int unVisitedCount=ROWS*COLS-1;
//Create a list of neighbors
List<Block> neighbors;
Block next;
while(unVisitedCount > 0) {
//Find neighbor collection (unreachable)
neighbors = current.findNeighbors();
//If the current cell has unvisited neighbors then:
if(neighbors.size() > 0) {
//Randomly select a neighbor from this list
int index = random.nextInt(neighbors.size());
next = neighbors.get(index);
//Stack the current cell
stack.push(current);
//Remove the walls between the current maze cell and the randomly selected neighbor cell
this.removeWall(current,next);
//Mark the neighbor cell as visited and use it as the current cell
next.setVisited(true);
current = next;
//If an access is marked, the counter is decreased by 1
unVisitedCount--;
}
else if(stack.isEmpty() == false) {//If the current maze cell does not have an unreachable adjacent maze cell, and the stack is not empty
/*
1.The maze unit at the top of the stack comes out of the stack
2.Make it the current maze unit
*/
Block cell = stack.pop();
current = cell;
}
}
}
//Find neighbors as well as the getneighbors methods:
//Find out whether the current cell has an unreachable neighbor cell
public List<Block> findNeighbors() {
//The neighbors are divided into upper, lower, left and right
List<Block> res = new ArrayList<Block>();
Block top = this.getNeighbor(0,false);
Block right = this.getNeighbor(1,false);
Block bottom = this.getNeighbor(2,false);
Block left = this.getNeighbor(3,false);
if(top != null){
res.add(top);
}
if(right != null){
res.add(right);
}
if(bottom != null){
res.add(bottom);
}
if(left != null){
res.add(left);
}
return res;//Return neighbor array
}
//Get neighbors according to direction
public Block getNeighbor(int type,boolean lose_visited) {
Block neighbor;
int neighbor_i = 0, neighbor_j = 0;
switch(type) {
case 0:
neighbor_i = this.i-1;
neighbor_j = this.j;
break;
case 1:
neighbor_i = this.i;
neighbor_j = this.j+1;
break;
case 2:
neighbor_i = this.i+1;
neighbor_j = this.j;
break;
case 3:
neighbor_i = this.i;
neighbor_j = this.j-1;
break;
}
Block[][] blocks = panel.blocks;
//It's beyond the boundary, therefore no neighbor
if(neighbor_i < 0 || neighbor_j < 0 || neighbor_i >= panel.ROWS || neighbor_j >= panel.COLS) {
neighbor = null;
}
//The dimensions are permitted, neighbor is found
else {
//Find the neighbor, either top/bottom/left/right
neighbor = blocks[neighbor_i][neighbor_j];
//Judge whether it is accessed. If it is accessed, null is returned
if(neighbor.visited && !lose_visited) {//lose_visited equals true to ignore access
neighbor = null;
}
}
return neighbor;
}
To make a maze with multiple solutions, you would want to remove walls that would connect the solution path to a non-solution path. That would then add that non-solution path to the alternate solutions.
You might also want to remove some walls between multiple non-solution paths just to make it interesting.
The question of leaving an empty area is more interesting. You can remove all 4 walls from a cell, if it is a 4-way junction, so you need to check that the neighbouring cells have walls connecting to the corners.
And then the question of is the removal trivial - is the connection close to the point where the 2 paths already junctioned?