Perfect maze generation – tile based version

December 6, 2008 • Game design, Php by Emanuele Feronato • 13 Comments

You may wonder why I am publishing another maze script.

The reason is simple: in Perfect maze generation with AS3 post and previous ones I just showed you how to make a perfect maze, but it’s not the kind of maze you can use in tile based or roguelike games.

Why not? Because walls aren’t tiles but just a side of the tile. In tile based games, walls are solid, but in my mazes walls are just paper sheets placed between a tile and another.

And it’s not over: in future posts (yes, expect more mazes, so what?) we’ll see how to convert a perfect maze into a dungeon.

This time I used PHP but it’s easily adaptable to AS3 or whatever other language, and of course I used backtracking.

The script is similar to the other ones, anyway I want to focus on maze size: in a normal perfect maze the size of the maze is exactly the number of empty spaces (tiles) we have on each side.

This happens because walls are not solid tiles, but just lines between a tile and another. Same thing for the boundaries.

In a tile based maze, a wall is a concrete tile, and same thing for the boundaries, so if you want a tile based maze with (virtually) the same walkable tiles as a normal (x,y) one, your size has to be (x*2+1,y*2+1).

Finally, when you walk through the maze removing walls, in tile based mazes you must walk through 2 tiles at every step, assuming the first tile is a wall and the second one is the tile you want to land on.

So here it is the script

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

<?php
// max number of horizontal/vertical walkable tiles
$maze_width = 30;
$maze_height = 30;
$maze = array();
$moves = array();
$width = 2*$maze_width+1;
$height = 2*$maze_height+1;
for($x=0;$x<$height;$x++){
     for($y=0;$y<$width;$y++){
          $maze[$x][$y]=1;
     }
}
$x_pos = 1;
$y_pos = 1;
$maze[$x_pos][$y_pos]=0;
array_push($moves,$y_pos+($x_pos*$width));
while(count($moves)){
     $possible_directions = "";
     if($maze[$x_pos+2][$y_pos]==1 and $x_pos+2!=0 and $x_pos+2!=$height-1){
          $possible_directions .= "S";
     }
     if($maze[$x_pos-2][$y_pos]==1 and $x_pos-2!=0 and $x_pos-2!=$height-1){
          $possible_directions .= "N";
     }
     if($maze[$x_pos][$y_pos-2]==1 and $y_pos-2!=0 and $y_pos-2!=$width-1){
          $possible_directions .= "W";
     }
     if($maze[$x_pos][$y_pos+2]==1 and $y_pos+2!=0 and $y_pos+2!=$width-1){
          $possible_directions .= "E";
     }
     if($possible_directions){
          $move = rand(0,strlen($possible_directions)-1);
          switch ($possible_directions[$move]){
               case "N": $maze[$x_pos-2][$y_pos]=0;
                         $maze[$x_pos-1][$y_pos]=0;
                         $x_pos -=2;
                         break;
               case "S": $maze[$x_pos+2][$y_pos]=0;
                         $maze[$x_pos+1][$y_pos]=0;
                         $x_pos +=2;
                         break;
               case "W": $maze[$x_pos][$y_pos-2]=0;
                         $maze[$x_pos][$y_pos-1]=0;
                         $y_pos -=2;
                         break;
               case "E": $maze[$x_pos][$y_pos+2]=0;
                         $maze[$x_pos][$y_pos+1]=0;
                         $y_pos +=2;
                         break;        
          }
          array_push($moves,$y_pos+($x_pos*$width));
     }
     else{
          $back = array_pop($moves);
          $x_pos = floor($back/$width);
          $y_pos = $back%$width;
     }
}
// drawing the maze
echo "<code style = \"font-size:10px;line-height:8px\">";
for($x=0;$x<$height;$x++){
     for($y=0;$y<$width;$y++){
          if($maze[$x][$y]==1){
               echo "#";
          }
          else{
               echo "&nbsp;";
          }
     }
     echo "<br>";
}
echo "</code>";
?>

At lines 3-4 you define maze size

And this is a demo of the script with a step-by-step explaination of the entire process during the creation of a 8×8 maze

If you want to translate it into AS3, I will be glad to publish it.

Next time, I’ll show you the differences between this maze and a dungeon.

Rate this post: 1 Star2 Stars3 Stars4 Stars5 Stars (13 votes, average: 5.00 out of 5)
Loading ... Loading ...
Be my fan on Facebook and follow me on Twitter! Exclusive content for my Facebook fans and Twitter followers

This post has 13 comments

  1. Joe

    on December 6, 2008 at 5:18 pm

    Dear Emanuel,

    Keep up the great tutorials! I was working on my own version of your floating ball one… could you keep going with that one? I am anxiously waiting for the next installment!

  2. Pedro Taranto

    on December 6, 2008 at 9:58 pm

    Hi Emanuele,

    I have just ported the code to AS3.
    If you click on stage it generates another maze.

    demo: http://www.pedrotaranto.com.br/labs/maze/tiledMazeGen.swf
    source: http://www.pedrotaranto.com.br/labs/maze/TiledMazeGen.as

    Its easy to implement a step by step to show how it is beeing generated.

    Now I am figuring out how to find the best finish position.

  3. joox

    on December 6, 2008 at 11:51 pm

    I think it just makes it so much easier to do it recursively, and you don’t have to keep track of your moves.

    Here’s my pseudocode-ish recursive function.

    Let’s say that maze is an 2D array initialized with all ones. 1 means wall. 0 means floor.

    function makemaze(x,y) {

    maze[x][y] = 0;

    chose random order of the 4 directions up, down, left right.

    loop through the 4 directions {

    if (direction==up AND y-2>0 AND maze[x][y-2]==1) makemaze[x][y-2];

    if (direction==right AND x+20 AND maze[x-2][y] == 1) makemaze[x-2][y];

    if (direction==down AND y+2<height AND maze[x][y+2]==1) makemaze[x][y+2];

    }

    }

    That’s all. Call makemaze(x,y) with any random x and y within the dimensions. No need to worry about start position. In a maze, any point on the path will be connected to any other point on the path.

  4. joox

    on December 6, 2008 at 11:57 pm

    Just noticed that some of the text dissapeared. Something to do with greater than and smaller than characters I guess.

    The LEFT part is half missing and mixed with the RIGHT part.

    (LT = less than, GT = greater than)

    Should be:

    if (direction==right AND x+2 LT width AND maze[x+2][y] == 1) makemaze[x+2][y];

    if (direction==left AND x-2 GT 0 AND maze[x-2][y] == 1) makemaze[x-2][y];

  5. Pedro Taranto

    on December 7, 2008 at 2:30 am

    Here you can see the step by step maze generation

    demo: http://www.pedrotaranto.com.br/labs/maze/stepByStepTiledMazeGen.swf
    source: http://www.pedrotaranto.com.br/labs/maze/StepByStepTiledMazeGen.as

    tomorrow I will try to use recursion and post the result here

  6. Pedro Taranto

    on December 7, 2008 at 2:48 am

    BTW fell free to modify my code and post the result here too

  7. JL

    on December 8, 2008 at 11:00 am

    I’m a complete noob at Flash Game Programming. Your tutorials are very inspiring and helpful. Especially the tutorials in AS3.0 – since that is the language that I am studying right now.

    Yes, please, an AS 3.0 version of your new maze generator would be fantastic.

    Keep it up.

  8. Perfect maze generation - tile based version - AS3 : Emanuele Feronato

    on December 8, 2008 at 12:34 pm

    [...] publishing Perfect maze generation – tile based version written in Php, I got some emails asking for an AS3 [...]

  9. The magic of compound objects with Box2D : Emanuele Feronato

    on December 12, 2008 at 7:28 pm

    [...] first let’s take a look at what I am going to create: a perfect tile based maze, made with small squares representing the tiles and managed as a single [...]

  10. Understanding roguelike dungeons : Emanuele Feronato

    on June 2, 2009 at 3:59 pm

    [...] part of a Roguelike game is the dungeon: unlike solid perfect mazes like the one explained at Perfect maze generation – tile based version, roguelike dungeons have rooms, corridors, loops… not the kind of stuff we can obtain with a [...]

  11. Tarcísio Gruppi

    on June 2, 2009 at 7:37 pm

    I did a slightly better version of code in PHP, I will make a version of AS that come home and post here to judge.

    http://codepad.org/oHHTOhuP

    –
    Translated by Google Translator

  12. Generating mazes in ColdFusion

    on July 24, 2009 at 2:40 pm

    [...] port of Emanuele Feronato’s PHP code to generate mazes. You can find her blog entry here. [...]

  13. Tarcisio Gruppi

    on March 22, 2010 at 12:22 am

    I had forgotten to send the class in AS3.

    http://codepad.org/0lH327ZR

< >