So I am making a maze generation algorithm using depth first search. I do this in a 2D array of characters. Walls are represented as '#' & paths are '.' I create a new maze each time I call the "Maze" class.
I do this using three methods:
1 - hasUnvisited: checks if a cell has any cells around it that have not been visited before by the algorithm. Only checks cells +2 units away either up or down or left or right. (UDLR)
2 - pather: carves a path through a grid made of just walls. Checks if a path is in not on the edge of the grid. Then turns that cell into a path. Then checks if the cell hasUnvisited. If it does, it chooses a random direction to go (UDLR). If that direction +2's (ex: left +2, right+2..etc.) cell is clear then it changes the direction's +1 into a wall and then calls pather for the directions +2. (this will in turn clear the +2 in the direction randomly chosen and recursively repeat until path does not haveUnvisited.
3 - mazer: this method is for aesthetics purposes only, so I have commented out a lot of it to focus on the underlying issue. It basically makes a grid, initializes it with all '#'. Then calls pather with starting row (sr) and starting column(sc) 1,1. Then returns that grid of chars.
For some reason, however, my code makes this weird path of 'columns' at the bottom of the maze every time I run it. I am 99% sure it is in the "clipping" section of the code in 'pather' method, but I have no idea how to end the method and stop it from going out of bounds at that point.
As you can see, this is Java, but I've tried the code in C++ and it does the same thing so I'm pretty sure this is language-independent.
Here is the code:
import java.util.Random;
public class Maze {
private char[][] grid;
private final int WIDTH;
private final int HEIGHT;
Random randomGen = new Random();
//Checks to see if any of the surrounding cells are un
private boolean hasUnvisited (char[][] grid, int sr, int sc) {
if (sc+2 > HEIGHT-1) {
} else if (grid[sr][sc+2]=='#') {
return true;
}
if (sc-2 < 0) {
} else if (grid[sr][sc-2]=='#') {
return true;
}
if (sr+2 > WIDTH-1) {
} else if (grid[sr+2][sc]=='#') {
return true;
}
if (sr-2 < 0) {
} else if (grid[sr-2][sc]=='#') {
return true;
}
return false;
}
//Visits each cell, turns it to '.'
private void pather (char[][] grid, int sr, int sc) {
//Sets current cell to '.' to mark as visited
grid[sr][sc] = '.';
//"Clipping": if it is at edge of grid, don't carve any more, just return.
if (sr>WIDTH-2||sr<1||sc>HEIGHT-2||sc<1) {
return;
}
//Gets a number between 0-3
switch (randomGen.nextInt(4)) {
case 0:
if(hasUnvisited(grid,sr,sc)) {
if(sc+2>HEIGHT-1) {
}else if(grid[sr][sc+2]!='.'){
grid[sr][sc+1]='.';
pather(grid,sr,sc+2);
}
pather(grid,sr,sc);
}
break;
case 1:
if(hasUnvisited(grid,sr,sc)) {
if(sc-2<0) {
} else if(grid[sr][sc-2]!='.'){
grid[sr][sc-1]='.';
pather(grid,sr,sc-2);
}
pather(grid,sr,sc);
}
break;
case 2:
if(hasUnvisited(grid,sr,sc)) {
if(sr+2>WIDTH-1) {
}else if(grid[sr+2][sc]!='.'){
grid[sr+1][sc]='.';
pather(grid,sr+2,sc);
}
pather(grid,sr,sc);
}
break;
case 3:
if(hasUnvisited(grid,sr,sc)) {
if(sr-2<0) {
} else if(grid[sr-2][sc]!='.') {
grid[sr-1][sc]='.';
pather(grid,sr-2,sc);
}
pather(grid,sr,sc);
}
break;
}
}
//Returns a complete maze, gets the carved out paths from the pather function,
//then 'cleans it up' to return a useable maze format for the game.
private char[][] mazer() {
grid = new char[WIDTH][HEIGHT];
//Initialize Grid with all walls
for (int i=0;i<WIDTH;i++)
{
for (int j=0;j<HEIGHT;j++)
{
grid[i][j]= '#';
}
}
//Starting from row and column 1 and 1, respectively.
int sr=1,sc=1;
//Carve Out the Grid
pather(grid,sr,sc);
/*
//Draw Vertical Surrounding Walls
for (int j=0;j<HEIGHT;j++)
{
grid [0][j]= '#';
grid [WIDTH-1][j]= '#';
}
//Draw Horizontal Surrounding Walls
for (int j=0;j<WIDTH;j++)
{
grid [j][0]= '#';
grid [j][HEIGHT-1]= '#';
}
*/
//JUST FOR DEBUGGING:
for (int i=0;i<HEIGHT;i++)
{
for (int j=0;j<WIDTH;j++)
{
System.out.print(grid[j][i]);
}
System.out.println("");
}
//JUST FOR DEBUGGING ERASE IMMEDIATELY AFTER DONE WITH
return grid;
}
public Maze (int wIn, int hIn) {
WIDTH = wIn;
HEIGHT = hIn;
grid = mazer();
}
//After Debugging the maze:
public static void main(String[] args) {
Maze maze = new Maze(15,10);
}
}
I fix your solution, the problem is the corner cases checking.
The main changes:
sc+2 > HEIGHT-1 => sc+2 > HEIGHT-2
sr+2 > WIDTH-1 => sr+2 > WIDTH-2
The updated code:
import java.util.Random;
public class Maze {
private char[][] grid;
private final int WIDTH;
private final int HEIGHT;
Random randomGen = new Random();
//Checks to see if any of the surrounding cells are un
private boolean hasUnvisited (char[][] grid, int sr, int sc) {
if (sc+2 > HEIGHT-2) {
} else if (grid[sr][sc+2]=='#') {
return true;
}
if (sc-2 < 0) {
} else if (grid[sr][sc-2]=='#') {
return true;
}
if (sr+2 > WIDTH-2) {
} else if (grid[sr+2][sc]=='#') {
return true;
}
if (sr-2 < 0) {
} else if (grid[sr-2][sc]=='#') {
return true;
}
return false;
}
//Visits each cell, turns it to '.'
private void pather (char[][] grid, int sr, int sc) {
//Sets current cell to '.' to mark as visited
grid[sr][sc] = '.';
//"Clipping": if it is at edge of grid, don't carve any more, just return.
if (sr>WIDTH-2||sr<1||sc>HEIGHT-2||sc<1) {
return;
}
//Gets a number between 0-3
switch (randomGen.nextInt(4)) {
case 0:
if(hasUnvisited(grid,sr,sc)) {
if(sc+2>HEIGHT-2) {
}else if(grid[sr][sc+2]!='.'){
grid[sr][sc+1]='.';
pather(grid,sr,sc+2);
}
pather(grid,sr,sc);
}
break;
case 1:
if(hasUnvisited(grid,sr,sc)) {
if(sc-2<0) {
} else if(grid[sr][sc-2]!='.'){
grid[sr][sc-1]='.';
pather(grid,sr,sc-2);
}
pather(grid,sr,sc);
}
break;
case 2:
if(hasUnvisited(grid,sr,sc)) {
if(sr+2>WIDTH-2) {
}else if(grid[sr+2][sc]!='.'){
grid[sr+1][sc]='.';
pather(grid,sr+2,sc);
}
pather(grid,sr,sc);
}
break;
case 3:
if(hasUnvisited(grid,sr,sc)) {
if(sr-2<0) {
} else if(grid[sr-2][sc]!='.') {
grid[sr-1][sc]='.';
pather(grid,sr-2,sc);
}
pather(grid,sr,sc);
}
break;
}
}
//Returns a complete maze, gets the carved out paths from the pather function,
//then 'cleans it up' to return a useable maze format for the game.
private char[][] mazer() {
grid = new char[WIDTH][HEIGHT];
//Initialize Grid with all walls
for (int i=0;i<WIDTH;i++)
{
for (int j=0;j<HEIGHT;j++)
{
grid[i][j]= '#';
}
}
//Starting from row and column 1 and 1, respectively.
int sr=1,sc=1;
//Carve Out the Grid
pather(grid,sr,sc);
/*
//Draw Vertical Surrounding Walls
for (int j=0;j<HEIGHT;j++)
{
grid [0][j]= '#';
grid [WIDTH-1][j]= '#';
}
//Draw Horizontal Surrounding Walls
for (int j=0;j<WIDTH;j++)
{
grid [j][0]= '#';
grid [j][HEIGHT-1]= '#';
}
*/
//JUST FOR DEBUGGING:
for (int i=0;i<HEIGHT;i++)
{
for (int j=0;j<WIDTH;j++)
{
System.out.print(grid[j][i]);
}
System.out.println("");
}
//JUST FOR DEBUGGING ERASE IMMEDIATELY AFTER DONE WITH
return grid;
}
public Maze (int wIn, int hIn) {
WIDTH = wIn;
HEIGHT = hIn;
grid = mazer();
}
//After Debugging the maze:
public static void main(String[] args) {
Maze maze = new Maze(17,17);
}
}
OUTPUT(17*17):
#################
#.#.............#
#.#######.#####.#
#.......#...#...#
#######.#.#.#####
#.#.....#.#.#...#
#.#.#####.#.#.#.#
#...#.....#...#.#
#.#######.#####.#
#.......#.....#.#
#######.#######.#
#.......#.....#.#
#.#######.###.#.#
#.#.......#.#.#.#
#.#######.#.#.#.#
#.........#.....#
#################
But when it comes to even width and height, it output a little bit weird(but correct, anyway) because of the move is +2.
OUTPUT(18*18):
################
#.......#.....##
#######.###.#.##
#.#.....#...#.##
#.#.#####.###.##
#.#.#.......#.##
#.#.#######.#.##
#...#.....#.#.##
#.###.###.#.#.##
#...#.#.#.#.#.##
###.#.#.#.#.#.##
#.#.#.#...#.#.##
#.#.#.#.###.#.##
#.....#.....#.##
################
################
My suggestion is try to refactor your solution to generate the path by 1 step move. Your code never generate a path like
#####
#.#.#
#...#
#####
since it walks the map by 2 step move.