前言

作為一個(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é)算法針對GPU編程的。客戶端邏輯的編寫也會用到一些算法，比如拋物線算法，曲線插值算法，A＊尋路算法等等。算法的優(yōu)勢主要體現(xiàn)在游戲核心功能和效率優(yōu)化上面，作為IT程序員來說，如果對算法不精通，或者不知道如何在程序中使用算法，隨著時(shí)間的推移會逐步被行業(yè)淘汰。當(dāng)然大家也不必為此擔(dān)心，筆者在此總結(jié)了學(xué)習(xí)算法必經(jīng)之路的三個(gè)主要階段。

第一階段 基礎(chǔ)篇

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

以二叉樹為例，介紹其在游戲開發(fā)中使用的案例，二叉樹在圖論中是這樣定義的：二叉樹是一個(gè)連通的無環(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)存用于存儲大圖片，然后新建一個(gè)空的二叉樹，把小圖片看作是二叉樹的子節(jié)點(diǎn)，依次去掛載到二叉樹的葉子節(jié)點(diǎn)上，掛接的順序采用的是先序遍歷的思想，這樣一張圖集就生成了。如果本階段的知識點(diǎn)讀者已經(jīng)掌握了可以直接略過，接下來進(jìn)入第二階段進(jìn)階篇。

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

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

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

第一步、設(shè)定最大遞歸深度；

第二步、找出場景的最大尺寸，并以此尺寸建立第一個(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ù)目還是一樣，會造成無窮切割的情形；

第六步、重復(fù)3步驟，直到達(dá)到最大遞歸深度。

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

一、用其加速用于可見性判斷的視錐裁剪；

二、加速射線投射，如用作視線判斷或槍擊判定；

三、鄰近查詢，如查詢玩家角色某半徑范圍內(nèi)的敵方NPC；

四、碰撞檢測的粗略階段，找出潛在可能碰撞的物體對。

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

第三階段 提高篇

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

《Mathematics for 3D Game Programming and Computer Graphics》和《Real-Time Rendering》這兩本書相對來說比較難。但是寫的非常好，有助于提升技術(shù)水平。市面上比較知名的引擎都使用了GPU編程技術(shù)，這些技術(shù)算法主要包含：PSSM算法、SSAO算法、Bloom算法、Blur算法、HDR算法、Deferred算法等，它們也是引擎的核心算法。

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

視錐體分割效果圖：
?

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

渲染分解效果圖：
?

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

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

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

后來筆者獨(dú)立寫過幾款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í)不是一朝一夕的，只要找對學(xué)習(xí)方法，分階段學(xué)習(xí)，持之以恒，相信隨著經(jīng)驗(yàn)的積累將來在IT“武林“真的可以獨(dú)步天下，以此文與讀者共勉。

總結(jié)

以上是生活随笔為你收集整理的游戏与算法的必经之路的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。