Perfect maze generation – tile based version

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

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.

Never miss an update! Join 13,000 developers and follow me on Facebook and Twitter
  • Joe

    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!

  • Pedro Taranto

    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.

  • joox

    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.

  • joox

    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];

  • Pedro Taranto

    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

  • Pedro Taranto

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

  • JL

    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.

  • Pingback: Perfect maze generation - tile based version - AS3 : Emanuele Feronato()

  • Pingback: The magic of compound objects with Box2D : Emanuele Feronato()

  • Pingback: Understanding roguelike dungeons : Emanuele Feronato()

  • 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

  • Pingback: Generating mazes in ColdFusion()

  • I had forgotten to send the class in AS3.

    http://codepad.org/0lH327ZR

  • I need an assistance on a assignment. I am to create a maze and perform a greedy search on it. can you help me please