C语言中的随机迷宫生成器

Question

我不知道如何确保随机生成的迷宫可以从右侧入口通向左侧出口，而不会有任何墙壁挡住路径。这是我迄今为止所做的代码。每个人都能给我一个提示或算法来实现简单迷宫（入口/出口）吗？谢谢！ P / S我的问题是迷宫生成器不能保证通往出口的路径...（卡住了）

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

#define SIZE 12
void mazeGenerator(char [][SIZE]);

int main(void)
{
    char maze[SIZE][SIZE];
    srand((unsigned int)time(NULL));
    mazeGenerator(maze);
    return 0;
}
void mazeGenerator(char a[SIZE][SIZE])
{
    size_t row,column = 0, r;

    // initialize '#' to all positions of left-hand wall
    for ( row = 0; row < SIZE; ++row )
    {
        a[row][column] = '#';
    }
    // initialize '#' to all positions of left-hand wall
    for ( row = 0; row < SIZE; ++row )
    {
        a[row][SIZE - 1] = '#';
    }

    // initialize '.' to left-hand wall random positions from 1 -> 10
    row = rand() % 11 + 1;
    a[row][0] = '.';

    // initialize '.' to right-hand wall random positions from 1 -> 10
    row = rand() % 11 + 1;
    a[row][SIZE - 1] = '.';

    // intialize '#' to all positions of top maze
    for (column = 1; column < SIZE - 1; ++column)
    {
        a[0][column] = '#';
    }

    // intialize '#' to all positions of bottom maze
    for (column = 1; column < SIZE - 1; ++column)
    {
        a[SIZE - 1][column] = '#';
    }

    // print maze
    puts("");
    puts("** Maze Generator by Huy Le **\n");
    for (row = 0; row < SIZE; ++row)
    {
        for (column = 0; column < SIZE; ++column)
        {
            printf_s("%2c",a[row][column]);
        }
        puts("");
    }
    puts("");
}

- lee huy

---

只是一个想法，为什么不先在入口和出口之间生成一条路径，然后再建造墙壁，并设置约束条件，使得没有任何一堵墙位于你所建造的路径上？ - Inox

我有同样的想法，但那会创建一条直线，看起来不自然。 - lee huy

Answer 1

您的问题在于您选择的算法不能保证从入口到出口有一条路径。实际上，您是随机填充迷宫，这样不会得到保证有路径的结果（实际上可能会有多条路径）。

您需要使用迷宫生成算法。这些算法是众所周知的算法类别，可以生成带有解决方案的迷宫（在某些情况下只有一个解决方案）。以下链接提供了一篇文章和数个此类算法的参考资料：http://en.wikipedia.org/wiki/Maze_generation_algorithm。

- abligh

---

事实上，一种常见的算法确保任意两个选定点之间始终存在唯一路径。在http://www.astrolog.org/labyrnth/maze.htm的“链接-迷宫创建”长列表中查找不同的方法。 - Jongware

Answer 2

你应该使用其中一个成熟的迷宫生成算法。这里是深度优先搜索（DFS）算法的非常简短的C ++实现： http://github.com/corporateshark/random-maze-generator

- Sergey K.