魂系列恶魔城和开放世界—关卡结构理论和非线性流程设计浅析上黑暗之魂游戏boss

本文引用关卡结构拓扑理论,使用数学方法对关卡结构的设计做出评价和指导,并通过不同游戏的案例分析阐述了理论的可行性、应用场景和局限性。在此基础上,将研究范围从静态结构延伸到动态流程的设计中,提出了一种指导和辅助流程设计的方法思路。

一、引言及背景

相信玩过魂系列(《恶魔之魂》、《黑暗之魂》系列,《血源诅咒》、《只狼》)及其他类魂作品的玩家能够深切感受到,有别于《美国末日》等线性流程的作品,魂类游戏往往缺乏相对明确的目标指引(地图的目标点、HUD的行动指示等),关卡和流程设计也绝非线性,因此初玩时面对凶险的战斗和复杂的关卡(以及不死人僵硬的动作)容易觉得无所适从甚至因此弃游;而一旦克服初见的恐惧和不适心理,耐心深入游玩下来,又往往被其精巧的关卡设计和晦涩的叙事风格所吸引,成为系列的爱好者,对其中的各类细节津津乐道,忍不住向周围的朋友安利,将其奉为心目中的“高势能产品”。

这类以地图探索为主要流程体验的游戏,细细品来与古早的《恶魔城》系列有异曲同工之妙,因此又有人把“类魂”游戏称为“3D银河恶魔城”游戏[1]。而从另一侧来说,近年来,随着“魂系列”影响力的扩大,许多优秀的类银河恶魔城作品,也被玩家打上了“类魂系列”的标签。这充分说明,魂系列与恶魔城这两类游戏即便视角完全不同,在流程体验上也是具有一定共性的。

Steam平台“类魂系列”标签最受欢迎游戏top10,可以看到其中的《空洞骑士》、《盐和避难所》、《终焉的莉莉丝》都是以地图探索为主要内容的类银河恶魔城游戏。说明这两个品类的游戏在玩家心目中的印象是具有一定共性的。

需要明确的是,本文只是以魂系列/恶魔城游戏为例,尝试归纳总结其风格化体验背后的关卡和流程设计的科学原理,将其归纳为“一种对应特定品类和体验”的设计方法,并无意表达“魂的、非线性的”体验流程就一定优于“不魂的、线性的”体验流程这样的暴论。游戏作为一种综合产品,其品质与体验受到系统、战斗、玩法、美术、叙事等多个维度的影响,关卡与流程设计只是玩法其中的一个维度,而“魂”或者“不魂”更只是关卡与流程设计中的不同思路方向:线性流程的游戏一样能够做得非常出色,同样的,非线性流程的游戏也不乏粪作。希望读者大大们能够理性看待,避免先入为主、踩一捧一的观念。

二、体验层次划分

回到背景中提出的问题,“魂味”是什么?“开放世界”与魂在流程上的体验共性和设计方法又是什么?要回答这两个问题,笔者首先对此类游戏给玩家带来的体验做一个层次上的划分。

尽管作为一种主观感受,游戏的“体验”对每个玩家个体来说都是千差万别的,但对于魂系列/恶魔城这类以地图探索作为游玩内容的游戏,归纳而言可以大致将其体验从“微观”到“宏观”划分为三个层次:

那么,“魂味”究竟是如何渗透到每个体验层次的呢?

从第一层体验的角度来看,“魂味”往往体现在一些系统和战斗的设计上,这些设计又是相互耦合、相辅相成的,共同构成了所谓的“魂味”感受。

举个简单的例子:战斗系统的精力、硬直和韧性设计,导致玩家同时面对多个敌人的作战极为困难,而作战类的开放区域往往远近前后安排了不同类型的小怪,需要玩家在游戏给定的数值养成系统内对有限的资源使用做出策略上的选择;数值收集和成长结合“死亡掉魂跑尸”的设计,又能够复用相同的关卡内容创造出截然不同的心流体验....如此种种不一而足。许多游戏也因为这些机制的存在,而被玩家们打上“类魂”的标签。

所谓“魂味”,在关卡逻辑方面,意指地图中存在优秀的、丰富的、多层次的环路结构。

——这三个形容词一个都不能少,环结构的链不能太冗余,否则就不够“优秀”,稳定度差。数目太少也不行,但是只堆数目也不行。环结构大的层次(高阶Cheeger数),表现为首尾至少要相连,极大环才不会出现驻点。要有很多细致的层次(高阶Cheeger数也要高)这样才叫一个有“魂味”的关卡。

如何定量描述“魂味”?——我们可以通过计算关卡的稳定因子,来定量化的描述“魂味”的多与少,乃至与其他地图的“魂味”浓度做比较。

简而言之,引文通过观察5款被广泛认可的类魂游戏,定义了一套评价关卡拓扑结构的数学模型,抽象出了“魂味”的评价因子,并经过了相对可靠的验证。本文也将对这个理论进行综述,并选择两款广受好评的游戏作为案例,从几个方面进行拓展,在综述的基础上,进行进一步的解释和分析。

事实上,笔者正是受了此文的启发,惊叹于游戏设计这一看似经验主义的工作能用如此精确的数学语言进行描述,才有了进一步探索研究的动机,也才有此拙文。在此对引文作者尼莫大神深表敬意与感谢。

第三层,也就是整个游戏的流程角度,笔者将基于关卡拓扑结构理论的成果,将分析范围从静态的结构延伸到动态的流程中,探讨这种风格化的体验究竟是如何通过对关卡顺序的组织和流程的设计实现的;同时,尝试将理论延伸到开放世界品类中,以《荒野之息》为例,探讨开放世界游戏是否也能使用类似的方法来对玩家的目标和流程进行引导和控制。

三、关卡拓扑结构理论综述及应用研究

3.1关卡拓扑结构理论综述

3.1.1基本概念定义

为了使用相对严谨的数学工具对“关卡体验”这一看似主观的感受进行定量分析,同时指导“关卡设计”这一看似经验主义的工作,我们首先需要建立一套从现实世界到理论空间的映射规则,对此类游戏的关卡中常见的设计,进行概念与表现形式的定义。

1兴趣点(POI,PointofInterest)

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

——用开放世界游戏来举例的话,《荒野之息》的塔、神庙、山巅,一切能引起玩家注意和好奇的物体,都可以看作是POI。

2开放区域(OpenArea)

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

——原文中,“开放区域”有着严格的定义和几何构造方法,但我们无需在此纠结,只需要带着这个印象:开放区域包含了一个或一组POI,内部是自由连通的,且相互之间依靠不含POI的路径相连接。

3路径(Path)

用于连接各个开放区域的线型结构,一般不含有POI。

——像是《荒野之息》中路边随处可见的蘑菇、苹果等可收集物,很遗憾便不能算作“POI”的范畴了;当然像是“一大片苹果林”这种,或是在“我正好急需几朵速速蘑菇来做任务”的情况下,则又另当别论了。究其根本,POI的定义核心仍然是玩家自身的“Interest”,因此尤其是在开放世界游戏中,POI的定义边界会随着玩家的心境和目的的改变随时变化。

4存档点

一种特殊的POI,玩家可以在此处进行休整、升级、传送、回复、备战等操作。通常而言整备操作会导致地图的刷新与怪物的重置。举例而言,魂系列的篝火、仁王的神社、血源的提灯、只狼的鬼佛等。由于存档点在关卡中的重要地位,在分析中会被单独划分为一个开放区域。

——出于机制、美术、叙事等方面的考量,不同游戏会有一些特殊设计,例如《黑暗之魂》、《空洞骑士》、《盐和避难所》都采用了大小存档点的设计,小存档点(小篝火、不带车站的椅子、小祭坛)往往只具有休整回复的功能,而无法进行传送等操作。这类“小篝火”的设计实际上是对关卡结构的一种补偿。

5初始点

玩家第一次进入关卡所处的位置,通常标记关卡的开始,单独划分为一个开放区域。

6Boss点

通常为该关卡区域最强力的敌人,到达并通过Boss点意味着关卡的结束和进入下一个关卡,单独划分为一个开放区域。

——在广义的魂系列/恶魔城游戏中,Boss战因其玩法上的特殊地位,往往还被视为关卡探索的“奖励”,不仅仅由于击败Boss能够获取大量资源或是解锁新的探索内容,还因为设计优秀的Boss战本身就宛如艺术品一般令人爱不释手:在紧张的气氛和华丽的演出中反复挑战、学习成长,成就感和挫败感不断累积、相互侵轧带来的心流体验在击败Boss的一刻达到峰值。这一点想必喜爱《只狼》的玩家们一定深有体会。

——回到概念定义上来,开放世界中,初始点和Boss点的功能定位有所不同,一般不存在“初始点”,而“世界Boss点”通常作为一个POI或是开放区域存在,且不会标记关卡的结束。

7全连通路径(UndirectedPath)

代表两个点之间是完全连通的关系,可以无条件相互前往。

8单向路(DirectedPath)

用单向箭头A---->B来表示,代表从A点可以进入B点,但B点无法原路直接返回A点而不经过其他开放区域,包括物理意义上的单向路(悬崖、滑坡)或是剧情意义上的单向传送(血源被布袋哥带到亚哈古尔、魂3灭薪王之后传送舞娘等)

9单向门(ShortCut)

或是常说的“捷径”,用A-->--B或是粗箭头来表示,代表玩家首次从其他路径到达B点时,无法从B点进入A点,但当玩家首次从其他路径到达A点时,可以建立起A、B之间的全连通路径,使两点之间永远变成全连通状态。主要表现形式有:“这一侧打不开”的门,“机关不会动”的电梯、可以放下的梯子、需要踢倒变成桥的大树等等。

10机关门(Mechanism)

用带端点的单向箭头A*-->B表示,表示玩家第一次到达A点时无法经由该路径到达B点,需要满足一定条件后(收集到特定物品、满足一定要求等)才能打开此路径使AB变为全连通状态。B点可以是单独的一个带锁宝箱、一间密室,也可以是一整块区域甚至后续所有的游戏流程的唯一起点。最常见的即为物理意义上的“带锁的门与钥匙”,其他意义上例如“需要13颗心心才能拔出大师剑”或是“需要佩戴深渊戒指才能进入深渊”、“需要收集到诡异人偶才能进入绘画世界”也属于此范畴。

——不同于单向路和单向门主要服务于关卡体验,机关门是控制周目流程和游玩体验的核心工具,这也是本文将会重点分析的内容。后续讨论为了表述方便,也会称机关门为“锁”,称“打开机关门的条件”为“钥匙”。

——单向门与机关门的核心区别在于:玩家一定是先见到单向门的“打不开的一侧”,然后才到达门的“打得开的一侧”来“把门打开”;换言之,假设笔者位于门的外侧,如果玩家能在此门打开之前从其他路径接触到这个门的另一侧,则这个门属于单向门,反之则属于机关门。

为了方便后文的表述,开放区域作为游戏内容的主要独立载体,抽象到关卡结构逻辑图上被称为“点”或“顶”,其中初始点、存档点/传送点、Boss点因其在流程中的特殊地位,被称为“不动点”,也就是“因为特殊所以在简化关卡逻辑结构表示的时候最好不要随便动的点”;四种路径连通形式,抽象到逻辑图上又可以被称为“键”,同理单向路、单向门、机关门又被称为“不动键”。

3.1.2理论内容综述

在明确了概念定义、表现形式和映射关系的基础上,尼莫大神在引文中选择图论这一数学工具,对关卡结构进行分析,总结了一套基于关卡拓扑结构的设计理论,本文在这里对其具体内容进行简要综述。(略去了所有复杂的数学理论推导过程,感兴趣的读者可以直奔原文细细研读):

1自然逻辑图

用点来表示不同的开放区域,用四种类型的键将开放区域按照关卡内的自然关系连接起来形成的结构图;通常能够直观表示关卡的自然逻辑结构

2最简逻辑图

依照最简缩并既约规则,在同伦变换唯一性的理论基础下,对自然逻辑图的一些点键进行缩并得到的最简图;同一关卡的最简逻辑图有且只有一个

——从自然逻辑图构建最简逻辑图的方法可以大致概括为:“将非不动键连接的两个非不动点、或一个不动点与一个非不动点缩并成一个点;不动点之间不可缩并;不可形成二顶环”。最简逻辑图能够清晰表示出关卡内部路径的成环逻辑和依赖关系,省去了非成环键对图结构的干扰,对“缩并规则”和“唯一性”感到困惑的朋友可以参考原文的详细定义和操作步骤。

3最小生成树

在逻辑图的基础上,隐去成环键,将全连通环缩并为一点,可以得到关卡结构图的最小生成树。选择成环键的优先级简单来说可以概括为单向门>单向路>机关门。

——理想情况下,最小生成树能够直观展示关卡的流程:其中最长的“树干”是关卡的主线流程,“树枝”则是支线流程。最小生成树不含任何环,且向其中添加任意键都会导致环的产生。

——原本不愿在本文多谈系统层面的设计,但为了防止不熟悉魂系列的朋友带着疑问阅读,这里单独解释一下为何“单向门”的地位如此之高:

在本格魂系列游戏中,玩家在探索过程中击败敌人的时候会获得并累积一种名为“魂”的核心资源,无论是自身数值成长还是购买任何道具都需要消耗魂作为硬通货,简而言之是游戏中的唯一货币;

魂只有到达存档点才能被使用掉,探索过程中不存在使用魂的途径;

一旦玩家死亡,玩家携带的所有魂就会掉落在死亡处附近,形成一个印记(《血源》是附着在附近的怪物身上,同理),玩家会在最近的存档点(篝火)处复活,并且需要回到死亡处拾取印记(血源则是消灭对应怪物特定百分比血量),才能将掉落的魂重新获得,也就是所谓的“捡魂”;

一旦掉落的魂尚未被拾回而玩家再次死亡,玩家的死亡印记将被覆盖刷新,上次死亡遗失的所有魂将永久失去,也就是俗称的“丢魂”;

基于其战斗系统和场景设计的特点,玩家在探索地图及跑图捡魂的过程中,都需要保持高度警惕,否则死亡是家常便饭的事情(“死亡是游戏的一部分”);

单向门通常是抵达存档点的反向捷径,能够打开的单向门意味着经过了漫长艰苦的探索过程后,已经离存档点不远了。

综上,相信即便没玩过魂系列的读者,也能够想象魂系列玩家经过了漫长艰苦的地图探索、怀揣一笔巨款时,发现并打开单向门的心流体验。

此外,此类游戏的Boss往往在设计之初便是“需要玩家反复挑战才能攻破”的设定,因此在尽可能保证关卡结构简洁的前提下,单向门成为了探索流程结束、从存档点迅速抵达Boss处反复挑战的快速通道,避免玩家在多次挑战Boss时反复穿越已经完成的探索部分。

多说一句:“捡魂”这一设计的缺失,是笔者认为《只狼》在系统层面不具有“魂味”的核心原因;而“Boss人手门口杵一尊鬼佛”这样的设计则代表其基本放弃了地图探索这一体验而是专注于战斗玩法。

4连通度

对于一张图,如果任意去掉k-1个点,剩下的子图仍然是连通图,且存在至少一种取法,在去掉k个点之后,剩下的子图是非连通图,则称该图的连通度为k

——“连通”是图的一种性质,意味着从图上的任意一点出发,能够沿着路径到达图上的任意另一点。拿掉就能够破坏图连通性的k个点称作图的k阶“驻点(对)”。

5Cheeger数

对于一张m点的图,若存在n种取法,使得删掉其中k个点之后的子图是非连通图,则称该图的k阶Cheeger数为1-n/Comb(m,k);

——概括而言,k阶Cheeger数指的是在所有拿掉k个点的取法中,仍然保持图连通的取法的占比,反映了这张图在拿掉k个点的情况下仍然保持连通的能力。

6稳定因子(魂味值)

无穷阶Cheeger数的泰勒级数和。鉴于高阶Cheeger数收敛得非常快,通常只取其三阶微扰来评价关卡结构,即定义一个关卡的最简逻辑图G,其1、2、3阶Cheeger数分别为a、b、c,则该关卡的稳定因子为3/5*(a+1/2*b+1/6*c)。

——后文均用“稳定因子”这一称呼指代“真正的稳定因子的三阶微扰”。稳定因子能够表示关卡“总体而言环路结构的稳定性和层次性”。不了解什么是泰勒级数和微扰的朋友只需要记住结论和上面的计算公式即可。

7稳定因子普适类(魂味区间)

对于一个关卡而言,大于0.94意味着高稳定因子(魂味最正)、0.94到0.91之间意味着中稳定因子(魂味尚可)、小于0.91意味着低稳定因子(魂味不照)

这套理论不仅适用于关卡维度的分析,也可以用来分析第三层也就是整个游戏周目流程的结构。例如《黑暗之魂重制版》全流程的稳定因子为0.9806,关卡塞恩古城为0.9636;《血源诅咒》全流程0.9086,关卡亚楠0.9794;《黑暗之魂3》全流程0.9050,关卡绘画世界(DLC1)0.9733,关卡大书库0.9691。不难看出,塞恩古城、绘画世界、大书库这样给人留下深刻印象的关卡,其稳定因子相当之高;但也能看出来,想要在游戏全流程保持“魂味”的环路结构是非常困难的,即便是血源和魂3这样的“魂本家”作品,在拥有多个高稳定因子关卡的同时,其全流程的稳定因子与魂1相比还是远远不及。(魂1什么历史地位不用多说了)(具体数据指标绝对值由于引文未公开计算过程,与笔者实际计算结果部分不一致导致存疑,实例详见后文,但指标之间的相对关系还是有参考意义的)

注意:此处抛开所有其他元素,仅仅评价关卡逻辑结构这一个维度的“魂味”,事实上“魂味”作为一种整体的体验和感受,还会受到战斗、美术、叙事等多个维度元素的影响,绝不能用单一的指标去完全概括。一个明显的反例是,一代的病村、亚诺尔隆德这样稳定因子相对偏低的地图,依然能够在玩家心目中留下深刻的印象甚至收获较高的评价。这是由于这些地图并非主要承载探索玩法的内容,而更多地为叙事、美术表达和氛围营造来服务。因此,希望读者把上述理论只是当作一种辅助看待关卡设计的工具,而绝非评价任何关卡或游戏的唯一标尺。(为我心爱的魂3挽一挽尊)

下面,笔者将选择《空洞骑士》和《只狼》两款游戏,对其关卡拓扑结构进行分析,并结合实际游戏体验,对该理论的有效性、应用范围与局限性做出具体阐述。其中《空洞骑士》作为一款典型的恶魔城游戏,非常适合用来验证该理论在评价恶魔城/魂系列关卡设计的有效性;而《只狼》作为一款受到争议的、在笔者心目中不具备“魂系列”关卡结构特点的FromSoftware游戏,则被用来说明该理论在“非魂系列关卡”设计领域的应用价值及其评价指标存在的局限性。

为什么不选魂本家或是《帕斯卡契约》、《仁王》这样的游戏呢?原因很简单,引文已经全部做完了,感兴趣的朋友可以移步查看。至于魂2,我没打完。

3.2理论应用——以《空洞骑士》为例

《空洞骑士》是一款笔者非常喜欢的,由来自澳洲的独立工作室TeamCherry开发的银河恶魔城风格的游戏,其战斗、关卡、叙事和美术设计都非常优秀,受到了类型爱好者的一致好评,在Steam“类魂系列”标签分类下的受欢迎程度甚至超越了《黑暗之魂》的本家正作。(双品类好评之王的含金量懂不懂啊)

同时,这款游戏也是笔者认为,当下少有的在关卡设计层面走到极致的作品。对比同时期其他同类作品(《盐和避难所》、《Ori》、《暗影火炬城》、《渎神》、《终焉的莉莉丝》)不约而同地把美术风格作为恶魔城品类的突破口,笔者认为从关卡出发的设计更加难能可贵、值得策划学习。

3.2.1游戏内容到理论空间的映射

为了使用关卡拓扑结构理论对其关卡设计进行分析,笔者首先阐明结构图上的“点”和“键”对应到游戏的映射规则:

1开放区域

由于游戏在机制设置上,把地图分割为了一小块一小块的“房间”,房间之间拥有黑屏的场景切换态,怪物无法通过,因此每个房间天然形成了关卡结构中的开放区域。

椅子(篝火)、车站(传送点)以及关卡Boss默认划分为开放区域。

重要的可收集道具(如生命碎片、灵魂Boss等)在自然逻辑图上也划分为开放区域;除此之外,还有一种开放区域的构建规则:当房间内存在玩家目前能力限制无法进入的区域(机关门)时,机关门后的空间被单独划分为一个开放区域。我们不妨暂且记下此处约定,在下一章中将作为重点分析。

2单向路

大多表现为跳下后使用任何能力都无法原路返回的悬崖,字面意义。在逻辑图上用单向箭头表示。

3单向门

可以反向开通的捷径,在游戏中由于叙事和美术包装,主要有两种形式:可以从背面摧毁支柱的墙(自然环境)以及可以从背面打开的机关门(虫造环境)。为了便于绘图,在逻辑图上用粗箭头表示。

4机关门

必须满足一定条件才能开启的门,在游戏中有非常丰富的表现形式,大多数情况下,挂钩主角在探索过程中获得的各种能力,例如必须学会灵魂冲击(波)才能消灭的堵门怪。在逻辑图上用带端点的箭头表示,并且尽可能在旁边注明需求的能力。

对于这种“能力锁”类型的机关门,我们不妨约定:只有当“拥有此项能力”不是玩家到达该门前的必要条件时,才将其作为不动键标注在自然逻辑图上,否则按全连通处理(对应“开放区域”划分原则的第三条)。相信这不难理解:我如果没有二段跳,遇到一个二段跳才能上去的高台,这对我来说是一个机关门;我如果能到达这个高台下就一定是拥有二段跳的,那这里对我来说就是全连通的,二段跳后面的区域也就可以视情况与前一个开放区域缩并了。

3.2.2什么是魂味——关卡拓扑结构分析及指标计算

应用上述原则,对游戏的第一个正式关卡“遗忘十字路”进行自然逻辑图的绘制如下所示:

请出这张陪伴了所有空洞玩家的全收集地图(局部)做一下对照:

好嘛,大概能对得上。有一些可收集道具在地图上标注了出来,但因为是初次到达就能立刻获得的,或是缩并成所属开放区域的单顶环的附件了,也就不满足机关门的条件,没出现在逻辑图上。

这张逻辑图也回答了笔者一个问题,那就是为什么当笔者安利一位玩魂3的朋友去玩空洞骑士时,他会在叫好的同时,因为迷路而大感困难。不妨拿魂3的第一个正式关卡“洛斯里克高墙”的自然逻辑图[1]对比一下:

不难看出,十字路不仅开放区域的数量远远多于高墙,多度顶点和不动键的个数也更多:在相似的场景下经过更多的的房间,面临着更频繁的岔路口和捷径,还有非常多“前面的区域以后再来探索吧?”的机关门/能力锁(如下图必须要获得水晶冲刺才能进入的通道),也难怪笔者那位朋友会迷路了。

再对比一下两张地图的最简逻辑图。

在对自然逻辑图的点键进行缩并时,我们不妨在最简缩并既约原则上增加这样一条:如果机关门的钥匙能够在本关卡流程内获得(不要求首次到达时,但要求在本关卡流程内,如此要求的依据见下一章分析),则将其按照全连通键处理,同时将这把钥匙标注为不动点;反之则仍然是不动键。同时,对于“打开德特茅斯的车站门”这样形式上创造捷径、逻辑上等同于传送点的单向门,我们也将其缩并到同一个点,便于分析。

在略去和其他地区的通路口(橙色开放区域)之后易得十字路的最简逻辑图如下:

观察十字路的最简逻辑图,可以找到4个极小环结构,相应的,假如我们隐去成环键也就是单向门(捷径),可以得到关卡的最小生成树,也就是对应到玩家的游玩流程:

其中,1号和4号两个三点环,分别分支出“生命碎片”与“商人”两个小的环路区域,对应可收集的关键道具。

玩家的主线流程由2、3两个环共同构成:玩家需要从德村一路向下,经过地图师之后向右穿过十字路下层到达车站处,打开回到十字路上层的捷径并激活存档点,之后前往挑战Boss,并在击败Boss并获得通往下一关的必备能力(波)之后打开另一条捷径,前往关卡的出口。

对比高墙和城外不死镇(魂1的第一个正式关卡)的最简逻辑图并计算拓扑结构指标,可得下表,其中的γ3就是稳定因子。

*细心的读者可能会发现,此处高墙的二、三阶驻点数与引文的计算结果有出入,笔者认为是尼莫大神在计算时出现了偏误。易知如上编号的高墙最简逻辑图二阶驻点对分别为(离塔篝火,飞龙塔),(离塔篝火,1号篝火),(离塔篝火,Boss),(飞龙塔,Boss),(飞龙塔,1号篝火),换言之就是存在这5种取法,使得删去两个点之后,这张图变成非连通图,故二阶驻点对数为5。原文高墙的二阶驻点对数为3,应为偏误。感兴趣的读者可以自行验算一下,笔者也将计算驻点对数、Cheeger数和稳定因子的python算法附在文后供查阅。

通过对比《空洞骑士》、《黑暗之魂3》、《黑暗之魂1》三款游戏的第一个正式关卡,也就是各自的前2小时内容来看,不难发现,在顶数和边数相近的情况下,空的首关稳定因子竟然比魂1魂3都要高,amazing!宫崎老贼跌落神坛!换言之,与洛斯里克高墙和城外不死镇相比,遗忘十字路的关卡设计存在着更优秀、更丰富、更多层次,也就是更有“魂味”的环路结构。而城外不死镇相比高墙更高的稳定因子,意味着从拓扑结构的角度来看,魂1的首个关卡地图相比魂3在环路结构上更为优秀,“魂味”更足,这也符合魂系列老玩家对两作的对比评价。

3.2.3全连通环路——最简逻辑图的局限性与解决思路

当然,上文结论只是基于最简逻辑图而言。既然十字路的最简逻辑图和最小生成树如此的清晰,为什么还会让人迷路呢?为了回答这个问题,我们回到自然逻辑图,可以发现,十字路拥有四层连通的水平结构,但最简逻辑图只体现了三层。十字路上层存在着茫茫多的开放区域,各自之间完全依靠全连通键相连,甚至出现了大规模的全连通环路结构(路口-大厅-米拉环),会给玩家的方向辨认带来一定的困难,而这种体验在最简逻辑图上没有得到体现:因为巨大的全连接环在缩并过程中全部收拢到了一个不动点上。

笔者建议,将米拉-过道处的全连通键改为单向门,在十字路第一、二层的大环路结构增加一道成环键来控制玩家的行动路径,以此构造有向环的同时,将玩家的注意力吸引到第二处成环键也就是笼子捷径附近;并且将龙牙哥-救虫的区域连接到米拉处而非过道处,一方面用对抗精英敌人龙牙哥的战斗来强化此处捷径通路的记忆——一旦玩家在与龙牙哥的战斗中落败,能够从刚刚打开的捷径通路迅速从德特茅斯的存档点返回此处,另一方面把可收集道具——幼虫作为发现捷径的奖励。这样综合下来能够一定程度上改善游戏前期在十字路上层“迷路”的体验。

同时得益于关卡本身优秀的环路结构设计,这样的改动并不会过多地影响关卡的整体结构。画出改动后的最简逻辑图并计算稳定因子,可以发现,改动后的地图结构依然属于中普适类,与改动前相比并未丢失过多的环路结构稳定性。

对修改后的十字路的最小生成树进行观察,可以发现:增加的一个三顶环以米拉线作为分支顶点,将重要的叙事剧情碎片从海量的开放区域中抽出来,作为重要的探索支线加以强调;同时关卡的主线流程和其他分支并未受影响。这正是我们想要的结果。

总结而言,最简逻辑图及其拓扑指标计算,作为校验关卡设计的一种工具,是存在一定局限性的,这是由于其对全连通环路结构的忽视导致的,而大规模全连通环路是关卡流程设计需要规避的要素。

在进行缩并工作之前,设计者需要:

1观察自然逻辑图,确保关卡结构中不存在大规模的全连通环路,在必要时添加成环键,对环路结构进行处理。

2对添加成环键之后的形成的新结构的最简逻辑图计算驻点对数和稳定因子,以此进行校验,确保没有过多地破坏原有环路结构的整体设计。

3.3理论应用——以《只狼》为例

《只狼》这款游戏,相信本文的读者都不会陌生,笔者也就不再过多介绍。作为一款剑戟风格鲜明的作品,尽管其全流程依然遵循着魂系列相似的流程,但具体到关卡层面,《只狼》把战斗体验作为核心内容,地图探索的特性被大大弱化了。本文以这一作为例,尝试通过分析,把关卡结构拓扑理论延伸到“不以地图探索为玩法核心”的游戏中,探讨一款游戏为什么在关卡层面“不具有魂味”,以及在这样的游戏中,理论工具的应用范围和局限性。

3.3.1线性关卡中环路结构的作用分析

沿用上文提到的思路,对《只狼》第一个正式关卡破旧寺院-鬼形部进行结构拆分,可以得到其自然逻辑图和最简逻辑图如下所示。

计算稳定因子的意义已经不大了:明眼人都能看出,这段关卡几乎是完完全全的线性结构,而且除了赤鬼(非邪道)与大蛇两处无法绕过之外,其他地方甚至称得上是鬼佛之间直接相连,遍布在鬼佛周围的战点能够直接被“绕过”而非“润过”,显得非常多余。这不难理解:作为玩家获得忍义手这一新体验道具后的首个关卡,这一段流程承载着相当重要的教学引导任务。大量的勾索点设计让玩家能够使用勾索跳过战点直达鬼佛,正是在强化这一新道具的作用。

这也是《只狼》自发售之初一直到现在,其“魂血统”都有争议的原因之一:相当一部分魂系列的老玩家认为这款游戏的地图设计丢失了“魂味”,也就是失去了优秀的、丰富的、多层次的环路结构。这一点在其前两个小时的游戏流程中体现的尤为充分,带来的刻板印象也根深蒂固。

但这不影响《只狼》成为一款出色的游戏:其优秀的战斗、美术和叙事体验,让这款游戏成为了年度最佳;也借着直播行业的兴起成功出圈,连着带火了制作人宫崎英高的名字和“魂系列”的概念。这也印证了笔者在背景介绍里的观点:游戏整体素质与综合体验取决于多个维度的设计,关卡结构的“魂味”有多重,与游戏的品质甚至整体体验并无直接的关系,玩家依然能够从系统、叙事等维度的设计获得“魂系列”的感受。

当然了,这也并不妨碍我们用最简逻辑图来分析线性流程关卡中环路结构的设计思路,以此来揣摩设计者的意图。

观察图上的三处极小环,一处在打完Boss之后打开角楼的门,为关卡提供了物理意义上的返回通路,保证了空间上的连通——倘若打完Boss只能通过传送点回到之前的区域,那也太不优雅了。环路结构的第一个作用:保证关卡在形式上的完整性。

另两处则围绕着山顶祭奠帮、铁炮山道以及城门道和虎口两个鬼佛之间构建了两道回环。相信玩过的朋友都有印象:沿着山路走城门道-铁炮通路-虎口鬼佛这条路线是极为困难的,城楼的铁炮哥、廊门上的火枪兵以及山路上的蓑衣兵对狼形成了全方位的夹击。但倘若在几次攻坚失败之后,细心观察周围局势,便能发现只要从城门道鬼佛的侧面跃下,就可以沿着勾索点一路潜行到铁炮哥的背后,在战斗开始前首先解决掉这个最棘手的敌人。这也是《只狼》这款游戏使用关卡设计传递给玩家的信号:身为忍者,就不应当直冲蛮干;善用地形要素,以暗杀的手段从隐匿之处消灭敌人才是忍者之风(隼龙:哦是吗)。这类设计在后续的关卡流程中也多次出现。环路结构的第二个作用:为玩法设计提供空间。

线性流程中添加局部环路,以此达成特定意图的关卡设计方法还有许多,笔者在此只是结合关卡结构理论简单举例分析,感兴趣的同好可以私下交流更多的案例进行分析。

3.3.2场景复用——基于最简逻辑图的一种方法

众所周知嗷,苇名城是《只狼》中最重要的一张地图,连接了城邑、仙峰寺、苇名之底、坠落之谷四个地区,不仅在叙事上是故事的中心,在关卡和流程结构上也处于绝对的核心地位。正式展开在苇名城的关卡流程(序章的教学关不算)有三段,分别是:

1正式流程首次击败火牛后进入-击败天守阁弦一郎结束;

2收集完结宿之石、馨香之莲、不死斩三件剧情核心道具之后,枭入侵苇名城-击败枭结束;(此时如果走修罗结局则不会触发第三次的流程,周目提前结束)

3前往源之宫完成拜泪后,内府军入侵-击败剑圣一心结束。

先看狼第一次进入这一段:

由于《只狼》相比黑魂增加了勾索的机制,地图在z轴的纵深大大增加,且跌落伤害的判定宽松了许多,所以“从高处跳下”这样的单向路变得非常普遍。

最终得到的自然逻辑图(红色虚线框部分)以及最简逻辑图如下所示,其中弦一郎和白蛇神社由于不满足缩并原则,在最简逻辑图上只能以“单顶环挂件”的形式存在。

从最简逻辑图上大概能看出来,以主城鬼佛为中心,流程分出了两条分支路径:一条在进城之后向左,联系贮水城区和地牢入口两个地区,分别通往仙峰寺和苇名之底;另一条则是向右勾索攀上屋顶,从武士候命室进入内城,进入内城后玩家可以沿天守阁一路上行、杀到顶楼的弦一郎,也可以向下打开望楼城门并一直前进到坠落之谷的铁炮要塞。

再看一下狼的第二次进入:

狼二次进入时,是在收集完三件关键剧情道具后。按照剧情设定,枭攻占了苇名,城内外所有的门都被关闭,鬼佛也失效了,唯一的通路就是地牢入口。

与第一次进入时相比,开放区域之间的连通关系发生了如下变化,我们在自然逻辑图上加以反映:

1玩家已经打开的单向门没有关闭,全部成为了全连通状态

2学会潜水之后,桥下水道与平台处水道连通成为自由键

3平台处和下层屋顶增加的梯子,使得平台、屋顶下层、屋顶上层之间的单向路变成了全连通

4由于主城入口的桥断了,主城入口与偷听之桥之间变为单向路(可以勾索过去但无法原路返回)

再看三次进入:

三次进入时,起点和终点均发生了变化,狼从天守阁的神子居室出发,需要赶到桥下山谷的暗道前。此次进入时,开放区域之间的连接关系发生了如下变化,我们在自然逻辑图上加以反映:

1地牢/投身之处/望月阁的道路都被切断,将这两片区域从关卡中剔除;

2主城鬼佛对岸的勾索被烧毁,下水的道路变成单向路(下水后无法通过勾索直接返回);

3城区增加的风筝构造了从主城下层屋顶到遗冢的单向路

4蛇谷的桥被修好,将城邑地区和主城连接到一起,导向怨鬼支线。

计算三次苇名城关卡的拓扑指标如下表所示

对比最简逻辑图和拓扑指标可以看出,三次关卡的结构完全不同。

在场景资源没有大的变动、开放区域划分不变的情况下,仅仅通过改变个别地区的键的关系以及玩家的进入点和Boss点位置,就实现了关卡结构的大改动,给玩家带来的流程体验也完全不同。

值得一提的是,在第一次的关卡结构中,由于贮水城区和地牢两片区域单独连接在主城鬼佛上,与其他区域没有交集,导致主城鬼佛成为一个一阶驻点,整个关卡实际上被这个点分成了相对独立的两个部分。而在二、三次进入时,旱井门的常开让平台与贮水城区形成全连通关系,且平台增加的勾索点让贮水城区与主城的房顶成为全连通关系,如此一来使得贮水城区-主城鬼佛-武士候命室形成了一个新的环状结构,消除了一阶驻点,让整个关卡的连通度提高到了2。类似的方法可以用来指导探索型关卡的设计:避免驻点的存在,通过添加键构建包含驻点的环状结构来保证关卡的连通度大于1。

这种“对关卡场景进行细节/方向改动来创造新体验,提高美术资源利用效率”的做法在不少游戏里都有体现:《仁王2》的支线关卡地图就是在主线关卡的地图的基础上,更改其中一些开放区域之间的连通关系得到的。《月下夜想曲》做的更为极致:仅仅将地图换了个方向,让玩家从终点出发,沿着完全相反的方向再探索一遍,便形成所谓的“逆城”(一些竞速游戏也有类似的做法,例如《尘埃》系列的Reverse赛道)。究其这样做的终极前提,还是之前提到的,玩家往往依靠端点来锚定记忆,对过程只有模糊的印象,所以哪怕只是将顺序反过来、或是将路口的连接关系稍作改变,在改变关卡结构的同时,对怪物和POI的投放也做出相应调整,如此对玩家而言就是新的关卡内容。

具体到工作中的实际做法,经过上面的分析相信也好理解:

1划分原关卡的开放区域,确认连接关系;

2根据设计需要,视情况修改一处或几处连接关系、以及初始点和最终点位置,并确认这样的逻辑修改映射到具体关卡中是可实现的——像是“给苇名城增加一部电梯“这样的做法虽然能够在逻辑上增加连接关系、改变关卡结构,但实际操作起来就不太现实了;

3对比更改前后的最简逻辑图,确认关卡的结构确实发生了变化——“稍作改变就是新体验”不意味着“不做改变也察觉不出来”;

4有需要的话,对更改后的最简逻辑图及其稳定因子进行评估,确保新关卡的逻辑结构满足设计目的——下一节会分析说明,为什么只有以“地图探索”作为设计目的的关卡才适合使用稳定因子进行评估。

5当然,想要在游戏中这么做,一定要在世界观上有一个让玩家信服的解释:譬如像《只狼》或《月下》这样用一个概念上完整的故事来交代前因后果。像《仁王2》这样寥寥几行字就把玩家打发到支线关卡里去的做法,不值得提倡。

3.3.3成环质量——稳定因子评价指标的局限性

上一小节的分析中暴露出的一个问题,相信细心的读者已经观察到了。那就是单从稳定因子这个指标来看,苇名城的稳定因子并不低(0.9229对应内府入侵),甚至远超过了《黑暗之魂3》的洛斯里克高墙(0.8829),略高于《黑暗之魂1》的城外不死镇(0.9119),刚好持平《空洞骑士》的遗忘十字路(0.9229)。这是否说明,内府入侵版本的苇名城,就是一个拥有优秀的、丰富的、多层次的环路结构的,充满“魂味”的,能够为其“魂血统”正名的地图呢?答案当然是否定的。

对比《空洞骑士》和《只狼》两张地图的最简逻辑图可以发现,十字路的结构中,单向门“捷径”的设计非常多,且每条捷径都能对应到一个极小环的成环,玩家的主线和支线探索流程及目标因此得到了很清晰的呈现,或者说流程是“可控”的:这对于以“地图探索”作为核心体验内容的游戏来说相当重要。反观苇名城的地图,其“成环”的核心原因是地图中大量作为不动点的鬼佛不满足缩并的要求,且成环质量相当低:不仅缺乏单向门这种能给玩家带来强烈的探索反馈的要素,而且由于不动点之间由大量的全连通键相连,缺乏单向门这样的高优先级成环键,实际的环和树的结构并不能反映和控制玩家的游玩流程——玩家可以从神子居室的窗口直取贮水城区入口鬼佛,过程中甚至完全不会遇到主城鬼佛武士-遗冢-怨鬼支线和水生氏成支线的任何入口。

因此我们不难得出这样的结论:

何为高质量的成环呢?对比两个关卡的结构和生成树不难发现,从存档点出发、经过探索区域,最后通过单向门回到存档点的设计才是能够控制流程的、高质量的成环;在关卡中应控制存档点的投放,避免存档点之间相互勾连带来的无意义成环。

对于非地图探索类型的游戏,可以使用关卡拓扑结构理论的逻辑图来一定程度上指导设计,为玩法和叙事提供空间,或是对关卡结构进行调整(正如前两个小节举的例子所做的那样),但基于最简逻辑图的高阶连通度与稳定因子不再成为其关卡结构设计评价的有效指标。

3.4小结与延申

本章内容在基本概念定义的基础上,对关卡拓扑结构理论进行了综述,并结合两个游戏的例子对其有效性、应用场景及局限性进行了分析说明。

首先是关卡拓扑结构理论的主要内容:

在明确了不同类型的开放区域(点)和路径(键)的概念及其在关卡中的具体表现形式和映射关系后,可以将现实关卡抽象概括为自然逻辑图。

在最简缩并既约原则和同伦变换唯一性的基础上,可以进一步将其概括为关卡的最简逻辑图。

通过对最简逻辑图的连通度进行考察,运用数学工具,可以计算得出关卡的k阶驻点(对)数量、k阶Cheeger数与k阶微扰;定义三阶微扰这一指标作为关卡的“稳定因子”,用于评价地图中环状结构设计的优秀程度(“魂味”程度)。

在综述理论的基础上,笔者选择了广受好评的类魂系列/恶魔城游戏《空洞骑士》,运用该理论对其首个正式关卡“遗忘的十字路”的结构和流程进行了分析,验证了理论的有效性,展示了如何构建关卡的自然逻辑图和最简逻辑图,同时如何使用最简逻辑图和最小生成树作为工具,来控制玩家的游玩流程。

同时,结合实际关卡体验指出了需要注意运用该理论指导关卡设计需要注意的一点:应当避免大规模全连通环路的设计,并在适当添加成环键的同时对其最简逻辑图用稳定因子进行校验,确保关卡环路结构在修正后的稳定性。

随后,笔者选取《只狼》这款游戏,将该理论拓展到非地图探索为导向设计的游戏中的关卡结构中,提出了几种应用手段:

1用于找到线性流程中的局部环路结构设计并分析其作用;

2用于实现关卡“再设计”:在逻辑图的基础上通过对现有关卡的不动点和连通关系的微调,结合适当的形式包装创造出新的流程体验,提高场景美术资源的利用效率。

同时,通过与《空洞骑士》关卡结构的对比,对该理论的局限性进行了进一步解释:作为成环键的单向门的缺失会导致环路结构失去控制关卡流程和制造探索心流的能力,因此在非地图探索为导向的关卡设计中“环路结构”的出现往往并不能反映设计者对流程控制的意图和有效性,导致基于关卡高阶连通度的稳定因子也就失去其对此类关卡设计的评价能力。

读到这里,读者可能会有这样的疑问:“那你分析的这些跟开放世界有什么关系呢?不都是箱庭游戏的设计思路吗”。诚然,该理论是从箱庭式关卡出发进行构建的,所举案例也都来自于箱庭式的关卡,但不代表其对于开放世界游戏就失去了应用价值,有两个方面的理由:

其一,正如“写实游戏应当满足玩家对现实的期待而非客观反映现实”一样,“开放世界”游戏要做的是满足玩家对“开放”这一概念的期待,而绝非实现真正的“完全开放”,毕竟游戏作为一项产品而非工具,在为玩家行为提供空间的同时,其行为空间一定是有边界的。虽然玩家在运动能力上认知的“开放”会与传统箱庭式关卡的设计理念相冲突,但这不代表设计师不能通过施加一定的条件来将玩家的行为边界限制在设计好的关卡结构里。

一个突出的例子就是:尽管《荒野之息》中野外的立面大部分是可以攀爬的,看似会破坏掉箱庭式的迷宫设计,但“爬墙”这一行为被设计成受到精力(玩过你原的应该都知道)和天气要素的制约(下雨天壁面打滑、无法攀爬)。在流程推进到前往卓拉领地这一段时,设计师用“大象神兽不受控制地喷水导致领地附近终日降雨不停”这一叙事包装拿掉了玩家爬墙的能力,使得玩家需要按照既定路线经过一段精心设计的、箱庭式的探索流程,感兴趣的读者可以尝试运用自然逻辑图和最简逻辑图这样的工具对这一段关卡进行结构分析。

综上,只要玩家的行为仍然受到规则的约束,设计师就可以在建立起游戏规则到理论空间的映射的基础上,基于本文所述理论工具对关卡结构进行设计和分析。

其二,“开放世界”不等于“开放关卡”,“箱庭关卡”也不等于“箱庭游戏”,好的游戏能够定义标签而非被标签所定义,好的设计思路和方法也不局限在某一特定品类的游戏设计中。即便是《荒野之息》这样的开放世界游戏品类标杆,其主线剧情及野外探索点仍不乏大量经典的箱庭式解谜关卡,但鲜有玩家会据此认为其是单纯的箱庭式解谜游戏,也鲜有设计者否认这些关卡应用了传统的迷宫设计方法。

引用笔者一位策划前辈的观点,开放世界不应当是程序生成的公式化内容的堆砌,而应当是

大片的工业化产出的内容,围绕着核心的、艺术化的、匠人精神的关卡

正如即将发售的《艾尔登法环》所呈现的那样,而关卡结构拓扑理论,无疑是指导这部分“核心的、艺术化的、匠人精神的”内容设计的重要工具之一。

THE END
1.《经典图论算法》无向图的连通性判断一般情况下讨论图的连通性主要是无向图,而对于有向图我们一般讨论比较多的是强连通分量。计算有向图的强连通分量可以使用kosaraju算法和Tarjan算法,其中Tarjan算法还可以计算图的割点和割边(如果存在割点和割边),这些在后面我们都会介绍。https://mp.weixin.qq.com/s?__biz=MzU0ODMyNDk0Mw==&mid=2247507628&idx=1&sn=21d70a523cd553afb1ca6b9a6d30c9b0&chksm=fa2548a183427d284a6c5e04658e29afe3bb9cd8dc969f03055100138f12f64961238bcc630c&scene=27
2.关于图和实例的学习之相关概念个人理解连通图关于图和实例的学习之相关概念个人理解 本文介绍了图论中的关键概念,包括连通图的定义及其在无向图和有向图中的表现,以及连通图的强弱连通性。此外,还探讨了实例和图的包、子图的概念,以及图和包的子图特征与实例特征的表示方法。 摘要由CSDN通过智能技术生成https://blog.csdn.net/rothschild666/article/details/124740228
3.图论连通图连通图的定义官方尚新途图论_连通图_强连通图和强连通分量 图论_连通图_弱连通图和单项连通图的定义 图论_判断图是否是强连通图,弱连通图还是单项连通图思路 图论_判断图是否为强连通图,弱连通图,单项连通图代码实现(Java) 图论_生成树_生成树的定义 图论_生成树_最小生成树的定义 38_拓扑排序,邻接表和邻接矩阵(JAVA版) 39_高精度https://www.sxt.cn/wiki/4999.html
4.2连通图的一些等价定义11苏静;马飞;姚兵;探索2-边连通图的等价定义[J];华东师范大学学报(自然科学版);2017年01期 12常帅;5等周边连通图的邻域条件[J];山西师范大学学报(自然科学版);2017年01期 13苏静;马飞;姚兵;2-连通图的一些等价定义[J];东北师大学报(自然科学版);2017年01期 https://www.cnki.com.cn/Article/CJFDTotal-DBSZ201701008.htm
5.21图结构的基本概念51CTO博客图结构的基本概念 图的定义:用于描述多对多的网状关系。 由用于表示事物的顶点(vertex)集合V,以及表示事物之间关系的边(edge)集合E构成 记作G=(V,E) 顶点数目n>0,边数目m≥0 V:非空有穷顶点(vertex)集 E :V上的顶点对所构成的边(edge)集 https://blog.51cto.com/u_15054039/3651681
6.图的基础概念和术语旧市拾荒三、树与图的关系 没有圈的连通图,就是树。 没有圈的非连通图,就是森林。 一棵树的边数等于顶点数-1。 边数等于顶点数-1的连通图,就是树 。 四、有向无环图 没有圈的有向图,叫做DAG(Directed Acyclic Graph,有向无环图) 拓扑排序定义:将DAG中的顶点以线性方式进行排序。即对于任何自顶点u到顶点v的https://www.cnblogs.com/xiaoyh/p/10411650.html
7.带你了解Java数据结构和算法之无权无向图java1、图的定义 我们知道,前面讨论的数据结构都有一个框架,而这个框架是由相应的算法实现的,比如二叉树搜索树,左子树上所有结点的值均小于它的根结点的值,右子树所有结点的值均大于它的根节点的值,类似这种形状使得它容易搜索数据和插入数据,树的边表示了从一个节点到另一个节点的快捷方式。 https://www.jb51.net/article/235417.htm
8.0图的基本概念.ppt0图的基本概念.ppt 离散数学 离散数学 三、图的连通性(续) v2 v3 v4 v1 (a) v2 v3 v4 v1 (b) v2 v3 v4 v1 (c) 强连通图的判定定理: 有向图D强连通,当且仅当D中存在一条回路,至 少经过每个顶点一次。 离散数学 四、点割集与边割集 点割集:设无向图G = V, E,若存在顶点子集 V ?V,https://m.book118.com/html/2017/0312/95104792.shtm
9.数据结构学习——图1.定义 图有顶点和边组成,顶点用有穷非空集合V(G)={v1,v2,,vn}表示,顶点之间的边用集合E(G)={(u,v)|u∈V,v∈V}表示,图可以表示为:G=(V,E)。其中G表示图,V表示顶点,E表示边。|V|表示顶点的个数,也称图的阶,|E|表示边的条数。 https://zhuanlan.zhihu.com/p/636110333
10.图的运用路径规划(连通图的生成树)连通图的生成树定义:所谓一个连通图的生成树是一个极小的连通子图,它含有图中全部的n个顶点,但只足以构成一颗树的n-1条边。 连通图的生成树的度判断 1.图是连通图; 2.图中包含了N个顶点; 3.图中边的数量等于N-1条边。 最小生成树 含义:把构成连通网的最小代价的生成树称为最小生成树。 https://www.jianshu.com/p/d6e77033ee53
11.第二章:图神经网络的图论基础在本章中,我们将深入探讨图论的基础知识,涵盖三个主要主题:图属性、图概念和图算法。我们将首先定义图及其组件。然后我们将介绍不同类型的图,解释它们的属性和应用。接下来,我们将介绍基本的图概念、对象和度量,包括邻接矩阵。最后,我们将深入研究图算法,重点关注两个基本算法,广度优先搜索(BFS)和深度优先搜索(DFS)https://fancyerii.github.io/gnn/ch2
12.斗鱼大佬分享!基于图的团伙挖掘算法实践机器之心本次分享的主题是《基于图的团伙挖掘算法实践》,主要包括三个方面: 团伙定义和特点 团伙挖掘流程和方法 经验与总结 团伙的定义和特点 我们这里所指的团伙是网络中的黑产团伙,这些团伙主要从事网络上的薅羊毛,刷单等非法活动,和金融场景中的团伙定义还是有一些差别。主要特点表现为: https://www.jiqizhixin.com/articles/2019-08-20-8
13.图在无向图G中,若两个顶点之间存在通路,则称这两个顶点是连通的。若无向图G是平凡图或者G中任意二顶点都是连通的,则称G是连通图,否则称G是非连通图。 在有向图D中,如果略去各边的方向所得的无向图是连通图,则称D是弱连通图或者连通图;弱D中任意两个顶点至少一个可达另一个,则称D是单向连通图;若D中http://www.notedeep.com/page/17864