文章性质：原创
发布日期：2004-04-02
Faculty of Software Engineering, ChongQing University
Student ID：20024317
Abstract
In this paper, I will give two method of random maze generating after my research on it. The second method uses the depth-first searching of graph theory. Comparing the two methods, we can see that discrete math is useful when we are dealing with many things. Methods given 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 maze which seems magic. Now let’s discuss how to make a simple random-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 “[]” represents obstacle 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 here give two methods. The first method is created by myself which doesn’t use discrete math knowledge and the second method is used by my friend which uses the graph theory knowlege.
3.1 Simple Generating Algorithm
Assume that the maze starts at left-top corner and ends at right-bottom corner. The generating method is: Beginning at the starting-point, choose a direction randomly, and it won’t stop until it reach the end-point. Of course, yet, we should make sure that the path shouldn’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 use Blue Block and White Block, representing obstacle block and through-able block separately. Now all blocks of our maze are Blue Block except the start-point and the end-point.
1.When there is more than one direction to go, here left block, right block and bottom block can be replace by White Block, we randomly choose one. And this is how a random-generating maze comes out.
(Figure 2, choose a direction)
2.We assume that right block is what we chose. To determine whether the block( yellow point in the figure ) we chose can be used as a White Block, we can just determine that there are only three Blue Block around the block( yellow point ), which guarantees the path won’t go across.
(Figure 3, Use the block chosen?)
3.If the path goes into a wrong direction( red point in the figure ), which can’t reach the end-point. We should let it go back to the last block( green point ). Thus, we need a path list to store all the block we had pass and when we meet the situation mentioned above, we can find the last block we need.
(Figure 4, wrong direction)
The above is the basic method, but here is a problem: if the situation below happens, even the path list can’t guarantee it can reach 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 stack and set it to C. Push all A-status-conjoint points of the point to the stack 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 stack and set it to C. Push all A-status-conjoint points of the point to the stack 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 searching algorithm has the same step: push all the A-status-conjoint points of the current visited point to the stack. In which order we should use to push 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. ①, ②, ③, ④ with coordinates (1,1) (3,1) (1,3) (3,3) are nodes, where are certainly through-able blocks. If we set (2,1) to through-able, it means ①?② is a path. With the depth-first searching, when we visit ② from ①, we will set (2,1) to through-able. And the maze will come out when the searching 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 last depth-first searching as example, we assume the visit order is: 1 2 3 4 7 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 a problem can be solved perfectly using discrete math knowledge. And how to use discrete math freely? That’s what you and I should practice in our 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.