简单实现迷宫生成方法（随机DFS） [英] Simple implementation of a maze generation method (random DFS)

问题描述

在一次采访中，我的采访者问我这个问题：

In an interview, my interviewer asked me this question:

开发一个生成随机迷宫的函数

Develop a function to generate a random maze

如果您之前没有解决过这个问题，这是一个很难在30分钟内解决的问题。在互联网上有很多解决方案，但似乎没有一个容易。该方法应该遵守这个约束：

This is a quite difficult question to solve in 30min if you don't have solved this question before. On the internet there are many solution but none seems easy. The method should respect this constraint:

• 它应该接受迷宫的大小（方形迷宫NxN）


• 它应该只包含Walls和Path


• 以使其简单，算法不需要设置条目和退出

我将使用解决方案发布答案​​，以便其他人能够找到这个问题。

I will post the answer with the solution so other people will be able to find this question.

示例生成的迷宫：

. # # . # . . . . . 
. . . . . . # # # . 
# . # # # # . . . . 
. # . . . . # . # . 
. # . # # . # . # . 
. # . # . . # . . # 
. . . # . # . # . . 
. # . # . . . # # . 
# . . . # . # . . . 
. . # . # . . . # . 

推荐答案

一个简单的随机DFS可用于生成迷宫。要开始一个完整的围墙迷宫初始化为NxN的大小，然后这个函数遍历迷宫并在可能的时候添加一个路径：

A simple randomized DFS can be used to generate the maze. To start a full walled maze is initialized to the size of NxN, then this function traverse the maze and adds a path whenever possibile:

function generateMaze(&$maze, $point) {
    $dirs = [
        [0,-1],
        [1,0],
        [0,1],
        [-1,0],
    ];

    shuffle($dirs);

    foreach($dirs as $dir) {
        $newPoint = [$point[0] + $dir[0], $point[1] + $dir[1]];

        if (isGoodPath($maze, $newPoint)) {
            $maze[$newPoint[0]][$newPoint[1]] = '.';
            generateMaze($maze, $newPoint);
        }
    }

    return $maze;
}

解决这个问题的关键是函数<$ c $的良好实现c> isGoodPath（）这个函数只是检查新路径是否在迷宫内，以及我们是否可以移除墙壁（即我们不能有两个平行的相邻自由路径）

The key to solve this is a good implementation of the function isGoodPath() this function just checks if the new path is inside the maze and if we can remove the walls (that is we cannot have two parallel adjacent "free" path)

您可以在此处运行完整实施： https://ideone.com/oufifB

You can run the full implementation here: https://ideone.com/oufifB

25x25迷宫：

# . . # . . . # . . . . . # . . . . . . . # . # . 
. # . # # # . . . # # # . . # # . # # # . . . . . 
. # . . . . # . # . . . # . . . # . . . . # . # . 
. . # # # . # . . # . # # # # . . . # # . # . . # 
. # . . # . . # . # . . # . # # # # . . # . # . . 
. . # . # # . # . . # . . . . . . # . # . . . # . 
# . . . . # . . # . . # . # . # # . . . . # # . . 
. . # # . . # . . # . # . # . . . . # # . . # . # 
. # . . # . # . # . . # . . # # . # . . # . # . . 
. . . # . . # . . . # . . # . # . # . # . . . # . 
# # . # . # . # # # . # # . . . . # . # . # # . . 
. . . # . . . . . . . . # . # # # # . . . # # . # 
# # # . . # # # # . # . . . # . . . . # # . . . # 
. . . # # . . . . # # . # . # . # # # # # . # # . 
. # . . . . # # . # . . # . # . . . . # . . # . . 
. . # . # # . . . . # # # . . # # # # . . # # # . 
# . . # . . . # # . . . . # . # . . . . # . # # . 
. # . . # . # . # # . # . . . # . # # # . . . . . 
. . # . . # . . . . # . # # . # . # . . # # . # . 
# . . # . . . # # . # . . . . # . . # . . . . # . 
. . # . . # # . # . . # # . # . # . . # . # # . . 
# . . . # . . . . # . . . # . . # # . # . # . # # 
# # . # . . # . # . # # . # # . . . . # . . . . . 
# . . . # # # . . . # # . . # # . # # . # # # # . 
. . # . . . . . # . . . # . . . . . . . . . . . . 

如果你想要一个更漂亮的迷宫，你可以简单地在迷宫的边界添加完整的墙壁

If you want a "prettier" maze you can simply add full walls to the border of the maze

这篇关于简单实现迷宫生成方法（随机DFS）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！