第三部分：核心遊戲程式設計
第11章 算法、資料結構、記憶體管理和多線程
第12章 人工智能
第13章 遊戲實體
第14章 文字時代
第15章 綜合運用：編寫遊戲！
第11章 算法、資料結構、記憶體管理和多線程
"You think I can get a hug after this?"
—Bear, Armageddon（電影《世界末日》）
本章将讨論在其他遊戲程式設計參考書常常會中疏漏的細節問題。我們将涉及編寫可儲存進度的遊戲、示範的制作、優化理論等所有内容。本章将幫您掌握這些必需的程式設計細節。這樣，當我們在下一章讨論人工智能的時候，你已很好地掌握了一些遊戲程式設計的一般概念，甚至連3D運算都不再能難倒你！
本章主要内容如下：
? 資料結構
? 算法分析
? 優化理論
? 數學運算技巧
? 混合語言程式設計
? 遊戲的儲存
? 多人遊戲的實作
? 多線程程式設計技術
資料結構
“遊戲所應當采用哪種資料結構？”，這幾乎是我最常被問到的問題。答案是：最快速最有效率的資料結構。然而，在大多數情況下，你并不需要采用那些所謂最先進也最複雜的資料結構。正相反，你應該盡可能将其簡化。在速度比記憶體更重要的今天，我們甯可先犧牲記憶體！
記住這一點，我們先來看幾個最常用于遊戲的資料結構，并給你何時以及如何使用這些資料結構的建議。
靜态結構和數組
資料結構最基本的形式，當然就是一個資料項單獨出現的形式，如一個結構或類。如下所示：
typedef struct PLAYER_TYP // tag for forward references
{
int state; // state of player
int x,y; // position of player
// ...
} PLAYER, *PLAYER_PTR;
C++
在C++中，你不必使用typedef來定義一個結構類型；當你使用到關鍵字struct時，編譯器會自動為之建立一個類型。此外，C++的struct甚至可以包含方法、公有和私有部分。
PLAYER player_1, player_2; // create a couple players
在這個例子中，一個帶有兩個靜态定義的記錄的資料結構就解決問題了。另一方面，如果遊戲玩家多于三個，那麼較好的做法是采用如下所示的數組：
PLAYER players[MAX_PLAYERS]; // the players of the game
這樣，你便可以用一個簡單的循環來處理所有的遊戲玩家了。Okay，非常好，但是如果在遊戲運作以前你不知道會有多少玩家或記錄參數，那又該如何呢？
當出現這種情況時，我們應計算出數組所可能具有的元素個數的最大值。如果數目較小，如256或更小，并且每個數組元素也相當的小（少于256位元組），我通常會采用靜态配置設定記憶體，并使用一個計數器來計算某個時刻已激活的元素的數目。
你也許覺得這對于記憶體而言是一種浪費。但是它比周遊一個連結清單或動态結構要容易和快速得多。關鍵在于，如果你在遊戲運作前知道數組元素的數目，并且數目不是太大，那麼就在遊戲啟動時通過調用函數malloc()或new()來靜态地預先配置設定記憶體。
警告
不要沉迷于靜态數組！例如，假如你有一個大小為4KB的結構，而且可能有1到256個該結構類型的數組。為防止某些時候數組元素的個數達到256而産生溢出錯誤，采用靜态配置設定記憶體方法時必須為之配置設定1MB的記憶體。這時，你顯然需要更好的方法——采用連結清單或動态配置設定的數組來配置設定記憶體，以避免浪費。
連結清單
對于那些在程式啟動或編譯時可以預估的、簡單的資料結構，數組是最合适的處理方法。但對于那些在運作時可能增大或縮小的資料結構而言，應當使用連結清單（linked list）這類形式的資料結構處理方法。圖11-1表示了一個标準的、抽象的連結清單結構。一個連結清單由許多節點構成。每個節點都包含資訊和指向表中下一個節點的指針。
圖11-1：一條連結清單
連結清單用起來很酷，因為你可以将一個節點插入到連結清單的任意位置，同樣也可以删除任意位置的節點。圖11-2示意了節點插傳入連結表的情形。由于在運作時可以插入或删除帶有資訊的節點，使得作為遊戲程式的資料結構，連結清單很具吸引力。
圖11-2：往連結清單中插入節點
連結清單惟一的缺點是你必須一個接一個地周遊節點來尋找你的目标節點（除非建立第二個資料結構來幫助查詢）。例如，假定你要定位一個數組中的第15個元素，你隻需這樣便可以通路它：
players[15]
但對于連結清單，你需要一個周遊算法以通路連結清單的節點來定位目标節點。這意味着在最壞的情況下，查詢的重複次數與連結清單的長度相等。這就是O(n)。O記号說明在有n個元素的情況下要進行與n同階次數的操作。當然，我們可以采用優化算法和附加的包含排序索引表的資料結構，來達到與通路數組幾乎同樣快的速度。
建立連結清單
現在來看一看如何建立一個簡單的連結清單、增加一個節點、删除一個節點，以及搜尋帶有給定關鍵字的資料項。下面是一個基本節點的定義：
typedef struct NODE_TYP
{
int id; // id number of this object
int age; // age of person
char name[32]; // name of person
NODE_TYP *next; // this is the link to the next node
// more fields go here
} NODE, *NODE_PTR;
為了通路一個連結清單，需要一個head指針和一個tail指針分别指向連結清單的頭節點和尾節點。開始時連結清單是空的，因而頭尾指針均指向NULL：
NODE_PTR head = NULL,
tail = NULL;
注意
Some programmers like to start off a linked list with a dummy node that's always empty. This is mostly a choice of taste. However, this changes some of the initial conditions of the creation, insertion, and deletion algorithms, so you might want to try it.
有些程式員喜歡以一個總是為空的啞元節點（即不表示實際資料的節點）作為一個連結清單的開始節點。這通常是個人習慣問題。但這會影響連結清單節點建立、插入和删除的算法中的初始條件，你不妨試一試。
周遊連結清單
出人意料的是，周遊連結清單是所有連結清單操作中最容易實作的。
1. 從head指針處開始。
2. 通路節點。
3. 連結到下一節點。
4. 如果指針非NULL，則重複第2、3步。
下面是源代碼：
void Traverse_List(NODE_PTR head)
{
// this function traverses the linked list and prints out
// each node
// test if head is null
if (head==NULL)
{
printf("/nLinked List is empty!");
return;
} // end if
// traverse while nodes
while (head!=NULL)
{
// visit the node, print it out, or whatever...
printf("/nNode Data: id=%d", head->id);
printf("/nage=%d,head->age);
printf("/nname=%s/n",head->name);
// advance to next node (simple!)
head = head->next;
} // end while
print("/n");
} // end Traverse_List
很酷是不是？下一步，讓我們看一看如何在連結清單中插入一個節點。
插入節點
插入節點的第一步是建立該節點。建立節點有兩種方法：你可以将新的資料元素傳遞給插入函數，由該函數來構造一個新節點；或者先構造一個新節點，然後将它傳遞給插入函數。這兩種方法在本質上是相同的。
此外，還有許多方法可以實作節點插傳入連結表的操作。蠻橫的做法是将要插入的節點插在連結清單的開頭或結尾。如果你不關心連結清單中節點的順序，這倒不失為一個便捷的方法。但如果想保持連結清單原來的排序，你就應當采用更聰明的插入算法，這樣可以保證插入節點後的連結清單仍然保持升序或降序的順序。這也可以讓以後進行搜尋時速度更快。
為簡明起見，我舉一個最簡單的節點插入方法的例子，也就是将節點插在連結清單的末尾。其實按順序的節點插入算法并不太複雜。首先要掃描整個連結清單，找出新節點所要插入的位置，然後将其插入。惟一的問題就是保證不要丢失任何指針和資訊。
下面的源代碼将一個新節點插傳入連結表的尾部（比插傳入連結表頭部難度稍大）。注意一下特殊的情況，即空連結清單和隻有一個元素的連結清單:
// access the global head and tail to make code easier
// in real life, you might want to use ** pointers and
// modify head and tail in the function ???
NODE_PTR Insert_Node(int id, int age, char *name)
{
// this function inserts a node at the end of the list
NODE_PTR new_node = NULL;
// step 1: create the new node
new_node = (NODE_PTR)malloc(sizeof(NODE)); // in C++ use new operator
// fill in fields
new_node->id = id;
new_node->age = age;
strcpy(new_node->name,name); // memory must be copied!
new_node->next = NULL; // good practice
// step 2: what is the current state of the linked list?
if (head==NULL) // case 1
{
// empty list, simplest case
head = tail = new_node;
// return new node
return(new_node);
} // end if
else
if ((head != NULL) && (head==tail)) // case 2
{
// there is exactly one element, just a little
// finesse...
head->next = new_node;
tail = new_node;
// return new node
return(new_node);
} // end if
else // case 3
{
// there are 2 or more elements in list
// simply move to end of the list and add
// the new node
tail->next = new_node;
tail = new_node;
// return the new node
return(new_node);
} // end else
} // end Insert_Node
As you can see, the code is rather simple. But it's easy to mess up because you're dealing with pointers, so be careful! Also, the astute programmer will very quickly realize that with a little thought, cases two and three can be combined, but the code here is easier to follow. Now let's remove a node.
你可能覺得代碼比較簡單。但實際上它卻很容易造成混亂，因為你處理的是指針，是以要小心謹慎！聰明的程式員腦筋一轉便會很快地意識到case 2和case 3可以合二為一，但這裡的代碼易讀性更好。下面我們來看一看節點的删除。
删除節點
删除節點比插入節點複雜，因為指針和記憶體都要重新定位和配置設定。大多數情況下，隻需删除指定的一個節點。但這個節點的位置可能是頭部、尾部或中間，是以你必須編寫一個通用的算法來處理所有可能的情況。如果你沒有将所有的情況都考慮進去并進行測試，那後果将是非常糟糕的！
一般而言，這個算法必須能夠按所給定的關鍵字搜尋連結清單、删除節點并釋放其占用的記憶體。此外，該算法還必須能夠修複指向該被删除節點的指針和該節點所指向的下一個節點的指針。看一看圖11-3便會一目了然。
圖11-3：從連結清單中删除節點
下面這段代碼可以基于關鍵字ID，完成删除任意節點的操作：
// again this function will modify the globals
// head and tail (possibly)
int Delete_Node(int id) // node to delete
{
// this function deletes a node from
// the linked list given its id
NODE_PTR curr_ptr = head, // used to search the list
prev_ptr = head; // previous record
// test if there is a linked list to delete from
if (!head)
return(-1);
// traverse the list and find node to delete
while(curr_ptr->id != id && curr_ptr)
{
// save this position
prev_ptr = curr_ptr;
curr_ptr = curr_ptr->next;
} // end while
// at this point we have found the node
// or the end of the list
if (curr_ptr == NULL)
return(-1); // couldn't find record
// record was found, so delete it, but be careful,
// need to test cases
// case 1: one element
if (head==tail)
{
// delete node
free(head);
// fix up pointers
head=tail=NULL;
// return id of deleted node
return(id);
} // end if
else // case 2: front of list
if (curr_ptr == head)
{
// move head to next node
head=head->next;
// delete the node
free(curr_ptr);
// return id of deleted node
return(id);
} // end if
else // case 3: end of list
if (curr_ptr == tail)
{
// fix up previous pointer to point to null
prev_ptr->next = NULL;
// delete the last node
free(curr_ptr);
// point tail to previous node
tail = prev_ptr;
// return id of deleted node
return(id);
} // end if
else // case 4: node is in middle of list
{
// connect the previous node to the next node
prev_ptr->next = curr_ptr->next;
// now delete the current node
free(curr_ptr);
// return id of deleted node
return(id);
} // end else
} // end Delete_Node
注意代碼中包括了許多特殊的情況。盡管每一種情況的處理都很簡單，但我還是希望提醒讀者，一定要考慮周全，不放過每一種可能的情況。
最後，你或許已經注意到删除連結清單内部節點的操作極富戲劇性。這是因為這個節點一旦被删除，就無法恢複。我們不得不跟蹤前一個NODE_PTR以跟蹤末尾的節點。可以使用如圖11-4所示的雙向連結清單來解決這個問題及其他類似的問題。
圖11-4：雙向連結清單
雙向連結清單的優點在于你可以在任何位置從兩個方向周遊連結清單節點，可以非常容易地實作節點的插入和删除。資料結構上，惟一的改變就是添加了一個連結字段，如下所示：
typedef struct NODE_TYP
{
int id; // id number of this object
int age; // age of person
char name[32]; // name of person
// more fields go here
NODE_TYP *next; // link to the next node
NODE_TYP *prev; // link to previous node
} NODE, *NODE_PTR;
應用雙向連結清單，你可以從任一個節點向前或向後搜尋，是以和節點插入和删除有關的跟蹤節點操作大大簡化。控制台程式DEMO11_1.CPP|EXE便是一個簡單的連結清單操作程式。它可以實作插入節點、删除節點和周遊連結清單。
注意
DEMO11_1.CPP是一個控制台程式而非标準的Windows .EXE程式。是以在編譯前應将編譯器設定為控制台應用程式。當然，這裡沒用到DirectX，是以也不必加載任何DirectX的.LIB檔案。
算法分析
算法設計與分析通常是進階的計算機科學知識。但我們至少要掌握一些常識般的技巧和思想，以利于我們編寫比較複雜的算法。
首先，要知道一個好的算法比所有的彙編語言或優化器都更好。例如，在前面說過，調整一下資料的順序便能夠減少按元素的幅度搜尋資料所花費的時間。是以所應掌握的原則是：選擇一個可靠的、适合問題和資料的算法，而與此同時，還要挑選一種易于該算法通路和處理的資料結構。
例如，假如你總是使用線性的數組，你就不要指望能夠進行優于線性搜尋時間的搜尋（除非你使用第二個資料結構）。但如果使用排序的數組，搜尋時間就會縮短成對數級别。
編寫一個好算法的第一步是掌握一些算法分析知識。算法分析技術又叫漸近分析（Asymptotic Analysis），通常是基于微積分的。我不想過多地深入，是以隻介紹一些概念。
分析一個算法的基本思想是看一看n個元素時主循環的執行次數。這裡n可代表任何資料結構的元素數目。這是算法分析最重要的思想。當然，有了好的算法後，每次的執行時間、初始化的系統開銷也同樣重要，但我們從循環執行的次數開始。讓我們看一看下面兩個例子：
for (int index=0; index {
// do work, 50 cycles
} // end for index
在這個例子中，程式執行n (=50)次循環，是以執行時間就是n階即O(n)。O(n)稱為大O記法，它是一個上限值，也是對執行時間的一個很粗糙的上限估計。假如要更精确一點，你知道其内部的計算需要50次循環，是以整個執行時間就是：
n*50 cycles
對嗎？錯了！如果要計算循環時間，你應當将循環自身花費的時間包括進去。這些時間包括變量的初始化、比較、增量和循環的跳轉。将這些時間加進去，如下式所示：
Cyclesinitialization+(50+Cyclesinc+Cyclescomp+Cyclesjump)*n
上式是一個較好的估計。這裡，Cyclesinc、Cyclescomp和Cyclesjump分别代表增量、比較和跳轉所需的周數。在奔騰級的處理器上，其值約為1~2周。是以，在這種情況下，循環本身所花費的時間和程式内部工作循環所需用的時間一樣多。這一點是非常重要的。
比如，許多遊戲程式員在處理有關像素繪圖的問題時，将其編寫成函數而非一個宏或内聯代碼。因為像素繪圖函數是如此簡單，以至于調用這個函數比直接畫圖所需時間還要多！是以在設計循環時必須確定循環内部有足夠的工作，而且循環運作所需時間要遠大于循環自身所花費的時間。
現在讓我們來看一看另一個例子——它的時間複雜度高于n：
// outer loop
for (i=0; i {
// inner loop
for (j=1; j<2*n; j++)
{
// do work
} // end for j
} // end for i
在這個例子中，我們假定循環中工作部分執行所需時間遠大于實作循環機制所花費的時間，這樣我們就不考慮循環自身花費時間而隻考慮循環執行的次數。這個程式的外部循環次數為n次，内部循環的次數為2n-1次，是以内部代碼總的執行次數為：
n*(2*n-1) = 2*n2-n
上式由兩項構成。2n2是主項，其值要遠大于後一項，并且随n取值的增加，兩項的內插補點也增大。如圖11-5所示。
.
圖11-5：2n2-n的增長速率
當n較小比如n=2時，上式的值為：
2*(2)2 - 2 = 6
在該情況下，n這項減去總花費時間的25%。但當n的值增大時，比如n=1000：
2*(1000)2 - 1000 = 1999000
這時，n這項隻減去總花費時間的0.5%，可以忽略不計。現在讀者該明白了為什麼2*n2項是主項或更簡單地說n2是主項。是以，這時的算法複雜度是O(n2)，這是非常糟糕的，以n2運算的算法是不能令人滿意的，是以當你提出這樣一個算法時，你最好從頭再來！
上述都是為漸近分析作準備的。最低要求是：你必須能夠粗略地估計你的遊戲程式中循環的執行時間。這将有助于你挑選算法和所需編碼空間。
遞歸
我們下一個所要探讨的主題是遞歸（Recursion）。遞歸是一種應用歸納的方法求解問題的技術。遞歸的基本含義是把許多問題連續分解成同一形式的簡單問題，直到能夠真正的求解為止。然後将這些小問題進行歸納、組合進而使整個問題得到解決。聽起來是不是很美妙？
在計算機程式設計中。我們通常使用遞歸算法來實作搜尋、排序和一些數學計算。遞歸的前提非常簡單：編寫一個函數，該函數具有調用自己來求解問題的能力。是不是聽起來不可思議？其關鍵在于該函數調用自己時，就在堆棧裡建立一組新的局部變量，是以相當于一個新的函數被調用。你惟一需要注意的是函數不能溢出堆棧，并且要有終止條件，程式結束時還要有結束處理代碼以保證堆棧通過return()釋放空間。讓我們看一個标準的執行個體：階乘的計算。一個數的階乘寫作n!，其含義如下：
n! = n*(n-1)*(n-2)*(n-3)*...(2)*(1)
并有0! = 1! = 1
Thus, 5! is 5*4*3*2*1.
這樣，5!就是5*4*3*2*1。
以下是用通常的方法編寫的計算代碼：
// assume integers
int Factorial(int n)
{
int sum = 1; // hold result
// accumulate product
while(n >= 1)
{
sum*=n;
// decrement n
n--;
} // end while
// return the result
return(sum);
} // end Factorial
看上去非常簡單。如果輸入0或1，則計算結果為1。若輸入3，則其計算順序如下：
sum = sum * 3 = 1 * 3 = 3
sum = sum * 2 = 3 * 2 = 6
sum = sum * 1 = 6 * 1 = 6
顯然，計算結果正确無誤。因為3! = 3*2*1。
以下是采用遞歸方法編寫的程式：
int Factorial_Rec(int n)
{
// test for terminal cases
if (n==0 || n==1) return(1);
else
return(n*Factorial_Rec(n-1));
} // end Factorial_Rec
這個程式并不怎麼複雜。我們看看當n分别為0和1時，程式是如何運作的。在這兩種情況下，第一個if語句為TRUE，就傳回值1并退出程式。但當n>1時，奇妙的事情就發生了。這時，執行else語句并傳回該函數調用自身（n-1）次後的值。這就是遞歸過程。
目前函數變量的取值仍在堆棧裡儲存，下次調用該函數就相當于調用一個以一組新變量為參數的函數。代碼中第一個return語句在進行下一個調用前不能執行完畢，就這樣一直循環下去直到執行結束語句為止。
讓我們來看一看n=3時，每次疊代時變量n的實際數值。
1.
第一次調用函數Factorial_Rec(3)，
函數開始執行return語句：
return(3*Factorial_Rec(2));
2.
第二次調用函數Factorial_Rec(2)，
函數又開始執行return語句：
return(2*Factorial_Rec(1));
3.
第三次調用函數Factorial_Rec(1)，
這次函數執行結束語句并傳回值1：
return(1);
現在奇妙的是，1被傳回給第二次調用的函數Factorial_Rec()，如下所示：
return(2*Factorial_Rec(1));
這也就計算出了
return(2*1);
随之這一數值便被傳回給第一次調用的函數，如下所示：
return(3*Factorial_Rec(2));
這也就計算出了
return(3*2);
And presto, the function can finally return with 6—which is indeed 3! That's recursion. Now, you might ask which method is better—recursion or non-recursion? Obviously, the straightforward method is faster because there aren't any function calls or stack manipulation, but the recursive way is more elegant and better reflects the problem. This is the reason why we use recursion. Some algorithms are recursive in nature, trying to write non-recursive algorithms is tedious, and in the end they become recursive simulations that use stacks themselves! So use recursion if it's appropriate and simplifies the problem. Otherwise, use straight linear code.
随之函數最終得到傳回值6即3！。這便是遞歸過程。這時你會問哪種方法更好一些呢——是遞歸法還是非遞歸法？很明顯，直接方法執行速度要快一些，因為沒有涉及到任何函數調用或堆棧操作。但遞歸方法更優雅，能更好地反映問題的本質。這就是我們使用遞歸的原因。有些算法本質上是遞歸的，為之編寫非遞歸算法會非常冗長，而且最終也必須使用堆棧進行遞歸模拟。如果适于簡化問題，就使用遞歸法程式設計；否則就使用直接方法。
例如，看一下程式DEMO11_2.CPP|EXE。該程式實作了階乘算法。注意一下階乘的溢出速度。看看你的機器能計算到多大階乘。絕大多數的機器可以計算到69！不騙你。
數學
我們來遞歸地實作一下菲波那契Fibonacci算法。第n個Fibonacci數列元素fn=fn-1+fn-2，另外，f0=0，f1=1，那麼，f2=f1+f0=1，f3=f2+f1=2。是以整個Fibonacci序列為：0，1，1，2，3，5，8，13…數一數向日葵中一圈圈的種子數目，恰好是Fibonacci序列。
樹結構
接下來我們要讨論的進階資料結構是：樹結構（tree）。通常人們使用遞歸算法來處理樹結構，是以我在上面論述中特别提到了遞歸。圖11-6圖示了一些不同的樹狀資料結構。
圖11-6：樹的拓撲結構
人們發明樹結構，用于儲存和搜尋海量的資料。最常見的樹結構是二叉樹，也叫作B-樹或二分查找樹（BST）。樹結構是從單一根節點發散出的樹狀結構，包含許多子節點。每個節點可以派生出一個或兩個子節點（兄弟節點，Sibling），二叉樹是以而得名。而且我可以讨論一個二叉樹的階（Order），即該樹一共有幾層。圖11-7所示的是不同層次的二叉樹。
圖11-7：一些不同階的二叉樹
關于樹結構，有趣的是資訊查詢的速度很快。絕大多數二叉樹使用單一的關鍵字來查詢資料。例如，假定你想建立一個包含遊戲對象記錄的二叉樹，且每一個遊戲對象具有多個屬性，你可能會使用遊戲對象的建立時間作為關鍵字，或将資料庫中的每一節點定義為代表一個人。下面是可以用來儲存單個人的節點的資料結構：
typedef struct TNODE_TYP
{
int age; // age of person
char name[32]; // name of person
NODE_TYP *right; // link to right node
NODE_TYP *left; // link to left node
} TNODE, *TNODE_PTR;
注意樹節點與連結清單節點的相似之處！它們之間惟一的不同是使用資料結構并構造樹的方法。看一看上例，假如有五個對象（人），其年齡分别為5、25、3、12和10。圖11-8表示包含該資料的兩個不同的二叉樹。不過，你可以做得更好，比如在插入算法中根據資料插入順序來維持二叉樹的某種屬性。
圖11-8：資料集合 年齡 {5，25，3，12，10} 的二叉樹編碼
注意
Of course, the data in this example can be anything you want.
當然，在本例中，資料可以定義為任何值。
注意在建立如圖11.8所示的二叉樹時，使用了如下約定：任一節點的右子節點總是大于或等于該節點本身，左子節點總是小于其本身。你還可以使用其他的約定，隻要保持一緻性。
二叉樹可以存儲海量資料，而且應用“二分查找法”可以快速地檢索資料。這是二叉樹的優越性所在。比如，如果一個二叉樹帶有一百萬個節點，至多進行20次比較便可以檢索到資料！這是不是棒極了？其原因在于檢索中的每次疊代，搜尋空間的節點數都減少一半。從根本上說，假如有n個節點，那麼平均搜尋次數為log2 n，運作時間為O(log2 n)。
注意
上述所說的搜尋時間隻适于平衡二叉樹——即每一層次均含有相等的左右子節點的二叉樹。如果二叉樹不是平衡的，那麼它就退化為一個連結清單，而搜尋時間也退化為一個線性函數。
B樹第二個非常酷的屬性是你可以定位子樹并單獨處理它。該子樹仍然具有B樹的所有屬性。是以，如果你知道檢索的位置，便可以搜尋子樹檢索你所需要的東西。這樣一來，你便可以建立樹的樹，或建立子樹的索引表，而不必處理整個樹。這在3D場景模組化中是非常重要的。你可以為整個遊戲空間建立一個樹結構，而以數百棵子樹來表示空間中的各個房間。你還可以建立另一個樹結構來指代具有偏序排列的指向子樹根指針的連結清單。如圖11-9所示。有關這方面更多的内容會在本書的以後章節中論及。
圖11-9：在B樹結構上使用一個二級索引表
最後，讓我們談一談何時使用樹結構。我建議，當所處理的問題或資料類似于樹結構時使用樹結構。比方說，當你随手畫出問題的草圖，而發現其中具有左右分支的話，樹結構明顯應該是合适的。
建立二分查找樹（BST）
由于應用于B樹的算法在本質上是遞歸的，是以這一節的主題比較複雜。讓我們先快速地浏覽一下二叉樹的一些算法，然後寫一些代碼，并完成一個示範程式。
與連結清單相似，建立BST有兩種方法：樹結構的根節點可以為啞元，也可以是實際有效的節點。我更喜歡以實際節點作為根節點。是以，一個空樹中沒有任何東西，而本應指向根節點的指針現在為NULL。
TNODE_PTR root = NULL;
Okay，要将資料插入BST，你必須确定插入資料所使用的關鍵字。在本例中，你可以使用人的年齡或名字。因為上面這些例子都使用年齡作為關鍵字，是以這裡也使用年齡作為關鍵字。然而，以名字作為關鍵字更簡單，你隻需使用詞典式的比較函數如strcmp()就可以确定名字的順序。無論如何，下面這段代碼将節點插入BST：
TNODE_PTR root = NULL; // here's the initial tree
TNODE_PTR BST_Insert_Node(TNODE_PTR root, int id, int age, char *name)
{
// test for empty tree
if (root==NULL)
{
// insert node at root
root = new(TNODE);
root->id = id;
root->age = age;
strcpy(root->name,name);
// set links to null
root->right = NULL;
root->left = NULL;
printf("/nCreating tree");
} // end if
// else there is a node here, lets go left or right
else
if (age >= root->age)
{
printf("/nTraversing right...");
// insert on right branch
// test if branch leads to another sub-tree or is terminal
// if leads to another subtree then try to insert there, else
// create a node and link
if (root->right)
BST_Insert_Node(root->right, id, age, name);
else
{
// insert node on right link
TNODE_PTR node = new(TNODE);
node->id = id;
node->age = age;
strcpy(node->name,name);
// set links to null
node->left = NULL;
node->right = NULL;
// now set right link of current "root" to this new node
root->right = node;
printf("/nInserting right.");
} // end else
} // end if
else // age < root->age
{
printf("/nTraversing left...");
// must insert on left branch
// test if branch leads to another sub-tree or is terminal
// if leads to another subtree then try to insert there, else
// create a node and link
if (root->left)
BST_Insert_Node(root->left, id, age, name);
else
{
// insert node on left link
TNODE_PTR node = new(TNODE);
node->id = id;
node->age = age;
strcpy(node->name,name);
// set links to null
node->left = NULL;
node->right = NULL;
// now set right link of current "root" to this new node
root->left = node;
printf("/nInserting left.");
} // end else
} // end else
// return the root
return(root);
} // end BST_Insert_Node
首先你要測試是否是空樹，如果是空樹就建立其根節點。如有必要，應使用最先插入BST的那項内容建立根節點。是以，最先被插入BST的那項内容或記錄就代表搜尋空間中靠近中間的項，以便樹能很好地平衡。總之，如果樹有超過一個的節點，你必須周遊該樹，至于将節點插入左子樹或右子樹則取決于你要插入的記錄。當你遇到樹結構的葉節點或終止枝時，便可以将新節點插入該處。
root = BST_Insert_Node(root, 4, 30, "jim");
圖11-10示意了如何将“Jim”插入一個樹中。
圖11-10：在BST中插入元素
将新節點插入BST這一過程的執行效率和在BST中搜尋節點相當，是以，一次插入操作所需的平均時間約為O(log2n)，而最壞的情況是O(n)（當關鍵字以降序線性排列時）。
搜尋BST
一旦建立了BST，就是進行資料的搜尋的時候了。當然這會用到許多遞歸處理方法，應加以關注。搜尋BST有三種方法：
? 前序——通路節點、然後按前序搜尋左子樹，最後按前序搜尋右子樹。
? 中序——按中序搜尋左子樹，然後通路節點，最後按中序搜尋右子樹。
? 後序——按後序搜尋左子樹，然後按後序搜尋右子樹，最後通路節點。
注意
左和右是任意的，關鍵在于通路和搜尋的順序。
參見圖11-11。該圖顯示了一個簡單的二叉樹及三種搜尋順序。
圖11-11：前序、中序、後序搜尋方式的節點通路次序
知道了這三種順序，你可以為之編寫相當簡單的遞歸算法來實作它們。當然，周遊二叉搜尋樹的目的是找到目标并将其傳回。下面的函數便實作了二叉樹周遊的功能。你可以為之增加停止代碼以便搜尋到目标關鍵字時結束程式。不過，現在你比較在意搜尋方法：
void BST_Inorder_Search(TNODE_PTR root)
{
// this searches a BST using the inorder search
// test for NULL
if (!root)
return;
// traverse left tree
BST_Inorder_Search(root->left);
// visit the node
printf("name: %s, age: %d", root->name, root->age);
// traverse the right tree
BST_Inorder_Search(root->right);
} // end BST_Inorder_Search
以下是前序搜尋代碼：
void BST_Preorder_Search(TNODE_PTR root)
{
// this searches a BST using the preorder search
// test for NULL
if (!root)
return;
// visit the node
printf("name: %s, age: %d", root->name, root->age);
// traverse left tree
BST_Inorder_Search(root->left);
// traverse the right tree
BST_Inorder_Search(root->right);
} // end BST_Preorder_Search
以下是後序搜尋代碼：
void BST_Postorder_Search(TNODE_PTR root)
{
// this searches a BST using the postorder search
// test for NULL
if (!root)
return;
// traverse left tree
BST_Inorder_Search(root->left);
// traverse the right tree
BST_Inorder_Search(root->right);
// visit the node
printf("name: %s, age: %d", root->name, root->age);
} // end BST_Postorder_Search
就這麼簡單，像不像變戲法？假設你已建立了一棵二叉樹，試着用這個調用進行中序周遊。
BST_Inorder_Search(my_tree);
提示
我很難形容類樹結構在3D圖形學中有多重要，希望你已經了解了上述内容。否則，當你構造二分空間分區(????)來解決渲染問題時，你将會陷入指針遞歸的苦海中。：）
你注意到我省略了如何删除一個節點。我是有意這樣做的。因為删除一個節點非常複雜，有可能破壞子樹的父節點和其與子節點間的連接配接。我想，删除節點就留作給讀者的一個練習好了。這裡我向大家建議一本好的資料結構參考書——由Sedgewick撰寫，Addison Wesley 出版社出版的《Algorithms in C++》（該書中文版《算法I~IV（C++實作）——基礎、資料結構、排序和搜尋（第三版）》已由中國電力出版社出版。——編者），這本書深入讨論了樹結構及其相關算法。
最後，讀者可以檢驗一下二叉搜尋樹的一個執行個體程式——DEMO11_3.CPP|EXE。該程式允許你建立一個二叉搜尋樹并使用三種算法周遊它。這也是一個控制台程式，是以需要正确地編譯它。
優化理論
比起編寫任何其他程式來說，編寫遊戲更重視性能優化。視訊遊戲永無止境地不斷突破硬體和軟體的極限。遊戲程式設計人員總是希望加入更多的生物、特效、聲音以及更好的智能等等。是以，優化至關重要。
在這一節，我們将讨論一些優化技術以幫助你進行遊戲程式設計。如果你對此有濃厚的興趣，有很多關于該方面的書可以參考，如由Addison Wesley出版社出版、Rick Booth編著《Inner Loops》，由Coriolis 集團出版、Mike Abrash 編著的《Zen of Code Optimization》，AP出版社出版、Mike Schmit編著的《Pentium Processor Optimization》。
運用你的頭腦
編寫優化代碼的第一要旨是了解編譯器和資料結構，以及你編寫的C/C++程式是如何被最終轉換為可執行的機器代碼的。基本思想是使用簡單的程式設計技巧和資料結構。你的代碼越複雜、設計越精巧，編譯器将其變換為機器代碼就越困難，是以（在大多數情況下）其執行速度也就越慢。以下是程式設計時需要遵循的基本原則：
? 盡可能使用32位資料。8位資料雖然占用空間較少，但英特爾的處理器是以32位為基準的，并針對32位資料進行了優化。
? 對于頻繁調用的小函數而言，應聲明為内聯函數。
? 盡可能使用全局變量，但避免産生可讀性差的代碼。
? 避免使用浮點數進行加法和減法運算，因為整數單元通常比浮點單元運算快。
? 盡可能使用整數。盡管浮點處理器幾乎和整數處理一樣快，但整數更精确。是以如果你不需要精确的小數位，就使用整數。
? 将所有的資料結構均調整為32個位元組對齊。在大多數編譯器上你可以使用編譯器訓示字來手工完成，或在代碼中使用#pragma。
? 除非是簡單類型的參數，否則盡可能不使用值傳遞的方式傳遞參數。應當使用指針。
? 在代碼中不要使用register關鍵字。盡管Microsoft聲稱它能夠加快循環，但這會造成編譯器沒有足夠可用的寄存器，結果是生成糟糕的代碼。
? 如果你是位C++程式員，用類和虛函數是可以的。但軟體的繼承和層次不要過多。
? 奔騰級的處理器使用一個内部資料和代碼緩存。了解這一點後，要確定函數代碼短小以适應緩存的大小（16KB至32KB以上）。此外，在儲存資料時，以其将被通路的方式進行存儲。這樣可以提高緩存的命中率、進而減少通路主存或二級緩存的次數。須知，主記憶體或二級緩存的通路速度要比内部緩存的通路速度慢10倍。
?
? 奔騰級的處理器具有類似RISC的核心，是以擅長處理簡單指令，并能夠在數個執行單元内同時處理二個以上的指令。是以，不推薦在一行代碼中書寫晦澀難懂的代碼，最好編寫較簡單的代碼。即使你可以将這些代碼合并成具有同樣功能的一行代碼，也盡量改成簡單的。
數學技巧
由于遊戲程式設計中大量的工作在實質上是數學問題，是以了解執行數學運算的更好方法是非常值得的。有許多通用的技巧和方法可供你利用，以提高程式運作速度：
參與整數運算的數必須是整數，參與浮點運算的數必須是浮點數。類型轉換必然降低性能。是以除非是迫不得已，否則不要進行類型轉換。
通過左移位操作可以實作整數與2的任何次幂的乘法運算。同樣地，通過右移位操作可以實作整數與2的任何次幂的除法運算。對于整數與非2的次幂的數的相乘和相除可以轉換為和運算或差運算。例如，640雖不是2的整數次幂，但512和128是2的整數次幂；是以當某整數與640相乘最好的方法是進行如下變換：
product=(n<<7) + (n<<9); // n*128 + n*512 = n*640
不過，如果處理器在1至2個時鐘周期内就可以完成乘法運算，這種優化就失去意義了。
如果你的算法中應用到矩陣操作，要充分利用矩陣的稀疏性——一些元素為零。
在建立常量時，確定其為恰當的類型以防編譯器編譯出錯或将其強迫轉換為整數類型。最好是使用C++中新的const訓示字。例如：
const float f=12.45;
避免使用平方根、三角函數或任何複雜的數學函數。一般而言，這些複雜函數的計算都可以根據特定的假設或近似而找到一個簡單的方法來實作。但即使結果還是不理想，你仍然可以做一張查找表。我在後面将會提及該表。
如果你要将一個大的浮點數組清零，要按如下方式使用memset()：
memset((void *)float_array,0,sizeof(float)*num_floats);
然而事實上也隻有這種情況下才能這樣做，因為浮點數是以IEEE格式編碼的，故而隻有整數零和浮點零的數值才完全相等。
在執行數學運算時，看一看在編碼前能否手工先将表達式簡化。比如，n*(f+1)/n等于(f+1)，因為除法和乘法的運算結果将n 消去了。
如果你要執行複雜的數學計算，而且你在下面的代碼中需要再次用到計算結果，那麼就将其暫存在高速緩存中。如下所示：
// compute term that is used in more than one expression
float n_squared = n*n;
// use term in two different expressions
pitch = 34.5*n_squared+100*rate;
magnitude = n_squared / length;
最後，很重要的一點是確定将編譯器的選項設定為打開浮點協處理器，這樣編譯出的代碼的執行速度較快。
定點運算
幾年以前，大多數3D引擎都采用定點運算來進行3D中大量的變換和數學運算。這是因為處理器對浮點的支援沒有對整數的支援快，甚至在奔騰處理器上也是如此。但是今天，奔騰Ⅱ、Ⅲ和Katmai處理器擁有更好的浮點能力，是以定點運算不再那麼重要。
然而在許多情況下，由浮點到整數的光栅變換仍然很慢，是以在内部循環的加法和減法運算中使用定點運算仍是一個較好的選擇。在低檔的奔騰機器上，這類運算依然比浮點運算要快，是以你可以運用技巧快速地從定點數中提取出整數部分，而不必進行float到int的類型轉換。
無論如何，這些都具有一定的不确定性。今天，使用浮點來處理任何運算通常都是最好的選擇，但是多了解一些定點運算總還是有幫助的。我的觀點是使用浮點來處理所有的資料表示和變換，對于低水準的光栅變換可以分别試一試定點運算和浮點運算，看一看那種處理方法最快。當然，如果你使用純硬體加速，無需多慮，隻要一直使用浮點數即可。
記住了這些，下面讓我們來看看如何表示定點數。
定點數的表示
所有的定點數學實際上是以整數尺度為基礎的。比如，我們想用一個整數來表示10.5。這做不到，因為沒有小數位。你可以将其截斷為10.0或将其舍入為11.0，但10.5不是一個整數。但如果你将10.5放大10倍，10.5就變成了105.0，這是一個整數。這便是定點數的基礎。你可以采用某一比例系數來對數值進行縮放，并在進行數學計算時将比例系數考慮進去。
由于計算機是二進制的，大部分遊戲程式傾向于使用32位整數（或int），以16.16的格式來表示定點數。如圖11-12所示。
圖11-12：一種16.16定點數表示法
你可以将整數部分放在高16位，小數部分置于低16位。這樣你已将整個數值放大為原來的216即65536倍。另外，為提取出一個定點數的整數部分，你可以移位并屏蔽掉高16位；為得到小數部分，你可以移位并屏蔽掉低16位。
以下是一些常用的定點數的類型：
#define FP_SHIFT 16 // shifts to produce a fixed-point number
#define FP_SCALE 65536 // scaling factor
typedef int FIXPOINT;
在定點與浮點之間轉換
有兩類數需要轉換為定點數：整數和浮點數。這兩類轉換是不同的，需分别考慮。對于整數，直接用其二進制的補碼表示。是以你可以移位操作來放大這個數，進而将其轉換為定點數。而對于浮點數，由于其使用IEEE格式，四位元組中有一個尾數和指數，是以移位将破壞這個數。是以，必須使用标準的浮點乘法來進行轉換。
數學
二進制補碼是一種表示二進制整數的方法。是以整數和負數均可以用這種方法表示，并且在該集合上數學運算都是正确的。一個二進制數的補碼是指将該二進制的每一位取反并與1進行加運算所得的數。在數學意義上，假定你想求6的補碼，先取反碼得-6，再與1相加即-6+1或~0110+0001=1001+0001=1010。該數就是10的普通二進制表示，但同時也是-6的補碼表示。
以下是将整數轉換為定點數的宏：
#define INT_TO_FIXP(n) (FIXPOINT((n << FP_SHIFT)))
例如：
FIXPOINT speed = INT_TO_FIXP(100);
下面是将浮點數轉換為定點數的宏：
#define FLOAT_TO_FIXP(n) (FIXPOINT((float)n * FP_SCALE))
例如：
FIXPOINT speed = FLOAT_TO_FIXP(100.5);
提取一個定點數也很簡單。下面是從高16位提取整數部分的宏：
#define FIXP_INT_PART(n) (n >> 16)
至于從低16位提取小數部分，則隻需将整數部分屏蔽掉即可：
#define FIXP_DEC_PART(n) (n & 0x0000ffff)
當然，如果你聰明的話，可以不需要進行轉換，隻要使用指針即時地通路高16位和低16位即可。如下所示：
FIXPOINT fp;
short *integral_part = &(fp+2), *decimal_part = &fp;
指針integral_part和decimal_part總是指向你所需的16位數。
精度
此刻一個問題突然出現在你的腦海中：二進制小數部分是怎麼回事？通常你不必理會這個問題，它僅在運算時用到。一般而言，在光栅轉換循環或其他循環中隻需整數部分即可。但因為以2為基數，是以小數部分也是以2為基數的小數。如圖11-12所示。例如二進制小數
1001.0001 是 9 + 0*1/2 + 0*1/4 + 0*1/8 + 1*1/16 = 9.0625
這給我們帶來了精度的概念。上式使用了四位二進制數，其精度大約與1.5位十進制數精度相同，或者說是±0.0625。對于16位二進制數，則可以精确到1/216=0.000015258或萬分之一。這一精度可以滿足絕大部分要求。另一方面，如果你僅用16位來存儲整數部分，其存儲的數值範圍為-32767~32768（無符号數可到65535）。這個限制在巨大的宇宙或數字空間将成為問題，是以要提防溢出問題。
加法和減法
定點數的加法和減法運算比較簡單。你可以采用标準的+和-運算符：
FIXPOINT f1 = FLOAT_TO_FIX(10.5),
f2 = FLOAT_TO_FIX(-2.6),
f3 = 0; // zero is 0 no matter what baby
// to add them
f3 = f1 + f2;
// to subtract them
f3 = f1 – f2;
注意
由于定點數以二進制的補碼表示，是以在進行上述運算時正負數都無問題。
乘法和除法運算
乘法和除法運算比加法和減法運算稍微複雜一些。問題在于定點數是被放大了的數。當進行乘法運算時你不僅乘上了定點數，同時也乘上了放大系數。看一看下述源代碼：
f1 = n1 * scale
f2 = n2 * scale
f3 = f1 * f2 = (n1 * scale) * (n2 * scale) = n1*n2*scale2
看到額外的放大系數嗎？為矯正這個問題，你需要除以或移出放大系數的平方scale2。這樣，兩定點數相乘的運算如下：
f3 = ((f1 * f2) >> FP_SHIFT);
定點數的除法也會遇到同乘法類似的問題，但結果相反。如下所示：
f1 = n1 * scale
f2 = n2 * scale
假設這樣，則：
f3 = f1/f2 = (n1*scale) / (n2*scale) = n1/n2 // no scale!
注意在運算過程中消去了放大系數因而得到的是非定點數。這在某些情況下是非常有用的。但若要成為定點數，必須進行放大：
f3 = (f1 << FP_SHIFT) / f2;
警告
定點數的乘法和除法具有上溢和下溢問題。就乘法而言，最壞的情況是我們不得不使用64位。同樣，對于除法分子的高16位通常丢失，僅剩下小數部分。解決的方法是使用24.8位格式或全64位格式進行運算。這可以使用彙編語言實作，因為Pentium及以上的處理器支援64位運算。或者，你也可以稍微改變一下格式，使用24.8位格式。這樣可以滿足定點數的乘法和除法運算而不至于一下子丢失所有資訊。但是，你的精度仍将大幅度下降。
程式DEMO11_4.CPP|EXE是一個定點數運算的例子。該程式允許你輸入兩個小數，然後執行定點數運算并觀察其計算結果。注意乘法和除法運算結果可能不正确，這是因為計算結果采用的是16.16格式而非64位格式。為修正這一點，你可以改用24.8格式重新編譯程式。條件編譯由程式頂端的兩個#defines控制：
// #define FIXPOINT16_16
// #define FIXPOINT24_8
删掉其中一行的注釋符，編譯器便可以開始編譯了。這是一個控制台應用程式，是以如黑人電影導演Spike Lee說的那樣：“為所欲為……”
循環體展開
下一個優化技巧是循環體展開。在8位和16位時代，這是最好的優化技術之一，但今天它可能帶來相反的後果。展開循環意味着分解一個重複多次的循環，并對每一行手工程式設計。舉例如下：
// loop before unrolling
for (int index=0; index<8; index++)
{
// do work
sum+=data[index];
} // end for index
這個循環的問題是工作花費的時間小于循環增量、比較和跳轉所花費的時間。如此一來，循環本身所需時間是工作代碼的二或三倍。你可以進行如下的循環展開：
// the unrolled version
sum+=data[0];
sum+=data[1];
sum+=data[2];
sum+=data[3];
sum+=data[4];
sum+=data[5];
sum+=data[6];
sum+=data[7];
這樣就快多了。但是有以下兩點需要說明：
如果循環體比循環結構複雜得多，那就沒有必要将其展開。例如，如果你要在循環體内計算平方根，就沒有必要展開了。
由于奔騰處理器帶有内部緩存，将一個循環展開太多會導緻内部緩存的擁塞。這将是災難性的，并會導緻代碼異常結束。我的建議是視情況而定，循環展開的次數宜為8至32次之間。
查找表
這是我個人最喜愛的優化技巧。查表法是預先計算出程式運作時的一些結果。在程式啟動時簡單地計算出所有可能的結果，然後再運作遊戲。例如，假定你需要計算出從0~359間各個角度的正弦和餘弦值。如果使用浮點處理器來計算sin()和cos()，将很費時間。但使用查表方法程式，則隻需幾個CPU周期便可以得出各角度的正弦和餘弦值。舉例如下：
// storage for look up tables
float SIN_LOOK[360];
float COS_LOOK[360];
// create look-up table
for (int angle=0; angle < 360; angle++)
{
// convert angle to radians since math library uses
// rads instead of degrees
// remember there are 2*pi rads in 360 degrees
float rad_angle = angle * (3.14159/180);
// fill in next entries in look-up tables
SIN_LOOK[angle] = sin(rad_angle);
COS_LOOK[angle] = cos(rad_angle);
} // end for angle
以下是一個利用該張查找表的例子，該代碼執行的結果是畫一個半徑為10的圓：
for (int ang = 0; ang<360; ang++)
{
// compute the next point on circle
x_pos = 10*COS_LOOK[ang];
y_pos = 10*SIN_LOOK[ang];
// plot the pixel
Plot_Pixel((int)x_pos+x0, (int)y_pos+y0, color);
} // end for ang
當然，查找表需要占用一定的記憶體，但這樣做也是值得的。“如果你能夠預先算出結果，就将其放進查找表中。”這是我的座右銘。你可以思考一下DOOM、Quake以及我的最愛Half-Life是怎樣工作的？
彙編語言
我想讨論的最後一種優化是使用彙編語言。你或許已擁有了很酷的算法和好的資料結構，但你還是希望更有效率。手工編寫彙編語言不再能使代碼如當年運作在8/16位處理器上那般，一下子快上1000倍，但它一般總能使你的代碼運作速度提高2至10倍。這說明手工編寫彙編語言代碼還是非常值得的。
當然，你必須確定隻轉換遊戲程式中需要轉換的代碼部分。注意不需要優化主菜單程式，因為那樣隻是浪費時間。用一個性能測試工具（Profiler）測試一下當你的遊戲程式運作的時候，CPU時間在何處被消耗殆盡（可能在圖形部分），然後定位該處并将其以彙編語言改寫。我建議使用Intel的Vtune作為性能測試工具。
在過去（幾年前），大部分編譯器不支援内聯彙編。如果有，也很難用！如今Microsoft、Borland和Watcom的編譯器都提供内聯彙編的支援，用來編寫數十句到幾百句的小程式就如同單獨使用彙程式設計式一樣得心應手。是以我建議如果需要彙編語句就使用内聯的彙編器。下面的代碼表明在使用Microsoft VC++時如何調用内聯彙編：
_asm
{
.. assembly language code here
} // end asm
内聯彙編器最突出的優點是它允許使用已在C/C++中定義的變量名。下面的代碼示範了如何使用内聯的彙編語言編寫一個32位的記憶體填充函數：
void qmemset(void *memory, int value, int num_quads)
{
// this function uses 32 bit assembly language based
// and the string instructions to fill a region of memory
_asm
{
CLD // clear the direction flag
MOV EDI, memory // move pointer into EDI
MOV ECX, num_quads // ECX hold loop count
MOV EAX, value // EAX hold value
REP STOSD // perform fill
} // end asm
} // end qmemset
要使用這個新的函數，你隻需這樣調用：
qmemset(&buffer, 25, 1000);
這樣從buffer的起始位址開始，1000個quads被逐一填充為值25。
注意
如果你使用的不是Microsoft VC++， 你應檢視一下你所用編譯器的幫助，弄明白内聯彙編器所需的文法格式。在大多數情況下，它們之間隻不過有些下劃線不同而已。
制作示範
假如你已完成遊戲程式的編寫，這時需要一個示範模式（Demo Mode）。制作示範主要有兩種方法：你可以自己玩這個遊戲并記錄你的動作，或者你可以使用一個人工智能玩家。記錄自己的遊戲玩法是最常見的選擇。因為編寫一個像真人一樣過關斬将的人工智能玩家是非常困難的，而且為了給潛在的買家留下良好的印象，就必然要求人工智能玩家以非常酷的方式玩遊戲，要做到這一點也是很困難的。讓我們扼要地看一下這兩種方法是怎樣實作的。
預先記錄的示範
為了記錄一段示範，基本上，你要記錄每一循環的各種輸入裝置的狀态，将資料寫入檔案，然後将該記錄檔案作為遊戲引擎的輸入來制作示範。看一看圖11-13中的A及B便一目了然了。這一方法的思路是遊戲本身并不知道輸入是來自鍵盤（輸入裝置）還是檔案，是以這種示範隻是簡單地回放遊戲。
圖11-13：示範回放
為使其工作，你必須有一個确定性（Deterministic）的遊戲政策：如果你再次玩這個遊戲并且玩法相同，那麼遊戲人物也将做同樣的事情。這意味着如同記錄輸入裝置一樣，你必須記錄初始的随機數種子，以便将遊戲記錄的開始狀态也像輸入一樣被記錄下來。這樣做確定了遊戲示範将按照你記錄時同樣的狀态播放。
記錄一個遊戲的最好辦法并不是以一定的時間間隔對輸入進行采樣，而是每幀都對輸入進行采樣。這樣一來，這個示範不論計算機快慢，回放時均能與遊戲保持同步。我通常的做法是将所有的輸入裝置并入到一個記錄中，一幀一個記錄，然後将這些記錄做成一個檔案。我将播放示範程式的狀态資訊或随機數放在檔案的開頭，以便于載回這些資料。是以，這個回放檔案如下所示：
Initial State Information
Frame 1: Input Values
Frame 2: Input Values
Frame 3: Input Values
.
.
Frame N: Input Values
初始狀态資訊
第1幀：輸入值
第2幀：輸入值
第3幀：輸入值
.
.
第N幀：輸入值
一旦你有了這個檔案，隻要簡單地将遊戲複位後從頭播放即可。随後讀入檔案，仿佛這些資料是從輸入裝置輸入的一樣。遊戲自身并不知道這點差别！
警告
The single worst mistake that you can make is sampling the input at the wrong time when you're writing out records. You should make absolutely certain that the input you sample and record is the actual input that the game uses for that frame. A common mistake that newbies make is to sample the input for the demo mode at a point in the event loop before or after the normal input is read. Hence, they're sampling different data! It's possible that the player might have the fire button down in one part of the event loop and not in another, so you must sample at the same point you read the input for the game normally.
你可能犯的最糟糕的一個錯誤是：在寫出記錄時，在不當的時機對輸入進行了采樣。事實上，應當務必確定采樣和記錄的輸入是遊戲相應的幀所實際使用的輸入。一個新手常犯的錯誤是這樣的，為遊戲示範所進行的采樣超前或落後于遊戲的正确輸入時刻。是以，所采樣到的資料是不同的資料！其可能造成的結果是遊戲玩家在遊戲事件循環的某一部分按下了發射鍵，而在另一部分卻松開了它。是以必須在同一處進行采樣與讀入輸入。
由人工智能控制的示範
記錄遊戲的第二個方法是借助于編寫的人工智能“bot”（機器人）來執行遊戲，就像人們聯網玩Quake一樣。bot在遊戲處于示範模式時會如同一個參與遊戲的人工智能角色一樣地玩遊戲。這種方法惟一的問題（除技術複雜外）是bot可能沒有展示出所有“酷”的房間、武器等等，因為它并不知道它在制作遊戲的示範。另一方面，采用bot參與遊戲的最大好處是每一個示範都不相同，并且這種多樣性在展示遊戲的時候很有價值，因為觀看者不會覺得乏味。
在遊戲中制作bot和制作其他的人工智能角色一樣。基本上你隻需将其與你的遊戲輸入接口連接配接起來并重載标準輸入流即可，如圖11-13的C所示。然後為bot編寫人工智能算法，設定一些主要的目标，如找出迷宮的路徑、射殺所見的每一個東西，或其他任務等。之後就簡單了，你隻需任由bot運作，直到玩家取而代之。
儲存遊戲的手段
在遊戲程式設計中，編寫儲存遊戲部分是最令人頭疼的事情之一。這是遊戲程式員最後才做的事情之一。關鍵是編寫遊戲的時候，就要考慮到你所編寫的遊戲應當為玩家提供儲存遊戲進度的功能。
在任何時候都能儲存遊戲意味着要記錄遊戲中每一個變量和每一個對象。是以在一個檔案中，你必須記錄所有的全局變量和每個對象的狀态。最佳的實作途徑是采用面向對象的方法來處理。與其編寫一個函數去記錄每個對象的狀态和所有的全局變量，倒不如使每個對象知道如何将自己的狀态讀出并寫入磁盤檔案。
為儲存遊戲，你所要做的就是編寫全局變量然後建立一個簡單的函數。由函數通知遊戲中的每個對象将其自身的狀态寫出。然後，當需要讀回遊戲進度的時候，你要做的就隻是将這些全局變量讀入系統，然後将所有對象的狀态讀入遊戲。
用這種辦法，如果你新增加了一個對象或對象類型，加載/儲存過程隻局限于該對象自身，而不會影響整個程式。
實作多人遊戲
下一個遊戲程式設計的花招是實作多人遊戲。當然，如果你想編寫一個網絡遊戲，那就另當别論了——盡管DirectPlay使得通信部分變得更為容易。然而，如果你希望的隻是讓兩個或兩個以上的玩家同時或輪流地玩你的遊戲，那你隻需增加一些額外的資料結構、稍微調整一下程式即可。
輪流
輪流的實作既簡單又複雜。說其簡單是因為既然你能夠實作一個玩家，為了實作兩個或更多玩家，隻需提供多于一個的遊戲玩家記錄即可。說它難是因為在切換時你必須為每一個玩遊戲者提供遊戲儲存的功能。是以通常而言，如果你的遊戲需要具備輪流切換選項，你就必須在遊戲中實作儲存的功能。顯而易見，遊戲玩家在輪換的時候并不知道遊戲已被儲存。
根據這點，下面依次列出了兩人輪流玩的遊戲所需的制作步驟：
1.
開始遊戲，玩家1開始。
2.
玩家1玩遊戲直到結束。
3.
玩家1的遊戲狀态被儲存，玩家2開始。
4.
玩家2玩遊戲直到結束。
5.
玩家2的狀态被儲存（這時進行輪換）。
6.
将玩家1先前被儲存的遊戲重新加載，玩家1繼續。
7.
回到步驟2。
你可以看到，輪換發生于步驟5，随後遊戲便在兩個玩家間輪流進行。假如遊戲的玩家是兩個以上，隻需簡單地在他們間輪流進行（一次隻能一個人玩），直到輪流到最後一個，然後再從頭開始。
分屏
實作兩個或兩個以上的玩家同時在同一個螢幕上玩遊戲比玩家輪流交換要複雜一些。因為你不得不将遊戲編寫得複雜一些——将玩家間的遊戲規則、沖突和互動考慮進去。而且在同一時刻多人玩的情況下，你必須為每個玩家配置設定指定的輸入裝置。這通常是指每個玩家配置設定一根遊戲操縱杆，或一個玩家使用鍵盤而另一個使用遊戲杆。
同一時刻多人參與的遊戲還有一個問題是，一些遊戲并不适于這樣做。例如在卷軸遊戲中，一個玩家想走這條路而另一個玩家卻想走另一條路。這将造成抵觸，你不得不予以考慮。是以最适于多人同時玩的是單螢幕格鬥遊戲，或多人為了同一個目标而走到一起的遊戲。
但如果你允許玩家自由地走動，這時你可以建立如圖11-14所示的分屏的顯示。
圖11-14：分屏遊戲顯示
多畫面顯示的惟一問題是多畫面顯示！你必須産生出兩個或更多的遊戲畫面。這在技術上極具挑戰性。此外，螢幕上或許沒有足夠的空間用于顯示兩幅或兩幅以上的畫面，因而玩家很難看到所發生的事情。但是如果你能實作分屏功能，最起碼它是一個非常酷的選項……
多線程程式設計技術
到目前為止，本書所談及的所有示範程式都是使用單線程事件循環和程式設計模型。事件循環對玩家的輸入作出響應并以每秒30幀以上的速度渲染遊戲畫面。在對玩家作出反應的同時，遊戲每秒要執行數百萬次的運算，同時處理數十或數百個諸如繪制所有的物體、取得輸入資料、播放音樂等小任務。圖11-15展示了标準遊戲循環。
圖11-15：标準DOS單任務遊戲循環
由圖11-15中可知，遊戲邏輯以串行（順序）方式來完成各項任務。當然也有例外，比如通過中斷來完成一些簡單的邏輯任務，諸如音樂、輸入控制等。但總地說來，遊戲就是一個長長的函數調用序列。
盡管每一項任務都是順序執行，但由于計算機足夠快，其執行的結果就如同同時發生一般，這樣便使遊戲看上去非常流暢和真實。是以，大多數遊戲程式是一個單任務執行線程——順序執行一些操作并輸出每一幀所需要的結果。這是解決問題最好的方法之一，也是DOS遊戲程式設計的必然結果。
然而在今天，DOS時代已成為過去，是以現在是發揮Windows 95/98/ME/XP/NT/2000多線程威力的時候了，我打賭你會喜歡的！
這節内容将就Windows 95/98/NT下的執行線程（thread of execution）進行探讨。通過使用線程可以輕易地在一個應用程式中運作多個任務。在開始之前，讓我們先看一些術語，這樣提到它們的時候不會太突兀。
多線程程式設計的術語
在計算機詞典裡有各種各樣以“multi-”開頭的詞語。讓我們先談一談多處理器（Multiprocessor）和多重處理（Multiprocessing），最後再讨論多線程（multithreading）。
一台多處理器計算機是指具有多個處理器的計算機。Cray和Connection Machine就屬于這類。Connection Machine計算機可以安裝多達64000個處理器（構成一個超立方體網絡），其中每一個處理器均用于執行代碼。
對一般消費者而言，購買配置有四個PIII+處理器的計算機用于運作Windows NT可能比較實際。通常它們都是SMP（對稱多處理，Symmetrical Multiprocessing）系統，即四個處理器可以對稱地執行任務。實際上，情況并非總是如此，因為作業系統核心隻運作在一個處理器上，但随着程序數量增加，其他任務便均勻地運作在每個處理器上。是以說，多處理器計算機的概念就是利用多個處理器來分擔工作量。
對于某些系統，在每個處理器上隻能執行一項任務或一個程序，而在其他系統上，如Windows NT，每個處理器上可運作數千個任務。基本上這便是多重處理——多個任務運作在一台具有單個（或多個）處理器的計算機上。
最新的概念是多線程，也是今天最令人感興趣的術語。在Windows 95/98/NT/2000下的程序就是一個完整的程式；盡管有些時候程序不能夠獨立地運作，通常情況下它的确是一個應用程式。它能夠擁有自己的記憶體空間、上下文，并獨立存在。
較之程序，線程（thread）是更為簡單的程式實體。線程由程序建立，彼此間各不相同，結構簡單并運作在建立它們所在的程序的位址空間内。線程的美妙之處在于它們能獲得盡量多的處理器時間，并存在于建立它們的父程序的位址空間内。
這意味着與線程的通信非常簡單。本質上，線程恰是遊戲程式員所需要的：一個執行線程并行地和其他的主程式任務一起工作，并可以通路程式中的變量。
既然帶有“multi-”字首，是以你有必要搞清楚幾個概念。首先，Windows 95、98、NT和2000都是多任務/搶先式作業系統。這表明任何任務、程序或線程都不能完全控制計算機。每一項任務、程序或線程在某種程度上都可被打斷或被阻塞，而允許下一個執行線程開始運作。這與Windows 3.1完全不同——在Windows 3.1不是搶先式的。如果在每個循環中沒有調用GetMessage(...)，其他程序就不工作。而在Windows 95/98/NT/2000下，你可以設定一個無限FOR循環，而作業系統依然能使其他任務照常運作。
而在Windows 95/98/NT/2000下，每一個程序或線程都有一個優先級，這個優先級決定了每個程序或線程在被打斷之前的運作時間。是以，如果有10個相同的優先級程序，那麼它們的運作時間相同或以循環的方式被處理。可是如果有一個線程具有核心級的優先級，該線程在每個循環中将獲得更多的運作時間，如圖11-16所示。
圖11-16：具有相等或不等優先級的輪轉線程執行過程
最後，問題出現了：Windows 95/98/NT/2000的多線程間有什麼差別？它們之間當然有一些差別。但符合Windows 95作業系統模型的程式大多可安全地運作在其他所有平台上。這是最基礎的作業系統。盡管98和NT的穩定性更好一些，但在本節裡我将仍然使用Windows 95機器來運作大部分的程式執行個體。
為何要在遊戲中使用線程？
現在這個答案是非常明顯的了。事實上，我想你随時都可以列出1000件可以用線程來做的事情。然而，假如你無法做到這一點（比如你剛剛從Mountain Dew（或Sobe，我最近愛上了它）的宿醉中醒過來），下面我列出一些用到多線程程式設計的地方：
? 更新動畫
? 産生環繞音響效果
? 控制小對象
? 查詢輸入裝置
? 更新全局資料結構
? 建立彈出菜單和控件
上述最後一項是我經常使用的。在遊戲正在運作的時候建立菜單并允許玩家改變設定，這一直是令人頭疼的事。但是用線程處理起來就簡單多了。
到目前為止，我依然沒有回答為什麼要在遊戲程式設計中使用線程而不使用一個龐大循環和函數調用這個問題。的确，線程完成的工作它們也能完成，但當你所建立的面向對象的程式越來越大，達到一定程度時，你就需要提出類似于自動機（Automaton）的結構。這些便是代表遊戲角色的對象——你希望在建立和銷毀的時候對遊戲主循環沒有邏輯副作用。這可以通過C++類并結合多線程程式設計來實作。
在開始你的第一個多線程程式前，讓我們搞清楚一下事實：在單處理器機器上，一次隻能運作一個線程。是以天下并沒有免費的午餐，但畢竟這是适應軟體的方法學，是以確定你是為了簡便性和正确性而進行多線程程式設計。圖11-17表示了一個主程序和三個線程同時執行的情況。
圖11-17：主程序産生三個子線程
圖中的時間表明了不同的線程對處理器的占用時間，機關是毫秒。如你所見，一次隻有一個線程在運作，但它們可以打亂順序運作，并根據優先級高低來确定運作時間。
前戲足夠了。讓我們看一些代碼吧！
取得一個線程
在下面的例子中，你将使用控制台模式程式。再次強調，請正确地編譯這些程式。（我已不堪多言，因為我每小時要收到30~60封來自我寫的幾本書的讀者的有關錯誤使用VC++編譯器的電子郵件。難道就沒有人讀前言嗎？）
還有一條告誡是：對于這些例子，你必須使用支援多線程的庫（Multithreaded Library）。進入MS DEV Studio的主菜單，選擇Project、Setting，在C++表欄的Category: Code Generatrion選項裡，将Use Run-time Library設定為Multithreaded。如圖11-18所示。此外，確定将優化（Optimization）選項設為off。因為有時候該選項會影響多線程同步代碼，是以最好将其關掉以防不測。
圖11-18：使用多線程庫建立一個控制台應用程式
注意
我有一種似曾相識的感覺。真的是似曾相識嗎？還是随機的假象？
如果你沒有這種感覺，你就不會知道你沒有的是什麼，那樣倒也無所謂。：）
一切就緒，讓我們開始吧。建立一個線程很簡單，而防止其被損壞才是困難的部分！Win32 API調用的格式如下：
HANDLE CreateThread(
LPSECURITY_ATTRIBUTES lpThreadAttributes,
// pointer to thread security attributes
DWORD dwStackSize, // initial thread stack size, in bytes
LPTHREAD_START_ROUTINE lpStartAddress,
// pointer to thread function
LPVOID lpParameter, // argument for new thread
DWORD dwCreationFlags, // creation flags
LPDWORD lpThreadId ); // pointer to returned thread identifier
lpThreadAttributes指向一個SECURITY_ATTRIBUTES結構，該結構指定了這個線程的安全屬性。如果這個lpThreadAttributes值為NULL，該線程就以預設的安全描述字建立，并且傳回的句柄不會被繼承。
dwStackSize指定線程堆棧的大小（機關是位元組）。如果指定其值為0，堆棧的大小就與程序的主線程相同。堆棧在程序的記憶體空間内自動配置設定，并在程序結束時釋放。如有必要堆棧大小可以增加。
CreateThread試圖配置設定大小為dwStackSize位元組數的記憶體，并在可用記憶體不足時傳回配置設定失敗消息。
lpStartAddress指向線程所要執行的由應用程式提供的函數，同時這也代表線程的開始位址。該函數接受一個32位的參數并傳回一個32位的值。
lpParameter定義一個傳遞給線程的32位參數值。
lpThreadId指向一個儲存線程辨別符的32位變量。
如果該函數執行成功，其傳回值是指向下一個新線程的句柄。如果該函數執行失敗，将傳回NULL。若要獲得更多的錯誤資訊，調用GetLastError()函數。
The function call might look a bit complex, but it's really not. It just allows a lot of control. You won't use much of its functionality in most cases.
該函數調用看上去有些複雜，但并非如此。它隻是提供了更多的控制功能。大多數情況下，你會用到的功能并不多。
當處理完一個線程時，你應當關閉該線程的句柄。換言之，就是讓系統知道你不再使用該對象。該功能通過調用函數CloseHandle()實作，該函數使用CreateThread()函數傳回的句柄，并将對應該核心對象的引用計數器減1。
對于每個線程都需要這麼處理。這不會強行結束該線程，隻是用于告訴系統，該線程處于結束運作狀态。該線程要麼自己結束，要麼被通知（使用函數TerminateThread()）結束，或者在主線程結束時被作業系統結束。這些我們以後會逐一讨論，現在隻需知道這是退出多線程程式之前必須要進行的一個起清除作用的調用。下面是該函數的原型：
BOOL CloseHandle(HANDLE hObject ); // handle to object to close
hObject表示了一個已打開的對象句柄。如果函數調用成功，将傳回TRUE；如果失敗，傳回FALSE。調用函數GetLastError()可得到詳細的出錯資訊。此外，CloseHandle()也适于關閉下列對象的句柄：
? 控制台輸入或輸出
? 事件檔案
? 檔案映射
? 互斥體（Mutex）
? 命名管道
? 程序
? 信号量（Semaphore）
? 線程
基本上說來，CloseHandle()使指定對象句柄無效，縮減對象句柄的引用計數，并進行對象存活性測試。當一個對象的最後一個句柄被關閉後，對象就從作業系統中被移除。
警告
一個新線程的句柄在建立時對該線程具有完全的通路權限。如果沒有提供安全描述符，該句柄可以被任何需要該線程句柄的函數使用。當提供安全描述符後，所有使用該句柄的通路都要進行權限檢查。如果檢查結果為拒絕，那麼請求的程序将被拒絕使用該句柄通路該線程。
現在來看一些代碼，它們代表一個能夠被傳遞給函數CreateThread()的線程：
DWORD WINAPI My_Thread(LPVOID data)
{
// .. do work
// return an exit code at end, whatever is appropriate for your app
return(26);
} // end My_Thread
現在你已具備了建立你的第一個多線程應用程式所需的一切條件。第一個例子将向你展示一個單線程的建立過程。被建立出的從線程列印出數字2，主線程（即主程式）将列印出數字1。DEMO11_5.CPP包括整個程式，如下所示：
// DEMO11_5.CPP - Creates a single thread that prints
// simultaneously while the Primary thread prints.
// INCLUDES
#define WIN32_LEAN_AND_MEAN // make sure win headers
// are included correctly
#include // include the standard windows stuff
#include // include the 32 bit stuff
#include
#include
#include
#include
#include
#include
#include
// DEFINES
// PROTOTYPES //
DWORD WINAPI Printer_Thread(LPVOID data);
// GLOBALS /
// FUNCTIONS ///
DWORD WINAPI Printer_Thread(LPVOID data)
{
// this thread function simply prints out data
// 25 times with a slight delay
for (int index=0; index<25; index++)
{
printf("%d ",data); // output a single character
Sleep(100); // sleep a little to slow things down
} // end for index
// just return the data sent to the thread function
return((DWORD)data);
} // end Printer_Thread
// MAIN ///
void main(void)
{
HANDLE thread_handle; // this is the handle to the thread
DWORD thread_id; // this is the id of the thread
// start with a blank line
printf("/nStarting threads.../n");
// create the thread, IRL we would check for errors
thread_handle = CreateThread(NULL, // default security
0, // default stack
Printer_Thread, // use this thread function
(LPVOID)1, // user data sent to thread
0, // creation flags, 0=start now.
&thread_id); // send id back in this var
// now enter into printing loop, make sure this takes longer than thread,
// so thread finishes first
for (int index=0; index<50; index++)
{
printf("2 ");
Sleep(100);
} // end for index
// at this point the thread should be dead
CloseHandle(thread_handle);
// end with a blank line
printf("/nAll threads terminated./n");
} // end main
輸出示例：
Starting threads...
2 1 2 1 2 1 2 1 1 2 2 1 1 2 2 1 1 2 2 1 1 2 2 1 1 2
2 1 1 2 2 1 1 2 2 1 1 2 2 1 1 2 2 1 1 2 2 1 1 2 2 2
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
All threads terminated.
正如你所看到的輸出結果，每一個線程隻運作很短的一段時間，然後系統便切換至另一個正等待運作的線程。在這種情況下，作業系統隻是簡單地在主線程和從線程間來回切換。
現在讓我們試着建立一個多線程程式。你隻需對DEMO11_5.CPP略加修改便可實作該功能。你隻需多次調用CreateThread()函數，每次調用就建立一個線程。而且每次傳遞給所建立線程的資料将被列印出來，這樣便可以區分你所建立的線程。
DEMO11_6.CPP|EXE包含了修改後的多線程程式，我在下面列出供你參考。注意在這裡我用數組儲存線程句柄和ID。
// DEMO11_6.CPP - A new version that creates 3
// secondary threads of execution
// INCLUDES /
#define WIN32_LEAN_AND_MEAN // make sure certain headers
// are included correctly
#include // include the standard windows stuff
#include // include the 32 bit stuff
#include
#include
#include
#include
#include
#include
#include
// DEFINES ///
#define MAX_THREADS 3
// PROTOTYPES ///
DWORD WINAPI Printer_Thread(LPVOID data);
// GLOBALS /
// FUNCTIONS //
DWORD WINAPI Printer_Thread(LPVOID data)
{
// this thread function simply prints out data
// 25 times with a slight delay
for (int index=0; index<25; index++)
{
printf("%d ",(int)data+1); // output a single character
Sleep(100); // sleep a little to slow things down
} // end for index
// just return the data sent to the thread function
return((DWORD)data);
} // end Printer_Thread
// MAIN ///
void main(void)
{
HANDLE thread_handle[MAX_THREADS]; // this holds the
// handles to the threads
DWORD thread_id[MAX_THREADS]; // this holds the ids of the threads
// start with a blank line
printf("/nStarting all threads.../n");
// create the thread, IRL we would check for errors
for (int index=0; index {
thread_handle[index] = CreateThread(NULL, // default security
0, // default stack
Printer_Thread, // use this thread function
(LPVOID)index, // user data sent to thread
0, // creation flags, 0=start now.
&thread_id[index]); // send id back in this var
} // end for index
// now enter into printing loop, make sure
// this takes longer than threads,
// so threads finish first, note that primary thread prints 4
for (index=0; index<75; index++)
{
printf("4 ");
Sleep(100);
} // end for index
// at this point the threads should all be dead, so close handles
for (index=0; index CloseHandle(thread_handle[index]);
// end with a blank line
printf("/nAll threads terminated./n");
} // end main
輸出示例：
Starting all threads...
4 1 2 3 4 1 2 3 4 1 2 3 1 4 2 3 4 1 2 3 1 4 2 3 4
1 2 3 1 4 2 3 4 1 2 3 1 4 2 3 4 1 2 3 4 1 2 3 4 1
2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2
3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3
4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
All threads terminated.
哇！是不是很酷？建立多線程是如此容易。如果你頭腦反應比較快，說不定你已經聽得厭煩，并會質疑：為何每次線程回調都使用同一個函數？這樣做的原因在于所有的變量都在堆棧中建立，而且每一個線程都有自己的堆棧。是以每個線程都能正常工作。如圖11-19所示。
圖11-19：主線程和從線程記憶體和程式空間分布
圖11-19描述了非常重要的一點：終止（Termination）。兩個線程都是自行終止運作的，但主線程對此沒有控制。此外，主線程也無法判斷其他線程是否已運作完畢或已終止（隻要它們還能夠傳回）。
我們需要的是一種線上程間通信和檢查各線程的狀态的方法。使用函數TerminateThread()結束函數是一種強制的方法，一般不建議讀者使用。
線程間的消息傳遞
讓我們看一看主線程是如何控制其所建立的子線程的。例如，主線程可能需要結束所有的子線程。怎樣才能實作呢？有以下兩種方法可以結束一個線程：
?
向該線程發送消息通知其結束（正确的方法）。
?
使用核心級的調用強行結束該線程（錯誤的方法）。
盡管在某些情況下也不得不使用錯誤的方法，但這樣是不安全的。因為這種方法隻是簡單地将線程的部分回收。當該線程需要執行清理操作時，将無法進行。這會造成記憶體和資源資訊的洩漏。是以在使用這種方法時要慎之又慎。圖11-20示意了使用這兩種方法結束線程的過程。
圖11-20：線程終止方法
首先來看一看如何使用TerminateThread()函數，然後看一個有關向線程發送結束消息以通知該線程執行結束操作的例子。
BOOL TerminateThread(HANDLE hThread, // handle to the thread
DWORD dwExitCode ); // exit code for the thread
hThread指明了要結束的線程。該句柄必須能夠通路THREAD_TERMINATE。
dwExitCode定義線程的退出代碼。使用GetExitCodeThread()函數以獲得線程的退出值。
如果函數調用成功，傳回值為TRUE；否則傳回值為FALSE。調用函數GetLastError()可得到詳細的出錯資訊。
TerminateThread()函數用于退出一個線程。當調用該函數時，目标線程就停止執行任何使用者代碼，并且其初始堆棧不會被釋放。而連接配接到該線程的動态連接配接庫并不會收到該線程正在結束的通知，這是不好的地方之一。：）
TerminateThread()函數的用法非常簡單，隻需簡單地調用被結束線程的句柄，并重載傳回代碼，此後該線程就不複存在了。可是不要誤解我的意思，畢竟如果此函數沒用的話就不會存在了。是以，用它的時候要確定你已經考慮周詳并明白該函數可能帶來的後果。
下面介紹通過由從線程監控的全局變量來進行消息傳遞的線程終止方法。當從線程檢測到該全局終止标志被設定時，從線程便全部結束。可是主線程如何知道所有的從線程結束了呢？完成該功能的一個方法是設定另一個線上程終止的時候遞減的全局變量——也就是某種引用計數器。
該計數器可以被主線程監測，當它為0時說明所有的從線程都已結束，主線程此刻可以安全地繼續工作并關閉線程的句柄。下面給出一個完整的消息傳遞系統例子，之後，我們離真正的程式設計就不遠了。DEMO11_7.CPP|EXE示範了全局消息傳遞的過程，如下所示：
// DEMO11_7.CPP - An example of global message passing to control
// termination of threads.
// INCLUDES ///
#define WIN32_LEAN_AND_MEAN // make sure certain headers
// are included correctly
#include // include the standard windows stuff
#include // include the 32 bit stuff
#include
#include
#include
#include
#include
#include
#include
// DEFINES //
#define MAX_THREADS 3
// PROTOTYPES //
DWORD WINAPI Printer_Thread(LPVOID data);
// GLOBALS /
int terminate_threads = 0; // global message flag to terminate
int active_threads = 0; // number of active threads
// FUNCTIONS
DWORD WINAPI Printer_Thread(LPVOID data)
{
// this thread function simply prints out data until it is told to terminate
for(;;)
{
printf("%d ",(int)data+1); // output a single character
Sleep(100); // sleep a little to slow things down
// test for termination message
if (terminate_threads)
break;
} // end for index
// decrement number of active threads
if (active_threads > 0)
active_threads--;
// just return the data sent to the thread function
return((DWORD)data);
} // end Printer_Thread
// MAIN //
void main(void)
{
HANDLE thread_handle[MAX_THREADS]; // this holds the
// handles to the threads
DWORD thread_id[MAX_THREADS]; // this holds the ids of the threads
// start with a blank line
printf("/nStarting Threads.../n");
// create the thread, IRL we would check for errors
for (int index=0; index < MAX_THREADS; index++)
{
thread_handle[index] = CreateThread(NULL, // default security
0, // default stack
Printer_Thread, // use this thread function
(LPVOID)index, // user data sent to thread
0, // creation flags, 0=start now.
&thread_id[index]);// send id back in this var
// increment number of active threads
active_threads++;
} // end for index
// now enter into printing loop, make sure this
// takes longer than threads,
// so threads finish first, note that primary thread prints 4
for (index=0; index<25; index++)
{
printf("4 ");
Sleep(100);
} // end for index
// at this point all the threads are still running,
// now if the keyboard is hit
// then a message will be sent to terminate all the
// threads and this thread
// will wait for all of the threads to message in
while(!kbhit());
// get that char
getch();
// set global termination flag
terminate_threads = 1;
// wait for all threads to terminate,
// when all are terminated active_threads==0
while(active_threads);
// at this point the threads should all be dead, so close handles
for (index=0; index < MAX_THREADS; index++)
CloseHandle(thread_handle[index]);
// end with a blank line
printf("/nAll threads terminated./n");
} // end main
輸出示例：
Starting Threads...
4 1 2 3 4 2 1 3 4 3 1 2 4 2 1 3 4 3 1 2 4 2 1 3 4 2
3 1 4 2 1 3 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1
4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2
3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 2 3 1 3 2
1 1 2 3 3 2 1 1 2 3 3 2 1 1 2 3 3 2 1 1 2 3 3 2 1 1 2
3 3 2 1 2 3 1 3 2 1 2 3 1 3 2 1 2 3 1 3 2 1 2 3 1 3 2
1 3 1 2 3 2 1 3 1 2 3 2 1
All threads terminated.
如輸出所示，當使用者敲擊一個鍵時，所有的線程被結束，随後主線程也被結束。這種方法有兩個問題。第一個問題比較不明顯。下面是它的具體案例，多看幾遍你便會發現問題：
1. 假定隻剩一個從線程沒有關閉。
2. 假定最後一個線程對處理器擁有控制，并遞減跟蹤激活線程數的全局變量值。
3. 就在這一刹那，程序切換到主線程。主線程監測全局變量并認為所有的線程都已結束，然而最後一個線程卻還沒有傳回！
在大多數情況下，這不是一個問題，但是如果遞減代碼和傳回代碼之間還有代碼，便會出現這個問題。是以我們需要一個函數來詢問線程是否已結束。很多情況下，這是非常有幫助的。參考一下Wait*()系列函數，對程式設計會大有益處。
第二個問題是當你建立了一個忙循環（Busy Loop）或輪詢的循環。在Win16/DOS系統下，該循環會良好地執行，但在Win32下，就很不好。在一個封閉的循環中，等待一個變量，會給多任務核心帶來繁重的負擔并嚴重占用CPU資源。
可以使用Windows附帶的SYSMON.EXE（Windows 95/98/ME/XP的附件中）、PERFMON.EXE（Windows NT/2000）或類似的第三方CPU占用率測試工具來進行測定。這些工具軟體會有助于你明白線程的運作狀态和處理器的占用率。接下來，我們看看Wait*()類函數将如何幫助我們确定一個線程是否結束。
等待合适時機
Get ready for the most confusing explanation you've ever heard… but it's not my fault, really! Whenever any thread terminates, it becomes signaled to the kernel, and when it is running, it is unsignaled. Whatever that means. And what is the price of plastic zippers tomorrow? You don't care! But what you do care about is how to test for the signaling.
我們知道，任何線程結束時都會向核心發出信号（Signaled），而它們運作時不會發出信号（Unsignaled）。需要了解的是如何監測這些信号。
可以使用Wait*()函數族來實作事件監測，該類函數可以實作單信号或多信号的偵測。此外，你可以調用其中一個Wait*()函數來等待，直到信号産生。這樣做就可以避免使用忙循環。在絕大多數情況下，這樣做要遠優于輪詢全局變量的方法。圖11-21示意了Wait*()函數的工作機制以及與運作程式和OS核心間的關系。
圖11-21：使用Wait*()函數的信号時間關系
需要使用的兩個函數分别是WaitForSingleObject()和WaitForMultipleObjects()。這兩個函數分别用于單信号和多信号偵測。它們的定義如下：
DWORD WaitForSingleObject(HANDLE hHandle, // handle of object to wait for
DWORD dwMilliseconds ); // time-out interval in milliseconds
hHandle用于确定對象。
dwMilliseconds定義逾時時間，以毫秒為機關。如果該段時間間隔已經過去，即使偵測對象無信号也要傳回。如果dwMilliseconds值為0，函數就立刻測讀對象的狀态并傳回。如果其值為無限大，則函數永不逾時。
If the function succeeds, the return value indicates the event that caused the function to return. If the function fails, the return value is WAIT_FAILED. To get extended error information, call GetLastError().
如果該函數執行成功，其傳回值包含傳回的條件狀态。如果該函數執行失敗，傳回值是WAIT_FAILED。調用函數GetLastError()可以獲得詳細的出錯資訊。
該函數的成功傳回值有以下幾種：
? WAIT_ABANDONED——所指定的對象是一個互斥對象，該對象在所屬線程結束前不能被線程釋放。互斥對象的所有權被授予調用線程，互斥對象被設定為無信号。
? WAIT_OBJECT_0——指定對象的狀态是有信号的。
? WAIT_TIMEOUT——逾時時間已過，對象的狀态是無信号的。
一般說來，WaitForSingleObject()函數檢查指定對象的目前狀态。如果對象無信号，調用線程就進入一種很有效率的等待狀态。在此期間，該線程隻占用極少的CPU時間，直到它等待的條件之一得到滿足才結束等待。下面是多信号偵測函數，主要用于終止多個線程：
DWORD WaitForMultipleObjects(DWORD nCount, // number of handles
// in handle array
CONST HANDLE *lpHandles, // address of object-handle array
BOOL bWaitAll, // wait flag
DWORD dwMilliseconds ); // time-out interval in milliseconds
nCount定義lpHandles所指向的對象句柄數組中元素的數目。對象句柄的最大數目是MAXIMUM_WAIT_OBJECTS。
lpHandles指向對象句柄的數組。該數組包含不同類型對象的句柄。注意對于Windows NT：句柄必須有SYNCHRONIZE通路。
bWaitAll定義等待類型。如果值為TRUE，則當lpHandles數組中所有對象同時都有信号時傳回。如果值為FALSE，那麼任一對象有信号就傳回。對于後一種情況，傳回值指明了引起函數傳回的的對象。
dwMilliseconds定義逾時時間（機關為毫秒）。即使bWaitAll參數定義的條件沒有得到滿足，隻要逾時間隔已過，該函數也要傳回。如果dwMilliseconds的值為0，函數就立刻偵測指定對象的狀态并傳回。如果其值為無窮，那麼函數永不逾時。
如果該函數執行成功，其傳回值表示引起函數傳回的事件。如果該函數執行失敗，則傳回WAIT_FAILED。調用函數GetLastError()可以獲得詳細的出錯資訊。函數傳回值主要有以下幾種：
?
WAIT_OBJECT_0 到(WAIT_OBJECT_0 + nCount - 1)——如果bWaitAll值為TRUE，則該傳回值表明所有指定對象都有信号。如果其值為FALSE，則傳回值減去WAIT_OBJECT_0，這差給出滿足等待的對象的lpHandles數組索引。如果在調用過程中，檢測到一個以上的對象有信号時，取有信号對象數組索引中的最小值。
?
WAIT_ABANDONED_0到(WAIT_ABANDONED_0 + nCount - 1)——如果bWaitAll值為TRUE，則該傳回值表明所有指定對象都有信号，而且至少有一個對象是被廢棄的互斥對象。如果bWaitAll值為FALSE，則傳回值減去WAIT_ABANDONED_0，這差給出滿足等待的廢棄互斥對象的lpHandles數組索引。
?
WAIT_TIMEOUT——逾時間隔已過，但不滿足由bWaitAll參數指定的條件。
?
WaitForMultipleObjects()函數确定是否滿足退出的等待條件。如果等待條件不滿足，調用線程就進入一個有效率的等待狀态，直到等待條件滿足。在此狀态下，該線程隻消耗很少的系統資源。
使用信令來同步線程
這些解釋的技術性很強，是以需要舉例來說明這些函數的用法，隻要對之前例子中的代碼稍加修改即可。在接下來的版本中，你将移去全局結束信号标志，并建立一個簡單調用函數WaitForSingleObject()的主循環。
移去全局結束消息隻是為了使程式變得簡單些。不可否認，它仍然是通知線程結束的最好方法。但由于處于忙循環中，是以不是測試線程自身是否已結束的最好方法。
這也是使用WaitForSingleObject()調用的原因所在。該調用處于一個占用較少CPU時間的、虛拟的等待循環中。而且因為函數WaitForSingleObject()隻能等待一個信号，即隻能用于一個線程的結束，是以這個例子中隻有一個從線程。
稍後，我們将重寫程式。新程式将包含三個線程，并使用WaitForMultipleObjects()來等待它們全部結束。DEMO11_8.CPP|EXE就使用了WaitForSingleObject()來結束單線程，并建立了另外一個線程，其代碼如下：
// DEMO11_8.CPP - A single threaded example of
// WaitForSingleObject(...).
// INCLUDES //
#define WIN32_LEAN_AND_MEAN // make sure certain
// headers are included correctly
#include // include the standard windows stuff
#include // include the 32 bit stuff
#include
#include
#include
#include
#include
#include
#include
// DEFINES //
// PROTOTYPES //
DWORD WINAPI Printer_Thread(LPVOID data);
// GLOBALS /
// FUNCTIONS //
DWORD WINAPI Printer_Thread(LPVOID data)
{ // this thread function simply prints out data 50
// times with a slight delay
for (int index=0; index<50; index++)
{
printf("%d ",data); // output a single character
Sleep(100); // sleep a little to slow things down
} // end for index
// just return the data sent to the thread function
return((DWORD)data);
} // end Printer_Thread
// MAIN ///
void main(void)
{
HANDLE thread_handle; // this is the handle to the thread
DWORD thread_id; // this is the id of the thread
// start with a blank line
printf("/nStarting threads.../n");
// create the thread, IRL we would check for errors
thread_handle = CreateThread(NULL, // default security
0, // default stack
Printer_Thread, // use this thread function
(LPVOID)1, // user data sent to thread
0, // creation flags, 0=start now.
&thread_id); // send id back in this var
// now enter into printing loop, make sure
// this is shorter than the thread,
// so thread finishes last
for (int index=0; index<25; index++)
{
printf("2 ");
Sleep(100);
} // end for index
// note that this print statement may get
// interspliced with the output of the
// thread, very key!
printf("/nWaiting for thread to terminate/n");
// at this point the secondary thread so still be working,
// now we will wait for it
WaitForSingleObject(thread_handle, INFINITE);
// at this point the thread should be dead
CloseHandle(thread_handle);
// end with a blank line
printf("/nAll threads terminated./n");
} // end main
輸出示例：
Starting threads...
2 1 2 1 2 1 1 2 2 1 1 2 2 1 1 2 2 1 1 2 2 1
1 2 2 1 1 2 2 1 1 2 2 1 1 2 2 1 1 2 2 1 1 2 2 1 1 2 2 1 1
Waiting for thread to terminate
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
All threads terminated.
這個程式很簡單。通常在建立從線程後就進入列印循環。當這些終止時，調用函數WaitForSingleObject()。如果主線程還有其他工作要做，則繼續進行。但在本例中，主線程沒有其他任務，因而直接進入等待狀态。如果你在運作該程式之前運作了SYSMON.EXE，你會看見進入等待狀态後CPU的占用率極低，而在忙循環中CPU被占用得相當厲害。
在這裡，函數WaitForSingleObject()有一個使用技巧。假如想知道一個線程在調用該函數時的狀态，可以通過用NULL調用WaitForSingleObject()函數來實作，源代碼如下：
//...code
DWORD state = WaitForSingleObject(thread_handle, 0); // get the status
// test the status
if (state==WAIT_OBJECT_0) { // thread is signaled, i.e. terminated }
else
if (state==WAIT_TIMEOUT) { // thread is still running }
//...code
簡單之至，這是檢測一個特定的線程是否已結束的絕妙方法。結合這一方法使用全局終止消息是一種非常可靠的終止線程的方法。同時該方法是在實時循環中檢測某個線程是否已終止，而無須進入等待狀态的好方法。
等待多個對象
問題現在幾乎都解決了。Wait*()類函數的最後一個函數就是一個用于等待多個對象或線程信号的函數。我們現在試着編寫使用該函數的程式。我們所要做的就是建立一個線程數組，然後将該句柄數組與若幹參數一起傳遞給WaitForMultipleObjects()函數。
當該函數傳回時，如果一切正常，那麼所有的線程應該都已終止。DEMO11_9.CPP|EXE與DEMO11_8.CPP|EXE相似，隻不過它是建立多線程，然後主線程等待所有其他線程終止而已。在這裡，不使用全局終止标志，因為你已知道如何實作這一功能。每個從線程運作幾個周期後就終止。DEMO11_9.CPP的源代碼如下所示：
// DEMO11_9.CPP -An example use of
// WaitForMultipleObjects(...)
// INCLUDES ///
#define WIN32_LEAN_AND_MEAN // make sure certain headers
// are included correctly
#include // include the standard windows stuff
#include // include the 32 bit stuff
#include
#include
#include
#include
#include
#include
#include
// DEFINES ///
#define MAX_THREADS 3
// PROTOTYPES /
DWORD WINAPI Printer_Thread(LPVOID data);
// GLOBALS
// FUNCTIONS //
DWORD WINAPI Printer_Thread(LPVOID data)
{
// this thread function simply prints out data 50
// times with a slight delay
for (int index=0; index<50; index++)
{
printf("%d ",(int)data+1); // output a single character
Sleep(100); // sleep a little to slow things down
} // end for index
// just return the data sent to the thread function
return((DWORD)data);
} // end Printer_Thread
// MAIN
void main(void)
{
HANDLE thread_handle[MAX_THREADS]; // this holds the
// handles to the threads
DWORD thread_id[MAX_THREADS]; // this holds the ids of the threads
// start with a blank line
printf("/nStarting all threads.../n");
// create the thread, IRL we would check for errors
for (int index=0; index {
thread_handle[index] = CreateThread(NULL, // default security
0, // default stack
Printer_Thread,// use this thread function
(LPVOID)index, // user data sent to thread
0, // creation flags, 0=start now.
&thread_id[index]); // send id back in this var
} // end for index
// now enter into printing loop,
// make sure this takes less time than the threads
// so it finishes first
for (index=0; index<25; index++)
{
printf("4 ");
Sleep(100);
} // end for index
// now wait for all the threads to signal termination
WaitForMultipleObjects(MAX_THREADS, // number of threads to wait for
thread_handle, // handles to threads
TRUE, // wait for all?
INFINITE); // time to wait,INFINITE = forever
// at this point the threads should all be dead, so close handles
for (index=0; index CloseHandle(thread_handle[index]);
// end with a blank line
printf("/nAll threads terminated./n");
} // end main
輸出示例：
Starting all threads...
4 1 2 3 4 1 2 3 1 4 2 3 2 4 1 3 1 4 2 3 2 4 1 3
1 4 2 3 2 4 1 3 1 4 2 3 2 4 1 3 1 4 2 3 2 4 1 3
1 4 2 3 2 4 1 3 1 4 2 3 2 4 1 3 1 4 2 3 2 4 1 3
1 4 2 3 2 4 1 3 1 4 2 3 2 4 1 3 1 4 2 3 2 4 1 3
1 4 2 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1
3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1
3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3
All threads terminated.
輸出正如你所預料的那樣。所有線程和主線程一樣都進行了列印輸出工作，但當主線程的循環完成時，次線程将繼續進行，直到它們全部完成為止。由于函數WaitForMultipleObjects()的阻塞作用，隻當所有線程全部結束後，主線程才終止傳回。
多線程和DirectX
現在我們對多線程有了一定的了解。下一個問題便是如何将其運用于遊戲程式和DirectX程式設計。放手去做——這裡有你需要的一切。當然，必須確定編譯時使用多線程庫而不是單線程庫。并且，在處理大量的DirectX資源時，我們還會遇上許多臨界區（Critical Section）的問題。
對于資源要有一個全局規劃，以防止一個以上的線程通路同一個資源時出現程式崩潰。比如，假定一個線程鎖定了一個表面，而另一個運作中的線程試圖鎖定同一個表面。這樣就會引起問題。這類問題可以使用信号量（Sempahore）、互斥體（Mutex）和臨界區來解決。在這裡我不能逐一詳細探讨。但你可以查閱相應的資料，如由Addsion Wesley出版、Jim Beveridge和Robert Weiner合著的《Multithreading Applications in Win32》。這是關于這方面内容最好的參考書。
為實作這類資源管理程式并正确地共享線程，我們需要建立一個變量來跟蹤其他使用該資源的線程。任何需要使用該資源的線程都必須檢測該變量，之後才能使用它。當然，這依然是個問題，除非這個變量能夠被檢測或獨立（Atomically）地修改，因為你可能正修改一個變量進行到一半而其他線程恰在這時獲得控制權。
可以将這類變量設定為volatile類型以将其問題發生機率最小化，這樣便告知編譯器不要為其進行記憶體拷貝。然而，最終你還不得不使用信号量（Semaphores，一個簡單的類似于全局變量的計數器，但卻是以不能被打斷的基本彙編代碼形式存在）、互斥體（Mutex，隻允許一個線程通路臨界區，是二進制的信号量）、臨界區（Critical Section，指定編譯器在編譯Win32調用時一次隻能允許一個線程）等等。另一方面，如果每一個線程的功能相對比較獨立，也就不必過多考慮這些。
DEMO11_10.CPP|EXE是一個應用多線程程式設計的DirectX執行個體（其16位版本是DEMO11_10_16B.CPP|EXE），讀者可以檢驗一下該程式。該程式建立了許多外星BOB（Blitter Object），并使它們圍繞主線運動。此外該程式還建立了另外一個線程以動态改變這些BOB的顔色。這是一個非常簡單、安全的多線程程式範例。最後要確定将該程式連上所有DirectX .LIB檔案。
但是，如果有許多線程都調用同一函數，就會産生可重入性（Reentrancy）的問題。需要重入的函數必須要有狀态資訊，而且不能使用可能會被具有搶占優先權的線程進出程式時破壞的全局變量。
此外，如果使用線程來使DirectX對象自己動起來，表面事故、計時及同步過程很可能會出錯。是以建議讀者嚴格限制使用線程來處理那些在很大程度上是獨立的、隻存在于它們自己的“狀态空間”中的并且不需要以精确頻率運作的對象。
進階多線程程式設計
好了！本章到此也告一段落。因為接下來我們隻能探讨競争條件、死鎖、臨界區、互斥體、信号量以及許多令人頭疼的問題。澄清所有這些問題（除了最後一個）都會有助于讀者編寫無錯的多線程程式。當然，即使對此一無所知，讀者仍然能夠依據常識編寫出基本安全的多線程程式，記住任何線程都可能會随時被其他線程打斷這個道理。注意你編寫的線程是如何通路共享資料結構的。
盡可能以獨立且自動的方式進行這些操作。確定這樣的事情不會發生：一個線程修改變量，而另一個線程錯誤地使用了正被修改到一半的變量。同時，除本章提及的函數調用外，還有幾個基本函數調用沒有提及，如ExitThread()和GetThreadExitCode()，但這幾個函數相對比較簡單易于了解，并可以在你的API參考書中查到它們。
總結
本章内容讀來比較輕松，沒有太多的技術術語，隻是一頓豐富的知識大餐。我形容它為大餐，呃，大概是因為我在寫作過程中吃了太多Power Bar速食條了。言歸正傳，本章中我們接觸了許多基礎知識：如資料結構、記憶體管理、遞歸、分析、定點數運算和多線程。
其中有些内容乍看與遊戲似乎關系不大，但确實相關。要制作一個遊戲，我們必須了解程式設計的每一方面——因為遊戲的确是如此複雜！現在本章告一段落，我要出門去租《2001: A Space Odyssey》回來看了，因為下一章我們将探讨人工智能……
![【資料結構】 醫院選址[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)