前言

作為一個(gè)在IT行業(yè)工作十五年的老兵，筆者在這里將自己多年的學(xué)習(xí)游戲算法經(jīng)驗(yàn)分享給讀者，希望能夠幫助那些想學(xué)習(xí)算法提升自己的讀者。算法是IT產(chǎn)品研發(fā)的核心，在IT的任何領(lǐng)域都離不開算法，目前比較流行的IT領(lǐng)域有：大數(shù)據(jù)，人工智能，深度學(xué)習(xí)，游戲開發(fā)，虛擬現(xiàn)實(shí)，增強(qiáng)現(xiàn)實(shí)等，這些領(lǐng)域的核心都是算法，可見算法在IT領(lǐng)域的重要性。本文主要聚焦游戲算法，游戲開發(fā)不外乎3D引擎接口調(diào)用和游戲邏輯編寫，3D游戲引擎的主要功能是渲染，渲染使用的是圖形學(xué)算法針對(duì)GPU編程的。客戶端邏輯的編寫也會(huì)用到一些算法，比如拋物線算法，曲線插值算法，A＊尋路算法等等。算法的優(yōu)勢(shì)主要體現(xiàn)在游戲核心功能和效率優(yōu)化上面，作為IT程序員來(lái)說(shuō)，如果對(duì)算法不精通，或者不知道如何在程序中使用算法，隨著時(shí)間的推移會(huì)逐步被行業(yè)淘汰。當(dāng)然大家也不必為此擔(dān)心，筆者在此總結(jié)了學(xué)習(xí)算法必經(jīng)之路的三個(gè)主要階段。

第一階段 基礎(chǔ)篇

對(duì)于初始學(xué)習(xí)算法的讀者，首先要把基礎(chǔ)算法學(xué)好，也就是把大廈的地基要打牢，毛澤東說(shuō)過(guò)“理論聯(lián)系實(shí)際”，學(xué)習(xí)算法先要把理論知識(shí)學(xué)好，給讀者推薦的學(xué)習(xí)資料是大學(xué)的經(jīng)典課程《數(shù)據(jù)結(jié)構(gòu)與算法》，涉及到的主要知識(shí)點(diǎn)有：快速排序，二叉樹排序，二分查找，哈希表，二叉樹等。掌握這些數(shù)據(jù)結(jié)構(gòu)并能運(yùn)用它們解決實(shí)際問(wèn)題，千萬(wàn)不要死記硬背，親自動(dòng)手將算法書寫一遍，編程的過(guò)程就是要反復(fù)的練習(xí)。另外，還要學(xué)習(xí)一些關(guān)于矩陣、向量運(yùn)算的知識(shí)點(diǎn)，這些知識(shí)點(diǎn)也是游戲開發(fā)必備的。給讀者推薦的資料是大學(xué)課程《線性代數(shù)》。掌握這些知識(shí)的方法就是讀者都要?jiǎng)邮謱⑺鼈冎鹦写a敲一遍并且用腦子反復(fù)琢磨領(lǐng)會(huì)貫通。

以二叉樹為例，介紹其在游戲開發(fā)中使用的案例，二叉樹在圖論中是這樣定義的：二叉樹是一個(gè)連通的無(wú)環(huán)圖，并且每一個(gè)頂點(diǎn)的度不大于3。有根二叉樹還要滿足根結(jié)點(diǎn)的度不大于2。有了根結(jié)點(diǎn)之后，每個(gè)頂點(diǎn)定義了唯一的父結(jié)點(diǎn)，和最多2個(gè)子結(jié)點(diǎn)。它在游戲中應(yīng)用案例給讀者介紹一下，在游戲開發(fā)中經(jīng)常使用圖集，就是把多張小圖片合成一張大的圖片一次性加載到內(nèi)存中，優(yōu)化了內(nèi)存加載效率，生成圖集的算法就是用二叉樹算法實(shí)現(xiàn)的，算法流程就是首先生成一塊內(nèi)存用于存儲(chǔ)大圖片，然后新建一個(gè)空的二叉樹，把小圖片看作是二叉樹的子節(jié)點(diǎn)，依次去掛載到二叉樹的葉子節(jié)點(diǎn)上，掛接的順序采用的是先序遍歷的思想，這樣一張圖集就生成了。如果本階段的知識(shí)點(diǎn)讀者已經(jīng)掌握了可以直接略過(guò)，接下來(lái)進(jìn)入第二階段進(jìn)階篇。

第二階段 進(jìn)階篇

在進(jìn)階篇階段是學(xué)習(xí)一些相對(duì)基礎(chǔ)篇比較復(fù)雜的算法，進(jìn)階篇的算法主要包括：A*算法，八叉樹算法，Perlin噪音等，筆者建議學(xué)習(xí)的資料是關(guān)于游戲編程方面的書籍《游戲編程大師技巧》（上下冊(cè)）這兩本書非常經(jīng)典，雖然其接口有些舊，但里面的編程理論非常適用游戲開發(fā)，筆者利用它的編程思想編寫了一本適合初學(xué)者學(xué)習(xí)的《手把手教你架構(gòu)3D游戲引擎》一書。

下面以八叉樹算法為例給讀者介紹其應(yīng)用，八叉樹（octree）是三維空間劃分的數(shù)據(jù)結(jié)構(gòu)之一，它用于加速空間查詢， Octree的實(shí)現(xiàn)原理主要分為六步：

• 第一步、設(shè)定最大遞歸深度；
• 第二步、找出場(chǎng)景的最大尺寸，并以此尺寸建立第一個(gè)立方體；
• 第三步、依序?qū)挝辉貋G入能被包含且沒有子節(jié)點(diǎn)的立方體
• 第四步、若沒有達(dá)到最大遞歸深度，就進(jìn)行細(xì)分八等份，再將該立方體所裝的單位元元素全部分擔(dān)給八個(gè)子立方體；
• 第五步、若發(fā)現(xiàn)子立方體所分配到的單位元元素?cái)?shù)量不為零且跟父立方體是一樣的，則該子立方體停止細(xì)分，因?yàn)楦鷵?jù)空間分割理論，細(xì)分的空間所得到的分配必定較少，若是一樣數(shù)目，則再怎么切數(shù)目還是一樣，會(huì)造成無(wú)窮切割的情形；
• 第六步、重復(fù)3步驟，直到達(dá)到最大遞歸深度；

給讀者舉個(gè)游戲案例，假設(shè)：我們有一個(gè)大的房間，房間里某個(gè)角落站了一只小動(dòng)物，我們想很快的把小動(dòng)物找出來(lái)，該如何做？我們可以把房間當(dāng)成一個(gè)立方體，先切成八個(gè)小立方體，?然后排除掉沒有放任何東西的小立方體，再把有可能藏小動(dòng)物的小立方體繼續(xù)切八?等份….如此下去，平均在Log8(房間內(nèi)的所有物品數(shù))的時(shí)間內(nèi)就可找到小動(dòng)物。?因此，八叉樹就是用在3D空間中的場(chǎng)景管理，可以很快地知道物體在3D場(chǎng)景中的位置，或偵測(cè)與其它物體是否有碰撞以及是否在可視范圍內(nèi)。進(jìn)而八叉樹的應(yīng)用場(chǎng)景可以推廣到解決如下技術(shù)問(wèn)題：

• 一、用其加速用于可見性判斷的視錐裁剪；
• 二、加速射線投射，如用作視線判斷或槍擊判定；
• 三、鄰近查詢，如查詢玩家角色某半徑范圍內(nèi)的敵方NPC；
• 四、碰撞檢測(cè)的粗略階段，找出潛在可能碰撞的物體對(duì)；

實(shí)現(xiàn)的八叉樹效果圖展示如下所示：

第三階段 提高篇

掌握了第二階段的學(xué)習(xí)后，接下來(lái)到了真正的提高篇，也就是“武林秘籍”的最高境界。提高篇主要是學(xué)習(xí)圖形學(xué)算法編程，推薦給讀者學(xué)習(xí)的書籍是：

《Mathematics for 3D Game Programming and Computer Graphics》和《Real-Time
Rendering》這兩本書相對(duì)來(lái)說(shuō)比較難。但是寫的非常好，有助于提升技術(shù)水平。市面上比較知名的引擎都使用了GPU編程技術(shù)，這些技術(shù)算法主要包含：PSSM算法、SSAO算法、Bloom算法、Blur算法、HDR算法、Deferred算法等，它們也是引擎的核心算法。
點(diǎn)此查看作者有關(guān)《【系列直播】算法與游戲?qū)崙?zhàn)技術(shù)》經(jīng)驗(yàn)分享。

以PSSM算法為例，給讀者分享一下應(yīng)用案例，如何在游戲中使用，首先要了解其原理：PSSM全稱 Parallel-Split Shadow Map
PSSM算法的核心就是把視椎體進(jìn)行分割，然后分別渲染組合。語(yǔ)言講解不如看圖直觀，先通過(guò)視錐體分割說(shuō)起。效果如下圖所示：

視錐體分割效果圖

PSSM實(shí)時(shí)陰影的繪制首先需要燈光，在現(xiàn)實(shí)生活中，白天只有太陽(yáng)出來(lái)了才可以看到影子。在虛擬世界中也是一樣的，場(chǎng)景使用的是Directional（平行光）相當(dāng)于現(xiàn)實(shí)世界的太陽(yáng)光。上圖左邊部分顯示的是視景體的投影，利用PSSM算法將其平行的分割成多個(gè)部分，然后對(duì)每個(gè)部分進(jìn)行渲染，分割成的塊數(shù)是可以自己設(shè)置的。右半部分是頂視角觀看的分割效果，把物體分成三塊進(jìn)行實(shí)時(shí)陰影的渲染。渲染的計(jì)算是GPU中執(zhí)行的，在GPU中執(zhí)行的流程如下圖所示：

渲染分解效果圖

上圖的處理流程首先是場(chǎng)景中的燈光照射到需要投影的物體上，接下來(lái)程序?qū)ν队暗奈矬w頂點(diǎn)進(jìn)行矩陣變換將其轉(zhuǎn)換到投影空間中，再轉(zhuǎn)換到裁剪空間進(jìn)行視口的平行分割，最后將其分別渲染出來(lái)。原理清楚了代碼編寫就很簡(jiǎn)單了，具體代碼讀者可以查看《手把手教你架構(gòu)3D游戲引擎》一書，下面給讀者展示效果圖如下所示：

下面筆者分享一下學(xué)習(xí)算法的感受，剛踏入IT行業(yè)時(shí)也不會(huì)算法編程，對(duì)算法有一種恐懼感，總感覺算法很神秘，更不知道如何使用，自己為此也苦惱過(guò)。剛?cè)肼毠镜臅r(shí)候跟大多數(shù)程序員一樣寫寫邏輯，兩年后，自己感覺水平也比較牛了。為此，自己申請(qǐng)加入到公司核心部門引擎部，初衷就是看看引擎組都做些什么事情，當(dāng)然也是想學(xué)習(xí)一些知識(shí)為了跳槽漲工資。

加入引擎組后，經(jīng)歷了一件事情徹底改變了我，更讓我認(rèn)識(shí)到算法的重要性。事情是這樣的，端游中實(shí)現(xiàn)的刀光拖尾算法，功能包括：取樣插值并且實(shí)現(xiàn)材質(zhì)的扭曲效果，當(dāng)時(shí)接到任務(wù)一下子就懵了，在網(wǎng)上不停的翻資料，那時(shí)網(wǎng)上沒有這方面的技術(shù)實(shí)現(xiàn)，最后只能硬著頭皮自己動(dòng)手寫了，經(jīng)過(guò)一周的折騰，選擇了B樣條曲線插值算法，再經(jīng)過(guò)一周將其實(shí)現(xiàn)了出來(lái)，最后一周的時(shí)間，度日如年，晚上基本上都沒睡好，做夢(mèng)都想著如何實(shí)現(xiàn)算法。有時(shí)自己都想離職走人了，感覺壓力太大了，但是最終還是實(shí)現(xiàn)出來(lái)了。經(jīng)歷過(guò)這段刻骨寧心的經(jīng)歷，讓我明白了算法是如何與游戲開發(fā)相結(jié)合的，也讓我明白了自己算法知識(shí)的薄弱，需要從頭開始把算法學(xué)好，最終我也是按照上面這三個(gè)階段學(xué)習(xí)的。在學(xué)習(xí)算法的過(guò)程中痛并快樂(lè)著，學(xué)習(xí)算法首先要明白其原理，然后再用代碼敲一遍實(shí)現(xiàn)出來(lái)，切記眼高手低。

后來(lái)筆者獨(dú)立寫過(guò)幾款3D引擎包括：3D渲染引擎，海水渲染引擎，物理引擎等。現(xiàn)將實(shí)現(xiàn)的效果給讀者展示如下：

海水渲染反射折射效果

實(shí)時(shí)航行軌跡模果

最后給讀者一個(gè)建議：學(xué)習(xí)算法關(guān)鍵是我們要有一個(gè)正確的學(xué)習(xí)方法再結(jié)合著實(shí)戰(zhàn)項(xiàng)目就可以快速的提升自己的技戰(zhàn)水平。算法的學(xué)習(xí)不是一朝一夕的，只要找對(duì)學(xué)習(xí)方法，分階段學(xué)習(xí)，持之以恒，相信隨著經(jīng)驗(yàn)的積累將來(lái)在IT“武林“真的可以獨(dú)步天下，以此文與讀者共勉。

點(diǎn)此查看作者有關(guān)《【系列直播】算法與游戲?qū)崙?zhàn)技術(shù)》經(jīng)驗(yàn)分享