You are probably very familiar with mazes surprisingly fun puzzles that can keep you interested for a long time. In this section we talk about the AI involved in creating random but perfect mazes. But first you should know what a perfect maze is, as opposed to an imperfect one. A perfect maze is one in which exactly one path exists between every two cells. In a perfect maze, you can choose any two cells and there will always exist a path between the two but only one. In a perfect maze, a looped path is not possible, and there are no closed-off areas. In the figure above, you can see both perfect and imperfect mazes. The imperfect one has both a closed-off cell and multiple paths between some cells. The perfect maze has no closed-off areas, and only one path exists between any two cells. Here is a larger, more interesting perfect maze. ## Rules for the Perfect MazeThis is a pretty simple application that makes use of two-dimensional arrays to store information about each tile. The maze is tile-based, and each tile has four walls. Now let's look at the rules for creating a perfect maze. -
Choose how many rows and columns you want in the maze. You have `rows*columns`number of cells in this maze. All the walls of these cells are currently up. Create a variable called`cellsVisited`with a value of 0. -
Create an array called `visitedList`. When a cell is visited, it will be added to this array. -
Choose a random starting cell. Make this the current cell. Increment `cellsVisited`. -
If the value of `cellsVisited`is equal to the number of cells, your maze is finished. Otherwise move on to step 5. -
Create an array called `neighbors`. Look at each of the immediate neighbors of this cell. We will call them`"``east``"`,`"``west``"`,`"``north``"`, and`"``south``"`. Add any neighbor that has never been visited to the`neighbors`array. If any of the neighbors have at one time been visited, then they are not added to this array. -
Randomly choose a neighbor from the `neighbors`array. If the`neighbors`array is empty (indicating that all of the neighbors have been visited), then move on to step 9. Otherwise, continue to step 7. -
Move to this randomly selected neighbor, knocking down the wall between the current cell and this neighbor cell. -
Make this neighbor cell the current cell, and add it to the `visitedList`array. Return to step 5. -
Move to the previous cell in the `visited`array, deleting the cell you are currently in from the`visitedList`array. Return to step 5.
The images below show an example of how a 3X3 maze would be created. ## Using ActionScript to Create the Perfect MazeNow that you have a good understanding of the algorithm, let's take a look at how it can be written in ActionScript. If you truly understand this algorithm (which you can probably do without too much trouble), and if you have a firm grasp of ActionScript, you should be able to write the ActionScript for this algorithm on your own. But just in case you don't want to try, we have done it for you.
In maze.fla there are three layers: Object Definition, Implementation, and Assets. The Object Definition layer contains the algorithm that creates the maze in memory. The Implementation layer contains the ActionScript needed to create a visual representation of the maze that we created in memory. The Assets layer contains the movie clips needed to display the maze. We are most concerned with the ActionScript in the Object Definition layer, since that contains the AI algorithm for maze creation. There are 75 lines of code in this frame, all for one long function. 1 maze = {}; 2 maze.createMaze = function(horizontal, vertical) { 3 this.rows = horizontal; 4 this.columns = vertical; 5 this.totalCells = this.rows*this.columns; 6 this.startRow = random(this.rows)+1; 7 this.startColumn = random(this.columns)+1; 8 this.cellsVisited = 0; 9 this.currentCell = "cell"+this.startRow+"_" +this.startColumn; 10 this[this.currentCell] = {name:this.currentCell, x:this.startRow, y:this.startColumn, exists:true}; 11 this.visitList = []; 12 this.visitList.push(this[currentCell]); 13 while (this.cellsVisited<this.totalCells) { 14 var cell = this[this.currentCell]; 15 var neighbors = []; 16 if (cell.x-1>0) { 17 //west cell 18 var x = cell.x-1; 19 var y = cell.y; 20 var westCell = "cell"+x+"_"+y; 21 if (!this[westCell].exists) { 22 neighbors.push([westCell, "west", "east", x, y]); 23 } 24 } 25 if (cell.y-1>0) { 26 //north cell 27 var x = cell.x; 28 var y = cell.y-1; 29 var northCell = "cell"+x+"_"+y; 30 if (!this[northCell].exists) { 31 neighbors.push([northCell, "north", "south", x, y]); 32 } 33 } 34 if (cell.x+1<=this.rows) { 35 //east cell 36 var x = cell.x+1; 37 var y = cell.y; 38 var eastCell = "cell"+x+"_"+y; 39 if (!this[eastCell].exists) { 40 neighbors.push([eastCell, "east", "west", x, y]); 41 } 42 } 43 if (cell.y+1<=this.columns) { 44 //south cell 45 var x = cell.x; 46 var y = cell.y+1; 47 var southCell = "cell"+x+"_"+y; 48 if (!this[southCell].exists) { 49 neighbors.push([southCell, "south", "north", x, y]); 50 } 51 } 52 //randomly choose a neighbor 53 if (neighbors.length>0) { 54 var nextCell = random(neighbors.length); 55 //knock down wall 56 cell[neighbors[nextCell][1]] = true; 57 //retrieve the name of the new cell 58 var newName = neighbors[nextCell][0]; 59 this[newName] = {}; 60 var newCell = this[newName]; 61 newCell.exists = true; 62 newCell.x = neighbors[nextCell][3]; 63 newCell.y = neighbors[nextCell][4]; 64 newCell.name = this.currentCell; 65 //knock down the wall 66 newCell[neighbors[nextCell][2]] = true; 67 this.currentCell = newName; 68 this.visitList.push(this.currentCell); 69 ++this.cellsVisited; 70 } else { 71 //step back to the last cell 72 this.currentCell = this.visitList.pop(); 73 } 74 } 75 }; We begin by creating an object called In line 14 we create a reference to the object that represents the current cell. Lines 15 51 perform step 5 from above: The In line 53 we start step 6. If the -
Create an object for that neighbor cell. -
Knock down the walls between the current cell and the neighbor cell. -
Increment the `cellsVisited`variable. -
Set the neighbor cell as the current cell.
This is all done in lines 54 69. As mentioned above, if there were no elements in the I hope you'll agree that while this script was long, it wasn't all that complicated, right? ## Visual Implementation of the Perfect MazeWe are not going to dissect the ActionScript found in the Implementation layer. However, I will briefly describe what it does. First, it calls the The rest of the ActionScript in that frame handles the movie clip that the user moves through the maze. |

Macromedia Flash MX Game Design Demystified: The Official Guide to Creating Games with Flash -- First 1st Printing -- CD Included

ISBN: B003HP4RW2

EAN: N/A

EAN: N/A

Year: 2005

Pages: 163

Pages: 163

Authors: Jobe Makar

Similar book on Amazon

flylib.com © 2008-2017.

If you may any questions please contact us: flylib@qtcs.net

If you may any questions please contact us: flylib@qtcs.net