阴阳师爬塔与迷宫生成算法

最近的阴阳师缘结神活动新增了走迷宫的要素。几百层的迷宫不可能手动绘制吧?于是想到了是不是有迷宫生成算法

能查到的迷宫生成算法有三种:递归回溯、 随机prim算法、 递归分割。前两种属于“拆墙法”,而递归分割则是“造墙法”。先放一下结论:

这三种算法分别适合不同的迷宫情况,递归回溯适合于那种主线支线明显的游戏(如RPG),而递归分割则适合转角较少的游戏(如FPS和ACT),至于Prim,似乎适合最标准的迷宫游戏(随机Prim算法生成的迷宫分支较多,整体上更复杂也更自然)。

阴阳师这个迷宫给我感觉是用递归回溯生成的,因为有一条指向终点的非常明显的通路。

递归回溯本质上是深度优先搜算方法,其迷宫生成步骤为(引自 https://www.jianshu.com/p/f643b0a0b887 ):

  1. 初始化,建立一个所有单元格都被墙隔开的迷宫。
  2. 随机选择一个单元格作为起始点,以此单元格开始打通墙壁。
  3. 以当前单元格为基准,随机选择一个方向,若此方向的邻接单元格没有被访问过,则打通这两个单元格之间的墙壁,并将此邻接单元格作为当前单元格,重复步骤3。
  4. 若当前单元格的四个邻接单元格都已经被访问过,则退回到进入当前单元格的邻接单元格,且以此单元格为当前单元格,重复步骤3,4。
  5. 直到起始点单元格被退回,则算法结束。

为了记录已经访问过的单元格,迷宫生成程序会维护一个,每次进入一个新的单元格,就将这个单元格的坐标放入栈顶。这样回退操作所需要的坐标从栈顶弹出就可以了。

又看了一下维基百科,自己摸索着写出了演示代码(github)。写完后发现,其实用这个算法的话,生成起点和生成终点未必就是玩家走的起点和终点。因为这个算法生成的图中,通路上的任意两点必然是可达的,因此起点和终点可以任意设置。

发表评论

电子邮件地址不会被公开。