如何设计一张有“魂味”的地图？——论“类魂”游戏关卡的拓扑结构

原文发表于知乎，作者尼莫，地址：https://zhuanlan.zhihu.com/p/415025159
GameRes经作者授权转载发布。

摘要

在本文中，我们试图探究“类魂”游戏(3D银河恶魔城类游戏)关卡存在的数学上的普遍性设计原理。

基于一种原胞自动机方法[1] ，可以一般的将关卡地图划分成“开放区域(Open Aera)”、“路径(Path)”与“兴趣点(POI)”，三类元素相互组合。此时可以得到与该关卡一一对应的、抽象的逻辑图结构。

据此，我们选取了五款主流的“类魂”游戏(《黑暗之魂1》、《黑暗之魂3》、《血源诅咒》、《仁王1》、《帕斯卡契约》)，并对五款游戏当中的84张地图进行了解析性分析。利用图论、拓扑学等数学工具，我们分别计算了总共84张地图各自的“稳定因子” y 值。(  y 定义见4.3小节)

结果表明，《黑暗之魂1》中46%地图的  y 值介于0.94~1之间；《黑暗之魂3》中57%地图的 y 值介于0.91~0.94之间；对于《仁王》，有81%地图的 y  值小于0.91。

证明了《黑暗之魂1》、《黑暗之魂3》、《仁王》这三款游戏的关卡地图设计逻辑存在本质上的差异。

调研统计结果又显示，玩家对于“类魂”游戏各个地图关卡设计的满意度，高度相关于地图的“稳定因子” y  。在统计上，地图的 y 值是和玩家给出的反馈呈正相关的 —— 一个定性的分析是：y 值愈高，玩家评价愈好。表明“稳定因子”的确是关于关卡设计评价标准的有效观测量。

因此对于一个以探索性为主要驱动的合格“类魂”游戏/3D银河恶魔城类游戏，我们认为至少需要保证其单关卡地图的 y 值大于0.94。

在文章的最后，基于该原理，我们试图修整《帕斯卡契约》当中不满足 y值大于0.94的地图，将其改造为“中 y 普适类”的类似于《魂3》的关卡——这个是一个可批判性的结果，如果本文的结论正确，那么这个被修整过的新地图理应得到玩家更高的评价。

关键词：游戏科学，关卡设计，类魂游戏，图论，拓扑学

前言

首先声明，本文虽然采用了期刊样的论文格式，但是在文章内容和遣词造句方面会随意很多，并不会遵守那些规矩。因为本文的目标读者，是广大热爱黑魂的普通玩家、想深入研究游戏机制的高端玩家、地图类Mod的制作者、新手策划、独立类魂游戏设计者，正在开发类魂游戏原型的开发者等等，而不是标准的科研工作者。为了能较好的传达笔者的研究成果，笔者会尝试用一种偏向科普式的讲法。类似于聊天一样，笔者会拿出一些很具体的实例去分析，尽量让不了解图论的读者也能很好的get到本文的核心观点。

在开始介绍研究成果之前，笔者会用较大的文字量去介绍“我们写这篇文章的目的”，是因为笔者希望观点千差万别的各类读者讲清楚，我们是在对过往“玩家&策划”二元叙事的扬弃，站在一个新的第三者中立视角去审视游戏关卡设计的更底层的数理逻辑。笔者真诚的希望各位读者在阅读本文之后，可以有所收获。

背景

我们为什么要写这篇文章？

自2009年From Software社由宫崎英高执掌的《恶魔之魂》发售至今的十二年里，总共产出了六部质量极高的、冠以“魂类”之名的作品。以其较高的难度性、键位简单但不失趣味的战斗玩法、精巧复杂的关卡地图设计、暗黑晦涩的文艺叙事，收获了核心玩家群体无数赞誉。特别是在2018年3月份，《只狼：影逝二度》（下文简称为《只狼》）发售之后，乘着直播业兴起的东风，依靠前五代作品的人气积累，再加上作品本身的话题性。《只狼》成功出圈，吸引了大批原本非单机游戏玩家以及非动作类游戏玩家群体。以往作为“小众”的“魂类”游戏，在TGA游戏大赏上，得票超过小岛秀夫的《死亡搁浅》，夺下了“年度最佳游戏(GOTY)”桂冠。

与《只狼》大火相对应的，是市场的迅速响应，并出现了一大批质量良莠不齐的“类魂（Soul's Like）”游戏。

2017年光荣社发售的游戏《仁王》，总监安田文彦在采访中表示，关卡设计受到了《黑暗之魂3》（下简称《魂3》）的启发。

2018年在E3游戏展亮相的《帕斯卡契约》（下简称《帕斯卡》），刚一亮相就被称作“国产黑魂手游”而备受期待。

2019年万代旗下的《噬神者》团队，将黑魂的设计理念，结合了自身共斗游戏的经验，推出了“二次元共斗类魂”作品《噬血代码》。

2020年，利用UE4制作的“类魂”游戏《致命躯壳》在Epic发售，引发国内最大游戏论坛NGA版上，新一轮对“类魂”游戏标准的大讨论。

2021年9月17日，国产克苏鲁风“类魂”游戏《明末：渊虚之羽》发布演示pv，引起玩家群体热议。(紧跟时事)

这些被冠以“类魂”之名的作品，往往一经出世就背负着极大的争议，褒贬具存。而当我们去询问那些抱有质疑的玩家，对这些作品的不满源自哪里，他们的回答往往是惊人的一致

——“没有‘魂味’”。

那么请问，什么是“魂味”？

更深入一点的问：“谁有权力定义‘魂味’？”

在这个问题当中，显而易见的存在两种语境——来自游戏玩家的阐述，以及来自游戏设计者的阐述。

在玩家的视角下，似乎在很多意义上，所谓的“高端玩家”化身成为了一种意见领袖，他们的测评成为了对该游戏有没有“魂味”评判锚点。常常有新人对某些游戏机制发出质疑的时候，会被一些老Ass（笔者注：对魂圈高玩的俗称）教导：“你操作太菜了”，或者“你玩到后期就会喜欢了”。亦或者他们会举出一些诸如“近路多少”、“篝火设置”，“难度曲线”的例子，再用“黑魂里却如何如何”进行对比，以此佐证这款游戏确实有或者没有“魂味”

在设计者视角下我们当然可以举出更多的例子来，我们可以去拆解一款游戏，是否有纯净UI、系统便于学习、关卡良好引导、战斗机制丰富、键位逻辑合理、摄像机视角跟随、美术素材精良、状态机中动画衔接流畅等等。设计者写反推案时，可以画出一个大大的思维树状图，以详细的分类给出，黑魂具有哪些游戏要素。而只要我做出的游戏有这些要素，那么我就是一个“好”的类魂游戏。

但是，这两种视点，无论哪一个，都是一种，基于自身经验的事实判断去推演一种价值判断的唯象表述，他的论述逻辑是这样的：什么是“魂味”？像《黑魂》的就是有魂味；为什么《黑魂》设计的好？因为黑魂有“魂味”。

这是显然一种典型的循环论证，因而不可能给出一个可证伪的科学评判。

一个比较现实的讽刺例子是，《仁王》的总监安田文彦在接受采访时，面对玩家“游戏不好玩”的质疑，他直言不讳的表达了自己的疑惑：“这么好玩的游戏，为什么大家不喜欢呢？”

而本文要做的，就是打破这种循环论证，给魂系列的游戏和宫崎英高本人“祛魅”。

转而利用客观的理性工具，去定量化、理论性、批判性的研究全体的“魂类”和“类魂”游戏。打破原有的“魂类”游戏(特指魂、血、狼)=好游戏，模仿宫崎英高“类魂”游戏=坏游戏的二元叙事。我们纵向剖开各个游戏，将游戏本身打碎，以各个关卡为单位进行研究。

须知，“魂类”游戏里面有“好”关卡，也有“坏”关卡，“类魂”游戏里面也有“好”关卡和“坏”关卡。“魂类”游戏里的“好”、“坏”关卡各占比多少？“类魂”游戏里的“好”、“坏”关卡又各占比多少？“好”关卡有什么通性？“坏”关卡又有什么通性？我们向上综合，理性抽象出一个优秀的3D银河恶魔城类游戏的一般性设计原理。

我们试图建立起这样一种理论：无论是否玩过黑魂，无论游戏技术高低，无论设计水平高低，当我去游玩一款“类魂”游戏时，都有这么一套行之有效的方法，可以让我对这款游戏设计的是否“优秀”，是否“有魂味”，做一个定量性的判断。

在对于黑魂的民间研究工作中，关于黑魂关卡的数值设计和机制设计，已经有了比较好的研究成果[2] [3] [4] [5] [6]。

本文的着眼点，将会是一个更宽泛的命题——黑魂的关卡地图的逻辑结构设计。

为什么是图论？为什么恰好是图论？

在1735年东普鲁士的 (加里宁格勒) 柯尼斯堡市区跨普列戈利亚河两岸，河中心有两个小岛。小岛与河的两岸有七条桥连接。


欧拉时代的柯尼斯堡地图，显示了当时七座桥的实际位置，河流和桥梁分别用蓝色和绿色标出

有人突发奇想：在所有桥都只能走一遍的前提下，如何才能把这个地方所有的桥都走遍？

问题提出后，很多人对此很感兴趣，在茶余饭后纷纷进行试验，但在相当长的时间里，始终未能解决。怎么才能找到成功走过每座桥而不重复的路线呢？因而形成了著名的“柯尼斯堡七桥问题”（Seven Bridges of Konigsberg Problem）。

这个问题是图论中的著名问题,也是世界上第一个图论问题。最终被当时的著名数学家欧拉所解决。

我们先暂且停下，从一个数学家的视角，欧拉将这个谜题称之为“问题(Problem)”。那么，如果我们从一个玩家或者策划的角度出发呢？

根据著名游戏设计师特雷西·富勒顿(Tracy Fullerton)表述的观点[7]，构成一个游戏的四个必须要素是：

• 空间(Space)
• 规则(Rule)
• 决策(Decision)
• 目标(Target)
  

对于“柯尼斯堡七桥”而言，我们具有

• 游戏空间——柯尼斯堡普列戈利亚河上的桥与河岸
• 任务规则——每条桥梁只能走一遍；
• 玩家决策——行人可以自由的选择起始地点，以及过桥的顺序；
• 胜利目标——所有的桥都走过一遍。
  

是的，你没看错。在玩家或者策划的眼中，“柯尼斯堡七桥”不再是一个问题(Problem)，而是一个游戏(Game)，名叫“柯尼斯堡七桥游戏”(Seven Bridges of Konigsberg Game)。更一般的可以看出，鉴于这个游戏空间并不是任意一点可达的(桥下的河水对行人来说不可达)，玩家(行人)被严格限制了探索区域，因此它不是一个开放世界，“柯尼斯堡七桥游戏”是一个事实上的“箱庭式关卡”。从游戏的角度来说，柯尼斯堡七桥本身也大抵是世界上最早的一批箱庭式关卡设计之一。

我们回到数学家视角，来继续看欧拉的故事，欧拉是如何解决这个问题的呢？

他在论文《柯尼斯堡的七桥》中，证明符合条件的走法并不存在，也顺带提出和解决了一笔画问题，成为图论史上第一篇重要文献。欧拉把实际的抽象问题简化为平面上的点与线组合，每一座桥视为一条线，桥所连接的地区视为点。这样若从某点出发后最后再回到这点，则这一点的线数必须是偶数，这样的点称为偶顶点。相对的，连有奇数条线的点称为奇顶点。欧拉论述了，由于柯尼斯堡七桥问题中存在4个奇顶点，它无法实现符合题意的遍历。


欧拉将7座桥抽象成了一根线，4处河岸抽象成了一个点，问题就被化简成了，分析这个4点7边的“图”的结构问题

而这些解析，最后发展成为了数学中的图论。

由此，借用这样一种“知识考古学”的办法追本溯源，我们成功在数学与游戏科学之间架起来一座桥梁——作为古典图论的源头，“柯尼斯堡七桥问题”既然也可以被诠释为一款箱庭式关卡游戏，并且这个游戏的“解法”是欧拉使用图论最终给出的。那么一个合理的反推是:我们有理由相信，得到了充分发展的现代图论，可以成为我们今日分析电子游戏当中箱庭式关卡的利器。同时，也指出了本文这套方法论的适用范围——即，3D银河恶魔城类游戏当中的箱庭式关卡。

类魂游戏，作为近十年来最经典的3D银河恶魔城类游戏，拥有清晰可辨的箱庭式关卡特征，这就是我们选择图论对其分析的缘由。

类魂关卡中的图结构

自然逻辑图

利用图论分析游戏关卡的做法，并非笔者本人的独创。早在2002年，Adams.David的一篇文章[8]，就已经开始尝试使用计算机图论的方法平台跳跃类游戏的地图。随后历经几位计算机图论专家的发展[9] [10] [11].

到了2010年，Joris Dormans撰写的《Adventures in Level Design》一文[1]开始进入箱庭式关卡设计领域。在这项工作中，他试图利用图论的方法“有限开圆覆盖”划分出一张地图的“开放区域”，这张地图就是著名游戏《塞尔达传说：黄昏公主》当中的地图关卡：森林寺庙。借此，Joris Dormans实现了将关卡的“Space”（空间几何属性）转化为“Mission”（任务逻辑属性）。


Joris Dormans后续的文章则继续探讨了计算机生成类似关卡的生成语法(Generative Gammar)方案。本文的思路与之不同，我们并不在意如何生成地图，我们是要探寻如何评价地图。分析利用已经被游戏设计者们设计出来的地图，分析那些被玩家认为是“好”的地图是否具有一般性的结构。

另一方面，是对于魂系关卡的科学量化研究。在2016年，乌普萨拉大学的Valdemar Ribbing, Laban Melander两位科研工作者试图利用对兴趣点、捷径等交互要素的统计，来给予关卡评价以更定量性的判据[12]。不过受制于早期不成熟解包工具的限制，很多数据只能通过游戏内比照来定标。

近些年来，随着魂系游戏反编译技术的成熟。作为一个后继者，我们不妨直接借鉴前人的成果。第一步，就是要对《黑暗之魂1》、《黑暗之魂3》、《血源诅咒》、《仁王1》、《帕斯卡契约》这五款游戏的总共84张地图进行剖分。

首先，我们需要定义一些“类魂”游戏关卡地图当中，常见游戏元素的概念。

1.兴趣点(POI,Point Of Interest)

游戏当中可以吸引玩家兴趣、引导游戏流程、维持心流体验的可交互元素。主要表现为：篝火(存档点)、可捡拾的宝物、敌人、宝箱、可交互NPC、掉落的素材/增益道具，或者特殊的灯光、建筑、奇观等等。

2.开放区域(Open Aera)

在关卡中，由一簇POI所框定的一块可探索区域，一般具有明晰的独立于其他开放区域的地标、独立的敌人AI适用区域(NavMesh)、美术风格或素材等。在我们的绘图中，普通的开放区域用绿色圆圈标出。

3.路径(Path)

用于给予各个开放区域的连接关系的线型结构，一般不含有POI。

4.存档点(Point Of Save&Load)

POI的一种，玩家可以在关卡当中的此处，进行休整、升级、传送、回复、配队、备战等等操作。与该POI交互时，系统会记录玩家的状态，刷新地图时会将玩家位置重置到最近一次使用的存档点处。在魂系列里，被称作“篝火”；仁王系列为“神社”；血源诅咒为“提灯”；帕斯卡为“祭坛”。初始点由于其在整个关卡中的重要地位，会被自动划分成一个开放区域。在我们的绘图中，用橙色圆圈标出。

5.初始点(Point Of Start)

开放区域的一种，玩家第一次进入该地图关卡所处的位置，一般来讲此处的POI是篝火(存档点)。初始点由于其在整个关卡中的重要地位，会被自动划分成一个开放区域。在我们的绘图中，用蓝色圆圈标出。

6.Boss点(Point Of Boss)

开放区域的一种，POI一般为该关卡区域中最强力的敌人。到达Boss点往往意味着关卡探索的结束。Boss点由于其在整个关卡中的重要地位，会被自动划分成一个开放区域。在我们的绘图中，用红色圆圈标出

7.全连通路径(Undirected Path)

路径的一种，在我们的绘图当中，利用A —— B或A <-> B来表示。这个连线符号，代表A、B两个开放区域之间是完全连通的关系，从A点出发可以无条件进入B点，从B点出发也可以无条件进入A点。

8.单向路(Directed Path)

路径的一种，在我们的绘图当中，用A->B 来表示，从A点出发可以进入B点，但从B点出发不可以进入A点而不经过其他区域。具体例子如：悬崖，可跳跃平台，滑坡(这种是物理意义上跳过去就回不来的路)；或者剧情意义上的单向传送(黑魂猎王之后传送舞娘、帕斯卡艾尔玛剧情战斗、黑魂1黑暗大蛇、血源诅咒被布袋哥抓进未见村等。)

9.单向门(ShortCut)

路径的一种，在我们的绘图当中，以

A—>—B

或

A—)—B

或

A<->B

这三种符号均代表，第一次到达B点时，玩家无法进入A点。但当玩家到达A点开启该单向门之后，A、B两点变为完全连通状态。俗称“捷径”、“近路”。主要表现形式有：单侧可打开的门、可放下的梯子、需要踩动的电梯、可断裂的石碑、可踢倒的大树、需要转动的旋转楼梯等等

10.机关门(Mechanism)

路径的一种，我们标注为

A●——>B

用于表示需要钥匙、特殊机关、等级锁、剧情锁等才能从A点开启的通向B点的路径。尽管同样在第一次到达B点时无法进入A点，但与单向门不同，A点亦是到达不了的，也无从谈起从A点反向到达B点。玩家需要在B点之前的区域探索、成长，直到满足某一需求(找到钥匙、特殊机关；升级到足够的等级、做了特殊任务等)，才能从B点进入A点。举例：黑魂1拿王器开金色大门；血源诅咒治愈教会上层、未见村后侧、通向禁忌森林的大门；魂3大书库大门、法兰要塞大门；仁王地图的等级锁；帕斯卡赐福之地四神柱等。

在我们后续的讨论中，称初始点、存档点、Boss点为“不动点”，单向门、单向路、机关门称为“不动键”或“特殊键”。(至于为何如此称呼请见下文)。

鉴于84张地图数量实在太多，无法每一张都详细展示说明。我们将绘制出的地图逻辑图全部附在附录“类魂关卡自然逻辑图一览”里面。(流泪了，鬼知道这么多张地图，我们这个只有两个人的研究团队，为了确定每一处最细小的悬崖，到底进游戏跑了多少遍地图才勉强画完，这种dirty work尽管收益很低，耗费时间最多，但又不得不做的，人都麻了。笔者按)

笔者特别精心挑择了如下三张地图：《仁王1》恶鬼栖息之岛、《黑魂3》幽邃教堂、《帕斯卡契约》伊瑟流姆，进行实例性的解说，讲述如何将从空间结构变换为逻辑的结构。

Step1：选取POI，对POI进行圆覆盖

我们引用同好手绘的《仁王1》恶鬼栖息之岛攻略地图[13]


对于恶鬼栖息之岛这张地图，一个比较理想的选取POI的方法，就是取木灵(对没有玩过仁王的读者：一种可以给主角加强力Buff的特殊收集要素)、场景中的水桶(对没有玩过仁王的读者：可以灭掉场中不可进入的火区，相当于钥匙)、以及开启宅门的钥匙。

接下来，我们要用一个圆去覆盖各个我们选中的POI，并且我们要求逐渐的去“吹大”(For Expert:双连续映射)这个圆，直到发生下述三种情况之一时，我们才停止扩张这个圆：

1.如果继续扩大圆的半径，会导致包含进圆内的点与圆心之间不存在一条通路(这条保证了圆内各点都是同一“开放区域”)

2.如果圆周接触了某个地图上的特殊键(这条保证所有特殊键都能被画出

3.该圆与其他圆相切(这条保证各个“开放区域”相互独立)

选取POI，并不是完全随意的，这个不随意性就在于，我们进行了圆覆盖之后的这张图，必须满足这个条件：

所有特殊键都已经落在覆盖地图的任一个圆的圆周上。

此时，我们称这个圆覆盖是“合法(Legal)”的。

对于恶鬼栖息之岛这张图而言，我们得到的圆覆盖如下图所示：


这样，按照我们对“开放区域”的定义“在关卡中，由一簇POI所框定的一块可探索区域”，就这样被划分好了。

Step2：依照各个开放区域之间的连通关系，将他们顺次连接

这一步没什么好细讲的，按照我们之前的全连通路径、单向路、单向门、机关门四种连通形式去连接就好了，对恶鬼栖息之岛，得到如下结果


Step3：将开放区域抽象成点、各区域之间连通性质抽象成键，从地图背景上取下，整理绘制出该关卡的“自然逻辑图”


这样，《仁王》恶鬼栖息之岛关卡的自然逻辑图就画好了。

依照同样的原理，我们可以绘制《黑魂3》幽邃教堂的关卡自然逻辑图。[14]


依次画出连通路径，有


整理得到


类似的，对于《帕斯卡契约》伊瑟流姆，引用同好的手绘地图[15]，我们有


用四种连通关系连接各个开放区域


整理得到伊瑟流姆自然逻辑图


到这里，其实我们已经可以开始“玩”这些绘制出来的结构图了，我们将这三幅图片并排放在一起。


不知道读者是否有一种“直感”，就是这三幅地图的结构，看起来有那么一点点不太一样？仁王的地图，点与点之间看起来关系更“分散”一点，帕斯卡契约的则联系的比较“紧密”，而黑魂3的地图则联系的更加“紧密”——甚至有些路径必须交叠着才能画出(For Expert:非平面图)。这是正确的，在4.1节，我们会科普性的介绍图论当中的“连通度”概念，即可确定性的描述这种模糊的感受。

关卡结构图中的最小生成树

那么，我们利用关卡当中的自然元素所构架的“自然逻辑图”已经画好了。作为一个实际的应用，我们不妨利用图论进行初步分析，看看能不能得到一些有趣的结果，顺便引入几个定义。

1.顶(顶点，Vertex)

由图中路径相交之处的点，称之为图的“顶”。


2.键(边，Bond/Edge)

从顶点到顶点的一个对应关系(映射)，称之为“键”。


3.链

由一系列顶和键交错构成的连续路径，称为“链”。


4.环路(圈，circle/loop)

首尾重合且各顶相异的链，称之为“环”


5.子图



6.连通与连通图

对于一张图G，取其中两顶 u,v 。若图G中存在以 u,v 为起点与终点的一条链，则称 u,v 连通。

若图G中任意两个顶均连通，则称图G为连通图


7.最小生成树

最小生成树就是该图的所有包含所有顶点的子图中键数最低的连通子图。


易证最小生成树有如下性质：

• 最小生成树当中不存在环
• 在最小生成树中添加一条边会构成环
  

对于我们手中已有的“自然逻辑图”，一个自然的想法就是，通过依次找出环路，然后剔除环路中的某一根键，不断进行下去，就可以得到最小生成树了。主要的问题就显露出来：是哪一根键这么“幸运”，需要被剔除呢？或者，更细致一点的问——一个环路当中，哪根键最特殊，会被认为是用于“形成环路”(下简称“成环”)的键呢 ？这我们需要仔细分析四种键的作用。

1.全连通路径

两侧均连通的路径，最普通的双向路，很难想象有什么特殊之处。我们不认为任何一条全连通路会起到成环作用。

2.单向门

捷径，专为成环而生的键，构建起整个地图回溯式探索的主要结构组成。成环优先度最高。

3.单向路

单侧连通的路径。单向路通常以跳点的形式体现，部分是为了成环，部分是为了去往下一个区域。对此，我们不妨做这样的认定：当一个环路里，不存在单向门时，单向路才负责成环。也即单向路的成环优先度是第二位的。

4.机关门

通常意义上来讲，机关门是用于锁住新区域，而非在旧区域内成环，有很多极端的例子，甚至于打开机关门之后，只有一个藏有宝箱的小房间。但是例外依然是有的(《仁王》佐贺山的武士，某一面机关门)，因此，我们把机关门的成环优先度放在最末一位。

这样，我们就可以安心的书写从自然逻辑图查找最小生成树的方案了。

《关卡逻辑图最小生成树方案》

对于任意环路：

1.若该环路存在单向门，则将全部单向门置为空。

2.若该环路不存在单向门，但存在一个或多个单向路，则统计所有单向路键，将被指向点的层级数(广度优先搜索，BFS意义上的“层级”)最低的那条单向路键置为空。

3.若该环路既不存在单向门也不存在单向路，但存在一个或多个机关门，则统计所有机关门键，将被指向点的层级数最低的那条机关门键置为空。

4.若该环路不存在任何特殊键，则将该环路缩并为一点。

此时可能有读者要问了：“自然逻辑图的最小生成树有什么用呢？”

作为例子，让我们看看黑魂3全游戏流程的自然逻辑图，并且将成环键标灰白色，使图结构成为最小生成树。


仔细观察可以发现，黑魂3的全地图流程的最小生成树，事实上有两条“枝”(For Expert:最长链和极长链)。


第一条很长，从火祭场开始，经由洛城高墙、不死聚落、磔罚森林、法兰要塞、地下墓地、伊鲁席尔、亚诺尔隆德直到最深处的地下——罪业之都结束。

另一条相对较短，起自火祭场，经过洛城高墙、洛城、进入妖王庭院截止。

(以及后续的无火祭祀场，但是这个无火祭祀场比较复杂，所以没写。事实上，解包游戏的结果显示，无火祭祀场和传火祭祀场其实是同一张图，只不过从不同的位置进入时，加载的天空球和敌人配置会不一样。

这两条路是什么呢？熟悉黑魂3的玩家可能很快就看出来了——这两条路分别对应两种设计师设计好的“游戏流程”。

第一条路，从高墙出发，击杀Boss冰狗下到高墙下方探索，猎王回来之后，再回到小环旗老婆婆处，击杀Boss舞娘，登上洛城。这一路是标准的魂3普通玩家的游戏流程。

另一条路，从高墙出发，直接击杀强力Boss舞娘，登上洛城。玩家只要能打过强力Boss舞娘，就可以在前期拿到后期的武器、装备、强化道具等。这一条路恰是留给高端玩家，速通黑魂3的流程。

也就是说，一个关卡的“自然逻辑图的最小生成树”事实上反映了设计者的设计意图，即设计者对玩家游玩流程的把控程度。

一个游戏、或者一张关卡，设计者留给玩家有几种游戏流程的选择，恰恰就蕴含在该图结构的最小生成树里。也就是说，从策划的视角来看，分析图结构的最小生成树，可以用于解析设计者的原本意图，快速写出的反推案。从玩家的视角，对于高端速通玩家或者想快速跑周目的普通玩家而言，列出图结构的最小生成树，也可以高效的帮助我们理顺游戏的必要流程，对于游戏攻略更加得心应手。

类似的我们来分析帕斯卡的地图“伊瑟流姆”。


同样的，我们也把最小生成树的几条极长的“枝”画出来。


可以看到，最长的枝(最长链)是放逐之径、水边塔二层、大树洞、教堂后门、教堂一层、水潭石山、遗物这一枝。这应该是设计者对玩家游玩流程的一个总体预规划。

另一条极长链，从放逐之径到无头骑士，这条比较特殊。仔细观察，整个地图当中的四条捷径，竟然全都指向这个红色圆圈内的区域，恰恰说明，这个区域是整个地图的连接核心，一条“中轴”。

此外，还有三条小的环路露出来的游离在外的键(For Expertangling Bond，自由键)。

三条分别是：水边塔和大树洞之间，设计者制作了一个小区域的分叉结构；从教堂后门爬上教堂二层，再二连跳进入教堂内部；水潭与石山附近，有一个小路通向卖不存在之靴(致没玩过帕斯卡契约的读者：一种跑图用的强力道具。)，再迅速回到主干道路上。

由上述推断，我们得到伊瑟流姆的设计意图应该是这样的：以放逐之径——无头骑士一线作为桥接整个地图的主轴，水边塔、大树洞、教堂、水潭石山等主要探索区域为旁支，每个旁支区域探索结束的位置，设计捷径将他们连回主轴，构成回路。为了增加趣味性和探索的难度，设计者又增补了三处小环路，用于隐藏主干道路、放置强力宝物以及扩大开放式探索区域。

以上就是笔者对于帕斯卡“伊瑟流姆”地图设计思路的一个试探性分析。我们直接去审视伊瑟流姆的原地图，它的几何结构也恰如我们所分析的那样。


可以明显的看到，水边塔、大树洞、教堂、水潭石山四个主要探索区域“恰巧”集中于一条绿色直线上——我们很难相信这不是来自于设计者精心构思的结果。

而放逐之径——无头骑士一线是一条长的、双向连通的路径，我们用暗红色直线标出，几乎平行贯穿整条地图。四个右侧的探索区域，每个区域探索结束的位置都会尽量拉出一条捷径，与主轴放逐之径——无头骑士一线相连，构成闭合回路。与我们对最小生成树的分析结果不谋而合。

最简逻辑图

本小节将是本文整套理论的最核心内容，这就是比关卡的“自然逻辑图”更进一步抽象的“最简逻辑图”的提出。

“最简逻辑图”并非空中楼阁，而是我们在使用“自然逻辑图”的过程中遇到了问题，才会冒出改进“自然逻辑图”的想法。

这个问题就是“自然逻辑图”的非唯一性。

我简单的举个例子，对于如下图所示的一张地图局部，我们画出来的自然逻辑图应该是什么样呢？


很遗憾的，随着我们选取POI的不同，这同样的空间几何结构，至少可以找出三种“自然逻辑图”的画法。


上述反例对于我们的理论来说，是巨大的缺陷。因为倘若同样的地图可以拥有不尽相同的图结构(For Expert:也就是讲，从几何空间到逻辑空间的双连续映射无法构成)，我们就无法进行定量的解析分析，那么找出类魂游戏关卡设计的一般规律就是无从谈起。

为了解决这一问题，我们必须寻找一种“既约规则”——这种规则可以对已有的“自然逻辑图”进一步简化，得到更抽象的“最简逻辑图”。我们希望各个地图关卡的原图仅能对应一张最简逻辑图(For Expert:满射)。

为了良好的定义这套化简的既约规则，我们需要再次引入新的概念：

1.度(Degree)

对于每个顶点，我们定义与之相关联的键的数目为该点的“度”或叫“度数”。


2.极小环

在平面图当中，极小环有着非常明确的几何意义——我们按照某一个固定的“手性”定则(譬如，我们知道，在走迷宫时，会有“左手定则”或“右手定则”，即遇见所有岔路口都固定向左手/右手方向转弯，最后一定可以走出迷宫)，绕着一张图一直走，直到回到原点。形成一条环路，这时候得到的环就是极小环。


更一般的对于非平面图，有极小环定义：对于图G，取一组它的环结构的集合。我们要求该集合中所有环的顶点和键必须覆盖原图G的所有顶和键。若该集合中任意两环结构不相同，且相互独立。则称该集合中所有环结构为该图G的极小环。我们也称“极小环”为“基环”，即，拆解一个图结构的“基矢量”

3.极大环

对一张图G所有极小环做模2加法(什么叫模2加法呢？就是说，如果两个环叠加形成新的图。如果只有一个环有对应边，则画上对应边；如果两条边重合在一起，则该边变成空置状态。你也可以称之为“异或”加法，只有两个输入值相异的时候，结果为1。输入值相同则为0。)，此时得到的环结构称为图的极大环。



4.邻边

两个极小环的公共键，我们称之为邻边

5.不动点(Fixed-Point)

无论如何绘制自然逻辑图，其个数都不会发生变化的顶。在分析类魂关卡时，就体现为初始点、存档点和Boss点。

6.不动键

无论如何绘制自然逻辑图，其个数都不会发生变化的键。在分析类魂关卡时，就体现为单向路、单向门和机关门。

7.缩并(Contraction)

将与同一顶相邻两相同键合并为同一键的操作，称为键的缩并。


8.同伦(Homotopic)

这个概念很重要——它就是我们从“自然逻辑图”变换到“最简逻辑图”时的数学表述。\par

定义：我们称两结构X和Y同伦，等价于当且仅当存在结构Z，该结构属于X、Y的一个公共子结构，且可以分别由X、Y在连续的形变收缩下得到。


9.同构(Isomorphism)

这个概念也很重要，在图论中，只要一个线性变换T是可逆的，那么这个线性变换T就称之为同构变换

简单意义上去理解，两个图同构，意味着两张图只是单纯的重命名(Rename)了顶，或者重排列(Rearrange)了键的位置，两张图本质上依然是同一张图。


如图所示，左侧和右侧的两个图结构是同构的，重命名并重排列各个顶之后，两张图本质上相同

10.无向图与有向图

键为有方向的图称作有向图。键无法分辨方向性的图称作无向图。


11.弱连通图与强连通图

在有向图G中，如果两个顶点 u,v 间存在一条 u->v 的有向路径，和 u->v的有向路径，则称两个顶点强连通(Strongly Connected)。如果有向图G的任两个顶点都强连通，称G是一个强连通图。

将有向图的所有的有向边替换为无向边，若该图是连通图，则有向图是弱连通(Weakly Connected)的图。


图中存在4—2的有向路径，但不存在2—4的有向路径，因此不是强连通图。若将此图无向化，可以形成环结构，显然有该图为弱连通

12.n顶环

一个具有n个顶的环路，称之为n顶环。


13.自由键(Dangling Bond，悬空键）

对于图中任一长链，其中除了首尾之外，其余顶点的度数为2，首尾任一点的度数为1，则称该长链上的任一条键为“自由键”。


我们摆出的一张自然逻辑图，本图为《帕斯卡契约》的地图阿达米亚。不难发现，其实整张自然逻辑图里有许多“冗余”的全连通键。我们的最简逻辑图正是要删掉这些不构成环的键或者构成了全连通的“伪环”。


我们需要一个完备的缩并键的规则集合，为此，我们要再回溯性的讨论四种键的各种组合。

首先考虑我们的“成环”判据。显然的，我们做出的自然逻辑图不是简单的无向图，甚至也不是简单的有向图——“捷径”这种线型结构，事实上在整个图论中就没出现过，但不妨我们类比着去研究。作为一种合理的近似，我们在判断一个回路结构是否“成环”的时候，不妨只讨论弱连通性下的成环，不要求强连通性的成环。

这种近似的，我们试图在谈论的是一张地图的整体结构。对于设计者来讲，是一种“顶层设计”；对于玩家来讲，仅当地图探索完成之后，整张地图的结构才在玩家的脑海里建构起来。捷径这种结构显然是有向的，但在地图探索结束、全部捷径被开启之后，这种有向就变成了无向。正因为如此，我们认为在探讨地图探索结束时才能完整显露的关卡结构时，只考虑弱连通性成环是合理的。

接下来看我们对环结构顶点的要求。一个成环的结构至少需要几个顶？答案似乎是三个，因为平面上最简单的多边形是三角形，它具有三个顶。

但事实上，两顶环和单顶环也是可以存在的，只不过比较少见——在地图当中，他们大多以藏于主路径边缘的小宝箱、小宝物或其他奖励性的收集要素的形式出现，一个合理的理解是，他们并不会参与主路径的成环构建。所以，我们的主目标还是要尽量将一张图里所有的极小环向三顶环那个方向去缩并。

另一方面，我们必须禁止两顶环，但是可以允许单顶环少量存在。——可能有人不好理解，为什么三顶以上都能允许，单顶也被允许，偏偏两顶就被pass了？这个是因为两顶环会导致一个很离谱的问题。假设点A与点B形成一个两顶环，那么从A到B的关系会有两种(For Export:这是一个双射，在我们写图结构的邻接矩阵时，A、B两点间关系对应的矩阵元同时存在两个数值，就没办法研究了。)无论是三顶以上的环，还是单顶环，任两个相邻点之间的关系都是唯一的(单顶环可以理解为A——A的一个连接，相当于自己映射自己)

这就是我们必须禁止两顶环的理由。


总结一下，我们的策略为“尽量三顶环，禁止两顶环，允许单顶环”，这是我们对最简逻辑图成环结构的顶数的要求。

下面我们考虑对键的性质的要求，全连通键肯定是尽量全部缩并掉，因为全连通键对成环只起到辅助作用，真正的成环一定要看不动键。

对于不动键，其实部分不动键依然有所冗余。譬如某条极小环里有多条单向路，这说明我们是连续多次跳悬崖到达了某个地方，尽管有多条单向路，但只有最后一条才实际起到了成环的作用。我们不妨将连续多条的同类型同向的单向路缩并为一条单向路，这样可以大大简化结构。

最后我们再分析一下自由键的问题。自由键的表述为：一长链，其中除了首尾之外，其余顶点的度数为2，首尾任一点的度数为1，则称该长链上的任一条键为“自由键”。

这样的结构显然是不能成环的。它在地图中，往往以：通向Boss的道路；探索途中的宝箱或特殊道具；特殊的NPC支线任务等形式出现。

既然已经确定了这些建都无法参与成环，为了分析的简洁性，不妨将这些键全部缩并掉。

最简缩并既约规则


部分读者可能看这些规则有些眼晕了。我们在这里拿出一些具体例子来

下面演示黑魂3的关卡：洛斯里克高墙。我们给出洛城高墙的自然逻辑图如下。


首先，根据既约规则4，图中存在5条自由键——离塔篝火、吸魂鬼支线、小偷支线以及两个Boss冰狗和舞娘。

作为第一步，我们将这五条键缩并为一点，命名规则按照规则3，得到


此时，可以看到图结构的极大环已经不存在重边了。

仔细观察上图，可以发现，图结构当中存在4个极小环。同时，极小环与极大环的邻边当中，有如下图所示的两条长链具有多条“冗余”的全连通键。


再注意到图结构中存在高墙一火、离塔篝火、Boss点三个不动点。根据既约规则5，一个简单的缩并思