|
游戲算法整理 算法一：A*尋路初探
作者： Patrick Lester
譯者：Panic 2005年3月18日
譯者序：很久以前就知道了A*算法，但是從未認(rèn)真讀過相關(guān)的文章，也沒有看過代碼，只是腦子里有個(gè)模糊的概念。這次決定從頭開始，研究一下這個(gè)被人推崇備至的簡單方法，作為學(xué)習(xí)人工智能的開始。
這篇文章非常知名，國內(nèi)應(yīng)該有不少人翻譯過它，我沒有查找，覺得翻譯本身也是對自身英文水平的鍛煉。經(jīng)過努力，終于完成了文檔，也明白的A*算法的原理。毫無疑問，作者用形象的描述，簡潔詼諧的語言由淺入深的講述了這一神奇的算法，相信每個(gè)讀過的人都會對此有所認(rèn)識（如果沒有，那就是偶的翻譯太差了 --b）。
現(xiàn)在是2005年7月19日的版本，應(yīng)原作者要求，對文中的某些算法細(xì)節(jié)做了修改。
原文鏈接：http://www.gamedev.net/reference/articles/article2003.asp
原作者文章鏈接：http://www.policyalmanac.org/games/aStarTutorial.htm
以下是翻譯的正文。
會者不難，A*(念作A星)算法對初學(xué)者來說的確有些難度。
這篇文章并不試圖對這個(gè)話題作權(quán)威的陳述。取而代之的是，它只是描述算法的原理，使你可以在進(jìn)一步的閱讀中理解其他相關(guān)的資料。
最后，這篇文章沒有程序細(xì)節(jié)。你盡可以用任意的計(jì)算機(jī)程序語言實(shí)現(xiàn)它。如你所愿，我在文章的末尾包含了一個(gè)指向例子程序的鏈接。 壓縮包包括C++和Blitz Basic兩個(gè)語言的版本，如果你只是想看看它的運(yùn)行效果，里面還包含了可執(zhí)行文件。
我們正在提高自己。讓我們從頭開始。。。
序：搜索區(qū)域
假設(shè)有人想從A點(diǎn)移動到一墻之隔的B點(diǎn)，如下圖，綠色的是起點(diǎn)A，紅色是終點(diǎn)B，藍(lán)色方塊是中間的墻。
[圖1]
你首先注意到，搜索區(qū)域被我們劃分成了方形網(wǎng)格。像這樣，簡化搜索區(qū)域，是尋路的第一步。這一方法把搜索區(qū)域簡化成了一個(gè)二維數(shù)組。數(shù)組的每一個(gè)元素是網(wǎng)格的一個(gè)方塊，方塊被標(biāo)記為可通過的和不可通過的。路徑被描述為從A到B我們經(jīng)過的方塊的集合。一旦路徑被找到，我們的人就從一個(gè)方格的中心走向另一個(gè)，直到到達(dá)目的地。
這些中點(diǎn)被稱為“節(jié)點(diǎn)”。當(dāng)你閱讀其他的尋路資料時(shí)，你將經(jīng)常會看到人們討論節(jié)點(diǎn)。為什么不把他們描述為方格呢？因?yàn)橛锌赡苣愕穆窂奖环指畛善渌皇欠礁竦慕Y(jié)構(gòu)。他們完全可以是矩形，六角形，或者其他任意形狀。節(jié)點(diǎn)能夠被放置在形狀的任意位置－可以在中心，或者沿著邊界，或其他什么地方。我們使用這種系統(tǒng)，無論如何，因?yàn)樗亲詈唵蔚摹?/p>
開始搜索
正如我們處理上圖網(wǎng)格的方法，一旦搜索區(qū)域被轉(zhuǎn)化為容易處理的節(jié)點(diǎn)，下一步就是去引導(dǎo)一次找到最短路徑的搜索。在A*尋路算法中，我們通過從點(diǎn)A開始，檢查相鄰方格的方式，向外擴(kuò)展直到找到目標(biāo)。
我們做如下操作開始搜索：
1，從點(diǎn)A開始，并且把它作為待處理點(diǎn)存入一個(gè)“開啟列表”。開啟列表就像一張購物清單。盡管現(xiàn)在列表里只有一個(gè)元素，但以后就會多起來。你的路徑可能會通過它包含的方格，也可能不會。基本上，這是一個(gè)待檢查方格的列表。
2，尋找起點(diǎn)周圍所有可到達(dá)或者可通過的方格，跳過有墻，水，或其他無法通過地形的方格。也把他們加入開啟列表。為所有這些方格保存點(diǎn)A作為“父方格”。當(dāng)我們想描述路徑的時(shí)候，父方格的資料是十分重要的。后面會解釋它的具體用途。
3，從開啟列表中刪除點(diǎn)A，把它加入到一個(gè)“關(guān)閉列表”，列表中保存所有不需要再次檢查的方格。
在這一點(diǎn)，你應(yīng)該形成如圖的結(jié)構(gòu)。在圖中，暗綠色方格是你起始方格的中心。它被用淺藍(lán)色描邊，以表示它被加入到關(guān)閉列表中了。所有的相鄰格現(xiàn)在都在開啟列表中，它們被用淺綠色描邊。每個(gè)方格都有一個(gè)灰色指針反指他們的父方格，也就是開始的方格。
[圖2]
接著，我們選擇開啟列表中的臨近方格，大致重復(fù)前面的過程，如下。但是，哪個(gè)方格是我們要選擇的呢？是那個(gè)F值最低的。
路徑評分
選擇路徑中經(jīng)過哪個(gè)方格的關(guān)鍵是下面這個(gè)等式：
F = G + H
這里：
* G = 從起點(diǎn)A，沿著產(chǎn)生的路徑，移動到網(wǎng)格上指定方格的移動耗費(fèi)。
* H = 從網(wǎng)格上那個(gè)方格移動到終點(diǎn)B的預(yù)估移動耗費(fèi)。這經(jīng)常被稱為啟發(fā)式的，可能會讓你有點(diǎn)迷惑。這樣叫的原因是因?yàn)樗皇莻€(gè)猜測。我們沒辦法事先知道路徑的長度，因?yàn)槁飞峡赡艽嬖诟鞣N障礙(墻，水，等等)。雖然本文只提供了一種計(jì)算H的方法，但是你可以在網(wǎng)上找到很多其他的方法。
我們的路徑是通過反復(fù)遍歷開啟列表并且選擇具有最低F值的方格來生成的。文章將對這個(gè)過程做更詳細(xì)的描述。首先，我們更深入的看看如何計(jì)算這個(gè)方程。
正如上面所說，G表示沿路徑從起點(diǎn)到當(dāng)前點(diǎn)的移動耗費(fèi)。在這個(gè)例子里，我們令水平或者垂直移動的耗費(fèi)為10，對角線方向耗費(fèi)為14。我們?nèi)∵@些值是因?yàn)檠貙蔷€的距離是沿水平或垂直移動耗費(fèi)的的根號2（別怕），或者約1.414倍。為了簡化，我們用10和14近似。比例基本正確，同時(shí)我們避免了求根運(yùn)算和小數(shù)。這不是只因?yàn)槲覀兣侣闊┗蛘卟幌矚g數(shù)學(xué)。使用這樣的整數(shù)對計(jì)算機(jī)來說也更快捷。你不就就會發(fā)現(xiàn)，如果你不使用這些簡化方法，尋路會變得很慢。
既然我們在計(jì)算沿特定路徑通往某個(gè)方格的G值，求值的方法就是取它父節(jié)點(diǎn)的G值，然后依照它相對父節(jié)點(diǎn)是對角線方向或者直角方向(非對角線)，分別增加14和10。例子中這個(gè)方法的需求會變得更多，因?yàn)槲覀儚钠瘘c(diǎn)方格以外獲取了不止一個(gè)方格。
H值可以用不同的方法估算。我們這里使用的方法被稱為曼哈頓方法，它計(jì)算從當(dāng)前格到目的格之間水平和垂直的方格的數(shù)量總和，忽略對角線方向。然后把結(jié)果乘以10。這被成為曼哈頓方法是因?yàn)樗雌饋硐裼?jì)算城市中從一個(gè)地方到另外一個(gè)地方的街區(qū)數(shù)，在那里你不能沿對角線方向穿過街區(qū)。很重要的一點(diǎn)，我們忽略了一切障礙物。這是對剩余距離的一個(gè)估算，而非實(shí)際值，這也是這一方法被稱為啟發(fā)式的原因。想知道更多？你可以在這里找到方程和額外的注解。
F的值是G和H的和。第一步搜索的結(jié)果可以在下面的圖表中看到。F,G和H的評分被寫在每個(gè)方格里。正如在緊挨起始格右側(cè)的方格所表示的，F(xiàn)被打印在左上角，G在左下角，H則在右下角。
[圖3]
現(xiàn)在我們來看看這些方格。寫字母的方格里，G = 10。這是因?yàn)樗辉谒椒较蚱x起始格一個(gè)格距。緊鄰起始格的上方，下方和左邊的方格的G值都等于10。對角線方向的G值是14。
H值通過求解到紅色目標(biāo)格的曼哈頓距離得到，其中只在水平和垂直方向移動，并且忽略中間的墻。用這種方法，起點(diǎn)右側(cè)緊鄰的方格離紅色方格有3格距離，H值就是30。這塊方格上方的方格有4格距離(記住，只能在水平和垂直方向移動)，H值是40。你大致應(yīng)該知道如何計(jì)算其他方格的H值了～。
每個(gè)格子的F值，還是簡單的由G和H相加得到
繼續(xù)搜索
為了繼續(xù)搜索，我們簡單的從開啟列表中選擇F值最低的方格。然后，對選中的方格做如下處理：
4，把它從開啟列表中刪除，然后添加到關(guān)閉列表中。
5，檢查所有相鄰格子。跳過那些已經(jīng)在關(guān)閉列表中的或者不可通過的(有墻，水的地形，或者其他無法通過的地形)，把他們添加進(jìn)開啟列表，如果他們還不在里面的話。把選中的方格作為新的方格的父節(jié)點(diǎn)。
6，如果某個(gè)相鄰格已經(jīng)在開啟列表里了，檢查現(xiàn)在的這條路徑是否更好。換句話說，檢查如果我們用新的路徑到達(dá)它的話，G值是否會更低一些。如果不是，那就什么都不做。
另一方面，如果新的G值更低，那就把相鄰方格的父節(jié)點(diǎn)改為目前選中的方格（在上面的圖表中，把箭頭的方向改為指向這個(gè)方格）。最后，重新計(jì)算F和G的值。如果這看起來不夠清晰，你可以看下面的圖示。
好了，讓我們看看它是怎么運(yùn)作的。我們最初的9格方格中，在起點(diǎn)被切換到關(guān)閉列表中后，還剩8格留在開啟列表中。這里面，F(xiàn)值最低的那個(gè)是起始格右側(cè)緊鄰的格子，它的F值是40。因此我們選擇這一格作為下一個(gè)要處理的方格。在緊隨的圖中，它被用藍(lán)色突出顯示。
[圖4]
首先，我們把它從開啟列表中取出，放入關(guān)閉列表(這就是他被藍(lán)色突出顯示的原因)。然后我們檢查相鄰的格子。哦，右側(cè)的格子是墻，所以我們略過。左側(cè)的格子是起始格。它在關(guān)閉列表里，所以我們也跳過它。
其他4格已經(jīng)在開啟列表里了，于是我們檢查G值來判定，如果通過這一格到達(dá)那里，路徑是否更好。我們來看選中格子下面的方格。它的G值是14。如果我們從當(dāng)前格移動到那里，G值就會等于20(到達(dá)當(dāng)前格的G值是10，移動到上面的格子將使得G值增加10)。因?yàn)镚值20大于14，所以這不是更好的路徑。如果你看圖，就能理解。與其通過先水平移動一格，再垂直移動一格，還不如直接沿對角線方向移動一格來得簡單。
當(dāng)我們對已經(jīng)存在于開啟列表中的4個(gè)臨近格重復(fù)這一過程的時(shí)候，我們發(fā)現(xiàn)沒有一條路徑可以通過使用當(dāng)前格子得到改善，所以我們不做任何改變。既然我們已經(jīng)檢查過了所有鄰近格，那么就可以移動到下一格了。
于是我們檢索開啟列表，現(xiàn)在里面只有7格了，我們?nèi)匀贿x擇其中F值最低的。有趣的是，這次，有兩個(gè)格子的數(shù)值都是54。我們?nèi)绾芜x擇？這并不麻煩。從速度上考慮，選擇最后添加進(jìn)列表的格子會更快捷。這種導(dǎo)致了尋路過程中，在靠近目標(biāo)的時(shí)候，優(yōu)先使用新找到的格子的偏好。但這無關(guān)緊要。（對相同數(shù)值的不同對待，導(dǎo)致不同版本的A*算法找到等長的不同路徑。）
那我們就選擇起始格右下方的格子，如圖。
[圖5]
這次，當(dāng)我們檢查相鄰格的時(shí)候，發(fā)現(xiàn)右側(cè)是墻，于是略過。上面一格也被略過。我們也略過了墻下面的格子。為什么呢？因?yàn)槟悴荒茉诓淮┰綁堑那闆r下直接到達(dá)那個(gè)格子。你的確需要先往下走然后到達(dá)那一格，按部就班的走過那個(gè)拐角。(注解：穿越拐角的規(guī)則是可選的。它取決于你的節(jié)點(diǎn)是如何放置的。)
這樣一來，就剩下了其他5格。當(dāng)前格下面的另外兩個(gè)格子目前不在開啟列表中，于是我們添加他們，并且把當(dāng)前格指定為他們的父節(jié)點(diǎn)。其余3格，兩個(gè)已經(jīng)在關(guān)閉列表中（起始格，和當(dāng)前格上方的格子，在表格中藍(lán)色高亮顯示),于是我們略過它們。最后一格，在當(dāng)前格的左側(cè)，將被檢查通過這條路徑，G值是否更低。不必?fù)?dān)心，我們已經(jīng)準(zhǔn)備好檢查開啟列表中的下一格了。
我們重復(fù)這個(gè)過程，直到目標(biāo)格被添加進(jìn)關(guān)閉列表(注解)，就如在下面的圖中所看到的。
[圖6]
注意，起始格下方格子的父節(jié)點(diǎn)已經(jīng)和前面不同的。之前它的G值是28，并且指向右上方的格子。現(xiàn)在它的G值是20，指向它上方的格子。這在尋路過程中的某處發(fā)生，當(dāng)應(yīng)用新路徑時(shí)，G值經(jīng)過檢查變得低了－于是父節(jié)點(diǎn)被重新指定，G和F值被重新計(jì)算。盡管這一變化在這個(gè)例子中并不重要，在很多場合，這種變化會導(dǎo)致尋路結(jié)果的巨大變化。
那么，我們怎么確定這條路徑呢？很簡單，從紅色的目標(biāo)格開始，按箭頭的方向朝父節(jié)點(diǎn)移動。這最終會引導(dǎo)你回到起始格，這就是你的路徑！看起來應(yīng)該像圖中那樣。從起始格A移動到目標(biāo)格B只是簡單的從每個(gè)格子（節(jié)點(diǎn)）的中點(diǎn)沿路徑移動到下一個(gè)，直到你到達(dá)目標(biāo)點(diǎn)。就這么簡單。
[圖7]
A*方法總結(jié)
好，現(xiàn)在你已經(jīng)看完了整個(gè)說明，讓我們把每一步的操作寫在一起：
1，把起始格添加到開啟列表。
2，重復(fù)如下的工作：
a) 尋找開啟列表中F值最低的格子。我們稱它為當(dāng)前格。
b) 把它切換到關(guān)閉列表。
c) 對相鄰的8格中的每一個(gè)？
* 如果它不可通過或者已經(jīng)在關(guān)閉列表中，略過它。反之如下。
* 如果它不在開啟列表中，把它添加進(jìn)去。把當(dāng)前格作為這一格的父節(jié)點(diǎn)。記錄這一格的F,G,和H值。
* 如果它已經(jīng)在開啟列表中，用G值為參考檢查新的路徑是否更好。更低的G值意味著更好的路徑。如果是這樣，就把這一格的父節(jié)點(diǎn)改成當(dāng)前格，并且重新計(jì)算這一格的G和F值。如果你保持你的開啟列表按F值排序，改變之后你可能需要重新對開啟列表排序。
d) 停止，當(dāng)你
* 把目標(biāo)格添加進(jìn)了關(guān)閉列表(注解)，這時(shí)候路徑被找到，或者
* 沒有找到目標(biāo)格，開啟列表已經(jīng)空了。這時(shí)候，路徑不存在。
3.保存路徑。從目標(biāo)格開始，沿著每一格的父節(jié)點(diǎn)移動直到回到起始格。這就是你的路徑。
(注解:在這篇文章的較早版本中，建議的做法是當(dāng)目標(biāo)格（或節(jié)點(diǎn)）被加入到開啟列表，而不是關(guān)閉列表的時(shí)候停止尋路。這么做會更迅速，而且幾乎總是能找到最短的路徑，但不是絕對的。當(dāng)從倒數(shù)第二個(gè)節(jié)點(diǎn)到最后一個(gè)（目標(biāo)節(jié)點(diǎn)）之間的移動耗費(fèi)懸殊很大時(shí)－例如剛好有一條河穿越兩個(gè)節(jié)點(diǎn)中間，這時(shí)候舊的做法和新的做法就會有顯著不同。)
題外話
離題一下，見諒，值得一提的是，當(dāng)你在網(wǎng)上或者相關(guān)論壇看到關(guān)于A*的不同的探討，你有時(shí)會看到一些被當(dāng)作A*算法的代碼而實(shí)際上他們不是。要使用 A*，你必須包含上面討論的所有元素－－特定的開啟和關(guān)閉列表，用F,G和H作路徑評價(jià)。有很多其他的尋路算法，但他們并不是A*，A*被認(rèn)為是他們當(dāng)中最好的。Bryan Stout在這篇文章后面的參考文檔中論述了一部分，包括他們的一些優(yōu)點(diǎn)和缺點(diǎn)。有時(shí)候特定的場合其他算法會更好，但你必須很明確你在作什么。好了，夠多的了。回到文章。
實(shí)現(xiàn)的注解
現(xiàn)在你已經(jīng)明白了基本原理，寫你的程序的時(shí)候還得考慮一些額外的東西。下面這些材料中的一些引用了我用C++和Blitz Basic寫的程序，但對其他語言寫的代碼同樣有效。
1.其他單位(避免碰撞)：如果你恰好看了我的例子代碼，你會發(fā)現(xiàn)它完全忽略了其他單位。我的尋路者事實(shí)上可以相互穿越。取決于具體的游戲，這也許可以，也許不行。如果你打算考慮其他單位，希望他們能互相繞過，我建議你只考慮靜止或那些在計(jì)算路徑時(shí)臨近當(dāng)前單位的單位，把它們當(dāng)前的位置標(biāo)志為可通過的。對于臨近的運(yùn)動著的單位，你可以通過懲罰它們各自路徑上的節(jié)點(diǎn)，來鼓勵(lì)這些尋路者找到不同的路徑(更多的描述見#2).
如果你選擇了把其他正在移動并且遠(yuǎn)離當(dāng)前尋路單位的那些單位考慮在內(nèi)，你將需要實(shí)現(xiàn)一種方法及時(shí)預(yù)測在何時(shí)何地碰撞可能會發(fā)生，以便恰當(dāng)?shù)谋苊狻７駝t你極有可能得到一條怪異的路徑，單位突然轉(zhuǎn)彎試圖避免和一個(gè)已經(jīng)不存在的單位發(fā)生碰撞。
當(dāng)然，你也需要寫一些碰撞檢測的代碼，因?yàn)闊o論計(jì)算的時(shí)候路徑有多完美，它也會因時(shí)間而改變。當(dāng)碰撞發(fā)生時(shí)，一個(gè)單位必須尋找一條新路徑，或者，如果另一個(gè)單位正在移動并且不是正面碰撞，在繼續(xù)沿當(dāng)前路徑移動之前，等待那個(gè)單位離開。
這些提示大概可以讓你開始了。如果你想了解更多，這里有些你可能會覺得有用的鏈接：
* 自治角色的指導(dǎo)行為：Craig Reynold在指導(dǎo)能力上的工作和尋路有些不同，但是它可以和尋路整合從而形成更完整的移動和碰撞檢測系統(tǒng)。
* 電腦游戲中的長短距指導(dǎo)：指導(dǎo)和尋路方面著作的一個(gè)有趣的考察。這是一個(gè)pdf文件。
* 協(xié)同單位移動：一個(gè)兩部分系列文章的第一篇，內(nèi)容是關(guān)于編隊(duì)和基于分組的移動，作者是帝國時(shí)代(Age of Empires)的設(shè)計(jì)者Dave Pottinger.
* 實(shí)現(xiàn)協(xié)同移動：Dave Pottinger文章系列的第二篇。
2. 不同的地形損耗：在這個(gè)教程和我附帶的程序中，地形只能是二者之－可通過的和不可通過的。但是你可能會需要一些可通過的地形，但是移動耗費(fèi)更高－沼澤，小山，地牢的樓梯，等等。這些都是可通過但是比平坦的開闊地移動耗費(fèi)更高的地形。類似的，道路應(yīng)該比自然地形移動耗費(fèi)更低。
這個(gè)問題很容易解決，只要在計(jì)算任何地形的G值的時(shí)候增加地形損耗就可以了。簡單的給它增加一些額外的損耗就可以了。由于A*算法已經(jīng)按照尋找最低耗費(fèi)的路徑來設(shè)計(jì)，所以很容易處理這種情況。在我提供的這個(gè)簡單的例子里，地形只有可通過和不可通過兩種，A*會找到最短，最直接的路徑。但是在地形耗費(fèi)不同的場合，耗費(fèi)最低的路徑也許會包含很長的移動距離－就像沿著路繞過沼澤而不是直接穿過它。
一種需額外考慮的情況是被專家稱之為“influence mapping”的東西（暫譯為影響映射圖）。就像上面描述的不同地形耗費(fèi)一樣，你可以創(chuàng)建一格額外的分?jǐn)?shù)系統(tǒng)，并把它應(yīng)用到尋路的AI中。假設(shè)你有一張有大批尋路者的地圖，他們都要通過某個(gè)山區(qū)。每次電腦生成一條通過那個(gè)關(guān)口的路徑，它就會變得更擁擠。如果你愿意，你可以創(chuàng)建一個(gè)影響映射圖對有大量屠殺事件的格子施以不利影響。這會讓計(jì)算機(jī)更傾向安全些的路徑，并且?guī)椭苊饪偸莾H僅因?yàn)槁窂蕉?但可能更危險(xiǎn))而持續(xù)把隊(duì)伍和尋路者送到某一特定路徑。
另一個(gè)可能得應(yīng)用是懲罰周圍移動單位路徑上得節(jié)點(diǎn)。A*的一個(gè)底限是，當(dāng)一群單位同時(shí)試圖尋路到接近的地點(diǎn)，這通常會導(dǎo)致路徑交疊。以為一個(gè)或者多個(gè)單位都試圖走相同或者近似的路徑到達(dá)目的地。對其他單位已經(jīng)“認(rèn)領(lǐng)”了的節(jié)點(diǎn)增加一些懲罰會有助于你在一定程度上分離路徑，降低碰撞的可能性。然而，如果有必要，不要把那些節(jié)點(diǎn)看成不可通過的，因?yàn)槟闳匀幌Ｍ鄠€(gè)單位能夠一字縱隊(duì)通過擁擠的出口。同時(shí)，你只能懲罰那些臨近單位的路徑，而不是所有路徑，否則你就會得到奇怪的躲避行為例如單位躲避路徑上其他已經(jīng)不在那里的單位。 還有，你應(yīng)該只懲罰路徑當(dāng)前節(jié)點(diǎn)和隨后的節(jié)點(diǎn)，而不應(yīng)處理已經(jīng)走過并甩在身后的節(jié)點(diǎn)。
3. 處理未知區(qū)域：你是否玩過這樣的PC游戲，電腦總是知道哪條路是正確的，即使它還沒有偵察過地圖？對于游戲，尋路太好會顯得不真實(shí)。幸運(yùn)的是，這是一格可以輕易解決的問題。
答案就是為每個(gè)不同的玩家和電腦（每個(gè)玩家，而不是每個(gè)單位－－那樣的話會耗費(fèi)大量的內(nèi)存）創(chuàng)建一個(gè)獨(dú)立的“knownWalkability”數(shù)組，每個(gè)數(shù)組包含玩家已經(jīng)探索過的區(qū)域，以及被當(dāng)作可通過區(qū)域的其他區(qū)域，直到被證實(shí)。用這種方法，單位會在路的死端徘徊并且導(dǎo)致錯(cuò)誤的選擇直到他們在周圍找到路。一旦地圖被探索了，尋路就像往常那樣進(jìn)行。
4. 平滑路徑：盡管A*提供了最短，最低代價(jià)的路徑，它無法自動提供看起來平滑的路徑。看一下我們的例子最終形成的路徑（在圖7）。最初的一步是起始格的右下方，如果這一步是直接往下的話，路徑不是會更平滑一些嗎？
有幾種方法來解決這個(gè)問題。當(dāng)計(jì)算路徑的時(shí)候可以對改變方向的格子施加不利影響，對G值增加額外的數(shù)值。也可以換種方法，你可以在路徑計(jì)算完之后沿著它跑一遍，找那些用相鄰格替換會讓路徑看起來更平滑的地方。想知道完整的結(jié)果，查看Toward More Realistic Pathfinding，一篇(免費(fèi)，但是需要注冊)Marco Pinter發(fā)表在Gamasutra.com的文章
5. 非方形搜索區(qū)域：在我們的例子里，我們使用簡單的2D方形圖。你可以不使用這種方式。你可以使用不規(guī)則形狀的區(qū)域。想想冒險(xiǎn)棋的游戲，和游戲中那些國家。你可以設(shè)計(jì)一個(gè)像那樣的尋路關(guān)卡。為此，你可能需要建立一個(gè)國家相鄰關(guān)系的表格，和從一個(gè)國家移動到另一個(gè)的G值。你也需要估算H值的方法。其他的事情就和例子中完全一樣了。當(dāng)你需要向開啟列表中添加新元素的時(shí)候，不需使用相鄰的格子，取而代之的是從表格中尋找相鄰的國家。
類似的，你可以為一張確定的地形圖創(chuàng)建路徑點(diǎn)系統(tǒng)，路徑點(diǎn)一般是路上，或者地牢通道的轉(zhuǎn)折點(diǎn)。作為游戲設(shè)計(jì)者，你可以預(yù)設(shè)這些路徑點(diǎn)。兩個(gè)路徑點(diǎn)被認(rèn)為是相鄰的如果他們之間的直線上沒有障礙的話。在冒險(xiǎn)棋的例子里，你可以保存這些相鄰信息在某個(gè)表格里，當(dāng)需要在開啟列表中添加元素的時(shí)候使用它。然后你就可以記錄關(guān)聯(lián)的G值（可能使用兩點(diǎn)間的直線距離），H值（可以使用到目標(biāo)點(diǎn)的直線距離），其他都按原先的做就可以了。
Amit Patel 寫了其他方法的摘要。另一個(gè)在非方形區(qū)域搜索RPG地圖的例子，查看我的文章Two-Tiered A* Pathfinding。(譯者注：譯文： A*分層尋路)
6. 一些速度方面的提示：當(dāng)你開發(fā)你自己的A*程序，或者改寫我的，你會發(fā)現(xiàn)尋路占據(jù)了大量的CPU時(shí)間，尤其是在大地圖上有大量對象在尋路的時(shí)候。如果你閱讀過網(wǎng)上的其他材料，你會明白，即使是開發(fā)了星際爭霸或帝國時(shí)代的專家，這也無可奈何。如果你覺得尋路太過緩慢，這里有一些建議也許有效：
* 使用更小的地圖或者更少的尋路者。
* 不要同時(shí)給多個(gè)對象尋路。取而代之的是把他們加入一個(gè)隊(duì)列，把尋路過程分散在幾個(gè)游戲周期中。如果你的游戲以40周期每秒的速度運(yùn)行，沒人能察覺。但是當(dāng)大量尋路者計(jì)算自己路徑的時(shí)候,他們會發(fā)覺游戲速度突然變慢。
* 盡量使用更大的地圖網(wǎng)格。這降低了尋路中搜索的總網(wǎng)格數(shù)。如果你有志氣，你可以設(shè)計(jì)兩個(gè)或者更多尋路系統(tǒng)以便使用在不同場合，取決于路徑的長度。這也正是專業(yè)人士的做法，用大的區(qū)域計(jì)算長的路徑，然后在接近目標(biāo)的時(shí)候切換到使用小格子/區(qū)域的精細(xì)尋路。如果你對這個(gè)觀點(diǎn)感興趣，查閱我的文章Two-Tiered A* Pathfinding。(譯者注：譯文 :A*分層尋路)
* 使用路徑點(diǎn)系統(tǒng)計(jì)算長路徑，或者預(yù)先計(jì)算好路徑并加入到游戲中。
* 預(yù)處理你的地圖，表明地圖中哪些區(qū)域是不可到達(dá)的。我把這些區(qū)域稱作“孤島”。事實(shí)上，他們可以是島嶼或其他被墻壁包圍等無法到達(dá)的任意區(qū)域。A*的下限是，當(dāng)你告訴它要尋找通往那些區(qū)域的路徑時(shí)，它會搜索整個(gè)地圖，直到所有可到達(dá)的方格/節(jié)點(diǎn)都被通過開啟列表和關(guān)閉列表的計(jì)算。這會浪費(fèi)大量的CPU時(shí)間。可以通過預(yù)先確定這些區(qū)域（比如通過flood-fill或類似的方法)來避免這種情況的發(fā)生,用某些種類的數(shù)組記錄這些信息，在開始尋路前檢查它。
* 在一個(gè)擁擠的類似迷宮的場合，把不能連通的節(jié)點(diǎn)看作死端。這些區(qū)域可以在地圖編輯器中預(yù)先手動指定，或者如果你有雄心壯志，開發(fā)一個(gè)自動識別這些區(qū)域的算法。給定死端的所有節(jié)點(diǎn)可以被賦予一個(gè)唯一的標(biāo)志數(shù)字。然后你就可以在尋路過程中安全的忽略所有死端，只有當(dāng)起點(diǎn)或者終點(diǎn)恰好在死端的某個(gè)節(jié)點(diǎn)的時(shí)候才需要考慮它們。
7. 維護(hù)開啟列表：這是A*尋路算法最重要的組成部分。每次你訪問開啟列表，你都需要尋找F值最低的方格。有幾種不同的方法實(shí)現(xiàn)這一點(diǎn)。你可以把路徑元素隨意保存，當(dāng)需要尋找F值最低的元素的時(shí)候，遍歷開啟列表。這很簡單，但是太慢了，尤其是對長路徑來說。這可以通過維護(hù)一格排好序的列表來改善，每次尋找F值最低的方格只需要選取列表的首元素。當(dāng)我自己實(shí)現(xiàn)的時(shí)候，這種方法是我的首選。
在小地圖。這種方法工作的很好，但它并不是最快的解決方案。更苛求速度的A*程序員使用叫做二叉堆的方法，這也是我在代碼中使用的方法。憑我的經(jīng)驗(yàn)，這種方法在大多數(shù)場合會快2～3倍，并且在長路經(jīng)上速度呈幾何級數(shù)提升(10倍以上速度)。如果你想了解更多關(guān)于二叉堆的內(nèi)容，查閱我的文章，Using Binary Heaps in A* Pathfinding。(譯者注：譯文：在A*尋路中使用二叉堆)
另一個(gè)可能的瓶頸是你在多次尋路之間清除和保存你的數(shù)據(jù)結(jié)構(gòu)的方法。我個(gè)人更傾向把所有東西都存儲在數(shù)組里面。雖然節(jié)點(diǎn)可以以面向?qū)ο蟮娘L(fēng)格被動態(tài)的產(chǎn)生，記錄和保存，我發(fā)現(xiàn)創(chuàng)建和刪除對象所增加的大量時(shí)間，以及多余的管理層次減慢的整個(gè)過程的速度。但是，如果你使用數(shù)組，你需要在調(diào)用之間清理數(shù)據(jù)。這中情形你想做的最后一件事就是在尋路調(diào)用之后花點(diǎn)時(shí)間把一切歸零，尤其是你的地圖很大的時(shí)候。
我通過使用一個(gè)叫做whichList(x,y)的二維數(shù)組避免這種開銷，數(shù)組的每個(gè)元素表明了節(jié)點(diǎn)在開啟列表還是在關(guān)閉列表中。嘗試尋路之后，我沒有清零這個(gè)數(shù)組。取而代之的是，我在新的尋路中重置onClosedList和onOpenList的數(shù)值，每次尋路兩個(gè)都+5或者類似其他數(shù)值。這種方法，算法可以安全的跳過前面尋路留下的臟數(shù)據(jù)。我還在數(shù)組中儲存了諸如F,G和H的值。這樣一來，我只需簡單的重寫任何已經(jīng)存在的值而無需被清除數(shù)組的操作干擾。將數(shù)據(jù)存儲在多維數(shù)組中需要更多內(nèi)存，所以這里需要權(quán)衡利弊。最后，你應(yīng)該使用你最得心應(yīng)手的方法。
8. Dijkstra的算法：盡管A*被認(rèn)為是通常最好的尋路算法(看前面的“題外話”),還是有一種另外的算法有它的可取之處-Dijkstra算法。 Dijkstra算法和A*本質(zhì)是相同的，只有一點(diǎn)不同，就是Dijkstra算法沒有啟發(fā)式(H值總是0)。由于沒有啟發(fā)式，它在各個(gè)方向上平均搜索。正如你所預(yù)料，由于Dijkstra算法在找到目標(biāo)前通常會探索更大的區(qū)域，所以一般會比A*更慢一些。
那么為什么要使用這種算法呢？因?yàn)橛袝r(shí)候我們并不知道目標(biāo)的位置。比如說你有一個(gè)資源采集單位，需要獲取某種類型的資源若干。它可能知道幾個(gè)資源區(qū)域，但是它想去最近的那個(gè)。這種情況，Dijkstra算法就比A*更適合，因?yàn)槲覀儾恢滥膫€(gè)更近。用A*，我們唯一的選擇是依次對每個(gè)目標(biāo)許路并計(jì)算距離，然后選擇最近的路徑。我們尋找的目標(biāo)可能會有不計(jì)其數(shù)的位置，我們只想找其中最近的，而我們并不知道它在哪里，或者不知道哪個(gè)是最近的。
進(jìn)一步的閱讀
好，現(xiàn)在你對一些進(jìn)一步的觀點(diǎn)有了初步認(rèn)識。這時(shí)，我建議你研究我的源代碼。包里面包含兩個(gè)版本，一個(gè)是用C++寫的，另一個(gè)用Blitz Basic。順便說一句，兩個(gè)版本都注釋詳盡，容易閱讀，這里是鏈接。
* 例子代碼： A* Pathfinder (2D) Version 1.9
如果你既不用C++也不用Blitz Basic,在C++版本里有兩個(gè)小的可執(zhí)行文件。Blitz Basic可以在從Blitz Basic網(wǎng)站免費(fèi)下載的Blitz Basic 3D(不是Blitz Plus)演示版上運(yùn)行。Ben O'Neill提供一個(gè)聯(lián)機(jī)演示可以在這里找到。
你也該看看以下的網(wǎng)頁。讀了這篇教程后，他們應(yīng)該變得容易理解多了。
* Amit的 A* 頁面:這是由Amit Patel制作，被廣泛引用的頁面，如果你沒有事先讀這篇文章，可能會有點(diǎn)難以理解。值得一看。尤其要看Amit關(guān)于這個(gè)問題的自己的看法。
* Smart Moves:智能尋路：Bryan Stout發(fā)表在Gamasutra.com的這篇文章需要注冊才能閱讀。注冊是免費(fèi)的而且比起這篇文章和網(wǎng)站的其他資源，是非常物有所值的。Bryan用Delphi寫的程序幫助我學(xué)習(xí)A*，也是我的A*代碼的靈感之源。它還描述了A*的幾種變化。
* 地形分析：這是一格高階，但是有趣的話題，Dave Pottinge撰寫，Ensemble Studios的專家。這家伙參與了帝國時(shí)代和君王時(shí)代的開發(fā)。別指望看懂這里所有的東西，但是這是篇有趣的文章也許會讓你產(chǎn)生自己的想法。它包含一些對 mip-mapping，influence mapping以及其他一些高級AI/尋路觀點(diǎn)。對"flood filling"的討論使我有了我自己的“死端”和“孤島”的代碼的靈感，這些包含在我Blitz版本的代碼中。
其他一些值得一看的網(wǎng)站：
* aiGuru: Pathfinding
* Game AI Resource: Pathfinding
* GameDev.net: Pathfinding
我同樣高度推薦下面這幾本書, 里面有很多關(guān)于尋路和其他AI話題的文章。 它們也附帶了實(shí)例代碼的CD。這些書我都買了。另外，如果你通過下面的鏈接購買了它們，我會從Amazon得到幾個(gè)美分。:)
好了，這就是全部。如果你剛好寫一個(gè)運(yùn)用這些觀點(diǎn)的程序，我想拜讀一下。你可以這樣聯(lián)系我：
現(xiàn)在，好運(yùn)！
譯者參考文獻(xiàn)：
在A*尋路中使用二叉堆
A*分層尋
游戲算法整理 算法二：碰撞
1. 碰撞檢測和響應(yīng)
碰撞在游戲中運(yùn)用的是非常廣泛的，運(yùn)用理論實(shí)現(xiàn)的碰撞，再加上一些小技巧，可以讓碰撞檢測做得非常精確，效率也非常高。從而增加游戲的功能和可玩性。
2D碰撞檢測
2D的碰撞檢測已經(jīng)非常穩(wěn)定，可以在許多著作和論文中查詢到。3D的碰撞還沒有找到最好的方法，現(xiàn)在使用的大多數(shù)方法都是建立在2D基礎(chǔ)上的。
碰撞檢測
碰撞的檢測不僅僅是運(yùn)用在游戲中，事實(shí)上，一開始的時(shí)候是運(yùn)用在模擬和機(jī)器人技術(shù)上的。這些工業(yè)上的碰撞檢測要求非常高，而碰撞以后的響應(yīng)也是需要符合現(xiàn)實(shí)生活的，是需要符合人類常規(guī)認(rèn)識的。游戲中的碰撞有些許的不一樣，況且，更重要的，我們制作的東西充其量是商業(yè)級別，還不需要接觸到紛繁復(fù)雜的數(shù)學(xué)公式。
圖1
最理想的碰撞，我想莫過于上圖，完全按照多邊形的外形和運(yùn)行路徑規(guī)劃一個(gè)范圍，在這個(gè)范圍當(dāng)中尋找會產(chǎn)生阻擋的物體，不管是什么物體，產(chǎn)生阻擋以后，我們運(yùn)動的物體都必須在那個(gè)位置產(chǎn)生一個(gè)碰撞的事件。最美好的想法總是在實(shí)現(xiàn)上有一些困難，事實(shí)上我們可以這么做，但是效率卻是非常非常低下的，游戲中，甚至于工業(yè)中無法忍受這種速度，所以我們改用其它的方法來實(shí)現(xiàn)。
圖2
最簡單的方法如上圖，我們尋找物體的中心點(diǎn)，然后用這個(gè)中心點(diǎn)來畫一個(gè)圓，如果是一個(gè)3D的物體，那么我們要畫的就是一個(gè)球體。在檢測物體碰撞的時(shí)候，我們只要檢測兩個(gè)物體的半徑相加是否大于這兩個(gè)物體圓心的實(shí)際距離。
這個(gè)算法是最簡單的一種，現(xiàn)在還在用，但是不是用來做精確的碰撞檢測，而是用來提高效率的模糊碰撞檢測查詢，到了這個(gè)范圍以后，再進(jìn)行更加精密的碰撞檢測。一種比較精密的碰撞檢測查詢就是繼續(xù)這種畫圓的思路，然后把物體細(xì)分，對于物體的每個(gè)部件繼續(xù)畫圓，然后再繼續(xù)進(jìn)行碰撞檢測，直到系統(tǒng)規(guī)定的，可以容忍的誤差范圍以后才觸發(fā)碰撞事件，進(jìn)行碰撞的一些操作。
有沒有更加簡單的方法呢？2D游戲中有許多圖片都是方方正正的，所以我們不必把碰撞的范圍畫成一個(gè)圓的，而是畫成一個(gè)方的。這個(gè)正方形，或者說是一個(gè)四邊形和坐標(biāo)軸是對齊的，所以運(yùn)用數(shù)學(xué)上的一些方法，比如距離計(jì)算等還是比較方便的。這個(gè)檢測方法就叫AABBs（Axis-aligned Bounding Boxes）碰撞檢測，游戲中已經(jīng)運(yùn)用的非常廣泛了，因?yàn)槠渌俣瓤欤矢撸?jì)算起來非常方便，精確度也是可以忍受的。
做到這一步，許多游戲的需求都已經(jīng)滿足了。但是，總是有人希望近一步優(yōu)化，而且方法也是非常陳舊的：繼續(xù)對物體的各個(gè)部分進(jìn)行細(xì)分，對每個(gè)部件做AABB 的矩形，那這個(gè)優(yōu)化以后的系統(tǒng)就叫做OBB系統(tǒng)。雖然說這個(gè)優(yōu)化以后的系統(tǒng)也不錯(cuò)，但是，許多它可以運(yùn)用到的地方，別人卻不愛使用它，這是后面會繼續(xù)介紹的地方。
John Carmack不知道看的哪本書，他早在DOOM中已經(jīng)使用了BSP系統(tǒng)（二分空間分割），再加上一些小技巧，他的碰撞做得就非常好了，再加上他發(fā)明的 castray算法，DOOM已經(jīng)不存在碰撞的問題，解決了這樣的關(guān)鍵技術(shù)，我想他不再需要在什么地方分心了，只要繼續(xù)研究渲染引擎就可以了。（Windows游戲編程大師技巧P392～P393介紹）（凸多邊形，多邊形退化，左手定律）SAT系統(tǒng)非常復(fù)雜，是SHT（separating hyperplane theorem，分離超平面理論）的一種特殊情況。這個(gè)理論闡述的就是兩個(gè)不相關(guān)的曲面，是否能夠被一個(gè)超平面所分割開來，所謂分割開來的意思就是一個(gè)曲面貼在平面的一邊，而另一個(gè)曲面貼在平面的另一邊。我理解的就是有點(diǎn)像相切的意思。SAT是SHT的特殊情況，所指的就是兩個(gè)曲面都是一些多邊形，而那個(gè)超平面也是一個(gè)多邊形，這個(gè)超平面的多邊形可以在場景中的多邊形列表中找到，而超平面可能就是某個(gè)多邊形的表面，很巧的就是，這個(gè)表面的法線和兩個(gè)曲面的切面是相對應(yīng)的。接下來的證明，我想是非常復(fù)雜的事情，希望今后能夠找到源代碼直接運(yùn)用上去。而我們現(xiàn)在講究的快速開發(fā)，我想AABB就足以滿足了。
3D碰撞檢測
3D的檢測就沒有什么很標(biāo)準(zhǔn)的理論了，都建立在2D的基礎(chǔ)上，我們可以沿用AABB或者OBB，或者先用球體做粗略的檢測，然后用AABB和OBB作精細(xì)的檢測。BSP技術(shù)不流行，但是效率不錯(cuò)。微軟提供了D3DIntersect函數(shù)讓大家使用，方便了許多，但是和通常一樣，當(dāng)物體多了以后就不好用了，明顯的就是速度慢許多。
碰撞反應(yīng)
碰撞以后我們需要做一些反應(yīng)，比如說產(chǎn)生反沖力讓我們反彈出去，或者停下來，或者讓阻擋我們的物體飛出去，或者穿墻，碰撞最討厭的就是穿越，本來就不合邏輯，查閱了那么多資料以后，從來沒有看到過需要穿越的碰撞，有摩擦力是另外一回事。首先看看彈性碰撞。彈性碰撞就是我們初中物理中說的動量守恒。物體在碰撞前后的動量守恒，沒有任何能量損失。這樣的碰撞運(yùn)用于打磚塊的游戲中。引入質(zhì)量的話，有的物體會是有一定的質(zhì)量，這些物體通常來說是需要在碰撞以后進(jìn)行另外一個(gè)方向的運(yùn)動的，另外一些物體是設(shè)定為質(zhì)量無限大的，這些物體通常是碰撞墻壁。
當(dāng)物體碰到質(zhì)量非常大的物體，默認(rèn)為碰到了一個(gè)彈性物體，其速度會改變，但是能量不會受到損失。一般在代碼上的做法就是在速度向量上加上一個(gè)負(fù)號。
絕對的彈性碰撞是很少有的，大多數(shù)情況下我們運(yùn)用的還是非彈性碰撞。我們現(xiàn)在玩的大多數(shù)游戲都用的是很接近現(xiàn)實(shí)的非彈性碰撞，例如Pain-Killer 中的那把吸力槍，它彈出去的子彈吸附到NPC身上時(shí)的碰撞響應(yīng)就是非彈性碰撞；那把殘忍的分尸刀把墻打碎的初始算法就是一個(gè)非彈性碰撞，其后使用的剛體力學(xué)就是先建立在這個(gè)算法上的。那么，是的，如果需要非彈性碰撞，我們需要介入摩擦力這個(gè)因素，而我們也無法簡單使用動量守恒這個(gè)公式。
我們可以采取比較簡單的方法，假設(shè)摩擦系數(shù)μ非常大，那么只要物體接觸，并且擁有一個(gè)加速度，就可以產(chǎn)生一個(gè)無窮大的摩擦力，造成物體停止的狀態(tài)。
基于別人的引擎寫出一個(gè)讓自己滿意的碰撞是不容易的，那么如果自己建立一個(gè)碰撞系統(tǒng)的話，以下內(nèi)容是無法缺少的：
– 一個(gè)能夠容忍的碰撞系統(tǒng)
– 一個(gè)從概念上可以接受的物理系統(tǒng)
– 質(zhì)量
– 速度
– 摩擦系數(shù)
– 地心引力
http://www.gamasutra.com/features/20000330/bobic_01.htm
http://www.gamasutra.com/features/20000330/bobic_02.htm
http://www.gamasutra.com/features/20000330/bobic_03.htm
這三篇是高級碰撞檢測。
游戲算法整理 算法三：尋路算法新思維
目前常用尋路算法是A*方式，原理是通過不斷搜索逼近目的地的路點(diǎn)來獲得。
如果通過圖像模擬搜索點(diǎn)，可以發(fā)現(xiàn)：非啟發(fā)式的尋路算法實(shí)際上是一種窮舉法，通過固定順序依次搜索人物周圍的路點(diǎn)，直到找到目的地，搜索點(diǎn)在圖像上的表現(xiàn)為一個(gè)不斷擴(kuò)大的矩形。如下：
 
很快人們發(fā)現(xiàn)如此窮舉導(dǎo)致搜索速度過慢，而且不是很符合邏輯，試想：如果要從（0，0）點(diǎn)到達(dá)（100，0）點(diǎn)，如果每次向東搜索時(shí)能夠走通，那么干嗎還要搜索其他方向呢？所以，出現(xiàn)了啟發(fā)式的A*尋路算法，一般通過 已經(jīng)走過的路程 + 到達(dá)目的地的直線距離 代價(jià)值作為搜索時(shí)的啟發(fā)條件，每個(gè)點(diǎn)建立一個(gè)代價(jià)值，每次搜索時(shí)就從代價(jià)低的最先搜索，如下：
 
綜上所述，以上的搜索是一種矩陣式的不斷逼近終點(diǎn)的搜索做法。優(yōu)點(diǎn)是比較直觀，缺點(diǎn)在于距離越遠(yuǎn)、搜索時(shí)間越長。
現(xiàn)在，我提出一種新的AI尋路方式——矢量尋路算法。
通過觀察，我們可以發(fā)現(xiàn)，所有的最優(yōu)路線，如果是一條折線，那么、其每一個(gè)拐彎點(diǎn)一定發(fā)生在障礙物的突出邊角，而不會在還沒有碰到障礙物就拐彎的情況：如下圖所示：
我們可以發(fā)現(xiàn)，所有的紅色拐彎點(diǎn)都是在障礙物（可以認(rèn)為是一個(gè)凸多邊形）的頂點(diǎn)處，所以，我們搜索路徑時(shí)，其實(shí)只需要搜索這些凸多邊形頂點(diǎn)不就可以了嗎？如果將各個(gè)頂點(diǎn)連接成一條通路就找到了最優(yōu)路線，而不需要每個(gè)點(diǎn)都檢索一次，這樣就大大減少了搜索次數(shù)，不會因?yàn)榫嚯x的增大而增大搜索時(shí)間。
這種思路我尚未將其演變?yōu)樗惴ǎ们姨岢鲆粋€(gè)偽程序給各位參考：
1．建立各個(gè)凸多邊形頂點(diǎn)的通路表TAB，表示頂點(diǎn)A到頂點(diǎn)B是否可達(dá)，將可達(dá)的頂點(diǎn)分組保存下來。如: ( (0,0) (100,0) ),這一步驟在程序剛開始時(shí)完成，不要放在搜索過程中空耗時(shí)間。
2．開始搜索A點(diǎn)到B點(diǎn)的路線
3．檢測A點(diǎn)可以直達(dá)凸多邊形頂點(diǎn)中的哪一些，挑選出最合適的頂點(diǎn)X1。
4．檢測與X1相連（能夠接通）的有哪些頂點(diǎn)，挑出最合適的頂點(diǎn)X2。
5．X2是否是終點(diǎn)B？是的話結(jié)束，否則轉(zhuǎn)步驟4（X2代入X1）
如此下來，搜索只發(fā)生在凸多邊形的頂點(diǎn)，節(jié)省了大量的搜索時(shí)間，而且找到的路線無需再修剪鋸齒，保證了路線的最優(yōu)性。
這種方法搜索理論上可以減少大量搜索點(diǎn)、缺點(diǎn)是需要實(shí)現(xiàn)用一段程序得出TAB表，從本質(zhì)上來說是一種空間換時(shí)間的方法，而且搜索時(shí)A*能夠用的啟發(fā)條件，在矢量搜索時(shí)依然可以使用。
游戲算法整理 算法四：戰(zhàn)略游戲中的戰(zhàn)爭模型算法的初步探討
《三國志》系列游戲相信大家都有所了解，而其中的（宏觀）戰(zhàn)斗時(shí)關(guān)于雙方兵力，士氣，兵種克制，攻擊力，增援以及隨戰(zhàn)爭進(jìn)行兵力減少等數(shù)值的算法是十分值得研究的。或許是由于簡單的緣故，我在網(wǎng)上幾乎沒有找到相關(guān)算法的文章。下面給出這個(gè)戰(zhàn)爭的數(shù)學(xué)模型算法可以保證游戲中戰(zhàn)爭的游戲性與真實(shí)性兼顧，希望可以給有需要這方面開發(fā)的人一些啟迪。
假設(shè)用x(t)和y(t)表示甲乙交戰(zhàn)雙方在t時(shí)刻的兵力，如果是開始時(shí)可視為雙方士兵人數(shù)。
假設(shè)每一方的戰(zhàn)斗減員率取決于雙方兵力和戰(zhàn)斗力，用f(x,y)和g(x,y)表示，每一方的增援率是給定函數(shù)用u(t)和v(t)表示。
如果雙方用正規(guī)部隊(duì)作戰(zhàn)（可假設(shè)是相同兵種），先分析甲方的戰(zhàn)斗減員率f(x,y)。可知甲方士兵公開活動，處于乙方?jīng)]一個(gè)士兵的監(jiān)視和殺傷范圍之內(nèi)，一但甲方的某個(gè)士兵被殺傷，乙方的火力立即集中在其余士兵身上，所以甲方的戰(zhàn)斗減員率只與乙方的兵力有關(guān)可射為f與y成正比，即f=ay,a表示乙方平均每個(gè)士兵對甲方士兵的殺傷率（單位時(shí)間的殺傷數(shù)），成為乙方的戰(zhàn)斗有效系數(shù)。類似g= -bx
這個(gè)戰(zhàn)爭模型模型方程1為
x’(t)= -a*y(t)+u(t) x’(t)是x(t)對于t 的導(dǎo)數(shù)
y’(t)= -b*x(t)+v(t) y’(t)是y(t)對于t的導(dǎo)數(shù)
利用給定的初始兵力，戰(zhàn)爭持續(xù)時(shí)間，和增援兵力可以求出雙方兵力在戰(zhàn)爭中的變化函數(shù)。
（本文中解法略）
如果考慮由于士氣和疾病等引起的非戰(zhàn)斗減員率（一般與本放兵力成正比，設(shè)甲乙雙方分別為h,w）
可得到改進(jìn)戰(zhàn)爭模型方程2：
x’(t)= -a*y(t)-h*x(t)+u(t)
y’(t)= -b*x(t)-w*y(t)+v(t)
利用初始條件同樣可以得到雙方兵力在戰(zhàn)爭中的變化函數(shù)和戰(zhàn)爭結(jié)果。
此外還有不同兵種作戰(zhàn)（兵種克制）的數(shù)學(xué)模型：
模型1中的戰(zhàn)斗有效系數(shù)a可以進(jìn)一步分解為a=ry*py*(sry/sx),其中ry是乙方的攻擊率（每個(gè)士兵單位的攻擊次數(shù)），py是每次攻擊的命中率。（sry/sx）是乙方攻擊的有效面積sry與甲方活動范圍sx之比。類似甲方的戰(zhàn)斗有效系數(shù)b=rx*px*(srx/sy)，rx和px是甲方的攻擊率和命中率，（srx/sy）是甲方攻擊的有效面積與乙方活動范圍sy之比。由于增加了兵種克制的攻擊范圍，所以戰(zhàn)斗減員率不光與對方兵力有關(guān)，而且隨著己放兵力增加而增加。因?yàn)樵谝欢▍^(qū)域內(nèi)，士兵越多被殺傷的就越多。
方程
x’(t)= -ry*py*(sry/sx)*x(t)*y(t)-h*x(t)+u(t)
y’(t)= -rx*px*(srx/sy)*x(t)*y(t)-w*y(t)+u(t)
游戲算法整理 算法五：飛行射擊游戲中的碰撞檢測
在游戲中物體的碰撞是經(jīng)常發(fā)生的，怎樣檢測物體的碰撞是一個(gè)很關(guān)鍵的技術(shù)問題。在RPG游戲中，一般都將場景分為許多矩形的單元，碰撞的問題被大大的簡化了，只要判斷精靈所在的單元是不是有其它的東西就可以了。而在飛行射擊游戲（包括象荒野大鏢客這樣的射擊游戲）中，碰撞卻是最關(guān)鍵的技術(shù)，如果不能很好的解決，會影響玩游戲者的興趣。因?yàn)轱w行射擊游戲說白了就是碰撞的游戲——躲避敵人的子彈或飛機(jī)，同時(shí)用自己的子彈去碰撞敵人。
碰撞，這很簡單嘛，只要兩個(gè)物體的中心點(diǎn)距離小于它們的半徑之和就可以了。確實(shí)，而且我也看到很多人是這樣做的，但是，這只適合圓形的物體——圓形的半徑處處相等。如果我們要碰撞的物體是兩艘威力巨大的太空飛船，它是三角形或矩形或其他的什么形狀，就會出現(xiàn)讓人尷尬的情景：兩艘飛船眼看就要擦肩而過，卻出人意料的發(fā)生了爆炸；或者敵人的子彈穿透了你的飛船的右弦，你卻安然無恙，這不是我們希望發(fā)生的。于是，我們需要一種精確的檢測方法。
那么，怎樣才能達(dá)到我們的要求呢？其實(shí)我們的前輩們已經(jīng)總結(jié)了許多這方面的經(jīng)驗(yàn)，如上所述的半徑檢測法，三維中的標(biāo)準(zhǔn)平臺方程法，邊界框法等等。大多數(shù)游戲程序員都喜歡用邊界框法，這也是我采用的方法。邊界框是在編程中加進(jìn)去的不可見的邊界。邊界框法，顧名思義，就是用邊界框來檢測物體是否發(fā)生了碰撞，如果兩個(gè)物體的邊界框相互干擾，則發(fā)生了碰撞。用什么樣的邊界框要視不同情況而定，用最近似的幾何形狀。當(dāng)然，你可以用物體的準(zhǔn)確幾何形狀作邊界框，但出于效率的考慮，我不贊成這樣做，因?yàn)橛螒蛑械奈矬w一般都很復(fù)雜，用復(fù)雜的邊界框?qū)⒃黾哟罅康挠?jì)算，尤其是浮點(diǎn)計(jì)算，而這正是我們想盡量避免的。但邊界框也不能與準(zhǔn)確幾何形狀有太大的出入，否則就象用半徑法一樣出現(xiàn)奇怪的現(xiàn)象。
在飛行射擊游戲中，我們的飛機(jī)大多都是三角形的，我們可以用三角形作近似的邊界框。現(xiàn)在我們假設(shè)飛機(jī)是一個(gè)正三角形（或等要三角形，我想如果誰把飛機(jī)設(shè)計(jì)成左右不對稱的怪物，那他的審美觀一定有問題），我的飛機(jī)是正著的、向上飛的三角形，敵人的飛機(jī)是倒著的、向下飛的三角形，且飛機(jī)不會旋轉(zhuǎn)（大部分游戲中都是這樣的）。我們可以這樣定義飛機(jī)：中心點(diǎn)O(Xo,Yo),三個(gè)頂點(diǎn)P0(X0,Y0)、P1(X1,Y1)、P2(X2,Y2)。中心點(diǎn)為正三角形的中心點(diǎn)，即中心點(diǎn)到三個(gè)頂點(diǎn)的距離相等。接下來的問題是怎樣確定兩個(gè)三角形互相干擾了呢？嗯，現(xiàn)在我們接觸到問題的實(shí)質(zhì)了。如果你學(xué)過平面解析幾何，我相信你可以想出許多方法解決這個(gè)問題。判斷一個(gè)三角形的各個(gè)頂點(diǎn)是否在另一個(gè)三角形里面，看起來是個(gè)不錯(cuò)的方法，你可以這樣做，但我卻發(fā)現(xiàn)一個(gè)小問題：一個(gè)三角形的頂點(diǎn)沒有在另一個(gè)三角形的里面，卻可能發(fā)生了碰撞，因?yàn)榱硪粋€(gè)三角形的頂點(diǎn)在這個(gè)三角形的里面，所以要判斷兩次，這很麻煩。有沒有一次判斷就可以的方法？我們把三角形放到極坐標(biāo)平面中，中心點(diǎn)為原點(diǎn)，水平線即X軸為零度角。我們發(fā)現(xiàn)三角形成了這個(gè)樣子：在每個(gè)角度我們都可以找到一個(gè)距離，用以描述三角形的邊。既然我們找到了邊到中心點(diǎn)的距離，那就可以用這個(gè)距離來檢測碰撞。如圖一，兩個(gè)三角形中心點(diǎn)坐標(biāo)分別為（Xo,Yo）和 (Xo1,Yo1),由這兩個(gè)點(diǎn)的坐標(biāo)求出兩點(diǎn)的距離及兩點(diǎn)連線和X軸的夾角θ，再由θ求出中心點(diǎn)連線與三角形邊的交點(diǎn)到中心點(diǎn)的距離，用這個(gè)距離與兩中心點(diǎn)距離比較，從而判斷兩三角形是否碰撞。因?yàn)槿切巫笥覍ΨQ，所以θ取-90～90度區(qū)間就可以了。哈，現(xiàn)在問題有趣多了，-90～90度區(qū)間正是正切函數(shù)的定義域，求出θ之后再找對應(yīng)的邊到中心點(diǎn)的距離就容易多了，利用幾何知識，如圖二，將三角形的邊分為三部分,即圖2中紅綠藍(lán)三部分，根據(jù)θ在那一部分而分別對待。用正弦定理求出邊到中心點(diǎn)的距離，即圖2中淺綠色線段的長度。但是，如果飛機(jī)每次移動都這樣判斷一次，效率仍然很低。我們可以結(jié)合半徑法來解決，先用半徑法判斷是否可能發(fā)生碰撞，如果可能發(fā)生碰撞，再用上面的方法精確判斷是不是真的發(fā)生了碰撞，這樣基本就可以了。如果飛機(jī)旋轉(zhuǎn)了怎么辦呢，例如，如圖三所示飛機(jī)旋轉(zhuǎn)了一個(gè)角度α，仔細(xì)觀察圖三會發(fā)現(xiàn)，用（θ-α）就可以求出邊到中心點(diǎn)的距離，這時(shí)你要注意邊界情況，即（θ-α）可能大于90度或小于-90度。啰羅嗦嗦說了這么多，不知道大家明白了沒有。我編寫了一個(gè)簡單的例程，用于說明我的意圖。在例子中假設(shè)所有飛機(jī)的大小都一樣，并且沒有旋轉(zhuǎn)。
/////////////////////////////////////////////////////////////////////
//example.cpp
//碰撞檢測演示
//作者 李韜
/////////////////////////////////////////////////////////////////////
//限于篇幅，這里只給出了碰撞檢測的函數(shù)
//define/////////////////////////////////////////////////////////////
#define NUM_VERTICES 3
#define ang_30 -0.5236
#define ang60 1.0472
#define ang120 2.0944
//deftype////////////////////////////////////////////////////////////
struct object
{
float xo, yo;
float radio;
float x_vel, y_vel;
float vertices[NUM_VERTICES][2];
}
//faction/////////////////////////////////////////////////////////////
//根據(jù)角度求距離
float AngToDis(struct object obj, float angle)
{
float dis, R;
R = obj.radius;
if (angle <= ang_30)
dis = R / (2 * sin(-angle));
else if (angle >= 0)
dis = R / (2 * sin(angle + ang60));
else dis = R / (2 * sin(ang120 - angle));
return dis;
}
//碰撞檢測
int CheckHit(struct object obj1, struct object obj2)
{
float deltaX, deltaY, angle, distance, bumpdis;
deltaX = abs(obj1.xo - obj2.xo);
deltaY = obj1.yo - obj2.yo;
distance = sqrt(deltaX * deltaX + deltaY * deltaY);
if (distance <= obj.radio)
{
angle = atan2(deltaY, deltaX);
bumpdis1 = AngToDis(obj1, angle);
return (distance <= 2 * bumpdis);
}
ruturn 0;
}
//End//////////////////////////////////////////////////////////////
上面程序只是用于演示，并不適合放在游戲中，但你應(yīng)該明白它的意思，以便寫出適合你自己的碰撞檢測。游戲中的情況是多種多樣的，沒有哪種方法能適應(yīng)所有情況，你一定能根據(jù)自己的情況找到最適合自己的方法。
游戲算法整理 算法六：關(guān)于SLG中人物可到達(dá)范圍計(jì)算的想法
下面的沒有經(jīng)過實(shí)踐，因此很可能是錯(cuò)誤的，覺得有用的初學(xué)朋友讀一讀吧：）
希望高人指點(diǎn)一二 :)
簡介：
在標(biāo)準(zhǔn)的SLG游戲中，當(dāng)在一個(gè)人物處按下鼠標(biāo)時(shí)，會以人物為中心，向四周生成一個(gè)菱形的可移動區(qū)范圍，如下：
0
000
00s00
000
0
這個(gè)圖形在剛開始學(xué)習(xí)PASCAL時(shí)就應(yīng)該寫過一個(gè)畫圖的程序（是否有人懷念？）。那個(gè)圖形和SLG的擴(kuò)展路徑一樣。
一、如何生成路徑：
從人物所在的位置開始，向四周的四個(gè)方向擴(kuò)展，之后的點(diǎn)再進(jìn)行擴(kuò)展。即從人物所在的位置從近到遠(yuǎn)進(jìn)行擴(kuò)展（類似廣寬優(yōu)先）。
二、擴(kuò)展時(shí)會遇到的問題：
1、當(dāng)擴(kuò)展到一個(gè)點(diǎn)時(shí)，人物的移動力沒有了。
2、當(dāng)擴(kuò)展的時(shí)候遇到了一個(gè)障礙點(diǎn)。
3、當(dāng)擴(kuò)展的時(shí)候這個(gè)結(jié)點(diǎn)出了地圖。
4、擴(kuò)展的時(shí)候遇到了一個(gè)人物正好站在這個(gè)點(diǎn)（與2同？）。
5、擴(kuò)展的點(diǎn)已經(jīng)被擴(kuò)展過了。當(dāng)擴(kuò)展節(jié)點(diǎn)的時(shí)候，每個(gè)節(jié)點(diǎn)都是向四周擴(kuò)展，因此會產(chǎn)生重復(fù)的節(jié)點(diǎn)。
當(dāng)遇到這些問題的時(shí)候，我們就不對這些節(jié)點(diǎn)處理了。在程序中使用ALLPATH[]數(shù)組記錄下每一個(gè)等擴(kuò)展的節(jié)點(diǎn)，不處理這些問題節(jié)點(diǎn)的意思就是不把它們加入到ALLPATH[]數(shù)組中。我們?nèi)绾稳U(kuò)展一個(gè)結(jié)點(diǎn)周圍的四個(gè)結(jié)點(diǎn)，使用這個(gè)結(jié)點(diǎn)的坐標(biāo)加上一個(gè)偏移量就可以了，方向如下：
3
0 2
1
偏移量定義如下：
int offx[4] = { -1, 0, 1, 0 };
int offy[4] = { 0, 1, 0, -1 };
擴(kuò)展一個(gè)節(jié)點(diǎn)的相鄰的四個(gè)節(jié)點(diǎn)的坐標(biāo)為：
for(int i=0; i<4; i )
{
temp.x = temp1.x offx[i];
temp.y = temp1.y offy[i];
}
三、關(guān)于地圖的結(jié)構(gòu)：
1、地圖的二維坐標(biāo)，用于確定每個(gè)圖塊在地圖中的位置。
2、SLG中還要引入一個(gè)變量decrease表示人物經(jīng)過這個(gè)圖塊后他的移動力的減少值。例如，一個(gè)人物現(xiàn)在的移動力為CurMP=5，與之相領(lǐng)的圖塊的decrease=2；這時(shí)，如果人物移動到這里，那它的移動力變成CurMP-decrease。
3、Flag域：寬度優(yōu)先中好像都有這個(gè)變量，有了它，每一個(gè)點(diǎn)保證只被擴(kuò)展一次。防止一個(gè)點(diǎn)被擴(kuò)展多次。（一個(gè)點(diǎn)只被擴(kuò)展一次真的能得到正確的結(jié)果嗎？）
4、一個(gè)地圖上的圖塊是否可以通過，我們使用了一個(gè)Block代表。1---不可以通過；0---可以通過。
這樣，我們可以定義一個(gè)簡單的地圖結(jié)構(gòu)數(shù)組了：
#define MAP_MAX_WIDTH 50
#define MAP_MAX_HEIGHT 50
typedef struct tagTILE{
int x,y,decrease,flag,block;
}TILE,*LPTILE;
TILE pMap[MAP_MAX_WIDTH][MAP_MAX_HEIGHT];
以上是順序數(shù)組，是否使用動態(tài)的分配更好些？畢竟不能事先知道一個(gè)地圖的寬、高。
四、關(guān)于路徑：
SLG游戲中的擴(kuò)展路徑是一片區(qū)域（以人物為中心向四周擴(kuò)展，當(dāng)然，當(dāng)人物移動時(shí)路徑只有一個(gè)）。這些擴(kuò)展的路徑必須要存儲起來，所有要有一個(gè)好的結(jié)構(gòu)。我定義了一個(gè)結(jié)構(gòu)，不是很好：
typedef struct tagNODE{
int x,y; //擴(kuò)展路徑中的一個(gè)點(diǎn)在地圖中的坐標(biāo)。
int curmp; //人物到了這個(gè)點(diǎn)以后的當(dāng)前的移動力。
}NODE,*LPNODE;
上面的結(jié)構(gòu)是定義擴(kuò)展路徑中的一個(gè)點(diǎn)的結(jié)構(gòu)。擴(kuò)展路徑是點(diǎn)的集合，因此用如下的數(shù)組進(jìn)行定義：
NODE AllPath[PATH_MAX_LENGTH];
其中的PATH_MAX_LENGTH代表擴(kuò)展路徑的點(diǎn)的個(gè)數(shù)，我們不知道這個(gè)擴(kuò)展的路徑中包含多少個(gè)點(diǎn)，因此定義一個(gè)大一點(diǎn)的數(shù)字使這個(gè)數(shù)組不會產(chǎn)生溢出：
#define PATH_MAX_LENGTH 200
上面的這個(gè)數(shù)組很有用處，以后的擴(kuò)展就靠它來實(shí)現(xiàn)，它應(yīng)該帶有兩個(gè)變量nodecount 代表當(dāng)前的數(shù)組中有多少個(gè)點(diǎn)。當(dāng)然，數(shù)組中的點(diǎn)分成兩大部分，一部分是已經(jīng)擴(kuò)展的結(jié)點(diǎn)，存放在數(shù)組的前面；另一部分是等擴(kuò)展的節(jié)點(diǎn)，放在數(shù)組的后面為什么會出現(xiàn)已擴(kuò)展節(jié)點(diǎn)和待擴(kuò)展節(jié)點(diǎn)？如下例子：
當(dāng)前的人物坐標(biāo)為x,y；移動力為mp。將它存放到AllPath數(shù)組中，這時(shí)的起始節(jié)點(diǎn)為等擴(kuò)展的節(jié)點(diǎn)。這時(shí)我們擴(kuò)展它的四個(gè)方向，對于合法的節(jié)點(diǎn)（如沒有出地圖，也沒有障礙......），我們將它們存放入AllPath數(shù)組中，這時(shí)的新加入的節(jié)點(diǎn)（起始節(jié)點(diǎn)的子節(jié)點(diǎn)）就是等擴(kuò)展結(jié)點(diǎn)，而起始節(jié)點(diǎn)就成了已擴(kuò)展節(jié)點(diǎn)了。下一次再擴(kuò)展節(jié)點(diǎn)的時(shí)候，我們不能再擴(kuò)展起始節(jié)點(diǎn)，因?yàn)樗且呀?jīng)擴(kuò)展的節(jié)點(diǎn)了。我們只擴(kuò)展那幾個(gè)新加入的節(jié)點(diǎn)（待擴(kuò)展節(jié)點(diǎn)），之后的情況以此類推。那么我們?nèi)绾沃滥男┦且呀?jīng)擴(kuò)展的結(jié)點(diǎn)，哪些是等擴(kuò)展的節(jié)點(diǎn)？我們使用另一個(gè)變量cutflag，在這個(gè)變量所代表的下標(biāo)以前的結(jié)點(diǎn)是已擴(kuò)展節(jié)點(diǎn)，在它及它之后是待擴(kuò)展結(jié)點(diǎn)。
五、下面是基本框架（只擴(kuò)展一個(gè)人物的可達(dá)范圍）：
int nodecount = 0; //AllPath數(shù)組中的點(diǎn)的個(gè)數(shù)（包含待擴(kuò)展節(jié)點(diǎn)和已經(jīng)擴(kuò)展的節(jié)點(diǎn)
int cutflag = 0; //用于劃分已經(jīng)擴(kuò)展的節(jié)點(diǎn)和待擴(kuò)展節(jié)點(diǎn)
NODE temp; //路徑中的一個(gè)點(diǎn)（臨時(shí)）
temp.x = pRole[cur] - >x; //假設(shè)有一個(gè)關(guān)于人物的類，代表當(dāng)前的人物
temp.y = pRole[cur] - >y;
temp.curmp = pRole[cur] - >MP; //人物的最大MP
AllPath[nodecount] = temp; //起始點(diǎn)入AllPath，此時(shí)的起始點(diǎn)為等擴(kuò)展的節(jié)點(diǎn)
while (curflag < nodecount) { //數(shù)組中還有待擴(kuò)展的節(jié)點(diǎn)
int n = nodecount; //記錄下當(dāng)前的數(shù)組節(jié)點(diǎn)的個(gè)數(shù)。
for (int i = cutflag; i < nodecount; i) { //遍歷待擴(kuò)展節(jié)點(diǎn)
for (int j = 0; j < 4; j) { //向待擴(kuò)展節(jié)點(diǎn)的四周各走一步
//取得相鄰點(diǎn)的數(shù)據(jù)
temp.x = AllPath[i].x offx[j];
temp.y = AllPath[i].y offy[j];
temp.curmp = AllPath[i].curmp -
pMap[AllPath[i].x][AllPath[i].y].decrease;
//以下為檢測是否為問題點(diǎn)的過程，如果是問題點(diǎn)，不加入AllPath數(shù)組，繼續(xù)處理其它的點(diǎn)
if (pMap[temp.x][temp.y].block) {
continue; //有障礙，處理下一個(gè)節(jié)點(diǎn)
}
if (temp.curmp < 0) {
continue; //沒有移動力了
}
if (temp.x < 0 || temp.x >= MAP_MAX_WIDTH || temp.y < 0 ||
temp.y >= MAP_MAX_HEIGHT) {
continue; //出了地圖的范圍
}
if (pMap[temp.x][temp.y].flag) {
continue; //已經(jīng)擴(kuò)展了的結(jié)點(diǎn)
}
//經(jīng)過了上面幾層的檢測，沒有問題的節(jié)點(diǎn)過濾出來，可以加入AllPath
AllPath[nodecount] = temp;
}
pMap[AllPath[i].x][AllPath[i].y].flag = 1; //將已經(jīng)擴(kuò)展的節(jié)點(diǎn)標(biāo)記為已擴(kuò)展節(jié)點(diǎn)
}
cutflag = n; //將已擴(kuò)展節(jié)點(diǎn)和待擴(kuò)展節(jié)點(diǎn)的分界線下標(biāo)值移動到新的分界線
}
for (int i = 0; i < nodecount; i) {
pMap[AllPath[i].x][AllPath[i].y].bFlag = 0; //標(biāo)記為已擴(kuò)展節(jié)點(diǎn)的標(biāo)記設(shè)回為待擴(kuò)展節(jié)點(diǎn)。
}
游戲算法整理 算法七 無限大地圖的實(shí)現(xiàn)
這已經(jīng)不是什么新鮮的東西了，不過現(xiàn)在實(shí)在想不到什么好寫，而且版面上又異常冷清，我再不說幾句就想要倒閉了一樣。只好暫且拿這個(gè)東西來湊數(shù)吧。
無限大的地圖，聽上去非常吸引人。本來人生活的空間就是十分廣闊的，人在這么廣闊的空間里活動才有一種自由的感覺。游戲中的虛擬世界由于受到計(jì)算機(jī)存儲空間的限制，要真實(shí)地反映這個(gè)無限的空間是不可能的。而對這個(gè)限制最大的，就是內(nèi)存的容量了。所以在游戲的空間里，我們一般只能在一個(gè)狹小的范圍里活動，在一般的RPG中，從一個(gè)場景走到另一個(gè)場景，即使兩個(gè)地方是緊緊相連的，也要有一個(gè)場景的切換過程，一般的表現(xiàn)就是畫面的淡入淡出。
這樣的場景切換給人一種不連續(xù)的感覺（我不知道可不可以把這種稱作“蒙太奇”:o)），從城內(nèi)走到城外還有情可緣，因?yàn)橛械莱菈β铮莾蓚€(gè)地方明明沒有界限，卻偏偏在這一邊看不到另外一邊，就有點(diǎn)不現(xiàn)實(shí)了。當(dāng)然這并不是毛病，一直以來的RPG都是遵循這個(gè)原則，我們（至少是我）已經(jīng)習(xí)慣了這種走路的方式。我在這里說的僅僅是另外一種看起來更自然一點(diǎn)的走路方式，僅此而已。
當(dāng)然要把整個(gè)城市的地圖一下子裝進(jìn)內(nèi)存，現(xiàn)在的確是不現(xiàn)實(shí)的，每一次只能放一部分，那么應(yīng)該怎么放才是我們要討論的問題。
我們在以前提到Tile方法構(gòu)造地圖時(shí)就談到過Tile的好處之一就是節(jié)省內(nèi)存，這里仍然可以借鑒Tile的思想。我們把整個(gè)大地圖分成幾塊，把每一塊稱作一個(gè)區(qū)域，在同一時(shí)間里，內(nèi)存中只保存相鄰的四塊區(qū)域。這里每個(gè)區(qū)域的劃分都有一定的要求：每個(gè)區(qū)域大小應(yīng)該相等這是一定的了，不然判斷當(dāng)前屏幕在哪個(gè)區(qū)域中就成了一個(gè)非常令人撓頭的事；另外每個(gè)區(qū)域的大小都要大于屏幕的大小，也只有這樣才能保證屏幕（就是圖中那塊半透明的藍(lán)色矩形）在地圖上蕩來蕩去的時(shí)候，最多同時(shí)只能覆蓋四個(gè)區(qū)域（象左圖中所表示的），內(nèi)存里也只要保存四個(gè)區(qū)域就足夠了；還有一點(diǎn)要注意的，就是地圖上的建筑物（也包括樹啦，大石頭啦什么的）必須在一個(gè)區(qū)域內(nèi)，這樣也是為了畫起來方便，當(dāng)然墻壁——就是那種連續(xù)的圍墻可以除外，因?yàn)閴Ρ诒緛砭褪且欢我欢纹雌饋淼摹?
我們在程序中可以設(shè)定4個(gè)指針來分別指向這4個(gè)區(qū)域，當(dāng)每次主角移動時(shí)，就判斷當(dāng)前滾動的屏幕是否移出了這四個(gè)區(qū)域，如果移出了這四個(gè)區(qū)域，那么就廢棄兩個(gè)（或三個(gè)）已經(jīng)在目前的四個(gè)相鄰區(qū)域中被滾出去的區(qū)域（說得很別扭，各位見諒），讀入兩個(gè)（或三個(gè)）新滾進(jìn)來的區(qū)域，并重新組織指針。這里并不涉及內(nèi)存區(qū)域的拷貝。
這樣的區(qū)域劃分方法剛好適合我們以前提到的Tile排列方法，只要每個(gè)區(qū)域橫向Tile的個(gè)數(shù)是個(gè)偶數(shù)就行了，這樣相鄰的兩個(gè)區(qū)域拼接起來剛好嚴(yán)絲合縫，而且每個(gè)區(qū)域塊的結(jié)構(gòu)完全一致，沒有那些需要重復(fù)保存的Tile（這個(gè)我想我不需要再畫圖說明了，大家自己隨便畫個(gè)草圖就看得出來了）。在文件中的保存方法就是按一個(gè)個(gè)區(qū)域分別保存，這樣在讀取區(qū)域數(shù)據(jù)時(shí)就可以直接作為一整塊讀入，也簡化了程序。另外還有個(gè)細(xì)節(jié)就是，我們的整個(gè)地圖可能不是一個(gè)規(guī)則的矩形，可能有些地方是無法達(dá)到的，如右圖所示，背景是黑色的部分代表人物不能達(dá)到的地方。那么在整個(gè)地圖中，這一部分區(qū)域（在圖中藍(lán)色的3號區(qū)域）就可以省略，表現(xiàn)在文件存儲上就是實(shí)際上不存儲這一部分區(qū)域，這樣可以節(jié)省下不少存儲空間。對于這種地圖可以用一個(gè)稀疏矩陣來存儲，大家也可以發(fā)揮自己的才智用其他對于編程來說更方便的形式來存儲地圖。
這就是對無限大地圖實(shí)現(xiàn)的一種方法，歡迎大家提出更好的方法。也希望整個(gè)版面能夠活躍一點(diǎn)。
|