这个系列主要记录一些最近探索过程中有意思的算法, 可能整体都比较简短杂乱, 希望有用. 目前的探索方向集中在程序性内容生成机制上. 本篇是基本的迷宫生成算法的介绍, 包含DFS法和BFS法, 下面是这篇文章主要的参考资料
总览, 介绍了几乎所有的程序式地图生成算法 Herbert Wolverson - Procedural Map Generation Techniques https://youtu.be/TlLIOgWYVpI
介绍了最基础的三种PCG地图算法的详细流程 三套简单的迷宫地图生成方案 - 兔四的文章 - 知乎 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迷宫, 整体比较规则
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);
}
}
}
}
BFS迷宫, 分岔路很多