游戏地图自动生成.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越大则路径越干净，非给定结点外的分支越少。 原地图生成 仿自然效果生成的不同“原地图” SUMARY 细胞自动机（Cellular Automata） 自然连通图 模仿峡谷与山洞的原地图生成 我们完成了“地图化”工作 TEA - TIME 喝水时间，休息十分钟 （接下来将介绍如何将导出三维模型并“自然化”） 第二章：自然化算法 如何生成山地？ 如何定制地形？ 如何导出模型？ 如何导出纹理？ 不规则地形生成 多数情况下，这是一种更简单、更真实的地形制作方法。 在超大规模地图制作以及动态地图方面，或者当我们没有足够资源让美术人员来为我们制作大型世界的时候，该技术将会发挥出它的特殊作用。 按照通常的表述方法，不规则地形生成也就是生成记录高度的二维数组以及相应纹理。 现有的不规则地形生成算法有：断层构造、中点位移、粒子沉积同流体侵蚀算法等。 Fault Formation（断层构造法）