过程生成与无限星辰这个游戏

　　最近无限星辰(Infinity)这个游戏又放出了新的截图，用GPU来进行它的过程生成运算，使得行星的表面有一次有了质的飞跃。
　　我们先看看这个游戏的自我介绍：

　　Infinity: The Quest for Earth（译名：《无限星辰：失落的地球》）是一个基于未来宇宙背景的大型多人在线游戏，目前还在紧张开发中。

　　这款游戏采用了一种先进的过程生成引擎。它会使玩家在宇宙中的探索看似无限大，而其中拥有着一颗颗独立的星球，同时在每颗星球上都可以做到无缝着陆。游戏将会给新老玩家提供一个宏大的故事背景，在宇宙中错综复杂的政治下，充斥着各种社会集团、公司和其他组织，而主线，将围绕游戏中的三大势力——人马座集团、德尔塔联邦和斯塔弗同盟之间的斗争展开。

通过使用I-Novae引擎先进的过程生成技术，《无限星辰》已经打破了往日游戏在固定空间内探索束缚。它将使动态生成数不清的星系与星球成为可能，每个独一无二的角落都在等待着发现它的人。通过绘制合理的天文距离与比例，每个在宇宙中不停运动天体轨道都会被精确地计算出来。在这里，从一睹遥远的双星系星球上两个太阳的日出，到观看一个距离你所在家园外千万光年的小月亮的月全食，都将成为可能。每一组景色，每一条地平线，在《无限星辰》世界里，都完全会是独一无二的。

　　怎么样？听起来不错吧？网游就应该是这样个样子才对。
它的主页：http://www.infinity-game.com/infinity/index.php


　　那么，这篇文章的主要目的还是通过这个游戏引入一种概念的介绍：Procedural Generation，这里被翻译作过程生成，其实理解就是在实际游戏的过程中生成游戏中相应的对象，这个游戏号称拥有的数十亿棵星球，每颗都有着有很多细节的地表。而这每颗星球的详细内容都是玩家在自己的机器上开启游戏后生成的。怎么样？神奇吧？
　　其实，要理解这个过程生成技术必须要从它的数学原理下手，那就是分形，这里有一篇介绍这一思想的文章：递归之美：数学，电脑科学与分形 ，转自：http://mmdays.wordpress.com/2007/05/24/recursive/

想像一下，我剛才說了一句話，那句話是：「想像一下，我剛才說了一句話，那句話是：「想像一下，我剛才說了一句話，那句話是：……….」」，如此下去，就好像站在兩面平行擺設的鏡子中間，鏡子中的影像不斷的重複。再舉個例子，寫完一封信想要匿名保密，就署名「知名不具」。回信的人寫：「知 知名不具 具」。之後再回信的時候就變成：知知知名不具具具，加上括號可能比較清楚：(知(知(知名不具)具)具)。

遞迴就是類似這樣子，不斷的重複同樣的東西，只不過每次重複的是比較小的東西了。大家應該對數學歸納法不陌生，在使用數學歸納法時，我們首先確定 n=1 的時候某件事情是成立，然後在證明 n 到 n+1 的過程是正確的，就可以從 n=1 的例子，一路推論出第 n 項是甚麼東西。就像是推骨牌一樣，把第一張牌推倒了之後，剩下的骨牌自然就被前面的骨牌給推倒。

遞迴的概念則是相反的方向：我們想要解決一個大小為 n 的問題，我首先做的事情是把問題化簡成大小為 n-1 的問題，但是解決的方法還是一樣，只不過大小是 n-1。如此繼續化簡，最後變成大小為 n=1 的基本問題，接著只要n=1的基本問題解決了，原來大小為n的問題也跟著解決了。

這又好像層層分工。假設每個人都會加法，然後今天我想求出 1+2+…+n 等於多少？其中一個辦法就是遞迴，我先假設 1+2+…+(n-1) 已經有人算好，那麼我只要再加上 n，就可以得到答案了。然而 1+2+…+(n-1) 要怎麼得到呢？我就請另外一位朋友幫我算。另外一位朋友接到這個問題以後，也用同樣的方法，他把 1+2+…+(n-2) 的結果交給另外一位朋友算，然後把這個結果加上 (n-1)，就變成我想要的 1+2+…+(n-1) 了。朋友的朋友也繼續用類似的方法，直到最後一位朋友只需要回答1，接著倒數第二位朋友就把1加上2，傳給倒數第三位朋友，倒數第三位朋友加上3，一直到我收到 1+2+…+(n-1) 的結果，再加上 n，就大功告成了。

不過可能會覺得，如此簡單的問題，為何還需要遞迴呢？其實遞迴也是比較適合一些問題來解，也就是那些「解決方式一樣，但是可以化成大小比較小」的問題，除此之外還可以輕鬆解決基本問題(n=1的時候)。舉例來說，有個古老的問題叫做河內塔 (Hanoi Tower)，問題的定義引述如下 (引述網站)

1883年，一位法國的數學家 Edouard Lucas 教授在歐洲的一份雜誌上介紹了一個相當吸引人的難題──迷人的智力遊戲。這個遊戲名為河內塔 (Tower of Hanoi)，它源自古印度神廟中的一段故事 (也有一說是 Lucas 教授為增加此遊戲之神秘色彩而捏造的)。傳說在古老的印度，有一座神廟，據說它是宇宙的中心。在廟宇中放置了一塊上面插有三根長木釘的木板，在其中的一根木釘上，從上至下被放置了64片直徑由小至大的圓環形金屬片。古印度教的天神指示祂的僧侶們將64片的金屬片移至三根木釘中的其中一根上。規定在每次的移動中，只能搬移一片金屬片，並且在過程中必須保持金屬片由上至下是直徑由小至大的次序，也就是說不論在那一根木釘上，圓環形的金屬片都是直徑較小的被放在上層。直到有一天，僧侶們能將64片的金屬片依規則從指定的木釘上全部移動至另一根木釘上，那麼，世界末日即隨之來到，世間的一切終將被毀滅，萬物都將至極樂世界。

倘若這個故事的敘述為真，那麼，我們只需加速移動金屬片，是不是就能愈早到達極樂世界呢？果真要移動這64片金屬片，那麼，至少要花幾次的搬動才能完成呢？有沒有規律可循呢？

這個問題，就很符合剛才的特性：我們可以把大問題化成小問題，而且解決的方法相同，只不過問題的大小變小了。另外基本問題(n=1)，就是移動一根金屬片所需要的次數，這個我們也可以輕易解決，所以這個問題就可以用遞迴來解。

首先，我們假設有A、B、C三根柱子，這64片金屬片一開始在柱子A上面，我們想要搬到柱子C。因為問題中規定某個金屬片上面是空的時候才能移動，我們就假設有個人可以幫我們把63片比較小的金屬片先從柱子A搬到柱子B上面，然後我們把最大的那一片從柱子A搬到柱子C，再請那位朋友把剛才的63片從柱子B搬到柱子C，整個問題就解決了。然後我們只要知道剛才那位朋友搬了幾次，然後加上我們自己般動的1次，就是整個問題要求的搬動次數了。

遞迴不僅僅在數學上有其重要性，在電腦科學之中扮演的角色更是至關重要。程式設計者對於遞迴絕對不會陌生，上面所舉的河內塔問題，實際上也是電腦科學的經典例子之一，是初學程式設計的人一定會學到的東西。遞迴的思維，常常可以讓程式設計者打造出簡潔的程式，讓繁冗的問題透過簡單的程式碼來解決 (例如 parser 的設計)。演算法上所講的 dynamic programming，就是遞迴思維在演算法的具體呈現。

遞迴同時也是碎形 (fractal) 這門大學問的基石，碎形是一種相當美妙的幾何圖案，就如同上面那一張蒙娜麗莎的圖一樣，圖中有圖，形中有形，且小的部分都是大的部分的縮影，我們就稱之為碎形。碎形本身的數學定義，實際上就包含了遞迴定義在裡面，我們甚至於可以說，碎形是遞迴在幾何學的一種具體呈現。但是碎形不僅僅是一種數學概念而已，在自然界中，有許許多多的地方都出現自然的碎形，讓人讚嘆遞迴原來就出現在我們的生活周圍。圖中的這棵花椰菜，就蘊含了遞迴的碎形圖案與於其中。碎形同時也在各個研究領域有著廣泛的應用，光是在電腦科學領域，就有人把碎形應用在影像和影片壓縮之上 (這不難想像，由於碎形這種以小見大的特性，我們可以用小的來表現大的，因此可以有壓縮的概念出現)，在電腦圖學上 (computer graphics)，也有人把碎形應用在設計電腦遊戲之中的一些景物，打造出有效率和簡潔的系統。現在電腦遊戲之中的景物，很多都是玩家邊玩、遊戲系統邊產生出即時的景物，這叫做 procedural generation，這種即時產生景物的技術，可以避免遊戲軟體預先儲存一堆要展現的景物，幫整個軟體瘦身。procedural generation 就使用了大量的碎形產生與合成技術於其中，而這些都根植於遞迴這一個深刻卻簡單的思維。

至於把碎形應用在遊戲之中，現在已經做到有多可怕的地步了呢？請大家看看以下的三張圖片，不妨猜猜擁有這種精緻畫面的遊戲軟體，其整個遊戲的size大小是多少呢？

正確答案是97KB！沒錯，我沒有打錯字，你的眼睛也沒有看錯，這款遊戲的大小只有 97KB！傳統的一片 3.5 吋磁片可以裝下十幾個這款遊戲！這一款第一人稱的射擊遊戲叫做 .kkrieger，是由德國的 demogroup .theprodukkt 所開發，截至目前為止還在beta測試版的階段，這款遊戲之所以可以壓縮到這麼小的境界，就是因為遊戲之中的場景和音樂幾乎全部都是由動態產生，遊戲之中預先存放的資料只有一些簡單的幾何形狀和 MIDI 音樂檔，所以自然檔案大小非常小。如果這款遊戲沒有用 procedural generation 的技巧進來的話，估計檔案大小會爆增成 200~300MB，這樣的技術，真是令人嘆為觀止。而背後最大的功臣，就是這篇文章談到的遞迴和碎形。各位也不妨下載來玩玩看吧 (下載點)。不過需要注意到一件事情，這款遊戲的載入時間非常長，因為他要靠著一點點的程式碼即時來運算製造出場景，所以要耗去很多計算時間，這可說是一種 time 和 space 的 tradeoff。

看完這篇文章，各位有沒有對看似枯燥的數學有了一點點不同的看法呢？沒想到遞迴可以這樣應用在遊戲開發之中吧。下次學習數學感覺到枯燥時，不妨從應用的角度切入試試看吧！

过程生成简述
　　过程生成的定义可以在维基上找到：

　　http://en.wikipedia.org/wiki/Procedural_generation
　　

　　但是呢，不要把过程生成仅仅看作游戏编程里的概念。 过程生成的理念具有深远意义，比如它可以取代人类来自动的处理一些重复性的智能工作。 更加有趣的情况是，通过将自动性与一系列过程代码的集成，人们完全可以做到曾经不可想象的事情。比如最近无敌的作品《孢子》http://en.wikipedia.org/wiki/Spore_%28game%29

一下是infinity论坛的一群人关于此群聊的内容：

Freeman:
看上去“过程生成”在游戏中占很重要的地位!怎么去理解它?有没有专业解答?诚挚谢意!
Magellanic:
没有专业解答,我相信之前我给出过基本介绍.
首先,Infinity项目负责人(IA)将其描述为：
“过程生成”是一种让电脑实时或按要求的生成宇宙的技术，而不是预先制作好。因此，创造出的宇宙理所当然很大很大。数以万亿的世界，等待着冒险者们的探索，然而大多数可能永远不会被发现。
我理解为，这是一个电脑程序，它会用数学算法创造一个多变的宇宙。我相信这多变性叫做“seeds”。（译：seed？gundan
seed？我就不翻了）不同的输入会得出不同的结果。如果你十分不熟悉数学，那我就用一个简单的代数方程来解释。
5 + x = y
如果 x = 1,
那么 y = 6 如果 x = 5, 那么 y= 10
对于每一个x值，都对应着一个不同的y值，由此会得出许许多多结果。我是在ICP测试中知道的。用这个理念，我们可以创造各不相同的世界，因为我们输入了不同的数据。
而且，因为公式是不变的，只要输入相同的“seed”，就会得出相同的结果。所以，宇宙的物理参数不需要存储在你的电脑里，系统保留其特有的属性，都依赖于“seed”。
但我不是个程序员。只是个普通的玩家。如果你要更多的信息，等开IA回答吧，或用google，原谅我可能给出的错误信息。

Delver：
Hi
Freeman.我对数学不是很在行。这很伤脑筋。
我想你肯定会中文。（译：haha，被看穿了）
我不能用英语简单的叙述，我试试吧。
一个程序是一个可以用来做任何事的数学公式。像是画一个圆或三角。它同样可以用来解决复杂的问题。作出树，行星或更复杂的东西。你可以让程序记住东西将会是什么样子。现在如果你有真正复杂的事，你就会想这一定很难。用数学就可以使其更简单。电脑要做很多工作，但它确实比人工制作星球，城市简单的多。
我可以用很长时间用图画软件Photoshop或3dstudio去画一张看上去很像地球图。者要很长时间。
除了做这些，如果确实太复杂，我可以用一系列的程序来创建一个球体，然后填充如岛屿，水，空气...我怎么做呢？可以给每一样物品编上号。我可以把红色描述为数字FF0000（16进制），我可以将树描述为数字，涂上绿色0000FF。
我如果正确使用这些数字画出一个星球，我就可以做出一个同样的。如果我记得画这个星球的数字，我就可以告诉你，你也可以做出一个相同的。
简而言之：
程序是一个储存或创建数字来创造东西的数学公式或告诉你这东西是什么。你可以想像成制作东西的便宜法门。如果数字相同，公式相同，我们创造的东西也永远相同。如果我改变一点，创造出来的东西就完全不同了。

Freeman:
感谢你们Magellanic &
Delver。感谢你们现身说法。

DeAdLy_cOoKiE:
我觉得“过程生成”是在一个大空间下,所有事物都是由程序产生的.许多老套的(译:应该是old school,我讨厌学习不认真的)演示都用“过程生成”创造物体来炫耀,因为(cause,再次bs)电脑的内存在当时十分有限。当然也有用它做游戏的（特别是地图），midwinter, liberation等等。你可以通过变更参数来得出完美的效果。

Delver:
freeman，你最好再多找点资料。看看fractals（分形），这是最早的“过程生成”的图形演示。这超过我的能力了。
除了这些问题，有时我觉得这技术在未来会越来越重要。我的假设在我上个帖子写过了。什么会被刻画？什么会被创造？想象一下整个宇宙都可以随机产生！

terra0nova:
呃，“过程生成”不会储存任何数据，这正是其美丽之处，数据可能会放在内存里，但不会在硬盘上（当然要在内存里暂存，但产生出来的行星数据，不会储存，程序会决定行星的位置）给出坐标，程序（关于坐标的算法，像是伪随机算法，把坐标作为seed[译：呵呵]）就会产生出你需要的行星。行星信息可能会暂存在内存中，以防你再次来（节省时间），但你一关游戏，数据就被删除了，如果需要，将再次由程序产生数据。
最大的问题是算法的速度，如果我们要这游戏与现实时间同步（很可能你到之前，行星就已经产生好了），即使如此，这算法仍要更快更完美（可以先大致产生些数据[星球外廓]，然后再慢慢填充细节[城市和地面细节]）。我不知道这些算法的速度，但如果做得太花，速度就会慢下来。城市看上去很有趣，但我们想要更大，更科幻的。

CutterJohn:
想象一下：
假如这就是我们的过程引擎：

X = 2y
那么现在我就向在座各位解释一下我的这个微型过程引擎。
请看，如果让Y = 5 （也就是所谓的‘seed’）。
每个人都拿出计算器来算一下X是多少。都是10吧？ 如果不是，去买个新的。。。
很明显，我的“过程”引擎是很简陋的，但依然是一个不错的类比。
其实所谓的“过程”就是一堆用来计算所需答案的神奇方程式组。而游戏里的每一个客户端都内嵌了相同的方程式组。那么在给定同一个“seed”的情况下，这组方程式（完全一致的，记住）将在每一台电脑上输出一模一样的结果。这就好比你们计算如上所示的那个微型引擎必然得出相同结果一样。

本段内容出自http://www.infinity-game.com/bbs/viewthread.php?tid=491