Hello everyone!
It’s been a while since I’ve posted something here, and the fact is that I didn’t come up with very creative ideas for good Processing projects, and when I came up with them they just were too complicated for me to code or I did lose interest (or time) to work on them (I’m still a student and since last year I wasn’t even attending uni). Also, I’m more used to code in C++ for school, so I use Processing very rarely and when I need to do something very graphically-complex (something I’m still unable to do in C++ for lack of knowledge on graphic libraries).
Anyways, now I have a bunch of free time between university exams, and in this weekend I programed this little beauty: a recursive randomized maze generator! (Here’s an image of what it looks like:)
First of all, I’m going to say that this is not my first attempt on this project. I already coded a similar thing in the past (about 2 or 3 years ago), but it was much slower (it didn’t have the recursive function that allows this “beast” to be ultra-fast) and a little buggy too. Also, that project was kind of a ripoff from a tutorial I found on YouTube, so it wasn’t even my project.
Then I tried to redo my work, this time focusing on the logic besides it and working not to follow any tutorial. It had to be mine. But I was hopeless, after 2 months of head-scratching and buggy things I almost forgot of its existence and decided to abandon the project.
But now, after almost 3 years from its predecessors, I found that fossils on my PC and decided to give them new birth, and after just 3 days of serious coding the very good version of this work is DONE!
With this program, you’ll be able to run a completely randomized search through a quite large grid of square cells, and “dig” onto it a randomized maze that you’ll be able to solve using keyboard input (I kinda dislike working with sprites, and I really like when a program is clean and monochrome, so its graphics side is not on the fancy side).
The cool fact is that it’s programmed using a recursive function that searches over 800 cells, so I think I did a good job on keeping the code clean and fast (something I don’t necessarily do every time, really proud of that) and it’s almost instant-generated (which is a very good upside, you don’t have to wait for ages in order to get it to generate a new randomized maze).
Also, I kind of made it’s generation custom adding a slider (from the ControlP5 library) that allows to have a “linearity” parameter on the maze generation, which controls how much the single paths will tend to be straight instead of looping on itself resulting in a more complicated maze.
And most importantly, it will be very easy for me (and for you, if you’ll want to add something to it) to debug and maintain the code, because for once in my life I remembered to comment almost every single line! (Another great problem that keeps me out from almost every big project I take on: I always forget to comment code, so every time I forget what a function or a line does and I’m no longer able to expand it in a good way, and it always comes up as a big, not-working mess of code)
I’m also going to add that it will be my job to keep it updated with some cool new features that I want to add, the proudest of them all being able to create a file to save a good maze layout you’ve solved in a file and be able to load it and play it every time you want to. I think I already have kind of an idea on how to make it, but I don’t have implemented it yet.
Now, here’s the code for the project. I sincerely hope that no-one who sees this is about to steal it and copy the code somewhere else pretending it’s his work, because it would be just unfair, but I’m assuming everyone who sees this project is a good person enough not to do it.
In order to make it work, you’ll just put these 4 files (saved as .pde, obviously) in a single folder, and name the folder with the same name as the file containing the void setup() and void draw() functions. Then, you’ll open the first file (the one containing this 2 functions) and run the code. In this way there will be no issues on having all the files being misread from the compiler, and everything will work just fine.
Remember also to install the ControlP5 library if you didn’t install it before. It’s necessary for the main menu shown when you run the program.
Enough talking, here’s the files!
First file (main)
import controlP5.*;
ControlP5 controls;
final int gridOffset=25, sliderDim=120, buttonDim=80;
float linearity=0.5;
int xStart=0, yStart=0;
boolean startMenu=true, mazeSolved=false;
Cell grid[][], cell;
ArrayList<Cell> path=new ArrayList<Cell>();
Player player, target;
void keyTyped() {
if (!mazeSolved) player.move(grid, key);
}
void setup() {
size(750, 750);
textAlign(CENTER, CENTER);
controls=new ControlP5(this);
controls.addSlider("linearity").setPosition(width/2-sliderDim/2, height/2+80).setSize(sliderDim, 30).setLabel("").setRange(0, 0.99);
controls.addButton("generate").setPosition(width/2-buttonDim/2, height/2+200).setSize(buttonDim, 20).setLabel("Generate Maze");
//setting player at starting position, target at the
//right-bottom corner of the maze
player=new Player(xStart, yStart, gridOffset);
target=new Player(width/gridOffset-1, height/gridOffset-1, gridOffset);
//setup for the grid
grid=new Cell[width/gridOffset][height/gridOffset];
for (int a=0; a<width/gridOffset; a++)
for (int b=0; b<height/gridOffset; b++) grid[a][b]=new Cell(a, b, gridOffset);
}
void draw() {
background(40);
stroke(128);
if (startMenu) {
background(255);
fill(0);
textSize(50);
text("Maze Generator!", width/2, height/2);
textSize(15);
text("Use this slider to adjust the linearity of the maze\n(0 is more convoluted, 1 is more linear", width/2, height/2+135);
} else if (!mazeSolved) {
//displaying background and maze grid
drawGrid(width, height, gridOffset);
for (int a=0; a<width/gridOffset; a++)
for (int b=0; b<height/gridOffset; b++)
if (grid[a][b].visited) grid[a][b].display(color(100), color(255));
if (!player.checkSolved(target)) {
//displaying the player and the target
player.display(color(0, 50, 200));
if (grid[target.x][target.y].visited) target.display(color(200, 0, 0));
//redrawing the borders for the occupied cells
grid[player.x][player.y].displayBorders(color(255));
grid[target.x][target.y].displayBorders(color(255));
} else {
//maze has been solved, change
//display menu
mazeSolved=true;
textSize(75);
}
} else if (mazeSolved) {
//drawing the background grid for the non-visited cells
drawGrid(width, height, gridOffset);
//drawing the maze
for (int a=0; a<width/gridOffset; a++)
for (int b=0; b<height/gridOffset; b++)
if (grid[a][b].visited) grid[a][b].display(color(100), color(255));
//drawing player and endwall
player.display(color(0, 200, 50));
grid[player.x][player.y].displayBorders(color(255));
strokeText("Maze solved!", 2, width/2, height/2, color(0), color(255));
}
}
//function to print a background grid (will
//not be visible most cases, because the maze
//will be printed above it)
void drawGrid(int w, int h, int off) {
for (int a=0; a<w-1; a+=off)
for (int b=0; b<h-1; b+=off) {
line(0, a, width, a);
line(b, 0, b, height);
}
}
//function to print a text string with some border of different color
void strokeText(String t, int dim, int x, int y, color bCol, color tCol) {
fill(bCol);
text(t, x-dim, y);
text(t, x+dim, y);
text(t, x, y-dim);
text(t, x, y+dim);
fill(tCol);
text(t, x, y);
}
//function called from the starting menu button
void generate() {
//hiding button and slider
controls.getController("linearity").hide();
controls.getController("generate").hide();
//setting as visited the first cell, adding it to the path
grid[xStart][yStart].visited=true;
path.add(grid[xStart][yStart]);
//generating a new maze
cell=mazeGen(grid, grid[xStart][yStart], (width/gridOffset)*(height/gridOffset)-1, 0); //the last number is the length of the path
println("Maze generated correctly.");
//checking for the number of non-visited cells
int notVis=0;
for (int a=0; a<width/gridOffset; a++)
for (int b=0; b<height/gridOffset; b++)
if (!grid[a][b].visited) notVis++;
//buffering the number of non visited cells
//if there's more than 0, display a warning message
if (notVis!=0) print("WARNING: ");
println(notVis+" cells have not been visited.");
//change display menu
startMenu=false;
}
Second file (Cell class)
class Cell {
int x, y; //position
int dim; //dimension
boolean visited=false; //check for being visited (on the grid)
boolean[] walls={true, true, true, true}; //east, south, west, north
//used to display the single cell on the grid
void display(color f, color s) {
fill(f);
noStroke();
square(this.x*this.dim, this.y*this.dim, this.dim);
//I need to separate the cell from its borders
//because it might not have every border marked as "true"
this.displayBorders(s);
}
//used to display the borders of a particular cell
void displayBorders(color s) {
stroke(s);
//if a particular border is true (it appears on the actual maze),
//I print it on the screen in the correct position
if (this.walls[0]) line(this.x*this.dim+this.dim, this.y*this.dim, this.x*this.dim+this.dim, this.y*this.dim+this.dim);
if (this.walls[1]) line(this.x*this.dim, this.y*this.dim+this.dim, this.x*this.dim+this.dim, this.y*this.dim+this.dim);
if (this.walls[2]) line(this.x*this.dim, this.y*this.dim, this.x*this.dim, this.y*this.dim+this.dim);
if (this.walls[3]) line(this.x*this.dim, this.y*this.dim, this.x*this.dim+this.dim, this.y*this.dim);
}
//used to create a new Cell object that is the
//copy of another object with some properties
Cell copyCell() {
Cell b=new Cell(this.x, this.y, this.dim);
b.visited=this.visited;
for (int a=0; a<this.walls.length; a++) b.walls[a]=this.walls[a];
return b;
}
Cell(int a, int b, int c) { //constructor
this.x=a;
this.y=b;
this.dim=c;
}
}
//this calculates the number of free available
//adjacent cells to generate the path on
int numNb(Cell c, Cell[][] g) {
int n=0; //start at 0
for (int a=(c.x<1 ? c.x : c.x-1); a<=(c.x>=width/c.dim-1 ? c.x : c.x+1); a++)
for (int b=(c.y<1 ? c.y : c.y-1); b<=(c.y>=height/c.dim-1 ? c.y : c.y+1); b++)
//if the cell on the same X or Y axis has been visited, add it to
//the list of occupied adjacent cells
if ((a==c.x || b==c.y) && !g[a][b].visited) n++;
//return the number of non-free cells
return n;
}
Third file (function that generates the maze)
Cell mazeGen(Cell[][] g, Cell c, int depth, int direction) {
Cell next=new Cell(-1, -1, c.dim);
int dir=0, neighbours=numNb(c, g);
boolean blindSpot=false;
boolean tried0=false, tried1=false, tried2=false, tried3=false;
//if I can go in any direction from the cell I'm now in,
//I start a random search for a new cell available
if (neighbours>=0) do {
//random chance to keep the direction I was coming from
if (random(0, 1)<linearity) dir=direction;
else dir=(int)random(0, 4); //generate random direction
//checking for already visited directions
if (dir==0) tried0=true;
else if (dir==1) tried1=true;
else if (dir==2) tried2=true;
else if (dir==3) tried3=true;
//check for boundaries conditions and generate new cell
if (dir==0 && c.x<width/c.dim-1 && !g[c.x+1][c.y].visited) next=g[c.x+1][c.y].copyCell();
else if (dir==1 && c.y<height/c.dim-1 && !g[c.x][c.y+1].visited) next=g[c.x][c.y+1].copyCell();
else if (dir==2 && c.x>0 && !g[c.x-1][c.y].visited) next=g[c.x-1][c.y].copyCell();
else if (dir==3 && c.y>0 && !g[c.x][c.y-1].visited) next=g[c.x][c.y-1].copyCell();
//if I do not reach a new cell, I've hit a blindspot
if (tried0 && tried1 && tried2 && tried3) {
blindSpot=true;
break;
}
} while (next.x==-1 && next.y==-1);
//otherwise, I've hit a blindspot
//and I need to backtrack more
else blindSpot=true;
//if the cell has not updated, I reached
//a spot in which I have no available adjacent cells;
//I start backtracking on the path I built in order to get
//to the last spot in which there is an available adjacent cell
if (blindSpot) {
next=path.get(path.size()-1).copyCell();
path.remove(path.size()-1);
} else {
//update next cell
g[c.x][c.y].walls[dir]=false;
g[next.x][next.y].walls[(dir>=2 ? dir-2 : dir+2)]=false;
g[next.x][next.y].visited=true;
path.add(g[c.x][c.y]); //add the cell to the tracked path
depth--; //go deeper in the generation process
}
if (checkFinished(g) || depth==0 || (next.x==0 && next.y==0)) {
//finished generate maze for the desired depth
return next;
} else return mazeGen(g, next, depth, dir);
}
//checks if every cell of the grid has been visited
boolean checkFinished(Cell[][] g) {
for (int a=0; a<width/gridOffset; a++)
for (int b=0; b<height/gridOffset; b++)
if (!g[a][b].visited) return false;
//return true if it doesn't find
//any non-visited cell
return true;
}
Fourth file (class to handle Player movements)
NOTE: This class is inherited from another project I took over,
it was a similar version of this program but it was much more slow and buggy.
I’m not intentioned to post it there, unless you ask me so
/*
CLASS INHERITED FROM ANOTHER PROJECT
(modified to fit the purpose of the project)
*/
class Player {
int x, y; //position
int dim; //dimension
//used to check if two Player objects have the same position
boolean checkSolved(Player other) {
return (this.x==other.x && this.y==other.y);
}
//used to move a single object using keyboard input (WASD or arrows)
void move(Cell[][] grid, char k) {
if ((k=='w' || (k==CODED && k==UP)) && !grid[this.x][this.y].walls[3]) this.y--;
if ((k=='a' || (k==CODED && k==LEFT)) && !grid[this.x][this.y].walls[2]) this.x--;
if ((k=='s' || (k==CODED && k==DOWN)) && !grid[this.x][this.y].walls[1]) this.y++;
if ((k=='d' || (k==CODED && k==RIGHT)) && !grid[this.x][this.y].walls[0]) this.x++;
}
//used to display a Player objet on the screen
void display(color c) {
fill(c);
noStroke();
square(this.x*this.dim, this.y*this.dim, this.dim);
}
Player(int a, int b, int c) { //constructor
this.x=a;
this.y=b;
this.dim=c;
}
}
Hope you’ll find interesting how I made it work, how I thought of coding every function inside it and most importantly you’ll enjoy solving paths over and over until this things has new functionalities I want to add. But for now, that’s it!
PS: For the very kind people out there who want to help me, I found out a little bug for which sometimes the maze won’t cover every single cell on the grid. You won’t have any issues on running the code, because I wanted this project to be published and I kind of hard-coded a solution for it, but you sometimes may generate an impossible maze (in which the ending cell that you need to reach, in order to solve the maze, is not generated) or find some “holes” here and there.
If you’re into help me, I will open another topic related to this bug fix, so you won’t need to spam this one of coding-related issues and use this one as a reference for the project. Thanks in advance!