Be my fan on FacebookPerfect maze generation with AS3
- November 28, 2008 by Emanuele Feronato
- Filed under Actionscript 3, Flash, Game design | 13 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.
(16 votes, average: 4.94 out of 5)
Loading ...They can be easily customized to meet the unique requirements of your project.
13 Responses
Leave a Reply
TUTORIAL SERIES:
- Una guida completa al gioco del poker online e una selezione dei migliori casino online.
- casino online
- migliori casino online
- BlackJack online
- casinò online
Hey cool tutorial.
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.
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.
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!
[...] 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 [...]
The Little Boy In The Puff Ball Hat Said “I Agree With Arxanas!!!!!!”
u know, this could be done in AS2.0, it would just need a little more work to get it done
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);
Great script
Is there a way to get the starting point and ending point from the script
Thanka