Perfect maze generation with AS3

I 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 understand how can we use a perfect maze.

Think about a perfect maze as a maze with no loops.

Apart from the classic game where someone is trapped into a maze filled with enemies and items to collect, it’s not that hard turning a perfect maze into a randomly generated dungeon to make roguelike games.

From Wikipedia: The roguelike genre of computer games is characterized by randomization for replayability, permanent death, ASCII graphics, and turn-based movement. Games are typically dungeon crawls, with many monsters, items, and environment features. Death is frequent and often avoidable. Many roguelikes employ the majority of the keyboard to facilitate interaction with items and the environment. The name of the genre comes from the 1980 game, Rogue.

The script I am going to introduce uses backtracking.

From Wikipedia: Backtracking is a general algorithm for finding all (or some) solutions to some computational problem, that incrementally builds candidates to the solutions, and abandons each partial candidate c (“backtracks”) as soon as it determines that c cannot possibly be completed to a valid solution [1] [2] [3].

Let’s see the code:

and this is the result:

Next time I’ll show you how to turn a maze into a dungeon.

Download the source code.

  • Hey cool tutorial.

  • joox

    Too much code for a maze. Do it recursively and you need only a few lines for it.

    There is also no need for a random start position. You can start the same place every time if you want. It makes no difference in the result.

  • Arxanas

    AWESOME!!! But it could be a problem if there’s no starting point…

    It would be cool if the maze was integrated with the platform game, so that the random maze could be a level.

  • Nice tutorial!

  • Very interesting, thanks for sharing.

  • Arxanas

    Hey, do you remember that one Windows 2000 screensaver with the customizable 3-D maze?

    What if somebody made an AI to move through the maze and check possibilities (like in the screensaver) until if found the end?

    That would be cool. I would love to do it but I can’t for 2 reasons:

    1. I suck at AS3
    2. I suck at making AI’s

  • As soon as I read this post I thought 2 things:
    1: The same thing that Arxanas said.
    2: Make a updated version of TileBall with the maps randomly made using this.

  • that’s pretty cool.
    the only thing if you are going to make it into a dungeon, is that it will have to have big rooms and empty spaces where you can’t walk.
    other than that, awesome!

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

  • Little Boy In The Puff Ball Hat

    The Little Boy In The Puff Ball Hat Said “I Agree With Arxanas!!!!!!”

  • a guy

    u know, this could be done in AS2.0, it would just need a little more work to get it done

  • a guy

    here it is and done

    maze_width = 24;
    maze_height = 19;
    wall_size = 20;
    maze = new Array();
    my_moves = new Array();
    _root.createEmptyMovieClip(“maze_draw”, 1);
    cell_count = maze_width*maze_height;
    pos = Math.floor(Math.random()*cell_count);
    visited = 1;
    for (i=0; i<cell_count; i++) {
    maze[i] = new Array(0, 1, 1, 1, 1);
    }
    maze[pos][0] = 1;
    while (visited<cell_count) {
    var possible = “”;
    if ((Math.floor(pos/maze_width) == Math.floor((pos-1)/maze_width)) && (maze[pos-1][0] == 0)) {
    possible = possible+”W”;
    }
    if ((Math.floor(pos/maze_width) == Math.floor((pos+1)/maze_width)) && (maze[pos+1][0] == 0)) {
    possible = possible+”E”;
    }
    if (((pos+maze_width)=0) && (maze[pos-maze_width][0] == 0)) {
    possible = possible+”N”;
    }
    if (possible) {
    visited++;
    my_moves.push(pos);
    var way = possible.charAt(Math.floor(Math.random()*possible.length));
    switch (way) {
    case “N” :
    maze[pos][1] = 0;
    maze[pos-maze_width][2] = 0;
    pos -= maze_width;
    break;
    case “S” :
    maze[pos][2] = 0;
    maze[pos+maze_width][1] = 0;
    pos += maze_width;
    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 {
    pos = my_moves.pop();
    }
    }
    maze_draw.lineStyle(1);
    maze_draw.moveTo(10, 10);
    start_y = 10-wall_size;
    start_x = 0;
    for (i=0; i<cell_count; i++) {
    start_x += wall_size;
    if (((i/maze_width)-Math.floor(i/maze_width)) == 0) {
    start_y += wall_size;
    start_x = 10;
    }
    if (maze[i][2] == 1) {
    maze_draw.moveTo(start_x, start_y+wall_size);
    maze_draw.lineTo(start_x+wall_size, start_y+wall_size);
    }
    if (maze[i][3] == 1) {
    maze_draw.moveTo(start_x+wall_size, start_y);
    maze_draw.lineTo(start_x+wall_size, start_y+wall_size);
    }
    }
    maze_draw.lineStyle(2, 0x000000);
    maze_draw.moveTo(10, 10);
    maze_draw.lineTo(10+wall_size*maze_width, 10);
    maze_draw.lineTo(10+wall_size*maze_width, 10+wall_size*maze_height);
    maze_draw.lineTo(10, 10+wall_size*maze_height);
    maze_draw.lineTo(10, 10);

  • Carl

    Great script

    Is there a way to get the starting point and ending point from the script

    Thanka

  • Pingback: WIP: Maze Generator (editor script) « UnityCoder – Unity3D()

  • Pingback: Breadth-first pathfinding in a randomly generated maze | Emanuele Feronato()