游戏地图自动生成.ppt
游戏地图自动生成,自然峡谷与山洞地型图生成技术网易互动娱乐 林伟,特性前瞻：,根据参数生成自然状态的峡谷与山洞地图根据参数添加各种游戏要素自动导出模型与纹理服务器每次只需传送参数与随机种子降低制作成本：大量固定场景可考虑自生成增加游戏乐趣：每次进入副本都不一样,自动地图历史,最早出现的各种自动迷宫生成算法早期红色警戒有了较低级的自动地图Jamis Buck 的“2D地下城生成算法”暗黑破坏神II中漂亮的2D动态地图系统注：更多早期地图生成算法信息详见参考篇,（插图）传统2D地下城生成算法,技术对比,传统技术基于传统2D游戏，难以3D化新技术更加注重模仿“自然状态”的各种规律传统技术需要大量图量单元用于拼接新技术不需要大量图量单元进行拼接,新系统结构图,地图化,路径图,原地图,游戏化,相关参数,(插图)原地图与原模型生成,自动地图在效果上肯定无法有手工地图细致不可能完全代替美术产生户外场景,第一章：地图化算法,如何初始化地图细胞自动机自然连通图原地图生成,我们需要怎样的算法？,现在有大量成熟的迷宫生成算法大都不适合自然地貌的生成我们需要怎样的算法呢？,如何初始化地图？,简单的初始化是根据长和宽创建二维数组将数组中所有的元素设置为“墙”然后随即将该数组中若干位置设为“地面”地面的砖块数除以数组面积是密度给定面积与密度下计算需要多少随机“地面”,（插图）我们得到下面的东西,这是地图初始化效果最简单的第一步神奇之旅将从此开始,Cellular Automata 细胞自动机,浏览数组中每个格子统计当前格子周围八个格子的“墙”的数量如果墙数小于X值，就将当前格设为“地面”如果墙数大于Y值，就将当前格设为“墙”如果在X-Y之间，则当前格保持不变实际生成中我们取4-5的模型,（插图）CA处理后结果,CA处理结果如右图同数组可以处理多次现在我们有六块区域此处需处理预设区域出口等位置在此设定剩下的就是连接它们,如何将随机结点连接起来？,Battle in Space（PKU-ACM试题）,新游戏“Battles in Space:Unification”(BSU)在不久的将来会发行：人类被分散到N个相互敌对的星球上，玩家扮演某一星球的领主，使用外交与军事技巧占领其余的星球。重构人类的新秩序。特殊的“星际隧道”将两个星球连接在一起，使他们可以进行交流，所有连接星球的隧道称为“地图”当前开发者正致力于生成随即的星际地图，他们将每两个星球是否相连用概率p来表示。,能够随机连接么？,如果按照游戏BSU中的做法：按40%概率随机连接两个结点，得到右图，显然不是我们需要的。如何连接各个结点才自然呢？神奇之处即将开始。,自然连接图,将所有结点连接起来并且没有环路的图，我们称为完备迷宫图（Perfect Maze）。模仿自然状态连接的完备迷宫图我们称为自然连接图。,判定两点间能够连接,如果两个点处于同一个集合则不能相连如果两点连线覆盖到另一点则不能相连如果两点连线交叉到已有线段则不能相连,算法定义,1）每个独立的节点为一个独立的集合2）计算所有能够连接的点和他们之间的距离3）在距离最短的备选边中选择一条最短的4）将其两点连接，归并到同一集合5）重复到2，直到空间中只有唯一一个集合,（插图）我们得到下面这类效果,算法由于选取优先连接短边，同时避免交叉，形成类似植物一节一节的生长的效果。该算法的结果是形成没有环路，连接所有结点的模仿自然状态的路径图,算法的技巧,每次不一定找最短的边，而是按所有可连通边的距离从小到大排序，筛选出前N名后随机取一条较短的。同样的结点按照上述方法生成2分结果后合并，可以得到带环路的路径图，一定量环路能增加游戏乐趣。给定预设点后，围绕预设点生成N个结点，与预设点一起生成路径图，然后循环m次，每次删除一个单向连通的非预设点。M越大则路径越干净，非给定结点外的分支越少。,原地图生成,我们将前面 Cellular Automate生成的类似细胞单元图，使用“自然连同图”算法进行带噪声的直线连接，取区域中心作为结点位置。如果在画直线过程中不管碰到目标区域或者非目标区域，都将其二者联合，重新计算可连通区域。最终得到右边形似山洞的效果，我们称为“原地图”。,仿自然效果生成的不同“原地图”,SUMARY,细胞自动机（Cellular Automata）自然连通图模仿峡谷与山洞的原地图生成我们完成了“地图化”工作,TEA-TIME,喝水时间，休息十分钟（接下来将介绍如何将导出三维模型并“自然化”）,第二章：自然化算法,如何生成山地？如何定制地形？如何导出模型？如何导出纹理？,不规则地形生成,多数情况下，这是一种更简单、更真实的地形制作方法。在超大规模地图制作以及动态地图方面，或者当我们没有足够资源让美术人员来为我们制作大型世界的时候，该技术将会发挥出它的特殊作用。按照通常的表述方法，不规则地形生成也就是生成记录高度的二维数组以及相应纹理。现有的不规则地形生成算法有：断层构造、中点位移、粒子沉积同流体侵蚀算法等。,Fault Formation（断层构造法）,首先将高度图的二维数组全部归零画一条通过网格的线，将线一端的地形升高特定高度重复上述步奏：画线升高，但减少每次升高的高度如果想要地形平滑，那增加一个平滑过滤器（如模糊过滤）,Midpoint Replacement（中点法）,二维生成为例：选取场景中的线段，找到其中点在其中点加入一个新节点并升高/降低一个随机数在两条新线段上重复该步骤并减少随机数范围,Midpoint Replacement（中点法）,重复上述步骤足够多次，便能得到下述图像,Midpoint Replacement（中点法）,用中点位移法加 Diamond-Square的分形方式可以如法泡制三维地形此方式除去生成三维地形外还能生成自然状态的云彩与河流,基础算法有何局限？,前面所述算法对系统而言几乎“不可控”除了改变随机种子外，无法控制整体格局无法根据我们的需要，导出模型因此，我们需要更高级的方法,Parametrically Controlled Terrain Generation GRAPHITE 07,通过平面画L条直线并切割出多个多边形区域。从包含指定山顶位置的多边形开始寻找R个相邻的多边形然后升高该区域地形特定的高度。重复上述步骤N次。通过控制参数（N，L，R）以及每步升高的因子可得到各式山峰。,如何用二维地图生成三维模型？,我们需要将第一章“地图化”导出的结果在这里生成模型。前面所述各种方法都可以用于将二维地图转化为三维地形。可以用上页所提及的方法，将二维原地图中属于“墙”的部分用特定参数生成一座一座的山峰，最终导出模型。我们也可以用中点位移法生成初始地图再按照二维原地图的形态进行若干修正。,中点位移修正法,先选择中点位移法生成任意给定大小的地形将地形的高度压缩到(0.1-0.4)之间整体高度增加0.4，则处于（）之间按照原地图与地形大小的比例来划分如果原地图某位置不是墙，那该区域平滑下降0.4用(0.1-0.2)之间的新地形和原地形作加法（避免路面太平）使用 Cellular Automata将模型边角除去使用平滑过滤器将模型平滑，最终导出高度图,三维地形的CA处理,考虑地图上每个节点周围26个节点，数出周围26个节点中属于“山”的个数N如果N小于特定值，那把该点删除如果N大于特定值，那把该点设置设置为山,最终模型导出,最终模型导出,通用纹理合成,通用编辑器都有纹理合成功能，一般将地图按高度分层，不同的高度对应不同的纹理：地、草、岩石和雪。再按具体高度差值得到最后的图像。这样的做法将生成比较机械的纹理，比如生成的草都在同一个等高线上，看起来十分不自然，所以该方法只能用于前期处理，一般都要美术最终手工修正才能勉强真实。自然状态的自动纹理合成是比较复杂的事情。,如何合成真实纹理？,仔细观察发现，各层地形材质的特性各不相同。山峰顶部的积雪，其实并不是按照等高线划分的，比如长期向阳的部分，积雪会比较薄，同时积雪无法留在山势陡峭的地方。草地也有其规律，向阳的地方比背阴处茂密，山势陡峭的地方也无法长草。最后根据太阳光照带来明暗效果生成光照图再合成为最终纹理。那么如何生成真实纹理呢？我们将采用 Gyurchev的算法。,Gyurchevs Texture Algorithm,高度：确定基本的地形纹理法向：确定该位置的倾斜度与材质修正光照：确定材质的稀疏程度与阴影过渡：规定材质过渡的范围Yordan Gyurchev 的算法将依据上述四个变量在高度图各个位置中的数值确定最终的合成结果。,真实纹理合成,真实纹理生成效果演示,后期峡谷效果（1）,后期峡谷效果（2）,峡谷内效果图,算法优化方向,将峡谷上下作镜象再合成可得山洞模型。基于中点位移法生成的地形细节不够。用流体侵蚀算法，制造更细致更加起伏跌宕的山脉。沿着峡谷边缘随机放置少量树木。比较大的空地上放置少量草地模型。适当的地方放置河流，用桥连接必要路径。,SUMARY,不规则地形生成法：断层构造中点位移法。参数可控的地形生成算法。根据二维原地图导出三维模型。如何根据模型导出真实纹理。算法优化的方向。,TEA-TIME,喝水时间，休息十分钟（接下来将介绍如何将导出三维模型并“自然化”）,第三章：要素合成,如何抽象NPC数据？如何批量产生NPC？如何放置NPC？如何添加道具？如何合成要素？,如何生成/放置NPC?,NPC生成/放置首要工作是参数模型抽象策划将给出NPC各项参数的范围批量生成评估地图各个区域的重要性根据路地图特点放置NPC本章只给出基本模型，具体游戏具体分析,NPC简单模型,批量生成NPC需要指定什么？,给定上述值后将根据种族与等级的范围批量生成NPC,网络资源,Ren Vernon 的NPC模板：将NPC抽象为七个大类别、二十七个小类别的方法。Jamis Buck 的NPC生成器：批量生成地牢游戏的NPC数据。NPC背景故事生成器：给定NPC的等级参数，它将为NPC生成一段动人的背景故事。,如何选择放置位置？,我们用2D原地图来分析如何放置更自然？如何放置更有趣？统计所有节点计算到出口的路径长短计算每个路口的角度和,地图区域如何评估？,我们需要用连通图来进行区域分析，计算各个地图区域的重要性,区域评估三要素,我们可将地图区域用如下三要素来表示：区域面积：就是CA过后该区域格子数量，用来计算该区域可以摆放多少东西。最短距离：该区域到入口的最短距离，用来将重要的东西摆远一点，这样玩家需要较长时间才能到达。累加角度：从入口到该节点的有向路径中各条边的角度差的绝对值和，用来描述一共拐了多少弯，值约大玩家越难发现，这样可以放置一些隐藏要素。,地图放置规则,从连通图中的单向连通节点区域开始按照到入口的最短距离排序按照宝物价值排序，顺序放入上述排序过的单向连通区域中，这样玩家不会因为走到一个死胡同一无所获而恼怒。按怪物等级高低排序，等级最高的放在离入口最远的地方，难度递增。从入口开始处延路径每经过一个节点的方向改变角度绝对值的和称为累加角度。角度和越大的地方，代表拐弯越多的地方，按此数值排序，顺序设置隐藏宝物，这样会增加玩家探索的乐趣。先按照节点的边数，再按照节点离入口的距离排序，然后顺序放下剩下等级怪物，这样重要的路口会有更厉害的怪物守卫。如果还有怪物剩下，那么随机放置到各条路径中。,要素合成 增加游戏乐趣,将地图的轮廓提取出来，部署栅栏模型在比较开阔的地方放置建筑或者标志设置可打破的墙壁将某些支路封闭隐藏在太阳经常照射的方向布置草模型在开阔的区域布置少量树模型在某些区域开辟山洞连接其他场景单独处理BOSS的生成与放置,网络化处理,生成地图需要相当大的计算过程，结果也相当庞大。服务器每日晚上计算出1000幅自动地图（不需要计算纹理），并保存参数与种子。当确定具体某场景后将该参数与种子传递给客户端，客户端同步计算出场景数据。客户端/服务器使用相同数据同时开始游戏。,SUMARY,NPC建模方式NPC自动批量生成地图区域评估NPC放置要素合成,参考资料,传统迷宫生成算法Jamis Buck的地下城生成/NPC生成法断层构造/中点位移/流体侵蚀算法参数可控山地生成Yordan Gyurchev的地形纹理合成法,发展方向,模型真实化的提高：可以参考地理信息系统的最新地形还原技术。纹理真实华的提高：倾斜度高的山脚用单独的纹理坐标防拉伸，考虑更多自然因素。加入更多地图要素：诸如河流，桥梁。随机加入带剧情/任务的NPC角色。,Terrain Synthesis from Digital Elevation Models IEEE 07,地理信息系统的地形生成的最新算法：将手绘的草图模型演化为真实三维场景通过在大量模型样本中匹配并提取相应的样本碎片拼接而成。,游戏自动地图生成技术的发展空间仍然很大，传统二维地形生成已经成为历史，如何生成更加真实自然与有趣的游戏关卡成为问题核心。虽然不能完全代替手工制作，但该方法在提升游戏乐趣与降低制作成本方面将发挥独特的作用。,课后交流,游戏地图自动生成的所有内容到此结束感谢大家,
