INFT72-232

Advanced Website Development

Maze Generator and Solver

Topics

Introduction

Maze Generation Algorithm

Maze Solving Algorithm

Implementation

Program Usage

Introduction

Mazes provide the foundation of many walk around, pick em up and knock em down games. There are a number of effective maze generation algorithms .

These include

• The depth first search alogrithm

• The prim algorithm

• The krustral algorithm.

This implementation in Flash Mx 2004 uses the depth first search algorithm to generate and faind the path through a perfect maze. A perfect maze is one in which there is a path between any two cells. Also a perfect maze has no cycles.

This assignment was chosen to show the potential of Macromedia's Flash and Actionscript as been an implementation language for online games and interactive online computer graphics. One key factor that makes this so, is that the graphic objects or primitives drawn on a surface are persistent ie. they do not have to be drawn for every iteration.

More details could be obtained from MazeWork

back to top

Maze Generation Algorithm

1. Pick any random cell in the grid.

2. Find a random neighboring cell that hasn't been visited yet and has all its four walls intact.

3. If you find one, strip the wall between the current cell and the neighboring cell.

4. If you don't find one,  return to the previous cell

5. Repeat steps 2 and 3  (or steps 2 and 4)  for every cell in the grid.

back to top

Maze Solving Algorithm

1. Take the starting cell.

2. Find a random neighbouring cell, such that there is no border between them.

3. If one is found, move to that cell, and push the previous cell on to stack.

4. If one is not found, pop the previously push cell from the stack.

5. Set the found cell to be the current cell.

6. Repeat step 2 and 3 or steps 2 and 4.

7. Until the target cell is reached.

back to top

Implementation Using Actionscript in Flash MX.

The implementation in action script, uses a one dimensional array to represent the grid. This requires functions to retrieve and save the two dimension coordinate needed for some computations. Such as determining whether there is a possible adjacent cell in any direction.

The while loop needed to iterate through the grid is implemented using the setInterval and ClearInterval functions.

Finally a class called Grid_cell was defined in order to maintain the data structure for each cell. This Object has the structure listed below.

class Grid_cells

{

var x_coord:Number; //represents the left coordinate
var y_coord:Number; //represents the top coordinate
var xoffset:Number; //represents the right coordinate
var yoffset:Number; //represents the bottom coordinate

var north:Boolean; //determines if there is a north wall present.
var south:Boolean; //determines if there is a south wall present.
var east:Boolean; //determines if there is a east wall present.
var west:Boolean; //determines if there is a west wall present.

var north_border:Boolean;
var south_border:Boolean;
var east_border:Boolean;
var west_border:Boolean;

var cell_visited:Boolean; //determines if a cell has already been visited.

}

The implementation of the program and the class file can be obtained here.

Note. This program use a class, in order to recompile the program, the class path of the flash IDE has to be set to the folder in which the file is downloaded.

back to top

Program Usage

1. Select the number of rows and columns by using the stepper control. Note (its best to have a square grid with the number of rows equal to the number of columns)

2. Click the Draw grid button. This generates the maze interactivelly and because the rendering in flash is persistent, there is no need to redraw the entire grid when the cells are modified only the modified cells are redrawn.

3. Watch the progress bar.

4. During the maze generation, the solve maze button is disabled.

5. When the progress reaches 100%, the maze has been fully generated.

6. Click the solve maze button. Set the Show All Path option.

7. This generates the path between the green and red cells.

back to top