随机地下城生成和 A* 寻路
4.26/5 (5投票s)
如何生成随机地牢，以及在两点之间寻找路径。
引言
许多视频游戏都基于迷宫般的房间，玩家必须穿梭其中。这些通常由人类设计师设计。然而，也有自动生成的需求，无论是为了辅助人类设计师，还是为了填充小型遭遇区域，或者如果游戏是随机而非人类设计的关卡，则在运行时生成地牢。设计地牢的方法有很多种，这取决于你希望地牢具有的特性。然而，我们几乎总是希望地牢是完全连通的，并且几乎总是希望它具有迷宫或房间划分的特性。
本文重点介绍二进制地牢生成。因此，所有的地牢都由填充或未填充的像素组成。这对于大多数游戏来说是不够的，你可能需要额外的符号来表示门、楼梯，也许还有地形类型。但这高度依赖于实际的游戏，例如更高级的逻辑是否允许门。然而，GIF允许每个单元格有256种颜色，而我们只使用了两种，所以有很大的空间来添加其他单元格类型。
没有怪物的地牢是不行的，怪物必须能够穿梭于迷宫般的通道中找到玩家。因此，随机地牢生成器自然而然地与A*寻路算法的实现相结合。
该程序被赋予了一个非常基本的图形用户界面，以允许算法设计师快速查看他们的结果。然而，它并非旨在作为最终用户程序。但它将允许你将地牢保存为GIF。
背景
出于某种原因，热衷于计算机编程的人也往往非常热衷于《龙与地下城》。我不知道它们的相关系数，但我怀疑非常高。最早的计算机程序有些是文字冒险，有些是基于光栅的地牢游戏，例如《Rogue》。尽管现代游戏极其复杂，投入了数百万美元。但是，无论它多么巧妙地向玩家隐藏，最终的游戏逻辑通常都基于一个概念，即它在一个网格上进行，其中一些单元格是可访问的，另一些则不可访问。
因此，我们需要大量的二进制地牢生成器，它们能吐出地牢的二进制地图，然后，如果我们和怪物无法在其中找到路径，那它就毫无用处，所以我们还需要A*寻路算法。然后，我们在这两个核心组件之上构建游戏的其余部分。
虽然所有的生成器都是随机的，但它们创建的地牢具有不同的风味或特性。同样，这高度依赖于游戏。通常，网格对玩家是可见的，并且必须看起来美观。我们通常还需要一个“房间”的概念，用于更高级别的游戏逻辑。有些（但不是所有）生成器自然地适合定义房间。
理解8连通和4连通之间的区别很重要。4连通是沿着边缘（上、下、右、左），8连通也沿着对角线（左上、右上、左下、右下）。通常，地牢游戏坚持可访问单元格的4连通，就像现实生活中一样，玩家无法挤过两个对角线相邻的石块。然而，在现实中，遇到这样放置的两个石块非常罕见，所以许多设计师会坚持可访问和不可访问单元格都采用4连通，并拒绝任何具有8连通单元格的地牢。
如果你使用自己的随机数生成器，你可以通过一个种子使地牢具有确定性。这非常有用。生成大量地牢，选择最好的一个，然后它们可以作为单个种子存储和召回。
使用代码
房间生成器
这或多或少是大多数随机地牢生成器网站使用的最先进的生成器。它不是我的，主要基于Bob Nystrom的工作，尽管我将其转换为C语言。该方法首先随机放置矩形房间。然后使用递归迷宫生成器填充房间之间的区域，该生成器会扩展一棵树，直到没有多余的像素。然后将房间连接到迷宫，并通过消除大多数死胡同来修剪迷宫。
这个算法创建了最好、最吸引人、最实用的地牢。它有大量的微调机会。然而，它创建了一个由通道连接的房间地牢，这不一定是你想要的。
洞穴生成器
对于洞穴关卡，基于方形房间和走廊的生成器是行不通的。所以我们有一个单独的洞穴生成器。
它基于细胞自动机原理工作。我们首先将所有瓷砖设置为随机，除了边框被硬编码为墙壁。然后我们进行多次多数过滤。这会创建连贯的洞穴和墙壁区域。
洞穴区域不相连，所以我们标记独立的区域，然后对于每个区域，取最接近中心的点。然后我们从洞穴到中心画一条略微锯齿状的走廊，直到我们遇到另一个洞穴。这几乎但不能完全保证连接我们所有的洞穴。因此，最后一步是消除任何未连接的洞穴，并打破我们可能引入的背景中的任何8连通。
请注意，你可以稍微修改该函数以保留标签。如果你想将洞穴视为房间或单独的遭遇区域，这可能会很有用。
种子生长生成器
这是另一个生成器。它通过在地牢中放置随机种子，然后扩展它们直到它们几乎接触。结果是一个几乎完全由矩形房间组成的地牢，只有少数填充区域。然后你连接它，这非常容易，只是在隔墙上打门。
可以先添加走廊以获得一些长窄矩形，就像我所做的那样。这种方法产生的空间划分比前一种方法更真实，但对于大多数《Rogue》类游戏来说，可玩性可能较低。
所以也许可以用于房屋内部。
方块生成器
在光栅上每三个方块填充一个可以创建一个迷宫，其连接性对于大多数游戏来说是合适的。一个非常简单的算法是重复这个过程，直到生成一个连接起点和终点的地牢。小时候，我们用这种方法制作自己的基于地牢的游戏，用Basic语言编写。
当前的生成器稍微复杂一点，但复杂程度不高。每三个方块中随机填充一个。打破8连通。然后填充小的、不连通的房间。然后使用简单的隧道连接任何不连通的房间。最后，剔除任何小柱子。
A*寻路
与随机地牢生成器打包在一起的A*寻路算法在二进制图像上寻找路径。它允许对角线移动，这是可访问单元格必须是4连通的一个好理由。
A*非常容易使用。你用一个二进制图像调用它，它会在两个并行数组中返回两点之间的路径，以避免声明“点”类型。如果找不到路径，它返回0。
/**
A star path finding algorithm.
@param[in] binary - the binary image
@param width - image width
@param height - image height
@param sx - start point x-coordinate
@param sy - start point y-coordinate
@param ex - end point x coordinate
@param ey - end point y coordinate
@param[out] pathx - return for x-coordinates of path (malloced)
@param[out] pathy - return for y-coordinates of path (malloced)
@returns Number of path points, -1 on fail.
*/
int astar(unsigned char *binary, int width, int height, int sx, int sy, int ex, int ey, int **pathx, int **pathy)
它是这样工作的。
int astar(unsigned char *binary, int width, int height, int sx, int sy, int ex, int ey, int **pathx, int **pathy)
{
unsigned char *img = 0;
HEAP *heap = 0;
int ok;
APOINT a, b, ap, np;
int set, otherset;
unsigned char neighbours[9];
int i, ii;
int j;
int nx, ny;
int targetx, targety;
int Npa, Npb;
int *pathax, *pathay, *pathbx, *pathby;
int *tpathx, *tpathy;
int answer = 0;
img = malloc(width * height);
if (!img)
goto out_of_memory;
for (i = 0; i < width*height; i++)
img[i] = binary[i] ? FILL : 0;
img[sy*width + sx] |= ASET;
img[ey*width + ex] |= BSET;
heap = HeapCreate(100);
if (!heap)
goto out_of_memory;
我们首先设置一个带标记的栅格，标记为`FILL`、`ASET`和`BSET`。`FILL`告诉我们单元格是否可访问，`ASET`和`BSET`用于从A和B生长的两个气泡，以标记单元格是否已被访问。我们还创建了一个优先级队列。我们将节点推送到优先级队列中，它平衡了两个因素。靠近起点和终点的节点（因此成本较低）获得优先权。但是与启发式匹配的节点也获得优先权，即最短路径将近似于乌鸦飞行的直线路径。
a.x = sx;
a.y = sy;
a.fscore = 0;
a.heuristic = diagonaldistance(sx, sy, ex, ey);
ok = HeapInsert(heap, 0, sizeof(APOINT), &a, heapcompf);
if (ok == 0)
goto out_of_memory;
b.x = ex;
b.y = ey;
b.fscore = 0;
b.heuristic = diagonaldistance(sx, sy, ex, sy);
ok = HeapInsert(heap, 0, sizeof(APOINT), &b, heapcompf);
if (ok == 0)
goto out_of_memory;
然后我们设置两个气泡，每个气泡最初由单个点A和B组成，放入优先级队列。
while (HeapGetSize(heap) > 0)
{
HeapDelete(heap, 0, 0, &ap, heapcompf);
get3x3(neighbours, img, width,height, ap.x, ap.y, 0x0);
set = neighbours[4] & SETMASK;
if (set == ASET)
{
otherset = BSET;
targetx = ex;
targety = ey;
}
else
{
otherset = ASET;
targetx = sx;
targety = sy;
}
现在我们从优先级队列中提取第一个条目，并确定它是来自A气泡还是B气泡。`otherset`是另一个集合。
for (j = 0; j < 9; j++)
{
nx = ap.x + (j % 3) - 1;
ny = ap.y + (j / 3) - 1;
遍历邻居，获取邻居的x, y坐标（nx, ny）。
if ((neighbours[j] & FILLMASK) && (neighbours[j] & SETMASK) == 0)
{
double cost = 0.0;
switch (j)
{
case 0: cost = 1.414; img[ny*width + nx] |= (set | SOUTHEAST); break;
case 1: cost = 1.0; img[ny*width + nx] |= (set | SOUTH); break;
case 2: cost = 1.414; img[ny*width + nx] |= (set | SOUTHWEST); break;
case 3: cost = 1.0; img[ny*width + nx] |= (set | EAST); break;
case 4: break;
case 5: cost = 1.0; img[ny*width + nx] |= (set | WEST); break;
case 6: cost = 1.141; img[ny*width + nx] |= (set | NORTHEAST); break;
case 7: cost = 1.0; img[ny*width + nx] |= (set | NORTH); break;
case 8: cost = 1.414; img[ny*width + nx] |= (set | NORTHWEST); break;
}
if (j != 4)
{
np.x = nx;
np.y = ny;
np.heuristic = diagonaldistance(np.x, np.y, targetx, targety);
np.fscore = ap.fscore + cost;
ok = HeapInsert(heap, 0, sizeof(APOINT), &np, heapcompf);
if (ok == 0)
goto out_of_memory;
}
}
然后我们扩展到任何未探索的单元格。一个4连通的邻居成本为1，一个8连通的邻居成本为sqrt(2)。我们还必须重新计算启发式函数。
else if ((neighbours[j] & SETMASK) == otherset)
{
Npa = traceback(img, width, height, ap.x, ap.y, &pathax, &pathay);
Npb = traceback(img, width, height, nx, ny, &pathbx, &pathby);
if (Npa == -1 || Npb == -1)
goto out_of_memory;
reverse(pathax, Npa);
reverse(pathay, Npa);
tpathx = malloc((Npa + Npb) * sizeof(int));
tpathy = malloc((Npa + Npb) * sizeof(int));
if (!tpathx || !tpathy)
goto out_of_memory;
for (ii = 0; ii < Npa; ii++)
{
tpathx[ii] = pathax[ii];
tpathy[ii] = pathay[ii];
}
for (ii = 0; ii < Npb; ii++)
{
tpathx[ii + Npa] = pathbx[ii];
tpathy[ii + Npa] = pathby[ii];
}
另一方面，如果我们击中了来自另一个集合的单元格，气泡已经连接，我们就完成了。我们需要追踪两条路径回到`sx`，`sy`和`ex`，`sy`，然后将它们连接起来，这就是我们的答案。
if (tpathx[0] != sx || tpathy[0] != sy)
{
reverse(tpathx, Npa + Npb);
reverse(tpathy, Npa + Npb);
}
free(pathax);
free(pathay);
free(pathbx);
free(pathby);
*pathx = tpathx;
*pathy = tpathy;
answer = Npa + Npb;
goto done;
}
}
}
done:
HeapDestroy(heap);
free(img);
return answer;
out_of_memory:
HeapDestroy(heap);
free(img);
return -1;
}
然后进行一些微调，确保路径方向正确并清理内存。
关注点
随机地牢生成器写起来很有趣，只要地牢是连通的，就没有对错之分，你可以尽情发挥。然而，公共随机地牢服务器相当复杂，这些算法还需要一段时间才能赶上它们。
历史
随机地牢生成器在GitHub上的二进制图像库中维护
http://malcolmmclean.github.io/binaryimagelibrary/