首页

同学萌好像都在准备 1024 程序员节（咋啥节日都有啊 qwq）

突然想起之前 yy 的用冰茶姬生成随机迷宫，正好来写写试试 (๑・̀ㅂ・́)و✧

搜了一波才发现已经广为流传了诶 QAQ

纯属摸鱼，仅仅是个有趣的玩法，不计代价，不管复杂度 qwq

游戏代码在文章最末，欢迎白嫖（大佬还请手下留情嘤嘤嘤 (｡>ㅿ<｡)

# 生成方法

建立一个那种就是.."一小格一小格的" 东西。不太会描述 QAQ、、放图：

<img src = "https://s1.ax1x.com/2020/10/15/07nLHP.png" width = "200px">

假设是要从左上角走到右下角。

我们可以用冰茶姬维护格子们：

​ 对任意两个格子，只要它们有路可通，就扔到同一集合里。

# 具体步骤

  • 建立上图的形状，随机选择 任意一面 非边界的 墙。
  • 用冰茶姬查询墙两侧的格子是否连通：
    • 若已连通，则啥都不干。（保证解的唯一性）
    • 若未连通，把这面墙拆掉，用冰茶姬连通这两点所在集合。
  • 重复上述过程至所有点都连通为止。

# 代码实现

​ 上面的图看上去不是很好搞 emmm，改成用二维数组存储，大概长这样（用 '#' 表示墙，空着是空格）：

<img src = "https://s1.ax1x.com/2020/10/15/07KAsA.png" width = "200px">

要保证地图行列都是是奇数_(:з」∠)_ // 菜菜的咱还不知道偶数咋写 qwq

我们可以发现，位于十字交叉处的 '#' 实际上并不算图 1 中的墙，我们将可以拆的墙用 '*' 标记一下：

<img src = "https://s1.ax1x.com/2020/10/16/0HOqud.png" width = "200px">

这样就可以 random 选择 '*' 墙并将其拆除，拆着拆着迷宫就出来了，思路大概就是这样。

Fake_code:

void Build() // 建立迷宫
{
    //init
    预处理出上图的形状。
    //build
    while (没有全部连通)
    {
        随机选取一面 '*' 墙
        if (其两侧格子未连通)
        {
            Merge(两侧的格子)；
        	Map[i][j] = ' '; // Map [i][j] 就是刚刚选的墙
        }
    }
}

再加上亿点点一点点细节，就生成这个迷宫啦 (๑＞ڡ＜)☆

Code (采用了很工程风的变量名欸嘿嘿..):

#include <cstdio>
#include <iostream>
#include <cstdlib>
#define rep(i, s, t) for (int i = s; i <= t; i++)
using namespace std;
const int N = 1e3 + 10, SIZE = 31; //SIZE 迷宫大小
char Map[N][N];
bool Vis_Map[N][N]; // 辅助随机选墙的标记数组
struct Disjoint_Set // 冰茶姬
{
    int Father, Size = 1;
} D_Set[N * N];
int GetID(int i, int j) // 将节点坐标转换为编号
{
    return (i - 1) * SIZE + j;
}
int GetFa(int x)
{
    return D_Set[x].Father == x ? x : D_Set[x].Father = GetFa(D_Set[x].Father);
}
void D_Merge(int x, int y, int i, int j)
{
    int Fx = GetFa(x), Fy = GetFa(y);
    if (Fx == Fy)
        return;
    if (D_Set[Fx].Size < D_Set[Fy].Size)
        swap(Fx, Fy);
    D_Set[Fy].Father = Fx;
    D_Set[Fx].Size += D_Set[Fy].Size;
    Vis_Map[i][j] = 1;
    return;
}
void Build() // 建立迷宫
{
    //init
    srand(233);
    rep(i, 1, SIZE) // 初始化地图为上图状态
        rep(j, 1, SIZE)
    {
    	D_Set[GetID(i, j)].Father = GetID(i, j);
        if (i == 1 || j == 1 || i == SIZE || j == SIZE)
            Map[i][j] = '#';
        else if (i & 1 && j & 1)
            Map[i][j] = '#';
        else if (i & 1 || j & 1)
            Map[i][j] = '*';
        else
            Map[i][j] = ' ';
    }
    //build
    // 复杂度爆炸，待优化，不计代价的话就这样了。。
    // 对于 SIZE * SIZE 的地图有这么多个空格↓
    while (D_Set[GetFa(GetID(2, 2))].Size != (SIZE / 2) * (SIZE / 2))
    {
        int i, j;
        do
        {
            i = rand() % SIZE + 1, j = rand() % SIZE + 1;
        } while (Map[i][j] != '*' || Vis_Map[i][j]); // 尝试用数学公式优化失败。。
        if (Map[i][j + 1] == '#') // 判断该墙是连接上下还是左右
            D_Merge(GetID(i - 1, j), GetID(i + 1, j), i, j);
        else
            D_Merge(GetID(i, j - 1), GetID(i, j + 1), i, j);
    }
    rep(i, 1, SIZE)
        rep(j, 1, SIZE)
        	if (Map[i][j] == '*')  // 多余的 '*' 换成 '#'，好看 qwq
                	if (Vis_Map[i][j])
						Map[i][j] = ' ';
    				else Map[i][j] = '#';
}
void Print()
{
    rep(i, 1, SIZE)
    {
        rep(j, 1, SIZE)
            printf("%c", Map[i][j]);
        printf("\n");
    }
}
int main()
{
    Build();
    Print();
    system("pause");
    return 0;
}
效果图：(u1s1 这个控制台好丑。。)
<img src = "https://s1.ax1x.com/2020/10/16/0bnpT0.png" width = "200px">
# 加入移动效果
套上之前的游标菜单思路，就可以搞成小游戏辣 (｢･ω･)｢，，诶嘿嘿..
Upd: 进行了优化，[摸鱼] 迷宫游戏的优化与添加双人功能 。
Code: （写得好乱 QAQ
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <windows.h>
#include <conio.h>
#include <time.h>
#define rep(i, s, t) for (int i = s; i <= t; i++)
using namespace std;
const int N = 1e3 + 10;
int MAZE_SIZE , Seed;
char Map[N][N];
bool Vis_Map[N][N];
struct Disjoint_Set
{
    int Father, MAZE_SIZE = 1;
} D_Set[N * N];
int GetID(int i, int j) // 获取节点编号
{
    return (i - 1) * MAZE_SIZE + j;
}
int GetFa(int x)
{
    return D_Set[x].Father == x ? x : D_Set[x].Father = GetFa(D_Set[x].Father);
}
void D_Merge(int x, int y, int i, int j)
{
    int Fx = GetFa(x), Fy = GetFa(y);
    if (Fx == Fy)
        return;
    if (D_Set[Fx].MAZE_SIZE < D_Set[Fy].MAZE_SIZE)
        swap(Fx, Fy);
    D_Set[Fy].Father = Fx;
    D_Set[Fx].MAZE_SIZE += D_Set[Fy].MAZE_SIZE;
    Vis_Map[i][j] = 1;
    return;
}
void Build() // 建立迷宫
{
    //init
    srand(Seed);
    rep(i, 1, MAZE_SIZE)
        rep(j, 1, MAZE_SIZE)
    {
    	D_Set[GetID(i, j)].Father = GetID(i, j);
        if (i == 1 || j == 1 || i == MAZE_SIZE || j == MAZE_SIZE)
            Map[i][j] = '#';
        else if (i & 1 && j & 1)
            Map[i][j] = '#';
        else if (i & 1 || j & 1)
            Map[i][j] = '*';
        else
            Map[i][j] = ' ';
    }
    //build
    // 差不多 O (MAZE_SIZE ^ 3)，待优化，目前最大只能生成 1e3 大小左右。。
    while (D_Set[GetFa(GetID(2, 2))].MAZE_SIZE != (MAZE_SIZE / 2) * (MAZE_SIZE / 2))
    {
        int i, j;
        do
        {
            i = rand() % MAZE_SIZE + 1, j = rand() % MAZE_SIZE + 1;
        } while (Map[i][j] != '*' || Vis_Map[i][j]); // 下次尝试用数学公式优化
        if (Map[i][j + 1] == '#')
            D_Merge(GetID(i - 1, j), GetID(i + 1, j), i, j);
        else
            D_Merge(GetID(i, j - 1), GetID(i, j + 1), i, j);
    }
    rep(i, 1, MAZE_SIZE)
        rep(j, 1, MAZE_SIZE) if (Map[i][j] == '*') if (Vis_Map[i][j])
            Map[i][j] = ' ';
    else Map[i][j] = '#';
}
void MAZE_Print()
{
    rep(i, 1, MAZE_SIZE)
    {
        rep(j, 1, MAZE_SIZE)
            printf("%c", Map[i][j]);
        printf("\n");
    }
}
void Character_Print(int x, int y) // 改变光标位置，输出人物位置
{
    COORD pos = {y, x - 1};
    HANDLE hOutput = GetStdHandle(STD_OUTPUT_HANDLE);
    SetConsoleCursorPosition(hOutput, pos);
    printf("\b&");
}
void Hide_Cursor() // 隐藏光标闪烁
{
    HANDLE Handle = GetStdHandle(STD_OUTPUT_HANDLE);
    CONSOLE_CURSOR_INFO CursorInfo;
    GetConsoleCursorInfo(Handle, &CursorInfo);
    CursorInfo.bVisible = 0;
    SetConsoleCursorInfo(Handle, &CursorInfo);
}
void Process(int dx, int dy)
{
    static int x = 2, y = 2;
    int tx = x + dx, ty = y + dy;
    if (tx == MAZE_SIZE - 1 && ty == MAZE_SIZE - 1)
    {
        printf("You win!\nCongratulations!\n");
        system("pause");
        exit(0);
    }
    if (Map[tx][ty] == '#')
        Character_Print(x, y);
    else
        Character_Print(x = tx, y = ty);
}
void Update() // 持续获取键盘信息
{
    while (1)
    {
        if (kbhit())
        {
            getch();
            char op = getch(); // 上下左右 72, 80, 75, 77
            system("cls");
            MAZE_Print();
            switch (op)
            {
                case  72: Process(-1, 0); break;
                case  80: Process(1, 0); break;
                case  75: Process(0, -1); break;
                case  77: Process(0, 1); break;
                default: Process(0, 0);
            }
        }
        Sleep(20);
    }
}
void init()
{
    printf("请选择迷宫大小：(输入序号)\n 1. 10*10\n 2. 20*20\n 3. 30*30\n 4. 50*50\n 5. 100*100\n");
    scanf("%d", &MAZE_SIZE);
    switch (MAZE_SIZE)
    {
        case 1 : MAZE_SIZE = 11; break;
        case 2 : MAZE_SIZE = 21; break;
        case 3 : MAZE_SIZE = 31; break;
        case 4 : MAZE_SIZE = 51; break;
        case 5 : MAZE_SIZE = 101; break;
    }
    printf("输入地图种子：\n");
    scanf("%d", &Seed);
    system("cls");
    printf("生成中");
    Sleep(500);
    printf(".");
    Sleep(500);
    printf(".");
    Sleep(500);
    printf(".");
    system("cls");
}
int main()
{
    init();
    Hide_Cursor();
    Build();
    MAZE_Print();
    Character_Print(2, 2);
    Update();
    system("pause");
    return 0;
}