網絡遊戲伺服器設計淺析

 談這個話題之前，首先要讓大家知道，什麼是伺服器。在中，伺服器所扮演的角色是同步，廣播和伺服器主動的一些行為，比如說天氣，NPC AI之類的，之是以現在的很多網絡遊戲伺服器都需要負擔一些遊戲邏輯上的運算是因為為了防止用戶端的作弊行為。了解到這一點，那麼本系列的文章将分為兩部分來談談網絡遊戲伺服器的設計，一部分是講如何做好伺服器的網絡連接配接，同步，廣播以及NPC的設定，另一部分則将着重談談哪些邏輯放在伺服器比較合适，并且用什麼樣的結構來安排這些邏輯。

伺服器的網絡連接配接

　　大多數的網絡遊戲的伺服器都會選擇非阻塞select這種結構，為什麼呢？因為網絡遊戲的伺服器需要處理的連接配接非常之多，并且大部分會選擇在 Linux/Unix下運作，那麼為每個使用者開一個線程實際上是很不劃算的，一方面因為在Linux/Unix下的線程是用程序這麼一個概念模拟出來的，比較消耗系統資源，另外除了I/O之外，每個線程基本上沒有什麼多餘的需要并行的任務，而且網絡遊戲是互交性非常強的，是以線程間的同步會成為很麻煩的問題。由此一來，對于這種含有大量網絡連接配接的單線程伺服器，用阻塞顯然是不現實的。對于網絡連接配接，需要用一個結構來儲存，其中需要包含一個向用戶端寫消息的緩沖，還需要一個從用戶端讀消息的緩沖，具體的大小根據具體的消息結構來定了。另外對于同步，需要一些時間校對的值，還需要一些各種不同的值來記錄目前狀态，下面給出一個初步的連接配接的結構：

typedef connection_s {

user_t *ob;

int fd;

struct sockaddr_in addr;

char text[MAX_TEXT];

int text_end;

int text_start;

int last_time;

struct timeval latency;

struct timeval last_confirm_time;

short is_confirmed;

int ping_num;

int ping_ticker;

int message_length;

char message_buf[MAX_TEXT];

int iflags;

} connection_t;

　　伺服器循環的處理所有連接配接，是一個死循環過程，每次循環都用select檢查是否有新連接配接到達，然後循環所有連接配接，看哪個連接配接可以寫或者可以讀，就處理該連接配接的讀寫。由于所有的處理都是非阻塞的，是以所有的Socket IO都可以用一個線程來完成。

　　由于網絡傳輸的關系，每次recv()到的資料可能不止包含一條消息，或者不到一條消息，那麼怎麼處理呢？是以對于接收消息緩沖用了兩個指針，每次接收都從text_start開始讀起，因為裡面殘留的可能是上次接收到的多餘的半條消息，然後text_end指向消息緩沖的結尾。這樣用兩個指針就可以很友善的處理這種情況，另外有一點值得注意的是：解析消息的過程是一個循環的過程，可能一次接收到兩條以上的消息在消息緩沖裡面，這個時候就應該執行到消息緩沖裡面隻有一條都不到的消息為止，大體流程如下：

while ( text_end – text_start > 一條完整的消息長度 )

{

從text_start處開始處理;

text_start += 該消息長度;

}

memcpy ( text, text + text_start, text_end – text_start );

　　對于消息的處理，這裡首先就需要知道你的遊戲總共有哪些消息，所有的消息都有哪些，才能設計出比較合理的消息頭。一般來說，消息大概可分為主角消息，場景消息，同步消息和界面消息四個部分。其中主角消息包括用戶端所控制的角色的所有動作，包括走路，跑步，戰鬥之類的。場景消息包括天氣變化，一定的時間在場景裡出現一些東西等等之類的，這類消息的特點是所有消息的發起者都是伺服器，廣播對象則是場景裡的所有玩家。而同步消息則是針對發起對象是某個玩家，經過伺服器廣播給所有看得見他的玩家，該消息也是包括所有的動作，和主角消息不同的是該種消息是伺服器廣播給用戶端的，而主角消息一般是用戶端主動發給伺服器的。最後是界面消息，界面消息包括是伺服器發給用戶端的聊天消息和各種屬性及狀态資訊。

　　下面來談談消息的組成。一般來說，一個消息由消息頭和消息體兩部分組成，其中消息頭的長度是不變的，而消息體的長度是可變的，在消息體中需要儲存消息體的長度。由于要給每條消息一個很明顯的區分，是以需要定義一個消息頭特有的标志，然後需要消息的類型以及消息ID。消息頭大體結構如下：

type struct message_s {

unsigned short message_sign;

unsigned char message_type;

unsigned short message_id

unsigned char message_len

}message_t;

伺服器的廣播

　　伺服器的廣播的重點就在于如何計算出廣播的對象。很顯然，在一張很大的地圖裡面，某個玩家在最東邊的一個動作，一個在最西邊的玩家是應該看不到的，那麼怎麼來計算廣播的對象呢？最簡單的辦法，就是把地圖分塊，分成大小合适的小塊，然後每次隻象周圍幾個小塊的玩家進行廣播。那麼究竟切到多大比較合适呢？一般來說，切得塊大了，記憶體的消耗會增大，切得塊小了，CPU的消耗會增大（原因會在後面提到）。個人覺得切成一屏左右的小塊比較合适，每次廣播廣播周圍九個小塊的玩家，由于廣播的操作非常頻繁，那麼遍利周圍九塊的操作就會變得相當的頻繁，是以如果塊分得小了，那麼遍利的範圍就會擴大，CPU的資源會很快的被吃完。

　　切好塊以後，怎麼讓玩家在各個塊之間走來走去呢？讓我們來想想在切換一次塊的時候要做哪些工作。首先，要算出下個塊的周圍九塊的玩家有哪些是現在目前塊沒有的，把自己的資訊廣播給那些玩家，同時也要算出下個塊周圍九塊裡面有哪些物件是現在沒有的，把那些物件的資訊廣播給自己，然後把下個塊的周圍九快裡沒有的，而現在的塊周圍九塊裡面有的物件的消失資訊廣播給自己，同時也把自己消失的消息廣播給那些物件。這個操作不僅煩瑣而且會吃掉不少CPU資源，那麼有什麼辦法可以很快的算出這些物件呢？一個個做比較？顯然看起來就不是個好辦法，這裡可以參照二維矩陣碰撞檢測的一些思路，以自己周圍九塊為一個矩陣，目标塊周圍九塊為另一個矩陣，檢測這兩個矩陣是否碰撞，如果兩個矩陣相交，那麼沒相交的那些塊怎麼算。這裡可以把相交的塊的坐标轉換成内部坐标，然後再進行運算。

　　對于廣播還有另外一種解決方法，實施起來不如切塊來的簡單，這種方法需要用戶端來協助進行運算。首先在伺服器端的連接配接結構裡面需要增加一個廣播對象的隊列，該隊列在用戶端登陸伺服器的時候由伺服器傳給用戶端，然後用戶端自己來維護這個隊列，當有人走出用戶端視野的時候，由用戶端主動要求伺服器給那個物件發送消失的消息。而對于有人總進視野的情況，則比較麻煩了。

　　首先需要用戶端在每次給伺服器發送update position的消息的時候，伺服器都給該連接配接算出一個視野範圍，然後在需要廣播的時候，循環整張地圖上的玩家，找到坐标在其視野範圍内的玩家。使用這種方法的好處在于不存在轉換塊的時候需要一次性廣播大量的消息，缺點就是在計算廣播對象的時候需要周遊整個地圖上的玩家，如果當一個地圖上的玩家多得比較離譜的時候，該操作就會比較的慢。

伺服器的同步

　　同步在網絡遊戲中是非常重要的，它保證了每個玩家在螢幕上看到的東西大體是一樣的。其實呢，解決同步問題的最簡單的方法就是把每個玩家的動作都向其他玩家廣播一遍，這裡其實就存在兩個問題：1，向哪些玩家廣播，廣播哪些消息。2，如果網絡延遲怎麼辦。事實上呢，第一個問題是個非常簡單的問題，不過之是以我提出這個問題來，是提醒大家在設計自己的消息結構的時候，需要把這個因素考慮進去。而對于第二個問題，則是一個挺麻煩的問題，大家可以來看這麼個例子：

　　比如有一個玩家A向伺服器發了條指令，說我現在在P1點，要去P2點。指令發出的時間是T0，伺服器收到指令的時間是T1，然後向周圍的玩家廣播這條消息，消息的内容是“玩家A從P1到P2” 有一個在A附近的玩家B，收到伺服器的這則廣播的消息的時間是T2，然後開始在用戶端上畫圖，A從P1到P2點。這個時候就存在一個不同步的問題，玩家A 和玩家B的螢幕上顯示的畫面相差了T2-T1的時間。這個時候怎麼辦呢？

　　有個解決方案，我給它取名叫 預測拉扯，雖然有些怪異了點，不過基本上大家也能從字面上來了解它的意思。要解決這個問題，首先要定義一個值叫：預測誤差。然後需要在伺服器端每個玩家連接配接的類裡面加一項屬性，叫latency，然後在玩家登陸的時候，對用戶端的時間和伺服器的時間進行比較，得出來的內插補點儲存在latency裡面。還是上面的那個例子，伺服器廣播消息的時候，就根據要廣播對象的latency，計算出一個用戶端的CurrentTime，然後在消息頭裡面包含這個 CurrentTime，然後再進行廣播。并且同時在玩家A的用戶端本地建立一個隊列，儲存該條消息，隻到獲得伺服器驗證就從未被驗證的消息隊列裡面将該消息删除，如果驗證失敗，則會被拉扯回P1點。然後當玩家B收到了伺服器發過來的消息“玩家A從P1到P2”這個時候就檢查消息裡面伺服器發出的時間和本地時間做比較，如果大于定義的預測誤差，就算出在T2這個時間，玩家A的螢幕上走到的地點P3，然後把玩家B螢幕上的玩家A直接拉扯到P3，再繼續走下去，這樣就能保證同步。更進一步，為了保證用戶端運作起來更加smooth，我并不推薦直接把玩家拉扯過去，而是算出P3偏後的一點P4，然後用(P4- P1)/T(P4-P3)來算出一個很快的速度S，然後讓玩家A用速度S快速移動到P4，這樣的處理方法是比較合理的，這種解決方案的原形在國際上被稱為（Full plesiochronous），當然，該原形被我篡改了很多來适應網絡遊戲的同步，是以而變成所謂的：預測拉扯。

　　另外一個解決方案，我給它取名叫 驗證同步，聽名字也知道，大體的意思就是每條指令在經過伺服器驗證通過了以後再執行動作。具體的思路如下：首先也需要在每個玩家連接配接類型裡面定義一個 latency，然後在用戶端響應玩家滑鼠行走的同時，用戶端并不會先行走動，而是發一條走路的指令給伺服器，然後等待伺服器的驗證。伺服器接受到這條消息以後，進行邏輯層的驗證，然後計算出需要廣播的範圍，包括玩家A在内，根據各個用戶端不同的latency生成不同的消息頭，開始廣播，這個時候這個玩家的走路資訊就是完全同步的了。這個方法的優點是能保證各個用戶端之間絕對的同步，缺點是當網絡延遲比較大的時候，玩家的用戶端的行為會變得比較不流暢，給玩家帶來很不爽的感覺。該種解決方案的原形在國際上被稱為（Hierarchical master-slave synchronization），80年代以後被廣泛應用于網絡的各個領域。

　　最後一種解決方案是一種理想化的解決方案，在國際上被稱為Mutual synchronization，是一種對未來網絡的前景的良好預測出來的解決方案。這裡之是以要提這個方案，并不是說我們已經完全的實作了這種方案，而隻是在網絡遊戲領域的某些方面應用到這種方案的某些思想。我對該種方案取名為：半伺服器同步。大體的設計思路如下：

　　首先用戶端需要在登陸世界的時候建立很多張廣播清單，這些清單在用戶端背景和伺服器要進行不及時同步，之是以要建立多張清單，是因為要廣播的類型是不止一種的，比如說有local message,有remote message,還有global message 等等，這些清單都需要在用戶端登陸的時候根據伺服器發過來的消息建立好。在建立清單的同時，還需要獲得每個清單中廣播對象的latency，并且要維護一張完整的使用者狀态清單在背景，也是不及時的和伺服器進行同步，根據本地的使用者狀态表，可以做到一部分決策由用戶端自己來決定，當用戶端發送這部分決策的時候，則直接将最終決策發送到各個廣播清單裡面的用戶端，并對其時間進行校對，保證每個用戶端在收到的消息的時間是和根據本地時間進行校對過的。那麼再采用預測拉扯中提到過的計算提前量，提高速度行走過去的方法，将會使同步變得非常的smooth。該方案的優點是不通過伺服器，用戶端自己之間進行同步，大大的降低了由于網絡延遲而帶來的誤差，并且由于大部分決策都可以由用戶端來做，也大大的降低了伺服器的資源。由此帶來的弊端就是由于消息和決策權都放在用戶端本地，是以給外挂提供了很大的可乘之機。

　 下面我想來談談關于伺服器上NPC的設計以及NPC智能等一些方面涉及到的問題。首先，我們需要知道什麼是NPC，NPC需要做什麼。NPC的全稱是（Non-Player Character），很顯然，他是一個character，但不是玩家，那麼從這點上可以知道，NPC的某些行為是和玩家類似的，他可以行走，可以戰鬥，可以呼吸（這點将在後面的NPC智能裡面提到），另外一點和玩家物件不同的是，NPC可以複生（即NPC被打死以後在一定時間内可以重新出來）。其實還有最重要的一點，就是玩家物件的所有決策都是玩家做出來的，而NPC的決策則是由計算機做出來的，是以在對NPC做何種決策的時候，需要所謂的NPC智能來進行決策。

　　下面我将分兩個部分來談談NPC，首先是NPC智能，其次是伺服器如何對NPC進行組織。之是以要先談NPC智能是因為隻有當我們了解清楚我們需要NPC做什麼之後，才好開始設計伺服器來對NPC進行組織。

NPC智能

　　NPC智能分為兩種，一種是被動觸發的事件，一種是主動觸發的事件。對于被動觸發的事件，處理起來相對來說簡單一些，可以由事件本身來呼叫NPC身上的函數，比如說NPC的死亡，實際上是在NPC的HP小于一定值的時候，來主動呼叫NPC身上的OnDie() 函數，這種由事件來觸發NPC行為的NPC智能，我稱為被動觸發。這種類型的觸發往往分為兩種：

一種是由别的物件導緻的NPC的屬性變化，然後屬性變化的同時會導緻NPC産生一些行為。由此一來，NPC物件裡面至少包含以下幾種函數：

class NPC {

public:

// 是誰在什麼地方導緻了我哪項屬性改變了多少。

OnChangeAttribute(object_t *who, int which, int how, int where);

Private:

OnDie();

OnEscape();

OnFollow();

OnSleep();

// 一系列的事件。

}

　　這是一個基本的NPC的結構，這種被動的觸發NPC的事件，我稱它為NPC的反射。但是，這樣的結構隻能讓NPC被動的接收一些資訊來做出決策，這樣的NPC是愚蠢的。那麼，怎麼樣讓一個NPC能夠主動的做出一些決策呢？這裡有一種方法：呼吸。那麼怎麼樣讓NPC有呼吸呢？

　　一種很簡單的方法，用一個計時器，定時的觸發所有NPC的呼吸，這樣就可以讓一個NPC有呼吸起來。這樣的話會有一個問題，當NPC太多的時候，上一次NPC的呼吸還沒有呼吸完，下一次呼吸又來了，那麼怎麼解決這個問題呢。這裡有一種方法，讓NPC異步的進行呼吸，即每個NPC的呼吸周期是根據NPC 出生的時間來定的，這個時候計時器需要做的就是隔一段時間檢查一下，哪些NPC到時間該呼吸了，就來觸發這些NPC的呼吸。

　　上面提到的是系統如何來觸發NPC的呼吸，那麼NPC本身的呼吸頻率該如何設定呢？這個就好象現實中的人一樣，睡覺的時候和進行激烈運動的時候，呼吸頻率是不一樣的。同樣，NPC在戰鬥的時候，和平常的時候，呼吸頻率也不一樣。那麼就需要一個Breath_Ticker來設定NPC目前的呼吸頻率。

　　那麼在NPC的呼吸事件裡面，我們怎麼樣來設定NPC的智能呢？大體可以概括為檢查環境和做出決策兩個部分。首先，需要對目前環境進行數字上的統計，比如說是否在戰鬥中，戰鬥有幾個敵人，自己的HP還剩多少，以及附近有沒有敵人等等之類的統計。統計出來的資料傳入本身的決策子產品，決策子產品則根據NPC 自身的性格取向來做出一些決策，比如說野蠻型的NPC會在HP比較少的時候仍然猛撲猛打，又比如說智慧型的NPC則會在HP比較少的時候選擇逃跑。等等之類的。

　　至此，一個可以呼吸，反射的NPC的結構已經基本構成了，那麼接下來我們就來談談系統如何組織讓一個NPC出現在世界裡面。

NPC的組織

　　這裡有兩種方案可供選擇，其一：NPC的位置資訊儲存在場景裡面，載入場景的時候載入NPC。其二，NPC的位置資訊儲存在NPC身上，有專門的事件讓所有的NPC登陸場景。這兩種方法有什麼差別呢？又各有什麼好壞呢？

　　前一種方法好處在于場景載入的時候同時載入了NPC，場景就可以對NPC進行管理，不需要多餘的處理，而弊端則在于在重新整理的時候是同步重新整理的，也就是說一個場景裡面的NPC可能會在同一時間内長出來。而對于第二種方法呢，設計起來會稍微麻煩一些，需要一個統一的機制讓NPC登陸到場景，還需要一些比較麻煩的設計，但是這種方案可以實作NPC異步的重新整理，是目前網絡遊戲普遍采用的方法，下面我們就來着重談談這種方法的實作：

　　首先我們要引入一個“靈魂”的概念，即一個NPC在死後，消失的隻是他的肉體，他的靈魂仍然在世界中存在着，沒有呼吸，在死亡的附近漂浮，等着到時間投胎，投胎的時候把之前的所有屬性清零，重新在場景上建構其肉體。那麼，我們怎麼來設計這樣一個結構呢？首先把一個場景裡面要出現的NPC制作成圖量表，給每個NPC一個獨一無二的辨別符，在載入場景之後，根據圖量表來載入屬于該場景的NPC。在NPC的OnDie() 事件裡面不直接把該物件destroy 掉，而是關閉NPC的呼吸，然後打開一個重生的計時器，最後把該物件設定為invisable。這樣的設計，可以實作NPC的異步重新整理，在節省伺服器資源的同時也讓玩家覺得更加的真實。

（這一章節已經牽扯到一些伺服器腳本相關的東西，是以下一章節将談談伺服器腳本相關的一些設計）

補充的談談啟發式搜尋（heuristic searching）在NPC智能中的應用。

　　其主要思路是在廣度優先搜尋的同時，将下一層的所有節點經過一個啟發函數進行過濾，一定範圍内縮小搜尋範圍。衆所周知的尋路A*算法就是典型的啟發式搜尋的應用，其原理是一開始設計一個Judge(point_t* point)函數，來獲得point這個一點的代價，然後每次搜尋的時候把下一步可能到達的所有點都經過Judge()函數評價一下，擷取兩到三個代價比較小的點，繼續搜尋，那些沒被選上的點就不會在繼續搜尋下去了，這樣帶來的後果的是可能求出來的不是最優路徑，這也是為什麼A*算法在尋路的時候會走到障礙物前面再繞過去，而不是預先就走斜線來繞過該障礙物。如果要尋出最優化的路徑的話，是不能用A*算法的，而是要用動态規劃的方法，其消耗是遠大于A* 的。

　　那麼，除了在尋路之外，還有哪些地方可以應用到啟發式搜尋呢？其實說得大一點，NPC的任何決策都可以用啟發式搜尋來做，比如說逃跑吧，如果是一個 2D的網絡遊戲，有八個方向，NPC選擇哪個方向逃跑呢？就可以設定一個Judge(int direction)來給定每個點的代價，在Judge裡面算上該點的敵人的強弱，或者該敵人的靈活如何等等，最後選擇代價最小的地方逃跑。下面，我們就來談談對于幾種NPC常見的智能的啟發式搜尋法的設計：

Target select （選擇目标）：

　　首先獲得地圖上離該NPC附近的敵人清單。設計Judge() 函數，根據敵人的強弱，敵人的遠近，算出代價。然後選擇代價最小的敵人進行主動攻擊。

Escape（逃跑）：

　　在呼吸事件裡面檢查自己的HP，如果HP低于某個值的時候，或者如果你是遠端兵種，而敵人近身的話，則觸發逃跑函數，在逃跑函數裡面也是對周圍的所有的敵人組織成清單，然後設計Judge() 函數，先選擇出對你構成威脅最大的敵人，該Judge() 函數需要判斷敵人的速度，戰鬥力強弱，最後得出一個主要敵人，然後針對該主要敵人進行路徑的Judge() 的函數的設計，搜尋的範圍隻可能是和主要敵人相反的方向，然後再根據該幾個方向的敵人的強弱來計算代價，做出最後的選擇。

Random walk（随機走路）：

　　這個我并不推薦用A*算法，因為NPC一旦多起來，那麼這個對CPU的消耗是很恐怖的，而且NPC大多不需要長距離的尋路，隻需要在附近走走即可，那麼，就在附近随機的給幾個點，然後讓NPC走過去，如果碰到障礙物就停下來，這樣幾乎無任何負擔。

Follow Target（追随目标）：

　　這裡有兩種方法，一種方法NPC看上去比較愚蠢，一種方法看上去NPC比較聰明，第一種方法就是讓NPC跟着目标的路點走即可，幾乎沒有資源消耗。而後一種則是讓NPC在跟随的時候，在呼吸事件裡面判斷對方的目前位置，然後走直線，碰上障礙物了用A*繞過去，該種設計會消耗一定量的系統資源，是以不推薦NPC大量的追随目标，如果需要大量的NPC追随目标的話，還有一個比較簡單的方法：讓NPC和目标同步移動，即讓他們的速度統一，移動的時候走同樣的路點，當然，這種設計隻适合NPC所跟随的目标不是追殺的關系，隻是跟随着玩家走而已了。

　在這一章節，我想談談關于伺服器端的腳本的相關設計。因為在上一章節裡面，談NPC智能相關的時候已經接觸到一些腳本相關的東東了。還是先來談談腳本的作用吧。

　　在基于編譯的伺服器端程式中，是無法在程式的運作過程中建構一些東西的，那麼這個時候就需要腳本語言的支援了，由于腳本語言涉及到邏輯判斷，是以光提供一些函數接口是沒用的，還需要提供一些簡單的文法和文法解析的功能。其實說到底，任何的事件都可以看成兩個部分：第一是對自身，或者别的物件的數值的改變，另外一個就是将該事件以文字或者圖形的方式廣播出去。那麼，這裡牽扯到一個很重要的話題，就是對某一物件進行尋址。恩，談到這，我想将本章節分為三個部分來談，首先是伺服器如何來管理動态建立出來的物件（伺服器記憶體管理），第二是如何對某一物件進行尋址，第三則是腳本語言的組織和解釋。其實之是以到第四章再來談伺服器的記憶體管理是因為在前幾章談這個的話，大家對其沒有一個感性的認識，可能不知道伺服器的記憶體管理究竟有什麼用。

4.1、伺服器記憶體管理

　　對于伺服器記憶體管理我們将采用記憶體池的方法，也稱為靜态記憶體管理。其概念為在伺服器初始化的時候，申請一塊非常大的記憶體，稱為記憶體池（Memory pool），同時也申請一小塊記憶體空間，稱為垃圾資源回收筒（Garbage recollecting station）。其大體思路如下：當程式需要申請記憶體的時候，首先檢查垃圾資源回收筒是否為空，如果不為空的話，則從垃圾資源回收筒中找一塊可用的記憶體位址，在記憶體池中根據位址找到相應的空間，配置設定給程式用，如果垃圾資源回收筒是空的話，則直接從記憶體池的目前指針位置申請一塊記憶體；當程式釋放空間的時候，給那塊記憶體打上已經釋放掉的标記，然後把那塊記憶體的位址放入垃圾資源回收筒。

　　下面具體談談該方法的詳細設計，首先，我們将采用類似于作業系統的段頁式系統來管理記憶體，這樣的好處是可以充分的利用記憶體池，其缺點是管理起來比較麻煩。嗯，下面來具體看看我們怎麼樣來定義頁和段的結構：

　　typedef struct m_segment_s

　　{

　　　　struct m_segment_s *next;　

　　　　struct m_segment_s *pre; int flags;　　// 該段的一些标記。

　　　　int start;　　　　　　　　　　　　　　// 相對于該頁的首位址。

　　　　int size;　　　　　　　　　　　　　　　// 長度。

　　　　struct m_page_s *my_owner;　　　　　　// 我是屬于哪一頁的。

　　　　char *data;　　　　　　　　　　　　　　// 内容指針。

　　}m_segment_t;

　　typedef struct m_page_s

　　{

　　　　unsigned int flags;　　　

　　　　int size;　　　　　　　　

　　　　int end;　　　　　　　 　

　　　　int my_index;　　　　　　

　　　　m_segment_t *segments;　　// 頁内段的頭指針。

　　}m_page_t;

　　那麼記憶體池和垃圾資源回收筒怎麼建構呢？下面也給出一些建構相關的僞代碼：

　　static m_page_t *all_pages;

　　// total_size是總共要申請的記憶體數，num_pages是總共打算建立多少個頁面。

　　void initialize_memory_pool( int total_size, int num_pages )

　　{

　　　　int i, page_size, last_size;　　　　// 算出每個頁面的大小。

　　　　page_size = total_size / num_pages;　// 配置設定足夠的頁面。

　　　　all_pages = (m_page_t*) calloc( num_pages, sizeof(m_page_t*) );

　　　　for ( i = 0; i < num_pages; i ++ )

　　　　{

　　　　　　// 初始化每個頁面的段指針。

　　　　　　all_pages[i].m_segment_t = (m_segment_t*) malloc( page_size );

　　　　　　// 初始化該頁面的标記。

　　　　　　all_pages[i].flags |= NEVER_USED;

　　　　　　// 除了最後一個頁面，其他的大小都是page_size 大小。

　　　　　　all_pages[i].size = page_size;

　　　　　　// 初始化随機通路的索引。

　　　　　　all_pages[i].my_index = i;

　　　　　　// 由于沒有用過，是以大小都是0

　　　　　　all_pages[i].end = 0;

　　　　}

　　　　// 設定最後一個頁面的大小。

　　　　if ( (last_size = total_size % num_pages) != 0 )

　　　　　　all_pages[i].size = last_size;

　　}

　　下面看看垃圾資源回收筒怎麼設計：

　　int **garbage_station;

　　void init_garbage_station( int num_pages, int page_size )

　　{

　　　　int i;

　　　　garbage_station = (int**) calloc( num_pages, sizeof( int* ) );

　　　　for ( i = 0; i < num_pages; i ++)

　　　　{

　　　　　　// 這裡用unsigned short的高8位來儲存首相對位址，低8位來儲存長度。

　　　　　　garbage_station[i] = (int*) calloc( page_size, sizeof( unsigned short ));

　　　　　　memset( garbage_station[i], 0, sizeof( garbage_station[i] ));

　　　　}

　　}

　　也許這樣的貼代碼會讓大家覺得很不明白，嗯，我的代碼水準确實不怎麼樣，那麼下面我來用文字方式來叙說一下大體的概念吧。對于段頁式記憶體管理，首先分成N個頁面，這個是固定的，而對于每個頁面内的段則是動态的，段的大小事先是不知道的，那麼我們需要回收的不僅僅是頁面的記憶體，還包括段的記憶體，那麼我們就需要一個二維數組來儲存是哪個頁面的那塊段的位址被釋放了。然後對于申請記憶體的時候，則首先檢查需要申請記憶體的大小，如果不夠一個頁面大小的話，則在垃圾資源回收筒裡面尋找可用的段空間配置設定，如果找不到，則申請一個新的頁面空間。

　　這樣用記憶體池的方法來管理整個遊戲世界的記憶體可以有效的減少記憶體碎片，一定程度的提高遊戲運作的穩定性和效率。

4.2、遊戲中物件的尋址

　　第一個問題，我們為什麼要尋址？加入了腳本語言的概念之後，遊戲中的一些邏輯物件，比如說NPC，某個ITEM之類的都是由腳本語言在遊戲運作的過程中動态生成的，那麼我們通過什麼樣的方法來對這些物件進行索引呢？說得簡單一點，就是如何找到他們呢？有個很簡單的方法，全部周遊一次。當然，這是個簡單而有效的方法，但是效率上的消耗是任何一台伺服器都吃不消的，特别是在遊戲的規模比較大之後。

　　那麼，我們怎麼來在遊戲世界中很快的尋找這些物件呢？我想在談這個之前，說一下Hash Table這個資料結構，它叫哈希表，也有人叫它散清單，其工作原理是不是順序通路，也不是随機通路，而是通過一個散列函數對其key進行計算，算出在記憶體中這個key對應的value的位址，而對其進行通路。好處是不管面對多大的資料，隻需要一次計算就能找到其位址，非常的快捷，那麼弊端是什麼呢？當兩個key通過散列函數計算出來的位址是同一個位址的時候，麻煩就來了，會産生碰撞，其的解決方法非常的麻煩，這裡就不詳細談其解決方法了，否則估計再寫個四，五章也未必談得清楚，不過如果大家對其感興趣的話，歡迎讨論。

　　嗯，我們将用散清單來對遊戲中的物件進行索引，具體怎麼做呢？首先，在記憶體池中申請一塊兩倍大于遊戲中物件總數的記憶體，為什麼是兩倍大呢？防止散清單碰撞。然後我們選用物件的名稱作為散清單的索引key，然後就可以開始設計散列函數了。下面來看個例子：

　　static int T[] =

　　{

　　　　1, 87, 49, 12, 176, 178, 102, 166, 121, 193, 6, 84, 249, 230, 44, 163,

　　　　14, 197, 213, 181, 161, 85, 218, 80, 64, 239, 24, 226, 236, 142, 38, 200,

　　　　110, 177, 104, 103, 141, 253, 255, 50, 77, 101, 81, 18, 45, 96, 31, 222,

　　　　25, 107, 190, 70, 86, 237, 240, 34, 72, 242, 20, 214, 244, 227, 149, 235,

　　　　97, 234, 57, 22, 60, 250, 82, 175, 208, 5, 127, 199, 111, 62, 135, 248,

　　　　174, 169, 211, 58, 66, 154, 106, 195, 245, 171, 17, 187, 182, 179, 0, 243,

　　　　132, 56, 148, 75, 128, 133, 158, 100, 130, 126, 91, 13, 153, 246, 216, 219,

　　　　119, 68, 223, 78, 83, 88, 201, 99, 122, 11, 92, 32, 136, 114, 52, 10,

　　　　138, 30, 48, 183, 156, 35, 61, 26, 143, 74, 251, 94, 129, 162, 63, 152,

　　　　170, 7, 115, 167, 241, 206, 3, 150, 55, 59, 151, 220, 90, 53, 23, 131,

　　　　125, 173, 15, 238, 79, 95, 89, 16, 105, 137, 225, 224, 217, 160, 37, 123,

　　　　118, 73, 2, 157, 46, 116, 9, 145, 134, 228, 207, 212, 202, 215, 69, 229,

　　　　27, 188, 67, 124, 168, 252, 42, 4, 29, 108, 21, 247, 19, 205, 39, 203,

　　　　233, 40, 186, 147, 198, 192, 155, 33, 164, 191, 98, 204, 165, 180, 117, 76,

　　　　140, 36, 210, 172, 41, 54, 159, 8, 185, 232, 113, 196, 231, 47, 146, 120,

　　　　51, 65, 28, 144, 254, 221, 93, 189, 194, 139, 112, 43, 71, 109, 184, 209,

　　};

　　// s是需要進行索引的字元串指針，maxn是字元串可能的最大長度，傳回值是相對位址。

　　inline int whashstr(char *s, int maxn)

　　{

　　　　register unsigned char oh, h;

　　　　register unsigned char *p;

　　　　register int i;

　　　　if (!*s)

　　　　　　return 0;

　　　　p = (unsigned char *) s;

　　　　oh = T[*p]; h = (*(p++) + 1) & 0xff;

　　　　for (i = maxn – 1; *p && –i >= 0; )

　　　　{

　　　　　　oh = T[oh ^ *p]; h = T[h ^ *(p++)];

　　　　}

　　　　return (oh << 8) + h;

　　}

　　具體的算法就不說了，上面的那一大段東西不要問我為什麼，這個算法的出處是CACM 33-6中的一個叫Peter K.Pearson的鬼子寫的論文中介紹的算法，據說速度非常的快。有了這個散列函數，我們就可以通過它來對世界裡面的任意物件進行非常快的尋址了。

4.3、腳本語言解釋

　　在設計腳本語言之前，我們首先需要明白，我們的腳本語言要實作什麼樣的功能？否則随心所欲的做下去寫出個C的解釋器之類的也說不定。我們要實作的功能隻是簡單的邏輯判斷和循環，其他所有的功能都可以由事先提供好的函數來完成。嗯，這樣我們就可以列出一張工作量的表單：設計物件在底層的儲存結構，提供腳本和底層間的通路接口，設計支援邏輯判斷和循環的解釋器。

　　下面先來談談物件在底層的儲存結構。具體到每種不同屬性的物件，需要采用不同的結構，當然，如果你願意的話，你可以所有的物件都采同同樣的結構，然後在結構裡面設計一個散清單來儲存各種不同的屬性。但這并不是一個好方法，過分的依賴散清單會讓你的遊戲的邏輯變得繁雜不清。是以，盡量的區分每種不同的物件采用不同的結構來設計。但是有一點值得注意的是，不管是什麼結構，有一些東西是統一的，就是我們所說的物件頭，那麼我們怎麼來設計這樣一個物件頭呢？

　　typedef struct object_head_s

　　{

　　　　char* name;

　　　　char* prog;

　　}object_head_t;

　　其中name是在散清單中這個物件的索引号，prog則是腳本解釋器需要解釋的程式内容。下面我們就以NPC為例來設計一個結構：

　　typedef struct npc_s

　　{

　　　　object_head_t header;　　　　// 物件頭

　　　　int hp;　　　　　　　　　　　// NPC的hp值。

　　　　int level;　　　　　　　 　　// NPC的等級。

　　　　struct position_s position;　// 目前的位置資訊。

　　　　unsigned int personality;　　// NPC的個性，一個unsigned int可以儲存24種個性。

　　}npc_t;

　　OK，結構設計完成，那麼我們怎麼來設計腳本解釋器呢？這裡有兩種法，一種是用虛拟機的模式來解析腳本語言，另外一中則是用類似彙編語言的那種結構來設計，設定一些條件跳轉和循環就可以實作邏輯判斷和循環了，比如：

　　set name, “路人甲”;

　　CHOOSE: random_choose_personality;　　// 随機選擇NPC的個性

　　compare hp, 100;　　　　　　　　　　　// 比較氣血，比較出的值可以放在一個固定的變量裡面

　　ifless LESS;　　　　　　　　　　　　　// hp < 100的話，則傳回。

　　jump CHOOSE;　　　　　　　　　　　　　// 否則繼續選擇，隻到選到一個hp < 100的。

　　LESS: return success;

　　這種腳本結構就類似CPU的指令的結構，一條一條指令按照順序執行，對于腳本程式員（Script. Programmer）也可以培養他們彙編能力的說。

　　那麼怎麼來模仿這種結構呢？我們拿CPU的指令做參照，首先得設定一些寄存器，CPU的寄存器的大小和數量是受硬體影響的，但我們是用記憶體來模拟寄存器，是以想要多大，就可以有多大。然後提供一些指令，包括四則運算，尋址，判斷，循環等等。接下來針對不同的腳本用不同的解析方法，比如說對NPC就用 NPC固定的腳本，對ITEM就用ITEM固定的腳本，解析完以後就把結果生成底層該物件的結構用于使用。

　　而如果要用虛拟機來實作腳本語言的話呢，則會将工程變得無比之巨大，強烈不推薦使用，不過如果你想做一個通用的網絡遊戲底層的話，則可以考慮設計一個虛拟機。虛拟機大體的解釋過程就是進行兩次編譯，第一次對關鍵字進行編譯，第二次生成彙編語言，然後虛拟機在根據編譯生成的彙編語言進行逐行解釋，如果大家對這個感興趣的話，可以去www.mudos.org上下載下傳一份MudOS的原碼來研究研究。