程序生成

**程序生成**（；參照）係電腦科學上嘅一個概念，指靠演算法產生數據，相對於要電腦死記住一拃數據。舉個具體例子：想像一隻電子遊戲，遊戲程式入邊有若干關；典型嘅廿世紀遊戲程式，做法會係要部電腦死記住每關地圖係咩樣；相比之下，用程序生成嘅遊戲就唔同－噉嘅遊戲程式會同每關記住一段演算法，玩家開嗰關嚟玩嘅時候，遊戲程式會即場用演算法產生一幅地圖。呢啲演算法可以有隨機性，噉次次產生地圖嗰陣，出嘅地圖都會有少少唔同樣。

程序生成喺廿一世紀初嘅遊戲設計上幾受注目，被指會有效提升一隻遊戲嘅重玩價值：重玩價值係指隻遊戲有幾能夠吸引玩家玩完再重新玩過；如果一隻遊戲用帶有隨機性嘅程序生成演算法嚟產生關卡，就可以令到玩家每次重玩嗰陣更有新鮮感，令佢哋更加有可能願意重玩。呢種做法喺開放世界遊戲同生存遊戲等要求玩家探索遊戲世界嘅遊戲類型當中零舍常見，實際嘅例子可以睇睇《做個創世神》呢件作品。

除咗遊戲，程序生成喺電腦圖像等嘅電腦相關領域上都有用，例如用程序生成造出嚟嘅快勞往往會細過一般嘅快勞－用程序生成嘅話，部電腦淨係需要記住一段源碼，有需要嗰陣即場用段碼砌拃數據出嚟，而唔使好似一般做法噉，死記住大拃數據。
## 遊戲製作

### 產生關卡

喺遊戲設計上，程序生成一個常見應用係用嚟整關卡地圖。

喺好多類型嘅遊戲入面，玩家都要控制住玩家角色過若干關，每關都有一啲可以引致玩家角色死亡嘅嘢，而如果玩家成功過嗮咁多關，就算係打爆機；廿世紀電子遊戲設計嘅做法主流係，由遊戲設計師諗好嗮每一關嘅地圖係點嘅樣，並且要個遊戲程式死記住每一關嘅地圖；但由廿世紀尾開始，唔少遊戲設計方面嘅工作者都覺得呢種做法有個問題，就係唔能夠令一隻遊戲有高嘅重玩價值－重玩價值係遊戲設計上嘅一個概念，如果話一隻遊戲有高嘅重玩價值，意思係話隻遊戲能夠吸引玩家玩完又玩，而一般遊戲設計師都希望自己設計嘅遊戲有高嘅重玩價值，而如果有方法令玩家每次玩一關嗰陣，嗰一關都會有少少唔同樣，就可以令玩家更加有新鮮感，提升隻遊戲嘅重玩價值。於是有人就提出運用程序生成整關卡－將一個遊戲程式設成 foreach 關卡記住一段演算法，每一關嘅相應演算法當中有隨機性，就可以做到「每次重玩一關嗰時，嗰關都會有少少唔同樣」嘅效果。

一般嚟講，一個用程序生成整遊戲內容嘅程式最基本會有以下部份：
#生成遊戲內容；途中會用到隨機數生成（RNG）。
#用某啲演算法評估個內容啱唔啱用，例：用程序生成產生一個關卡，再睇吓呢一個關卡係咪有可能過得到嘅（因為個演算法可能有時會意外產生一個根本冇可能過到嘅關卡）；
#如果步驟 2 嘅分析顯示個內容有問題，返去步驟 1；
#如果步驟 2 嘅分析顯示個內容冇問題，攞個內容去用。

以下嘅 C＃ 碼可以用嚟喺遊戲空間當中產生幾間相連嘅房：


```csharp
class Room extends Sprite {
    // 一柞變數表示間房嘅坐標位置。
    public var x1:Int;
    public var x2:Int;
    public var y1:Int;
    public var y2:Int;
 
    // 變數表示間房嘅長同闊。
    public var w:Int;
    public var h:Int;
 
    // 變數表示間房嘅中心點。
    public var center:Point;
 
    // 產生一間新嘅四方形房。
    public function new(x:Int, y:Int, w:Int, h:Int) {　// 攞四個整數做輸入。呢四個數字可以用隨機數產生法產生。
        super();
 
        x1 = x;
        x2 = x + w;
        y1 = y;
        y2 = y + h;
        this.x = x * Main.TILE_WIDTH;
        this.y = y * Main.TILE_HEIGHT;
        this.w = w;
        this.h = h;
        center = new Point(Math.floor((x1 + x2) / 2), // 用簡單嘅幾何原理，由間房嘅坐標位置計出佢中心點嘅坐標。
            Math.floor((y1 + y2) / 2));
    }
 
    // 睇吓間房有冇同第間房相交（檢查吓個內容有冇問題），如果有，呢個子程序會俾 true 做輸出。
    public function intersects(room:Room):Bool {
        return (x1 <= room.x2 && x2 >= room.x1 &&
            y1 <= room.y2 && room.y2 >= room.y1);
    }
}
```


「用程序生成產生關卡地圖」呢家嘢常見於開放世界遊戲同生存遊戲等有探索性質嘅遊戲類型。例如係《無人深空》呢隻喺 2016 年出嘅 PS4 遊戲噉：隻遊戲屬生存遊戲，講玩家探索外太空；成隻遊戲裏面有一個廣闊嘅宇宙俾玩家探索，呢個宇宙入面有無數咁多粒行星可以俾玩家去，而每粒行星上嘅地形、氣候同有嘅生命體都唔同；個遊戲程式嘅做法係，用一個擬亂數產生器每當有玩家要喺一粒行星上降落嗰陣即場產生粒行星，並且記住粒行星（另外一個玩家去到嗰粒行星見到嘅嘢會同第一個玩家去嗰粒行星見到嘅一樣），最後形成一個有多個玩家同時喺度探索嘅虛擬星系，而且玩家彼此之間可以分享有關「邊度邊度有粒點嘅行星」等嘅知識－令玩家更加有「自己真係探索緊太空」嘅感覺。

亦有種做法係攞程序生成演算法產生若干個板，然後設計師揀其中一個板嚟做關卡最後個樣。最後隻遊戲入面嗰關次次玩親都係嗰個樣。

### 掠奪品

又有啲遊戲會用程序生成產生玩家可以得到嘅掠奪品。掠奪品泛指玩家可以由遊戲環境嗰度攞嘅道具，可以做到俾玩家一路通過關卡一路慢慢變強（手上嘅槍炮愈嚟愈勁）嘅效果；例如喺《邊緣禁地系列》呢隻動作 RPG 入面，玩家會一路通過一個關卡一路用槍炮同敵人戰鬥，而途中可能會透過打低敵人或者搵到寶箱等嘅方法得到掠奪品，掠奪品包括咗武器或者裝甲等，而喺呢隻遊戲入面，啲槍炮係用程序生成產生嘅－每把槍炮都有若干個屬性，例如係火力同類型（手槍、散彈槍同狙擊槍等），而每當一個玩家將要得到掠奪品嗰陣，遊戲都會隨機噉揀選一把槍嘅屬性，並且即場砌一把槍出嚟，而喺個系列嘅第一作當中，一把用呢種方法產生嘅槍炮總共有成 17,750,000 個可能嘅款。

### 設計討論
用咗程序生成嘅遊戲，包括以下呢啲：
*《做個創世神》（2009 年）、
*《文明帝國系列》（首作出於 1991 年）、
*《無人深空》（2016 年）、
*《孢子》（2008 年）、
*《傭兵戰場》（2000 年）
... 等等。

有遊戲設計師指出，有隨機性嘅程序生成唔保證一定能夠令一隻遊戲有高嘅重玩價值，因為就算兩嚿物體唔同，如果佢哋之間嘅差異唔重要唔明顯，噉對用家嚟講兩嚿物體基本上一樣。例如喺 2016 年，有遊戲設計研究者喺遊戲製作雜誌 Gamasutra 嗰度撰文，以《無人深空》做例子：
粵語翻譯：「每粒行星都獨一無二」（呢句嘢）意思可以係話每一粒行星都有一個複雜嘅科幻背景故仔，（每個呢啲故仔嘅內容）豐富到可以填滿一集兩部份嘅《星空奇遇記》（對玩家嚟講有趣嘅獨特性）。但呢句嘢意思又可以係話喺數學上嚟講，粒行星上某處有嚿岩石係宇宙入面冇任何一嚿岩石同佢一樣樣嘅（對玩家嚟講唔有趣嘅獨特性）。啲人用起「獨一無二」呢個詞嗰陣，幾乎永遠都係用緊個字最弱、最技術上正確嘅意思。

## Roguelike

Roguelike（大致）可以話係基於程序生成嘅一種電子遊戲類型。Roguelike 係一類遊戲，受到桌上 RPG 龍與地下城（D&D）影響，玩迷宮探索嘅。呢種電子遊戲類型好大程度上源自 1980 年出嘅《Rogue》（英文 **roguelike** 意思正正就係「好似 Rogue 噉嘅」噉解），具有以下嘅特性：
*行回合制；
*地圖分做一格格；
*用永久死亡機制；
*用程序生成產生關卡；
*遊戲嘅故仔通常會用奇幻嘅美學設計。
等等。當中「用咗程序生成」可以話係 roguelike 最重要嘅特徵－Roguelite（**lite** 嚟自英文 **light**，意思係形容詞**輕**噉解）係指**輕度 roguelike**，即係指隻遊戲有某啲 roguelike 特徵，但有唔齊。就算係 roguelite 遊戲基本上都實會有程序生成，例子可以睇吓用咗程序生成產生關卡嘅動作 RPG 系列《暗黑破壞神》。

## 體驗主導

程序生成可以配合玩家體驗模擬（PEM）嚟用：遊戲製作最重要嘅目的係要令玩家開心過癮；電子遊戲 AI 嘅技術可以用嚟建立數學模型模擬玩家體驗，呢啲模型一般會攞描述遊戲參數嘅變數做 `input`，即係例如係關卡參數（有幾多敵人、幾長...）同遊戲畫面呀噉，而 `output` 就係（個模型所預測嘅）玩家體驗，用「玩完之後，彈個視窗出嚟問佢哋 1 至 10 分會俾隻遊戲幾多分」等嘅方法量度；然後研究者可以例如用監督式學習訓練人工神經網絡由遊戲參數預測玩家體驗；如果順利嘅話，個模型可以話到俾製作組聽，「如果隻遊戲係噉噉噉樣，玩家嘅體驗會係噉噉噉樣」嘅資訊。呢種建構模型嚟預測玩家體驗嘅做法，就係所謂嘅玩家體驗模擬。

**體驗主導程序內容生成**係指用玩家體驗模擬主導遊戲嘅程序生成：舉個簡單例子說明，遊戲設計師可以將隻遊戲設計成噉：
#Foreach 玩家，用程序生成演算法產生關卡地圖，而段演算法有一啲可調節嘅參數（例如**敵人之間嘅平均距離**）；
#用玩家體驗模擬推算玩家會有幾過癮；
#以呢個數字（f）同第啲指標做基準，衡量嗰柞演算法參數（一個陣列嘅數值）有幾「好」；
#重複。
f 呢個數字就可以（例如）做進化演算法上嘅適應度數值，代表邊一柞參數數值先係「理想」。不過呢種做法吓吓都要玩家俾反應，可以會搞到玩家覺得煩，所以遊戲製作界仲有諗第啲方法用嚟評估玩家有幾鍾意一個用程序生成產生嘅遊戲內容。

## 睇埋

*隨機同隨機數生成
*馬可夫決策過程
*遊戲副本
*打機用語
*生成藝術
*動態難度調控

## 文獻
英文文獻：

*Ebert, David S.; Musgrave, F. Kenton; Peachey, Darwyn; Perlin, Ken; Worley, Steve (2002). *Texturing and Modeling: A Procedural Approach (3rd ed.)*. Morgan Kaufmann. ISBN 978-1-558-60848-1.
*Liapis, A., Yannakakis, G. N., & Togelius, J. (2012). Adapting models of visual aesthetics for personalized content creation (PDF). *IEEE Transactions on Computational Intelligence and AI in Games*, 4(3), 213-228.
*Shaker, Noor; Togelius, Julian; Nelson, Mark J. (2016). *Procedural Content Generation in Games: A Textbook and an Overview of Current Research*. Springer. ISBN 978-3-319-42714-0.
*Smith, G. (2015, June). An Analog History of Procedural Content Generation (PDF). In *FDG*.
*Yannakakis, G. N., & Togelius, J. (2011). Experience-driven procedural content generation. IEEE Transactions on Affective Computing (PDF), 2(3), 147-161.
*Raouf's Blog (GitHub). Perlin Noise: A Procedural Generation Algorithm：呢篇文講程序生成可以點樣配合柏林雜音嚟用，產生出望落自然（唔完美跟從規律但又唔係完全隨機）嘅花臣。簡化講，要望落自然，重點係每一點嘅值都要同佢附近啲點嘅值相似。


## 註釋

## 引咗
篇文引用咗嘅文獻同網頁，有以下呢啲：

## 外拎
* 程序生成 Wiki
* 波函數崩塌 Python 教學，依篇文講到所謂嘅「波函數崩塌」演算法。段演算法有用到資訊熵嘅概念。
* 程序生成地下迷城. *Gamasutra*.
* 內容嘅未來，Game Developers Conference 2005.
* 實時程序宇宙，講到用程序生成產生虛擬行星。
* 鬼船公司甲舨下談：銀河洞穴大冒險當中嘅山窿生成，講到《銀河洞穴大冒險》裡便用程序生成嚟產生虛擬嘅礦洞。