做一个迷宫游戏，需要自动生成迷宫，或者做寻路，也需要一些迷宫做测试
那么怎么生成一个规则的迷宫呢
为什么选择prim
递归分割会生成一个很简单的迷宫，深度优先虽然会生成一个稍微难的迷宫，但是深度优先会遍历全局生成一条通路过后再补充剩下的空余，就会出现一条很长的通路，和其他全是很短的路，显得刻意为之，反而没什么难度而且缺少“美观”
prim则会生成一个非常规则，每条路平均都是一样长的迷宫，虽然迷宫大小很小的时候，难度会因为平均分了而很小，但是当迷宫尺寸逐渐变大时，prim就显然是比深优和分割更正确的做法了
效果：https://file.xiaoshiyan.top/seekRoadGame/#a
原理
- 初始地图（分为墙与房间）
- 任意插入一个空格进列表，记录为已经过
- 从已经过里找出边界（外边是还没有经过的，里面是已经经过的）
- 从边界里找出所有能到的将要房间，记录为将要经过的房间
- 打破与将要经过的房间的墙，将他加入已经过，删去即将经过
- 重复3-5，直到将要经过的列表为空
初始化
先初始化模板，为了得到“正规”的迷宫（墙与墙，路与路之间只有垂直连接），你需要先把基点（行列均为偶的格子，即使生成完也是墙）全部生成墙，然后为了生成迷宫，需要把整个迷宫分成很多个“小房间”，像这样
1 2 1 2 1 2 1
2 2 2 2 2 2 2
1 2 1 2 1 2 1
2 2 2 2 2 2 2
1 2 1 2 1 2 1
1表示路，2表示墙生成迷宫就变成了，打破墙连接这些房间，且每到一个新房间只打通一扇“门”（或者破一堵墙）
生成这个迷宫可以比喻为扩张领地
开始
将一个房间加入列表，表示你现在所在位置（你的初始领地），这个列表记录为已经过的房间
一般我们选择第一个为起点
边界
就像国家扩张一样，内部的土地没办法扩张，只有与外疆接壤的才能扩张
将要到达的房间
在边界上扩张领地不能跳着扩，也不能扩张自己的，将要到达的房间就是与边界相接的还未到达的房间
每次随机选择一个与之前的房间连接，打破墙（随机性在这里体现的）
最后就是重复这些操作，直到领地扩张，占领全图，没有将要到达的房间（未占领的领地）了结束生成结束了
代码
以c为例，大一开学不久后做的，代码比较简陋，加入了文件写入功能保存存档，如果你要使用这个代码，记得新建一个date.txt文件(data打成了date，懒得改了)
/*
迷宫游戏 1.0
made by 小世炎
2020 10 15——————2020 10 16
啦啦啦啦啦！
*/
/*
2.0 更新
2020 10 22——————2020 10 22
*/
/*
修改规范格式 2.1
2021 3 9——————2021 3 9
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <conio.h>
/************ 全局变量 ************/
int n = 17, game = 0; //迷宫大小，游戏模式（0：新，1：读取，2：晋级）
int board[100][100]; //游戏界面
int past_list[1001][2], next_list[1001][2], hit_pos[2]; //生成迷宫用到的数组
int len_next; //next_list长度
int win; //胜利判断条件
char choice; //操作
int player_pos[2]; // 玩家位置
/************ 函数声明 ************/
/* 迷宫生成 */
int break_wall(); // 打破为通过的墙
int update_list(); // 更新未打破的墙
/*辅助操作*/
int is_in(int a[], int b[][2]); //判断一个坐标是否在二维数组中
void insert(int sub_list[], int list[][2], int n); //将坐标插入至数组首位
void poop(int pos, int a[][2], int ans[]); //删除并返回一个数组中的坐标
void del_sublist(int list[][2], int sublist[], int n); //删除子列表
/* 文件读取和写入 */
int r_board(); //读取记录
void w_board(); //记录数据
/*游戏*/
void init_all_data(); //初始化数据
void print_board(); //输出游戏界面
int get_input(); // 获取合法输入，移动并判断是否结束
/************ 主函数 ************/
int main()
{
system("cls");
printf("Made by xiaoshiyan\nPRESS ANY KEY TO CONTINUE!");
getch();
system("cls");
while (n < 37)
{
len_next = 0;
win = 0;
srand(time(0));
if (game == 0)
{
while (1)
{
printf("Enter \"n\" TO CREATE A NEW GAME!\nOr \"c\" TO CONTINUE!\n");
choice = getch();
if (choice == 'c' || choice == 'C')
{
n = r_board();
game = 1;
break;
}
else if (choice == 'n' || choice == 'N')
{
game = 0;
break;
}
system("cls");
printf("!!!!! Wrrong,please enter 'c' or 'n' !!!!!\n\n");
}
}
if (game == 0 || game == 2)
{
init_all_data();
while (1)
{ //生成迷宫
printf("CREATING GAME BOARD!");
print_board();
len_next = update_list();
len_next = break_wall();
if (len_next == 0)
{
break;
}
}
board[0][0] = 2;
board[n - 1][n - 1] = 4;
}
print_board();
if (n == 17)
{
printf("Now Complete!\n");
printf("'A' means your position now.\n");
printf("'#' means the way.\n");
printf("enter (w,a,s,d) to move.\n");
printf("To reach the 'E'(ending) to get win\n");
printf("Press any key to play!\n");
}
getch();
while (1)
{
print_board();
printf("//**Made by XiaoShiYan!**\\\\\n");
printf("Level:%d\n", (n - 17) / 2 + 1);
win = get_input();
if (win)
{
game = 2;
break;
}
}
printf("You win!\nPress any key to next level.\n");
getch();
n += 2;
}
printf("Congratulations!\nYou finished all the levels!");
}
/************ 函数定义 ************/
int break_wall()
{
int selectable_wall[4][2] = {{0}};
int temp[2] = {0};
int len_select = 0;
int r = rand() % len_next;
poop(r, next_list, hit_pos);
len_next -= 1;
temp[0] = hit_pos[0] - 2; //上
temp[1] = hit_pos[1];
if (is_in(temp, past_list))
{
temp[0] += 1;
insert(temp, selectable_wall, 4);
len_select += 1;
}
temp[0] = hit_pos[0]; //左
temp[1] = hit_pos[1] - 2;
if (is_in(temp, past_list))
{
temp[1] += 1;
insert(temp, selectable_wall, 4);
len_select += 1;
}
temp[0] = hit_pos[0] + 2; //下
temp[1] = hit_pos[1];
if (is_in(temp, past_list))
{
temp[0] -= 1;
insert(temp, selectable_wall, 4);
len_select += 1;
}
temp[0] = hit_pos[0]; //右
temp[1] = hit_pos[1] + 2;
if (is_in(temp, past_list))
{
temp[1] -= 1;
insert(temp, selectable_wall, 4);
len_select += 1;
}
r = rand() % len_select;
board[selectable_wall[r][0]][selectable_wall[r][1]] = 1;
return len_next;
}
int update_list()
{
int w[2] = {hit_pos[0] - 2, hit_pos[1]}, a[2] = {hit_pos[0], hit_pos[1] - 2}, s[2] = {hit_pos[0] + 2, hit_pos[1]}, d[2] = {hit_pos[0], hit_pos[1] + 2};
insert(hit_pos, past_list, 1001);
if (w[0] >= 0 && not is_in(w, past_list) && not is_in(w, next_list))
{
insert(w, next_list, 1001);
len_next += 1;
}
if (a[1] >= 0 && not is_in(a, past_list) && not is_in(a, next_list))
{
insert(a, next_list, 1001);
len_next += 1;
}
if (s[0] < n && not is_in(s, past_list) && not is_in(s, next_list))
{
insert(s, next_list, 1001);
len_next += 1;
}
if (d[1] < n && not is_in(d, past_list) && not is_in(d, next_list))
{
insert(d, next_list, 1001);
len_next += 1;
}
return len_next;
}
int is_in(int a[], int b[][2])
{
int i;
for (i = 0; i < 1001; i++)
{
if (b[i][0] == a[0] && b[i][1] == a[1])
{
return 1;
}
}
return 0;
}
void insert(int sub_list[], int list[][2], int n)
{
int i;
for (i = n - 1; i > 0; i--)
{
list[i][0] = list[i - 1][0];
list[i][1] = list[i - 1][1];
}
list[0][0] = sub_list[0];
list[0][1] = sub_list[1];
}
void poop(int pos, int a[][2], int ans[])
{
int i;
ans[0] = a[pos][0];
ans[1] = a[pos][1];
for (i = pos; i < 1000; i++)
{
a[i][0] = a[i + 1][0];
a[i][1] = a[i + 1][1];
}
}
void del_sublist(int list[][2], int sublist[], int n)
{
int temp[10];
int pos, i;
for (i = 0; i < n; i++)
{
if (list[i][0] == sublist[0] && list[i][1] == sublist[1])
{
pos = i;
break;
}
}
poop(i, list, temp);
}
int r_board()
{
FILE *fpin;
int x, n;
int pos = 0, line = 0;
fpin = fopen("date.txt", "r");
if (fpin == NULL)
{
printf("YOU DO NOT HAVE ANY DATA!");
exit(1);
}
fscanf(fpin, "%d %d", &player_pos[0], &player_pos[1]);
fscanf(fpin, "%d", &n);
while (fscanf(fpin, "%d", &x) != -1)
{
board[line][pos] = x;
pos++;
if (pos == n)
{
pos = 0;
line++;
}
if (line == n)
{
break;
}
}
fclose(fpin);
return n;
}
void w_board()
{
FILE *fpout;
int i, j;
fpout = fopen("date.txt", "w");
if (fpout == NULL)
{
printf("can't find file:\"date.txt\"!\n");
exit(1);
}
fprintf(fpout, "%d %d\n", player_pos[0], player_pos[1]);
fprintf(fpout, "%d\n", n);
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
fprintf(fpout, "%d ", board[i][j]);
}
fprintf(fpout, "\n");
}
fclose(fpout);
}
void init_all_data()
{ //初始化相关数据
int i, j, k;
for (i = 0; i < n; i++)
{ //初始化版面
for (j = 0; j < n; j++)
{
if ((i + 1) % 2 == 0 || (j + 1) % 2 == 0)
{
board[i][j] = 0;
}
else
{
board[i][j] = 1;
}
}
}
for (i = 0; i < 1001; i++)
{ //初始化数据列表
past_list[i][0] = 3;
next_list[i][0] = 3;
past_list[i][1] = 3;
next_list[i][1] = 3;
}
hit_pos[0] = 0;
hit_pos[1] = 0;
player_pos[0] = 0;
player_pos[1] = 0;
len_next = 0;
}
void print_board()
{
int i, j;
system("cls");
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
if (board[i][j] == 2)
{
printf("%s%c", j == 0 ? "" : " ", 'A');
}
else if (board[i][j] == 0)
{
printf("%s%c", j == 0 ? "" : " ", ' ');
}
else if (board[i][j] == 4)
{
printf("%s%c", j == 0 ? "" : " ", 'E');
}
else
{
printf("%s%c", j == 0 ? "" : " ", '#');
}
}
printf("\n");
}
w_board();
}
int get_input()
{
char derection;
int move[2] = {0};
derection = getch();
if (derection == 'w')
{
move[0] = player_pos[0] - 1;
move[1] = player_pos[1];
}
else if (derection == 'a')
{
move[0] = player_pos[0];
move[1] = player_pos[1] - 1;
}
else if (derection == 's')
{
move[0] = player_pos[0] + 1;
move[1] = player_pos[1];
}
else if (derection == 'd')
{
move[0] = player_pos[0];
move[1] = player_pos[1] + 1;
}
else
{
print_board();
printf("//**Made by XiaoShiYan!**\\\\\n");
printf("Level:%d\n", (n - 17) / 2 + 1);
printf("wrrong input,try again(w,a,s,d)\n");
get_input();
return win;
}
if (move[0] < 0 || move[1] < 0 || move[0] >= n || move[1] >= n || board[move[0]][move[1]] == 0)
{
print_board();
printf("//**Made by XiaoShiYan!**\\\\\n");
printf("Level:%d\n", (n - 17) / 2 + 1);
printf("you can go to this derection,try again(w,a,s,d)\n");
get_input();
return win;
}
else if (board[move[0]][move[1]] == 4)
{
return 1;
}
else
{
board[player_pos[0]][player_pos[1]] = 1;
board[move[0]][move[1]] = 2;
player_pos[0] = move[0];
player_pos[1] = move[1];
}
return win;
}
还是这个链接，https://file.xiaoshiyan.top/seekRoadGame/
完全仿照c用js写的，另外还有个py版的，是高三的时候写的，不过被删了找不到了
