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

  • 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:

Enjoy it and give me feedback.

  • 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!

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

  • Pingback: Perfect maze generation with AS3 : Emanuele Feronato()

  • 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

  • I did maze generation using a database. Try it out here:

    http://www.louigiverona.ru/mw