Step by step perfect maze generation with php
This is a project I made for teaching purpose.
First of all, let’s see what is a perfect maze.
From Maze Works: A perfect maze is defined as a maze which has one and only one path from any point in the maze to any other point. This means that the maze has no inaccessible sections, no circular paths, no open areas.
This is a perfect maze

This is not a perfect maze

With the script I provide, you can generate perfect mazes with a given length and height, and the cute thing is that the script will “think loud” its actions in order to explain how does it work.
It uses backtracking.
The program, like most maze generators, starts off by building a maze with all the walls between the cells intact.
Then chooses a random cell where to start and mark the current cell as ‘Visited’;
If the current cell has any neighbour cells which have not been visited
- Randomly choose one of these cells
- Knock down the wall between current and choosen cells
- Make the chosen cell the current cell
- Mark the new current cell as visited
else
- Go to your previoulsy visited cell
Until all cells are visited
So, you can use it both for generating perfect mazes, and to show how would you generated a perfect maze.
In the example, the script executed with a 5×5 maze.
Later I will explain the code, meanwhile here it is:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 |
<?php $dim_x = 5; $dim_y = 5; $cell_count = $dim_x*$dim_y; $moves = array(); // MAZE CREATION for($x=0;$x<$cell_count;$x++){ $maze[$x] = "01111"; // visted, NSEW } $pos = rand(0,$cell_count-1); $html .= "My start position is randomly set at $pos<br>"; $maze[$pos]{0} = 1; $visited ++; // determine possible directions while($visited<$cell_count){ $possible = ""; if((floor($pos/$dim_x)==floor(($pos-1)/$dim_x)) and ($maze[$pos-1]{0}==0)){ $possible .= "W"; } if((floor($pos/$dim_x)==floor(($pos+1)/$dim_x)) and ($maze[$pos+1]{0}==0)){ $possible .= "E"; } if((($pos+$dim_x)<$cell_count) and ($maze[$pos+$dim_x]{0}==0)){ $possible .= "S"; } if((($pos-$dim_x)>=0) and ($maze[$pos-$dim_x]{0}==0)){ $possible .= "N"; } $html .= "I am in $pos and I can go to: $possible<br>"; if($possible){ $visited ++; array_push($moves,$pos); $direction = $possible{rand(0,strlen($possible)-1)}; $html .= "I randomly choose to go $direction"; switch($direction){ case "N": $maze[$pos]{1} = 0; $maze[$pos-$dim_x]{2} = 0; $pos -= $dim_x; break; case "S": $maze[$pos]{2} = 0; $maze[$pos+$dim_x]{1} = 0; $pos += $dim_x; break; case "E": $maze[$pos]{3} = 0; $maze[$pos+1]{4} = 0; $pos ++; break; case "W": $maze[$pos]{4} = 0; $maze[$pos-1]{3} = 0; $pos --; break; } $maze[$pos]{0} = 1; } else{ $html .= "No possible moves, I have to perform a backtracking<br>"; $pos = array_pop($moves); } $html .= "<table style = \"border:2px solid black\"; cellspacing = \"0\" cellpadding = \"0\">"; for($x=0;$x<$cell_count;$x++){ if($x % $dim_x == 0){ $html .= "<tr>"; } $style = $maze[$x]{2}.$maze[$x]{3}; if($x!=$pos){ $html.= "<td class = \"$style\">$x</td>"; } else{ $html .= "<td class = \"$style\"><strong>$x</strong></td>"; } if(($x % $dim_x) == ($dim_x-1)){ $html .= "</tr>"; } } $html .= "</table>"; } $html.= "Hooray, that's the final maze"; ?> <html> <head> <style> body{line-height:25px;} td{text-align:center;} .00{width:50px;height:50px;border:0px;} .01{width:50px;height:50px;border:0px;border-right:1px solid black;} .10{width:50px;height:50px;border:0px;border-bottom:1px solid black;} .11{width:50px;height:50px;border:0px;border-bottom:1px solid black;border-right:1px solid black;} strong{color:red;} </style> </head> <body> <?php echo $html; ?> </body> </html> |
Enjoy it and give me feedback.





(7 votes, average: 4.86 out of 5)








This post has 7 comments
T Munk
Excellent bit of work! I was looking for something to randomly generate a dungeon for each user for one of the quests in my game, and your code turns out to be a really nice jumping-off point. (:
Note: firefox doesn’t like class names that start with a number in stylesheets, and thus doesn’t render your pretty maze correctly. You can fix this in your code by adding a letter to the class name:
Line 78:
Line 81:
Line 98: .c00{width:50px;
ditto with line 99,100,101.
Thanks!
Leo
Hey… im not a expert in PHP, but i wanna ask:
Whats does $maze[$pos]{0} = 1; do?
and $maze[$pos]{2} = 0;?
and $maze[$pos+1]{4} = 0;?
etc…
i dont catch those lines!
please, help!
Jahn
$maze is the variable.
[$pos] is the area of the array
{2} designates one character versus the whole string at postition 2.
Perfect maze generation with AS3 : Emanuele Feronato
[...] already talked about perfect mazes a couple of years ago with Step by step perfect maze generation with php and Perfect maze generation with Flash actionscript, but now it’s time to make it with AS3 and [...]
Darty
Nice tutorial, takes me back to my second year of university where we had to do the exact same thing in c++
Mark
Hello,
Loved your maze example, I had the same issue as [T Munk] with firefox. Did my own generator a while ago but will improve it using tricks from your example.
Mine was as follows:
<?php
////////////////////////////////////////////////////////////////////////////////////////////
class grid {
function gen($x,$y) {
session_start();
$_SESSION['grid0'] = 0;
$current = 1;
$max = $x * $y;
while ($current <= $max):
$_SESSION['grid'.$current] = 0;
$_SESSION['completed'.$current] = 0;
$current = $current + 1;
endwhile;
}
function valid($excludeRef,$ref,$x,$y) {
$result = 0;
// Start and End Of Grid
$end_result = $ref / $x;
$start_result = ($ref – 1) / $x;
if(($ref – $x) ($x * $y)) { $down_ref = 0; }else{ $down_ref = $ref + $x; }
if(strpos($start_result, ‘.’) == ”) {
$left_ref = 0;
}else{
if(($ref – 1) ($x * $y)) { $right_ref = 0; }else{ $right_ref = $ref + 1; }
}
// 0 Out the Exclusion
if($up_ref == $excludeRef){$up_ref = 0;}
if($down_ref == $excludeRef){$down_ref = 0;}
if($left_ref == $excludeRef){$left_ref = 0;}
if($right_ref == $excludeRef){$right_ref = 0;}
// Gen Result
if($_SESSION['grid'.$ref] == 0 AND $_SESSION['grid'.$up_ref] == 0 AND $_SESSION['grid'.$down_ref] == 0 AND $_SESSION['grid'.$left_ref] == 0 AND $_SESSION['grid'.$right_ref] == 0 ) {
$result = $ref;
}
return $result;
}
}
////////////////////////////////////////////////////////////////////////////////////////////
class maze {
function fill($ref) {
$_SESSION['grid'.$ref] = 1;
}
function setstart($ref) {
$_SESSION['grid'.$ref] = 2;
}
function setend($ref) {
$_SESSION['grid'.$ref] = 3;
}
function comp($ref) {
$_SESSION['completed'.$ref] = 1;
}
function gen($start_ref,$x,$y) {
$grid = new grid;
$maze = new maze;
$grid->gen($x,$y);
$loop_create = 1;
$ref = $start_ref;
$path = $start_ref;
$maze->setstart($ref);
while($loop_create > 0):
// Start and End Of Grid
$end_result = $ref / $x;
$start_result = ($ref – 1) / $x;
// Gen Next Refs
if(($ref – $x) valid($ref,($ref – $x),$x,$y); }
if(($ref + $x) > ($x * $y)) { $down_ref = 0; }else{ $down_ref = $grid->valid($ref,($ref + $x),$x,$y); }
if(strpos($start_result, ‘.’) == ”) {
$left_ref = 0;
}else{
if(($ref – 1) valid($ref,($ref – 1),$x,$y); }
}
if(strpos($end_result, ‘.’) == ”) {
$right_ref = 0;
}else{
if(($ref + 1) > ($x * $y)) { $right_ref = 0; }else{ $right_ref = $grid->valid($ref,($ref + 1),$x,$y); }
}
// All Done for This Path?
$path_open = $up_ref + $down_ref + $left_ref + $right_ref;
if($path_open == 0) {
// Mark Cell; Finished
$maze->comp($ref);
// Try and Find Another
$find_cell_current = 1;
$find_cell_max = $x * $y;
$last_cell = $ref;
while($find_cell_current 0):
$rand = rand(1,4);
if($rand ==1){$next_cell=$up_ref;}
if($rand ==2){$next_cell=$down_ref;}
if($rand ==3){$next_cell=$left_ref;}
if($rand ==4){$next_cell=$right_ref;}
if($next_cell > 0){
$maze->fill($next_cell);
$loop_rand = 0;
$ref = $next_cell;
$path = $path . “-” . $next_cell;
}
endwhile;
}
endwhile;
// Choose an end point
//Draw
$maze->draw($x,$y);
}
function draw($x,$y) {
$current = 1;
$row = 1;
$max = $x * $y;
echo “”;
while ($current <= $max):
$value = $_SESSION['grid'.$current];
if($value == 0){ echo "”; }
if($value == 1){ echo “”; }
if($value == 2){ echo “”; }
if($value == 3){ echo “”; }
if($row == $x){ echo “”; $row = 0;}
$current = $current + 1;
$row = $row + 1;
endwhile;
echo “”;
echo “”;
$current = 1;
$row = 1;
$max = $x * $y;
echo “”;
while ($current <= $max):
$value = $_SESSION['grid'.$current];
if($value == 0){ echo 0; }
if($value == 1){ echo 1; }
if($value == 2){ echo 2; }
if($value == 3){ echo 3; }
if($row == $x){ echo '’; $row = 0;}
$current = $current + 1;
$row = $row + 1;
endwhile;
echo “”;
echo “”;
}
}
////////////////////////////////////////////////////////////////////////////////////////////
$maze = new maze;
////////////////////////////////////////////////////////////////////////////////////////////
$x = 40;
$y = 30;
////////////////////////////////////////////////////////////////////////////////////////////
?>
Marks Maze Bullshit
.contain {
border-width:2px;
border-color:black;
border-style:solid;
display:block;
float:left;
}
.clear {
clear:both;
}
.black {
color: black;
background-color: black;
width:20px;
height:20px;
display:block;
float:left;
}
.white {
color: white;
background-color: white;
width:20px;
height:20px;
display:block;
float:left;
}
.green {
color: green;
background-color: green;
width:20px;
height:20px;
display:block;
float:left;
}
.red {
color: red;
background-color: red;
width:20px;
height:20px;
display:block;
float:left;
}
Your Random Mark Maze!
gen(1,$x,$y);
?>
Refresh
Louigi Verona
I did maze generation using a database. Try it out here:
http://www.louigiverona.ru/mw