基于Map-Elites的第一人称射击游戏地图程序化生成

# 使用 MAP-Elites 程序化生成第一人称射击游戏地图
来源：https://arxiv.org/html/2605.30570
[![[未加标题的图片]](https://arxiv.org/html/2605.30570v1/x1.png)Simone de Donato](https://orcid.org/0009-0002-1844-9845) 米兰理工大学 — DEIB simone\.dedonato@mail\.polimi\.it &[![[未加标题的图片]](https://arxiv.org/html/2605.30570v1/x2.png)Pier Luca Lanzi](https://orcid.org/0000-0002-1933-7717) 米兰理工大学 — DEIB pierluca\.lanzi@polimi\.it &[![[未加标题的图片]](https://arxiv.org/html/2605.30570v1/x3.png)Daniele Loiacono](https://orcid.org/0000-0002-5355-0634) 米兰理工大学 — DEIB pierluca\.lanzi@polimi\.it

###### 摘要

我们研究了如何应用 MAP-Elites（一种知名的质量多样性算法）来设计第一人称射击（FPS）游戏关卡。我们考虑了两种常用的地图表示方法（All-Black 和 Grid-Graph），并引入了两种新的表示方法（Point-Line 和 Spatial-Layout），从而改进 FPS 地图的特征描述。我们定义了一系列指标来描述地图的拓扑属性（仅依赖于地图布局）和涌现属性（必须通过实际游戏过程来评估）。我们进行了深入分析，以确定最适合引导 MAP-Elites 照明过程的特征。我们应用了带滑动边界的 MAP-Elites（MESB）来进化 FPS 地图种群。我们的结果表明，与之前用于进化 FPS 地图的表示方法相比，新的表示方法能够生成多样性更高、质量更好的地图。

*关键词* 质量多样性⋅\\cdotMAP-Elites⋅\\cdot程序化内容生成⋅\\cdot关卡设计⋅\\cdot地图设计⋅\\cdot第一人称射击

## 1 引言

基于搜索的程序化内容生成已被应用于使用传统\[6 (https://arxiv.org/html/2605.30570#bib.bib2),20 (https://arxiv.org/html/2605.30570#bib.bib27),5 (https://arxiv.org/html/2605.30570#bib.bib21),21 (https://arxiv.org/html/2605.30570#bib.bib30)\]和交互式进化计算\[23 (https://arxiv.org/html/2605.30570#bib.bib113)\]来进化 FPS 游戏地图。所有这些方法都专注于关卡设计的某个特定方面，例如两次击杀之间的平均游戏时间\[6 (https://arxiv.org/html/2605.30570#bib.bib2)\]、游戏平衡性\[20 (https://arxiv.org/html/2605.30570#bib.bib27),5 (https://arxiv.org/html/2605.30570#bib.bib21)\]、实现逃跑行为\[21 (https://arxiv.org/html/2605.30570#bib.bib30)\]，或者遵循一组设计指南\[23 (https://arxiv.org/html/2605.30570#bib.bib113)\]。这些方法生成的地图使某个特定目标最大化，并且通常探索有限的设计空间\[23 (https://arxiv.org/html/2605.30570#bib.bib113)\].

在本文中，我们探索应用质量多样性方法，特别是 MAP-Elites\[22 (https://arxiv.org/html/2605.30570#bib.bib93)\]，来进化多人 FPS 游戏的地图。MAP-Elites 是一种进化算法，用于在由一对特征定义的照明搜索空间中探索和优化多样化、高性能的解决方案。个体由一个系统必须最大化的适应度来表征，算法维护一个精英解决方案的存档。解决方案存储在由系统用于照亮搜索空间的特征值所标识的格子中。具体来说，我们应用了带滑动边界的 MAP-Elites（MESB）\[11 (https://arxiv.org/html/2605.30570#bib.bib81)\]，它维护一个自适应格子存档。我们考虑了两种常用的地图表示方法（All-Black 和 Grid-Graph）\[6 (https://arxiv.org/html/2605.30570#bib.bib2)\]，并引入了两种我们专门创建的新表示方法（Point-Line 和 Spatial-Layout），以丰富 FPS 地图的特征描述。我们定义了几个指标来描述地图的拓扑属性（从地图布局计算得出）和涌现属性（通过实际游戏过程评估）。我们对可用特征进行了广泛分析，并重点关注了文献中被认为对 FPS 地图设计最有趣的那些特征\[15 (https://arxiv.org/html/2605.30570#bib.bib1),6 (https://arxiv.org/html/2605.30570#bib.bib2),2 (https://arxiv.org/html/2605.30570#bib.bib3)\]。具体来说，我们关注三个拓扑特征：可步行面积和地图对称性（maxSymmetry），它们提供了地图拓扑的高级描述\[15 (https://arxiv.org/html/2605.30570#bib.bib1),6 (https://arxiv.org/html/2605.30570#bib.bib2)\]；以及地图离心率（averageEccentricity），这是专门为基于图的 FPS 地图表示引入的\[2 (https://arxiv.org/html/2605.30570#bib.bib3)\]。我们还考虑了地图节奏（pace），它衡量战斗交战的频率\[6 (https://arxiv.org/html/2605.30570#bib.bib2)\]。111我们请读者参考\[10 (https://arxiv.org/html/2605.30570#bib.bib195)\]以了解我们分析的所有特征的全面讨论。我们将这四个特征组合成两对：area-maxSymmetry，仅捕捉 FPS 地图的拓扑特性；以及 pace-averageEccentricity，结合了游戏性和拓扑特征。我们比较了使用四种表示方法以及这两对特征通过 MAP-Elites 进化得到的地图。结果表明，与之前用于进化 FPS 地图的表示方法相比，新的表示方法能够生成多样性更高、整体质量更好的地图。所有实验均使用开源框架 Project Arena\[3 (https://arxiv.org/html/2605.30570#bib.bib193)\]（用于第一人称射击游戏研究的扩展版）和 PyRibs 库\[27 (https://arxiv.org/html/2605.30570#bib.bib74)\]（用于质量多样性优化）运行。本文讨论的实验所用的所有代码以及呈现的实验数据可在\[26 (https://arxiv.org/html/2605.30570#bib.bib194)\]获得。

## 2 相关工作

基于搜索的程序化内容生成（SB-PCG）\[28 (https://arxiv.org/html/2605.30570#bib.bib115)\]将生成-测试方法应用于程序化内容生成。首先生成候选方案，然后使用适应度函数进行评估，并根据评估结果创建新的候选方案。SB-PCG 包含多种遗传和进化计算方法，并已应用于多种游戏类型，包括第一人称射击游戏。

### 2.1 用于 FPS 游戏的 SB-PCG

Cardamone 等人\[6 (https://arxiv.org/html/2605.30570#bib.bib2)\]是首个将基于搜索技术应用于为《Cube 2: Sauerbraten》\[9 (https://arxiv.org/html/2605.30570#bib.bib10)\]的“死亡竞赛”游戏模式生成可玩 FPS 地图的研究。在他们的工作中，他们引入了四种基因型（All-White、All-Black、Grid 和 Random-Digger）以及相应的映射函数，用于生成《Cube 2》的地图。候选地图通过模拟一场 10 分钟的四名机器人比赛来评估；适应度计算为从机器人开始战斗到被对手击败的平均时间。在\[6 (https://arxiv.org/html/2605.30570#bib.bib2)\]中，作者认为有趣的地图应具备允许长时间战斗发生的特征，例如逃生路线和放置得当的资源。Lanzi 等人\[20 (https://arxiv.org/html/2605.30570#bib.bib27)\]专注于进化允许不同技能水平和游戏风格（例如，进攻型、防守型）的机器人之间进行平衡的 1 对 1“死亡竞赛”比赛的地图。他们也使用了《Cube 2》、All-Black 基因型\[6 (https://arxiv.org/html/2605.30570#bib.bib2)\]，并通过模拟涉及不同类型机器人的比赛来评估地图。适应度函数计算为得分（击杀数）比率分布的熵，因为熵越高，得分分布越平衡，因此比赛越平衡。Bhojan 和 Wong\[4 (https://arxiv.org/html/2605.30570#bib.bib123)\]专注于更快的进化方法，在他们开发用于测试其方法的游戏中，为“夺旗”游戏模式在线进化地图。Bhojan 和 Wong\[4 (https://arxiv.org/html/2605.30570#bib.bib123)\]旨在实现快速进化，因此他们没有使用模拟，而是定义了一个适应度函数，该函数是测量的地图特征之和，例如连通性、强制碰撞点、旗帜公平性、总体旗帜公平性\[4 (https://arxiv.org/html/2605.30570#bib.bib123)\]。他们通过放置瓷砖来生成地图，这些瓷砖要么是室内区域、室外区域，要么是不可进入区域，并遵循与已有瓷砖的相邻规则。然后清理地图中的伪影，并使用洪水填充算法\[32 (https://arxiv.org/html/2605.30570#bib.bib28)\]扫描以识别区域，然后在需要的地方用门连接起来。最后，地图上装饰了战略点位，如重生点、旗帜位置和掩体。Ølsted 等人\[23 (https://arxiv.org/html/2605.30570#bib.bib113)\]转向为《FPSEvolver》游戏进化地图，重点关注类似于《反恐精英》的“拆除炸弹”游戏模式。他们定义了一组指南（良好交战规则），并设计了一种能够创建符合这些概念的布局的基因型，避免死胡同并确保竞技场的存在。他们应用交互式进化计算来进化地图，由人类玩家游玩地图，然后要求他们留下简单的二进制反馈（点赞或点踩），并以此指导进化\[23 (https://arxiv.org/html/2605.30570#bib.bib113)\]。Cachia 等人\[5 (https://arxiv.org/html/2605.30570#bib.bib21)\]在《Cube 2》中进化了占据不止一层的地图，使用了一个基因组，该基因组结合了第一层和第二层的不同表示——前者是一组识别可通行瓷砖的走廊和相连房间，后者使用 Random-Digger\[6 (https://arxiv.org/html/2605.30570#bib.bib2)\]。适应度基于人工代理的模拟、可用的导航空间以及特定关卡模式的存在性。Loiacono 等人\[21 (https://arxiv.org/html/2605.30570#bib.bib30)\]采取了与\[6 (https://arxiv.org/html/2605.30570#bib.bib2)\]类似的方法，利用相同的 All-Black 表示来进化促进逃跑行为的地图。适应度计算为比赛中机器人丢失当前正在战斗的敌人踪迹的次数。他们表明，他们的方法能够生成在专为持续攻击而设计的机器人中启用逃跑行为的地图，同时显著降低地图的节奏\[21 (https://arxiv.org/html/2605.30570#bib.bib30)\].

### 2.2 用于游戏的 MAP-Elites

MAP-Elites 已被用于为多种游戏类型生成内容，例如平台游戏、“类塞尔达”冒险游戏、益智游戏和卡牌游戏。

平台游戏。Khalifa 等人\[17 (https://arxiv.org/html/2605.30570#bib.bib59)\]引入了受约束的 MAP-Elites 来进化各种可玩的《超级马里奥兄弟》关卡，并比较了生成这些关卡的不同模拟方法\[17 (https://arxiv.org/html/2605.30570#bib.bib59)\]。Warriar 等人\[30 (https://arxiv.org/html/2605.30570#bib.bib56)]实现了 PlayMapper，这是 MAP-Elites 算法的一个变体，能够生成不同大小的《超级马里奥兄弟》关卡，并赋予对其生成的显著控制权。Fontaine 等人\[12 (https://arxiv.org/html/2605.30570#bib.bib51)\]应用了一组 MAP-Elites 方法来照亮生成对抗网络（GAN）的潜在空间，评估了算法在生成具有特定特征的《超级马里奥兄弟》场景任务上的性能。

冒险游戏。Alvarez 等人\[1 (https://arxiv.org/html/2605.30570#bib.bib87)\]引入了交互式受约束 MAP-Elites 来在《Evolutionary Dungeon Designer》（EDD）中进化地牢房间，这是一个混合主动的共创工具。他们将 EDD 与可行-不可行双种群（FI2Pop）遗传算法\[19 (https://arxiv.org/html/2605.30570#bib.bib99)\]相结合，创建了一个交互式版本的受约束 MAP-Elites，用户通过选择要探索的特征来引导搜索，并对生成的房间提供反馈\[1 (https://arxiv.org/html/2605.30570#bib.bib87)\]。Charity 等人\[7 (https://arxiv.org/html/2605.30570#bib.bib95)\]在 GVG-AI 框架的游戏\[24 (https://arxiv.org/html/2605.30570#bib.bib129)\]中搜索具有特定机制的关卡，这些游戏包括一个“类塞尔达”游戏\[7 (https://arxiv.org/html/2605.30570#bib.bib95)\]。González-Duque 等人\[13 (https://arxiv.org/html/2605.30570#bib.bib77)\]应用了智能试错法（一种使用 MAP-Elites 生成先验的贝叶斯优化形式）来执行动态难度调整，为一个“类塞尔达”游戏生成所需难度的关卡。Viana 等人\[29 (https://arxiv.org/html/2605.30570#bib.bib75)\]应用 MAP-Elites 来生成具有锁门任务和敌人放置的高质量、高多样性的关卡。

益智游戏。Charity 等人\[8 (https://arxiv.org/html/2605.30570#bib.bib94)]开发了《Baba is Y’all》，这是一个混合主动版本的《Baba is You》，玩家可以与机器协作设计关卡。该游戏允许玩家编辑《Baba is You》的关卡，类似于《超级马里奥制造》，但额外目标是填充底层 MAP-Elites 算法的存档，其中关卡根据解决时激活的机制（规则）组合来放置。系统可以根据存档中已有的内容以及当前缺失的内容，为用户编辑提出各种起始关卡，以帮助玩家填充存档\[8 (https://arxiv.org/html/2605.30570#bib.bib94)\].

卡牌游戏。MAP-Elites 也被用于为《炉石传说》生成具有竞争力的卡组。Fontaine 等人\[11 (https://arxiv.org/html/2605.30570#bib.bib81)\]注意到 MAP-Elites 均匀地划分行为空间，但这可能导致与行为空间的真实分布不匹配，从而降低照明效果。此外，他们认为先验分布可能是难以甚至不可能知道的。为了解决这些问题，他们提出了带滑动边界的 MAP-Elites（MESB），这是 MAP-Elites 的一个变体，其中单元格之间的边界不是基于特征值均匀放置，而是动态地放置在分布的一定百分位数标记处。指定了重映射频率，这意味着定期重新计算边界，从而允许对搜索空间的分布进行良好的估计。\[11 (https://arxiv.org/html/2605.30570#bib.bib81)\]

其他类型。Khalifa 等人\[18 (https://arxiv.org/html/2605.30570#bib.bib91)\]已应用 MAP-Elites 来生成弹幕射击游戏关卡。Gravina 等人\[14 (https://arxiv.org/html/2605.30570#bib.bib5)\]应用受约束惊喜搜索为《虚幻竞技场 III》第一人称射击游戏生成武器。

质量多样性方法尚未应用于 FPS 游戏关卡的生成，这正是我们研究的目标。

## 3 Project Arena

Project Arena\[3 (https://arxiv.org/html/2605.30570#bib.bib193)\]是一个开源平台，用于使用 Unity 游戏引擎开发的第一人称射击游戏研究。它具有模块化架构，由一系列管理器、机器人和可视化组件构成，由于有众多可用的 Unity 扩展，这些组件可以轻松自定义。

管理器。游戏管理器处理主要生命周期，包括设置、游戏模式、比赛、地图管理和生成。Project Arena 有三种游戏模式：Duel，实现了所有 FPS 中经典的死亡竞赛；Target Rush，包含越来越难的攻击敌人波次，玩家必须消灭它们；以及 Target Hunt，玩家必须在时间限制内搜索并消灭敌人。