一个迷宫的随机生成程序

最近看了yzfy博客里的迷宫生成程序,只能用一句话形容:很好很强大。
里面的随机性非常的好。
个人感觉写一个迷宫的生成程序真的很有趣,有时候,把代码用于实际,往往更能体现代码的价值。
虽然这只是一段小小的代码,不过话费我的时间可不少,不仅花了N个小时(N>20)去反复思索,还和网上诸多朋友探讨了一番。当然,不是一次花费N小时去想的,然后从半年前看到那个代码,期间反反复复想过几次,但都没有收获,这次终于有感觉了,兴奋啊。

以下是迷宫生成代码,我自己修改了一点微不足道的地方:

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
// Author: Tanky Woo
// Blog:   www.WuTianQi.com
// Brief:  a Maze program
#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;
#define MAZE_MAX 50
char map[MAZE_MAX+2][MAZE_MAX+2];
const int x = 11, y = 11;
int z1, z2;
 
void printMaze();
void makeMaze();
int searchPath(int, int);
int main()
{
	for(int i=0; i<=x*2+2; ++i)
		for(int j=0; j<=y*2+2; ++j)
			map[i][j] = 1;
 
	makeMaze();
	cout << "Tanky Woo" << endl;
	printMaze();
}
 
void printMaze()
{
    for(z2=1; z2<=y*2+1; z2++)
    {
        for(z1=1;z1<=x*2+1;z1++) 
            fputs(map[z2][z1]==0?" ":"█",stdout);
        putchar(10);
    }
	cout << endl;
}
 
void makeMaze()
{
	for(z1=0, z2=2*y+2; z1<=2*x+2; ++z1)
	{
		map[z1][0] = 0;
		map[z1][z2] = 0;
	}
	for(z1=0, z2=2*x+2; z1<=2*y+2; ++z1)
	{
		map[0][z1] = 0;
		map[z2][z1] = 0;
	}
	map[2][1] = 0;
	map[2*x][2*y+1] = 0;
 
	srand((unsigned)time(NULL));
	searchPath(rand()%x+1, rand()%y+1);
}
 
int searchPath(int x, int y)
{
	static int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
	int zx = x*2;
	int zy = y*2;
	int next, turn, i;
	map[zx][zy] = 0;
	turn = rand()%2 ? 1 : 3;
	for(i=0, next=rand()%4; i<4; ++i, next=(next+turn)%4)
		if(map[zx+2*dir[next][0]][zy+2*dir[next][1]] == 1)
		{
			map[zx+dir[next][0]][zy+dir[next][1]] = 0;
			searchPath(x+dir[next][0], y+dir[next][1]);
		}
	return 0;
}

给大家来个截图:

然后我分析代码时,在makeMaze()的searchPath()语句前面加了printMaze(),在searchPath()中的map[][]赋0语句后面也加了printMaze(),并且把x,y都改成2.生成下面的生成过程图:

这方面的资料不太多,有人建议看《设计模式》里的生成迷宫。我上次看见Weiss的书里讲到用并查集处理迷宫的。有时间再试试,并找一些随机算法的资料来。

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《一个迷宫的随机生成程序》有45个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注