【UE4】算法简记 - 地牢(1) DFS迷宫和BFS迷宫

ZifengHuang

发布于 2022-04-15 09:34:50

7170

发布于 2022-04-15 09:34:50

绪

这个系列主要记录一些最近探索过程中有意思的算法, 可能整体都比较简短杂乱, 希望有用. 目前的探索方向集中在程序性内容生成机制上. 本篇是基本的迷宫生成算法的介绍, 包含DFS法和BFS法, 下面是这篇文章主要的参考资料

总览, 介绍了几乎所有的程序式地图生成算法 Herbert Wolverson - Procedural Map Generation Techniques https://youtu.be/TlLIOgWYVpI
介绍了最基础的三种PCG地图算法的详细流程三套简单的迷宫地图生成方案 - 兔四的文章 - 知乎 https://zhuanlan.zhihu.com/p/27381213

DFS迷宫

大致流程

使用二维整型矩阵来表示迷宫地图, 0为墙壁, 1为可达区域, 2为已到达区域
将地图矩阵根据某种规则初始化得到可达和不可达区域的组合. 最简单的方法是给将行索引和列索引都为奇数的元素设置为可达区域
在地图中按某种规则设置一个迷宫起点元素, 设为已到达区域, 并以这个元素开始生成. 最简单的方法是取某一个角落的元素
从当前元素开始, 随机选取周围四个方向之一, 判断这个方向上2步远(相邻元素为1步)的元素是否可达元素, 若可达, 则将其设为已到达区域, 然后将这两个元素之间的不可达区域设为已到达.
从这个新元素开始继续上面的流程, 直到周边没有可继续前进的方向, 然后递归回来, 也就是DFS搜索
重复直到递归完全结束, 然后从地图中按某种规则选择一个终点则生成完成
借用一下算法示意图:

ref: 三套简单的迷宫地图生成方案 - 兔四的文章 - 知乎 https://zhuanlan.zhihu.com/p/27381213

代码

void AMapGenerator::_CreateDFSMazeArray(Array2D<int32>& ret, const FIntPoint& StartPoint)
{
    // DFS迷宫的非递归写法
    const int32 h = ret.H();
    const int32 w = ret.W();
    // 四方向偏移写法, Leetcode常见写法
    const int32 directions[] = { -1, 0, 1, 0, -1 };

    // 准备一个栈帧结构
    struct Cache
    {
        // 此栈帧的坐标
        int32 x;
        int32 y;
        // 打乱此处来从四方向中随机取值
        TArray<int32> shuffle{ 0, 1, 2, 3 };
        // 修改这个下标来完成四个方向的遍历
        int32 shuffle_idx = -1;
    };

    // 压入第一个元素
    TArray<Cache> stack;
    Cache tmp;
    tmp.x = StartPoint.X;
    tmp.y = StartPoint.Y;
    // 自己包装FisherYates算法来打乱数组
    RandomUtils::FisherShuffle(tmp.shuffle);
    stack.Emplace(tmp);

    // 重复直到栈空
    while (stack.Num() != 0)
    {
        Cache& c = stack.Top();
        bool flag = false;
        while (c.shuffle_idx < 3)
        {
            ++c.shuffle_idx;
            // 取出当前的方向下标
            int32 dir_idx = c.shuffle[c.shuffle_idx];
            // 两步外的下标
            int32 next_x = directions[dir_idx] * 2 + c.x;
            int32 next_y = directions[dir_idx + 1] * 2 + c.y;

            // 判断未到边缘
            if (
                (next_x < w) && (next_x > 0) && (next_y < h) && (next_y > 0)
                )
            {
                // 若下一个位是可达区域, 生成走廊并压栈继续DFS
                if (ret.Get(next_x, next_y) == 1)
                {
                    // 设置当前遍历的元素属性为'已到达'
                    ret.Set(next_x, next_y, 2);
                    ret.Set(directions[dir_idx] + c.x, directions[dir_idx + 1] + c.y, 2);
                    // 准备新的递归帧
                    tmp.x = next_x;
                    tmp.y = next_y;
                    RandomUtils::FisherShuffle(tmp.shuffle);
                    stack.Emplace(tmp);
                    flag = true;
                    break;
                }
            }
        }

        // 到达递归末端, 出栈并继续
        if (!flag)
            stack.Pop(false);
    }
}

特性

实现简单
生成的迷宫由于DFS特性, 会有一个明显的主路存在, 但是整体比较有规律, 分叉较少, 比较适合游玩和进一步设计

效果

DFS迷宫, 整体比较规则

BFS迷宫

大致流程

使用二维整型矩阵来表示迷宫地图, 0为墙壁, 1为可达区域, 2为已到达区域
将地图矩阵根据某种规则初始化得到可达和不可达区域的组合. 最简单的方法是给将行索引和列索引都为奇数的元素设置为可达区域
在地图中按某种规则设置一个迷宫起点元素, 设为已到达区域, 并以这个元素开始生成. 最简单的方法是取某一个角落的元素
将当前可达区域周围邻接的不可达区域放入列表中记为一个待选不可达列表
从当前的可达区域的邻接的待选不可达列表中, 随机取一个元素, 判断这个元素是否连接着另一个还未到达过的可达元素.
若是, 将这个可达区域连接扩展为迷宫的一部分, 然后从这个区域处刷新待选不可达区域列表
若否, 将这个不可达区域从列表中去除
重复直到不可达区域列表耗尽
借用一下算法示意图:

ref: 三套简单的迷宫地图生成方案 - 兔四的文章 - 知乎 https://zhuanlan.zhihu.com/p/27381213

代码

void AMapGenerator::_CreateBFSMazeArray(Array2D<int32>& ret, FIntPoint StartPoint)
{
    // BFS迷宫的非递归写法
    const int32 h = ret.H();
    const int32 w = ret.W();
    // 四方向偏移写法
    const int32 directions[] = { -1, 0, 1, 0, -1 };

    ret.Set(StartPoint.Y, StartPoint.X, 2);

    // 准备一个栈帧结构
    struct Cache
    {
        // 此栈帧的坐标
        int32 x;
        int32 y;
        // 储存此帧的方向
        int32 dir_idx = -1;
    };

    // 压入第一个元素
    TArray<Cache> stack;
    Cache tmp;
    for (int32 dir_idx = 0; dir_idx < 4; ++dir_idx) {
        // 下一步的下标
        int32 next_x = directions[dir_idx] + StartPoint.X;
        int32 next_y = directions[dir_idx + 1] + StartPoint.Y;
        if (
            (next_x < w) && (next_x > 0) && (next_y < h) && (next_y > 0)
            )
        {
            if (ret.Get(next_y, next_x) == 0) {
                ret.Set(next_y, next_x, -1);
                tmp.x = next_x;
                tmp.y = next_y;
                tmp.dir_idx = dir_idx;
                stack.Emplace(tmp);
            }
        }
    }

    while (stack.Num() != 0) {
        // 随机选择一个元素作为下一步扩展的目标
        int32 r_idx = FMath::RandRange(0, stack.Num() - 1);
        // 用交换来减少数组操作的代价
        stack.Swap(r_idx, stack.Num() - 1);
        Cache c = stack.Top();
        stack.Pop();

        if (ret.Get(c.y, c.x) == -1) {
            // 下一步的下标
            int32 next_x = directions[c.dir_idx] + c.x;
            int32 next_y = directions[c.dir_idx + 1] + c.y;
            if (
                (next_x < w) && (next_x > 0) && (next_y < h) && (next_y > 0)
                )
            {
                if (ret.Get(next_y, next_x) == 1) {
                    ret.Set(c.y, c.x, 2);
                    ret.Set(next_y, next_x, 2);
                    for (int32 dir_idx = 0; dir_idx < 4; ++dir_idx) {
                        int32 store_x = directions[dir_idx] + next_x;
                        int32 store_y = directions[dir_idx + 1] + next_y;
                        if (
                            (store_x < w) && (store_x > 0) && (store_y < h) && (store_y > 0)
                            )
                        {
                            if (ret.Get(store_y, store_x) == 0) {
                                ret.Set(store_y, store_x, -1);
                                tmp.x = store_x;
                                tmp.y = store_y;
                                tmp.dir_idx = dir_idx;
                                stack.Emplace(tmp);
                            }
                        }
                    }
                }
                else {
                    ret.Set(c.y, c.x, 0);
                }
            }
            else {
                ret.Set(c.y, c.x, 0);
            }
        }
    }
}