前言

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

第一階段 基礎篇

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

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

第二階段 進階篇

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

下面以八叉樹算法為例給讀者介紹其應用，八叉樹（octree）是三維空間劃分的數據結構之一，它用于加速空間查詢， Octree的實現原理主要分為六步：

• 第一步、設定最大遞歸深度；
• 第二步、找出場景的最大尺寸，并以此尺寸建立第一個立方體；
• 第三步、依序將單位元素丟入能被包含且沒有子節(jié)點的立方體
• 第四步、若沒有達到最大遞歸深度，就進行細分八等份，再將該立方體所裝的單位元元素全部分擔給八個子立方體；
• 第五步、若發(fā)現子立方體所分配到的單位元元素數量不為零且跟父立方體是一樣的，則該子立方體停止細分，因為跟據空間分割理論，細分的空間所得到的分配必定較少，若是一樣數目，則再怎么切數目還是一樣，會造成無窮切割的情形；
• 第六步、重復3步驟，直到達到最大遞歸深度；

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

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

實現的八叉樹效果圖展示如下所示：

第三階段 提高篇

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

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

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

視錐體分割效果圖

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

渲染分解效果圖

上圖的處理流程首先是場景中的燈光照射到需要投影的物體上，接下來程序對投影的物體頂點進行矩陣變換將其轉換到投影空間中，再轉換到裁剪空間進行視口的平行分割，最后將其分別渲染出來。原理清楚了代碼編寫就很簡單了，具體代碼讀者可以查看《手把手教你架構3D游戲引擎》一書，下面給讀者展示效果圖如下所示：

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

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

后來筆者獨立寫過幾款3D引擎包括：3D渲染引擎，海水渲染引擎，物理引擎等。現將實現的效果給讀者展示如下：

海水渲染反射折射效果

實時航行軌跡模果

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

點此查看作者有關《【系列直播】算法與游戲實戰(zhàn)技術》經驗分享