本文作者：kasicass
文章性质：原创
发布日期：2004-04-02 TangZeJiang, 2002
Faculty of Software Engineering, ChongQing University
Student ID：20024317
Abstract
In this paper, I will give two method of random maze generatingafter my research on it. The second method uses the depth-firstsearching of graph theory. Comparing the two methods, we can see thatdiscrete math is useful when we are dealing with many things. Methodsgiven by discrete math is always more effective.
Key words：random maze generating、depth-first searching
1. Introduction
In some small PC games, we often see some random-generating mazewhich seems magic. Now let’s discuss how to make a simplerandom-generating maze.
2. Maze Description
We can use a matrix maze[m][n] to represent a m * n random-generating maze(figure 1).
(Figure 1. random-generating maze)
There are two maze samples in the figure and “[]” representsobstacle where you can go through. Look at the left one, we can use a 7* 7 matrix to represent it:
1 1 1 1 1 1 1
0 0 0 0 0 0 1
1 1 1 1 1 0 1
1 0 0 0 1 0 1
1 0 1 1 1 0 1
1 0 0 0 0 0 0
1 1 1 1 1 1 1
( 0 – through-able block, 1 – obstacle block )
3.Random Maze Generating Algorithm
There are lots of ways to make random-generating maze and heregive two methods. The first method is created by myself which doesn’tuse discrete math knowledge and the second method is used by my friendwhich uses the graph theory knowlege.
3.1 Simple Generating Algorithm
Assume that the maze starts at left-top corner and ends atright-bottom corner. The generating method is: Beginning at thestarting-point, choose a direction randomly, and it won’t stop until itreach the end-point. Of course, yet, we should make sure that the pathshouldn’t go across and it won’t go out of the boundary of the maze.
The following illustrate what it does. In the figures, we useBlue Block and White Block, representing obstacle block andthrough-able block separately. Now all blocks of our maze are BlueBlock except the start-point and the end-point.
1.When there is more than one direction to go, here leftblock, right block and bottom block can be replace by White Block, werandomly choose one. And this is how a random-generating maze comesout.
(Figure 2, choose a direction)
2.We assume that right block is what we chose. Todetermine whether the block( yellow point in the figure ) we chose canbe used as a White Block, we can just determine that there are onlythree Blue Block around the block( yellow point ), which guarantees thepath won’t go across.
(Figure 3, Use the block chosen?)
3.If the path goes into a wrong direction( red point inthe figure ), which can’t reach the end-point. We should let it go backto the last block( green point ). Thus, we need a path list to storeall the block we had pass and when we meet the situation mentionedabove, we can find the last block we need.
(Figure 4, wrong direction)
The above is the basic method, but here is a problem: if thesituation below happens, even the path list can’t guarantee it canreach the end-point.
(Figure 5, we can’t reach the end-point)
A Solution
Two-path searching, which we can make the path from start-point and end-point simultaneously.
以上是通过很直接的思考方式得来的随机迷宫之实现。
3.2 Algorithm Using Graph Theory
3.2.1 Introduction to Depth-First Searching
For example, we will search through the whole graph above
Use the depth-first searching( begin at 1 )
Prepare a stack s, and define three statuses: A – not visited; B – prepare to visit; C – visited
1. Visit point 1, set it to C. Push all A-status-conjoint points of point 1 to the stack and set their status to B.
Current system status:
Visited points: 1
Not visited points: 3 4 6 7 8 9 10
Prepare to visit points: 2 5 ( stored in the stack )
2. Get the next point( here is point 2 ) from the stackand set it to C. Push all A-status-conjoint points of the point to thestack and set their status to B. ( Figure 6 )
(Figure 6)
Current system status:
Visited points: 1 2
Not visited points: 4 6 7 8 9 10
Prepare to visit points: 3 5 ( stored in the stack )
3. Get the next point( here is point 3 ) from the stackand set it to C. Push all A-status-conjoint points of the point to thestack and set their status to B. ( Figure 7 )
(Figure 7)
Current system status:
Visited points: 1 2 3
Not visited points: 7 8 9 10
Prepare to visit points: 4 6 5
It goes like this till the stack is empty, which means all the points has been visited.
One of the probable visit path:
(Figure 8)
3.2.2 Maze Generating Algorithm Using Depth-First Searching
But, how can we make a random maze?
Have you found that every time the depth-first searchingalgorithm has the same step: push all the A-status-conjoint points ofthe current visited point to the stack. In which order we should use topush them? Randomly! It is just how random maze been built.
Now let’s see how it works.
Assume that we want to make a 5 * 5 maze. ①, ②, ③, ④ withcoordinates (1,1) (3,1) (1,3) (3,3) are nodes, where are certainlythrough-able blocks. If we set (2,1) to through-able, it means ①?② is apath. With the depth-first searching, when we visit ② from ①, we willset (2,1) to through-able. And the maze will come out when thesearching ends.
(Figure 9)
Points ①②③④ in figure 9, we can assume them to a 2 * 2 matrix, illustrated bellow:
(Figure 10)
The problem is when we should “make the path”. Using the lastdepth-first searching as example, we assume the visit order is: 1 2 3 47 10 9 8 6 5
When it just visit point 9, points 8 and 6 will be pushed to the stack and we should make the path from 9 to 8 and 6.
3.2.3 Path is unique
The depth-first searching algorithm guarantees that there is only one path from start-point to end-point in the maze.
3.2.4 Disadvantage of The Algorithm
The algorithm can just make a m * n maze, where m and n is odd.
4. Comparing of The Two Algorithm
Maze builds using the first algorithm:
Maze builds using the second algorithm:
Obviously, depth-first searching maze algorithm is more effective.
5. Conclusion
Through a discussing of the maze generating, we can see that aproblem can be solved perfectly using discrete math knowledge. And howto use discrete math freely? That’s what you and I should practice inour life.
Reference
Bernard Kolman, Robert C. Busby, Sharon Cutler Ross, “Discrete Mathematical Structures”( Fourth Edition), 高等教育出版社
Kenneth H. Rosen, “Discrete Mathematics and Its Applications”( Third Edition ), McGraw-Hill, Inc.
