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
Perfect maze

This is not a perfect maze
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

else

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.

Rate this post: 1 Star2 Stars3 Stars4 Stars5 Stars (5 votes, average: 4.80 out of 5)
Loading ... Loading ...
If you found this post useful, please consider a small donation.

5 Responses

  1. T Munk says:
    September 1, 2006 at 9:10 pm

    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!

    Reply
  2. Leo says:
    November 2, 2006 at 6:18 pm

    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!

    Reply
  3. Jahn says:
    January 28, 2007 at 2:43 am

    $maze is the variable.
    [$pos] is the area of the array
    {2} designates one character versus the whole string at postition 2.

    Reply
  4. Perfect maze generation with AS3 : Emanuele Feronato says:
    November 28, 2008 at 4:38 pm

    [...] 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 [...]

    Reply
  5. Darty says:
    August 19, 2009 at 3:46 am

    Nice tutorial, takes me back to my second year of university where we had to do the exact same thing in c++

    Reply

Leave a Reply