过程生成技术

  cheney

    过程生成技术是一种可以广泛应用的媒体制作技术,它的程序能够自动生成内容,而不是设计者之间就设计好的,这意味着必须有一个创造的过程。这往往涉及到计算机图形学的应用。过程控制能够在游戏中发挥极大的作用,本文介绍递归分形等过程生成的支撑,以及过程控制与游戏的制作

    为了很好的说明这个概念,正好有一个绝佳的例子,一个只有96kb的游戏「kkrieger」:

    kkrieger

    这个容量只有96K的第一人称射击游戏「kkrieger」,是由德国一家名为「.the .produkkt」的小组完成的,但玩过的玩家都被这个游戏的视觉表现深深的震撼:不管是超炫的光影表现、实时阴影投射、环境贴图、凹凸贴图等3D效果一应俱全,加上游戏中的人物、怪物3D模块也建构得很仔细,游戏关卡也设计得颇有气氛,这么高水平的游戏就算是直接拿市面上已经发售的同类型游戏来比都胜过太多了,但游戏容量竟然只有96K。

    别看该游戏体积很小,但对机器配置要求却很高,一般人的电脑恐怕都不能运行。看来是拿来测试计算机硬件效能的好东西,要求基本配备:

    操作系统:

    • Windows Me / 2000 / XP
    • DirectX 9.0b
    • CPU:Pentium3 1.5GHz 以上
    • 内存:512MB 以上

    3D显示卡:Geforce4Ti 或 ATI Radeon8500 以上(支持pixel shaders 1.3功能,内建128MB绘图内存)释放后占用了近300MB内存

    运行该游戏后先要经历一段长时间的解压缩过程,而这些数据都将释放到内存中,所以512MB以上的内存配置是必须的。该游戏所占据的内存容量,已经接近300MB。「.the .produkkt」小组表示,「kkrieger」这款游戏总共将有三个章节,而现在发布的仅仅是第一章的测试版,未来发布的版本体积可能会上100KB,但将修正更多BUG,运行也会更加稳定。

    ##原理揭秘

    不知道大家是否有印象,以前网上经常传出许多大小只有64KB的3D演示动画,一些3D迷宫什么的,那是一些编程高手为了展示自己的实力完全采用汇编语言完成的作品。而相比来看,这款96KB的FPS游戏则更加精彩,因为他是一款有声有色,并且真正可以“玩”的游戏。 这款游戏之所以可以压缩到这么小的境界,就是因为游戏之中的场景和音乐几乎全部都是由动态产生,游戏之中预先存放的资料只有一些简单的几何形状和MIDI音乐档,所以自然档案大小非常小。如果这款游戏没有用“过程生成”(Procedural Generation)的技巧进来的话,估计档案大小会爆增,这样的技术,真是令人叹为观止。而背后最大的功臣,就是递归和碎形。

    ###递归

    有一个经典的数学问题汉诺塔。

    汉诺塔

    汉诺塔(又称河内塔)问题是源于印度一个古老传说。世界的中心有三根金刚石柱子,在一根柱子上从下往上安大小顺序摞着64片黄金圆盘。大梵天命令僧人们把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。

    有个僧人说:“只要有一个人能够把63个盘子挪到另一个柱子上我就能够把64个盘子挪过去。”

    又有一个僧人说:“只要有一个人能够把62个盘子挪到另一个柱子上我就能够把63个盘子挪过去。”

    又有一个僧人说:“只要有一个人能够把61个盘子挪到另一个柱子上我就能够把62个盘子挪过去。”

    ……

    又有一个僧人说:“只要有一个人能够把3个盘子挪到另一个柱子上我就能够把4个盘子挪过去。”

    最后一个僧人说:“我会挪动3个盘子。”

    三个盘子的挪动方法很简单,于是这个大的问题就解决了,这就是递归调用。

    递归不仅仅在数学上有其重要性,在电脑科学之中扮演的角色更是至关重要。程式设计者对于递归绝对不会陌生,上面所举的汉诺塔问题,实际上也是电脑科学的经典例子之一,是初学程序设计的人一定会学到的东西。递归的思维,常常可以让程式设计者打造出简洁的程式,让繁冗的问题透过简单的程式码来解决。

    ###分形

    还记得盗梦空间里,小LOLI用两面镜子互相反射对面的像来制造了一个延伸到天边的长廊么?递归同时也是分形(fractal)这门大学问的基石,分形是一种相当美妙的几何图案,就如同下面那一张蒙娜丽莎的图一样,图中有图,形中有形,且小的部分都是大的部分的缩影,我们就称之为分形。

    分形本身的数学定义,实际上就包含了递归定义在里面,我们甚至于可以说,分形是递归在几何学的一种具体呈现。 但是分形不仅仅是一种数学概念而已,在自然界中,有许许多多的地方都出现自然的分形。分形是用来描述大自然的一门几何学,它所描述的图形可以是分数维.分形的特征是整体和局部有严格的或统计意义下的自相似性.描述分形的定量参数为分维,而维数的定义种类很多,如相似维数、Hausdorff维数、盒维数(box dimansion)、拓扑维数(topological dimension)等,需要随研究对象的改变来选择.研究表明,分形在自然界中随处可见,例如,曲折而不规则的闪电路径,弯曲复杂的海岸线形状、密如蛛网的人体血管系统、变换不定的宇宙星云分布以及材料的组织生长、准晶态的晶体结构、材料的损伤等等.从地理学、生物学到物理学、化学甚至社会科学都普遍存在分形现象.分形理论在高分子科学中的应用研究也有很多文献报道,例如分形理论与各种现代分析手段相结合,已用于研究高分子的链结构、结晶过程、凝胶化过程、高分子的相形态结构等等方面.

    图中的这棵花椰菜,就蕴含了递归的碎形图案与于其中。 分形同时也在各个研究领域有着广泛的应用,光是在电脑科学领域,就有人把分形应用在影像和影片压缩之上(这不难想像,由于分形这种以小见大的特性,我们可以用小的来表现大的,因此可以有压缩的概念出现),在电脑图学上(computer graphics),也有人把碎形应用在设计电脑游戏之中的一些景物,打造出有效率和简洁的系统。

    现在电脑游戏之中的景物,很多都是玩家边玩、游戏系统边产生出即时的景物,这叫做procedural generation(过程生成),这种即时产生景物的技术,可以避免游戏软件预先储存一堆要展现的景物,帮整个软件瘦身。“过程生成”就使用了大量的分形产生与合成技术于其中,而这些都根植于递归这一个深刻却简单的思维。

    ##过程控制与游戏

    随着每一代的新主机的降临,创造游戏的成本,不论是时间还是资金,都飞速地增长。而小型开发组无力应付这样的增长,“内容的自动生成”于是便有了用武之地。自动生成的内容是由计算机算法创造出来的,而不是由美工精心雕琢而出的。这样的内容完全是动态生成,或者可以在一些(比如由用户或文本文件的)外部输入的基础上来生成。

    在IntroversionSoftware的最新游戏《核战危机》(《DEFCON》)里,真正由创作的内容只有音效。游戏中几乎所有的其他内容都是来自于公之于众的信息——城市的位置,多变的海岸线的经纬度,国家的边境线等全都可以在互联网上免费获取。在《Darwinia》中的场景是有几行代码自动生成的——如果这其中的每一样都要手工来做的话,不知道要花费多少时间。又比如像《GTA3》一样的游戏。你可以为了一个城市花上几个月的时间,为它增加建筑,为游戏世界铺上材质。或者你可以花费几个星期的时间,来研究一个自动生成这些城市的方法。这样做的成果是有几乎无限数量的城市供你游玩,而开发时间却被大大减少了。

    你也许会不服气,认为这样创造出来的城市远没有手工制作地那样精细,但这全看你在这些动态内容上投入多少精力。你的动态建筑可以是简单的方块,加上窗户和门的贴图,或者这些逼真的窗子可以是基于建筑本身的设计和大小生成出来的,窗户的贴图甚至可以依据放置在边上的邻居的房子来改变。作为一个只有有限数量员工,并且没有3D模型师的公司,这显然是一个比花费数月手工制作成堆的模型更可取得方案。

    自动生成内容还能让你大大增加游戏的广度。就用前一个例子,在一个手工建造的城市和十万个可比较的自动生成的城市间选择,答案是显而易见的。WillWright的《孢子》(《Spore》)就将这个概念发挥到了极致——整个星系,大到星系系统,小到这些星系里行星上的微生物,都由每个开始游戏的玩家动态生成的。

    其实自动生成内容并非是一个新鲜事物——事实上,多数早期的电子游戏都将自动生成作为将大量数据装进那个时期仅有的相对较小的媒体中的唯一手段。《精英》(《Elite》)及其续作《边境》(《Frontier》)就是典型的例子——动态生成的星系系统,动态生成的关卡,以及一整套其他的特色内容全都是程序生成的——一个本质上无穷尽的宇宙就这样被装进了一张软盘里。 当然,你能够用程序生成的不仅是静态的模型和形状。贴图,音效,甚至动画都可以由算法在运行(runtime)时被创造出来。

    再回到先前的例子,《Spore》的一大特色就是能动态生成玩家创造的生物的动画和贴图。动画是根据给定生物的骨骼解剖架构动态创造出来的,这包括行走,奔跑,进食,甚至舞蹈。这个生物的贴图和它的身形完全匹配,而它的身形是由头部,胃部,背部和身体上其他部位的位置决定的。

    另一个更加极端的例子是文章开头提供的一个叫做《.kkrieger》的演示作品。这是一款第一人称射击游戏,其中的任何东西都完全有程序自动生成。关卡(只有一个关卡,这毕竟只是一个演示作品),贴图,模型,动画,音效——全都是由游戏在运行时动态创造的。更加令人叫绝的是,这样华丽的图像(考虑到所有因素而言),整个游戏只有96kb——你下载这篇文章里都包含不止96kb的信息量!如果所有的数据都是预先制作好,并且以传统的方式来存储的话,它很有可能占几百兆的空间。

    当然,自动生成内容也有些许不足。对于初学者来说,如果你的整个游戏都是由程序自动生成出来的,就很难有外观别致的场景——很容易得到尽管布局不同,却十分雷同的关卡。这意味着一定程度的人为介入是让游戏变得光鲜所必需的。 《Darwinia》就是一个很好的例子——《Darwinia》的布景是接受简单字符串输入后由程序自动生成的,但游戏里所有的建筑都是手工摆放的,设计者还写了一部分由脚本控制的事件序列。尽管团队尝试过完全随机动态地生成关卡,但发现要产生玩起来有趣的场景,添加特殊场景是极其困难的。

    另一个致命的不足是动态生成内容所要花费的时间。比如,也许生成城市里的一栋建筑只需要花费不足一秒钟的时间,而一旦你要生成整个城市里的几百栋建筑,以及道路系统,这就会累积成一段明显的停顿时间。这个问题在前面提到的《.kkrieger》中尤为明显——游戏开始前会有一段冗长的“读盘”时间,其间关卡中的所有内容正在生成。这也意味着运行这样的游戏要比预制预存的游戏需要一台CPU更强劲的电脑。

    尽管如此,程序自动生成内容对小型开发团队来说是一个关键的工具。而且有些人可能还会持有这样的观点——这将是业界的未来。随着开发成本铺卷开来,难以控制,发行商们变得越来越不敢冒险,尝试投资新生作品,情愿守着那些已经尝试过和考验过的方法,也不愿发掘原创作品。使用程序自动生成的方法可以降低成本,开发者们可以获得更多的自由来测试新的想法。