Perfect maze generation with AS3

November 28, 2008 by Emanuele Feronato
Filed Under Actionscript 3, Flash, Game design • 12 Comments 

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:

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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125

package {
	import flash.display.Sprite;
	import flash.events.Event;
	public class as3maze extends Sprite {
		// maze width and height, in cells
		var maze_width=24;
		var maze_height=19;
		// wall size, in pixels
		var wall_size=20;
		// array that will contain maze information
		var maze = new Array();
		// array to keep track of my moves
		var my_moves = new Array();
		// sprite to visually display the maze
		var maze_draw:Sprite = new Sprite();
		public function as3maze() {
			// determining the number of cells in the maze
			var cell_count=maze_width*maze_height;
			// random starting position
			var pos=Math.floor(Math.random()*cell_count);
			// I am on a cell, so I visited one. Let's count visited cells...
			var visited=1;
			for (var i=0; i<cell_count; i++) {
				// this array contains VISITED (0 = not visited), NORTH WALL (1=up;0=down), SOUTH WALL, EAST WALL, WEST WALL
				maze[i]=new Array(0,1,1,1,1);
			}
			// marking the cell I am on as visited
			maze[pos][0]=1;
			// loop to be executed until all cells have been visited
			while (visited<cell_count) {
				// check for possible moves
				var possible="";
				// possible move at west
				if ((Math.floor(pos/maze_width) == Math.floor((pos-1)/maze_width)) && (maze[pos-1][0] == 0)) {
					possible=possible+"W";
				}
				// possible move at east
				if ((Math.floor(pos/maze_width) == Math.floor((pos+1)/maze_width)) && (maze[pos+1][0] == 0)) {
					possible=possible+"E";
				}
				// possible move at south
				if (((pos+maze_width)<cell_count) && (maze[pos+maze_width][0] == 0)) {
					possible=possible+"S";
				}
				// possible move at north
				if (((pos-maze_width)>=0) && (maze[pos-maze_width][0] == 0)) {
					possible=possible+"N";
				}
				// if a move exists, crash a wall && mark new cell as visited     
				if (possible) {
					// increasing number of visited cells
					visited++;
					// saving my position the moves array
					my_moves.push(pos);
					// choosing a random direction
					var way=possible.charAt(Math.floor(Math.random()*possible.length));
					switch (way) {
						case "N" :
							// going north: crashing walls and updating position
							maze[pos][1]=0;
							maze[pos-maze_width][2]=0;
							pos-=maze_width;
							break;
						case "S" :
							// going south: crashing walls and updating position
							maze[pos][2]=0;
							maze[pos+maze_width][1]=0;
							pos+=maze_width;
							break;
						case "E" :
							// going east: crashing walls and updating position
							maze[pos][3]=0;
							maze[pos+1][4]=0;
							pos++;
							break;
						case "W" :
							// going west: crashing walls and updating position
							maze[pos][4]=0;
							maze[pos-1][3]=0;
							pos--;
							break;
					}
					// set the cell as visited
					maze[pos][0]=1;
					// if I cannot movie anymore, backtrack to a previously saved cell
				} else {
					pos=my_moves.pop();
				}
			}
			// start of maze drawing routine
			addChild(maze_draw);
			// black line
			maze_draw.graphics.lineStyle(1);
			maze_draw.graphics.moveTo(10,10);
			var start_y=10-wall_size;
			var start_x=0;
			// drawing walls: I only draw east and south walls, because a cell's south wall is southern cell's north wall
			// and same thing for the east/west ones
			for (i=0; i<cell_count; i++) {
				start_x+=wall_size;
				if ((i%maze_width) == 0) {
					start_y+=wall_size;
					start_x=10;
				}
				if (maze[i][2]==1) {
					// south
					maze_draw.graphics.moveTo(start_x,start_y+wall_size);
					maze_draw.graphics.lineTo(start_x+wall_size,start_y+wall_size);
				}
				if (maze[i][3]==1) {
					// east
					maze_draw.graphics.moveTo(start_x+wall_size,start_y);
					maze_draw.graphics.lineTo(start_x+wall_size,start_y+wall_size);
				}
			}
			// red line for maze border
			maze_draw.graphics.lineStyle(2,0xff0000);
			maze_draw.graphics.moveTo(10,10);
			maze_draw.graphics.lineTo(10+wall_size*maze_width,10);
			maze_draw.graphics.lineTo(10+wall_size*maze_width,10+wall_size*maze_height);
			maze_draw.graphics.lineTo(10,10+wall_size*maze_height);
			maze_draw.graphics.lineTo(10,10);
		}
	}
}

and this is the result:

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

Download the source code.

Rate this post: 1 Star2 Stars3 Stars4 Stars5 Stars (16 votes, average: 4.94 out of 5)
Loading ... Loading ...
If you found this post useful, please consider a small donation.
» Flash Templates provided by Template Monster are pre-made web design products developed using Flash technology.
They can be easily customized to meet the unique requirements of your project.

12 Responses to “Perfect maze generation with AS3”

  1. Shival on November 28th, 2008 5:16 pm

    Hey cool tutorial.

  2. joox on November 28th, 2008 5:25 pm

    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.

  3. Arxanas on November 28th, 2008 7:02 pm

    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.

  4. jeanpier on November 28th, 2008 8:33 pm

    Nice tutorial!

  5. subblue on November 29th, 2008 10:29 pm

    Very interesting, thanks for sharing.

  6. Arxanas on November 30th, 2008 4:04 am

    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

  7. Quarky Quantum on December 1st, 2008 5:47 am

    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.

  8. xavi on December 1st, 2008 7:04 pm

    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!

  9. Little Boy In The Puff Ball Hat on December 18th, 2008 12:40 am

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

  10. a guy on May 11th, 2009 10:56 am

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

  11. a guy on May 11th, 2009 11:08 am

    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, 0×000000);
    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);

Leave a Reply




Trackbacks

  1. Perfect maze generation - tile based version : Emanuele Feronato on December 6th, 2008 2:30 pm

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

flash games company