- 本文由 伯樂(lè)在線 - stonesun 翻譯，黃利民 校稿。未經(jīng)許可魄健，禁止轉(zhuǎn)載！
英文出處：Amit Patel插勤。歡迎加入翻譯組沽瘦。
本系列：
- 關(guān)于尋路算法的一些思考（1）：A* 算法介紹
- 關(guān)于尋路算法的一些思考（2）：Heuristics 函數(shù)
- 關(guān)于尋路算法的一些思考（3）：A* 算法的實(shí)現(xiàn)
- 關(guān)于尋路算法的一些思考（4）：A* 算法的變體
- 關(guān)于尋路算法的一些思考（5）：處理移動(dòng)中的障礙物
- 關(guān)于尋路算法的一些思考（6）：預(yù)先計(jì)算好的路徑的所用空間
- 關(guān)于尋路算法的一些思考（7）：地圖表示
- 關(guān)于尋路算法的一些思考（8）：長(zhǎng)期和短期目標(biāo)
- 關(guān)于尋路算法的一些思考（9）：尋路者的移動(dòng)成本
- 關(guān)于尋路算法的一些思考（10）：最短路徑的用戶體驗(yàn)
- 關(guān)于尋路算法的一些思考（11）：尋路算法的其他應(yīng)用
- 關(guān)于尋路算法的一些思考（12）：AI 技術(shù)
有時(shí)候革骨，影響計(jì)算尋路路徑的不是時(shí)間，而是計(jì)算路徑所需的上百個(gè)單元格所占的空間析恋。尋路是需要內(nèi)存來(lái)運(yùn)行尋路算法良哲，還需要額外內(nèi)存來(lái)存儲(chǔ)尋到的路徑。運(yùn)行尋路算法（A*,開集或閉集）所需的臨時(shí)空間經(jīng)常會(huì)比存儲(chǔ)這些尋到的路徑所需的空間更大助隧。通過(guò)在同一時(shí)間內(nèi)只進(jìn)行一條路徑計(jì)算來(lái)限制游戲中的計(jì)算量筑凫，可以將你需要的臨時(shí)空間降到最少。另外并村，對(duì)開集閉集的數(shù)據(jù)結(jié)構(gòu)的選擇也會(huì)對(duì)減少你所需的臨時(shí)內(nèi)存產(chǎn)生很大的影響巍实。在本章中將會(huì)轉(zhuǎn)而關(guān)注通過(guò)生成的路徑減少使用的空間。
位置vs方向
一條路徑可以是一堆位置或者一堆方向哩牍，位置需要更多的空間棚潦，但是它的優(yōu)勢(shì)在于它很容易決定一條路徑上的一個(gè)任意的位置點(diǎn)或者方向而不用遍歷這條路徑。當(dāng)存儲(chǔ)方向的時(shí)候膝昆，只需要這個(gè)方向就可以很容易的決定丸边；而位置只能通過(guò)遵循某個(gè)方向經(jīng)由整條路徑才能決定，在傳統(tǒng)的柵格化地圖中荚孵，位置可能使用兩個(gè)16位的整數(shù)來(lái)存儲(chǔ)妹窖，這樣的話，每一步存儲(chǔ)都需要32字節(jié)收叶。因?yàn)樗懈俚姆较蛩孕枰目臻g就更少嘱吗。如果一個(gè)單元格只能在四個(gè)方向上移動(dòng)，每一步只需要2字節(jié)滔驾；如果單元格可以在六個(gè)或者八個(gè)方向上移動(dòng)谒麦，每一步就會(huì)需要3字節(jié)。這些存儲(chǔ)在存儲(chǔ)位置上的路徑點(diǎn)在路徑中是非常重要的哆致。Hannu Kankaanpaa建議你可以通過(guò)存儲(chǔ)絕對(duì)的方向(比如”向北”)而不是存儲(chǔ)這些相對(duì)方向(比如”右轉(zhuǎn)60度”)來(lái)進(jìn)一步的減少存儲(chǔ)所需的空間绕德。一些相對(duì)方向可能讓一些單元格難以理解。比如說(shuō)如果你的單元格在想北方移動(dòng)摊阀，那它下一步就不大可能向南移動(dòng)耻蛇。在一個(gè)六方向的游戲中，你只有五個(gè)有意義的方向胞此。在一些地圖中你可能只有3個(gè)方向(直走臣咖，左轉(zhuǎn)60度，右轉(zhuǎn)60度)有意義漱牵。但是在一些其他的地圖中右轉(zhuǎn)120度可能才是一個(gè)有效的移動(dòng)(比如通過(guò)Z字形路線爬一座陡峭的山)夺蛇。
路徑壓縮
一旦一個(gè)路徑被找到，它將會(huì)通過(guò)某種方式被壓縮酣胀。我們可以使用一個(gè)通用的壓縮算法刁赦，但是我們不會(huì)在這篇文章中討論這個(gè)算法娶聘。一個(gè)針對(duì)具體路徑的壓縮算法可以用來(lái)縮短基于位置的路徑或者基于方向的路徑。在做決定之前甚脉，考慮你游戲中的具體的典型路徑來(lái)決定哪一種壓縮算法最適合你所尋到的路徑丸升。同時(shí) 也要考慮在你游戲中實(shí)施(或者調(diào)試)的可行性，代碼的體積還有這個(gè)壓縮算法是否真的很重要牺氨。如果你有 個(gè)300單元格的限制狡耻，在同一時(shí)間只有50個(gè)單元格在移動(dòng)，并且路徑很短(只有100步)猴凹，那么所需要的內(nèi)存可能最多只有50k夷狰，那么你就不需要再考慮使用路徑的壓縮算法了。
位置點(diǎn)存儲(chǔ)
在一張地圖中如果障礙是尋路的主要影響因子而不是地形精堕，那么就可以將路徑分成很多條線段孵淘，如果是這種情況的話，那么一條路徑只需要包括這些線段集合的各個(gè)終點(diǎn)位置(有時(shí)也被稱為路徑點(diǎn))歹篓。運(yùn)動(dòng)就是由檢查這條路徑的下一個(gè)終點(diǎn)位置并沿著直線向終點(diǎn)移動(dòng)組成瘫证。
方向存儲(chǔ)
當(dāng)方向被存儲(chǔ)的時(shí)候，它可能是在一排中多次出現(xiàn)的方向庄撮，你可以利用那種常見的模式使用較少的空間去存儲(chǔ)那條路徑背捌。
一種最好的存儲(chǔ)路徑方式是同時(shí)存儲(chǔ)這個(gè)方向和指明單元格將在這個(gè)方向上移動(dòng)多少次的數(shù)字。不同于位置存儲(chǔ)的優(yōu)化洞斯，當(dāng)這個(gè)方向在這一排中并沒(méi)有多次使用的時(shí)候這種優(yōu)化可能會(huì)變得很糟毡庆。當(dāng)然，對(duì)于很多直線路徑的位置存儲(chǔ)這種方式很有效烙如，由于線可以不與的行走方向之一對(duì)齊么抗，這種情況并不適用方向存儲(chǔ)的壓縮。當(dāng)有多種可選方向時(shí)亚铁，你可以選擇清除“一直直走”作為一個(gè)可行的方向蝇刀。Hannu Kankaanpaa指出在一個(gè)八方向圖中，你可以清除直走徘溢，后退還有135度左吞琐，右轉(zhuǎn)（假設(shè)你的地圖允許這樣），然后你可以僅僅使用2字節(jié)去存儲(chǔ)每個(gè)方向然爆。
另一種存儲(chǔ)路徑的方法是使用可變長(zhǎng)度的編碼站粟。這是指使用一個(gè)單字節(jié)去存儲(chǔ)大部分的一般性步驟比如說(shuō)：直走。使用數(shù)字1去標(biāo)記轉(zhuǎn)向曾雕，在跟上一個(gè)數(shù)字1使用一些字節(jié)去表示轉(zhuǎn)向奴烙，在一個(gè)4向圖中，你只可以左轉(zhuǎn)或者右轉(zhuǎn)，所以你可能需要使用10來(lái)表示左轉(zhuǎn)11來(lái)表示右轉(zhuǎn)缸沃。
可變長(zhǎng)度編碼更為通用恰起，可能比游程編碼工作起來(lái)更好修械，但是對(duì)于長(zhǎng)直型的路徑就不如混合編碼了趾牧。這個(gè)(北向，六步直走肯污，左轉(zhuǎn)翘单，直走三步，右轉(zhuǎn)蹦渣，直走5步哄芜，左轉(zhuǎn)，直走六步)的序列被使用長(zhǎng)編碼的[(North,6),(WEST,3),(NORTH,5),(WEST,2)]所代替柬唯。如果每個(gè)方向占用2字節(jié)认臊，美短距離占用8字節(jié)，這條路徑需要40字節(jié)去存儲(chǔ)锄奢。如果使用可變長(zhǎng)度編碼失晴，你需要使用1個(gè)字節(jié)去存儲(chǔ)各個(gè)步驟2個(gè)字節(jié)去存儲(chǔ)每次轉(zhuǎn)向-[NORTH 0 0 0 0 0 0 10 0 0 0 11 0 0 0 0 0 10 0 0]總共需要24字節(jié)。如果初始化的方向和每次轉(zhuǎn)向代表一步拘央，你可以每次轉(zhuǎn)向省下一字節(jié)涂屁，這樣你只需要20字節(jié)就可以存儲(chǔ)這條路徑。但是使用可變長(zhǎng)度編碼在遇到較長(zhǎng)的路徑可能需要使用更多的空間灰伟。如果使用游程編碼這個(gè)序列(north,直走200步)是[(NORTH,200)]只需要10個(gè)字節(jié)拆又，同樣的序列如果使用可變長(zhǎng)度編碼就變成[NORTH 0 0…],總共需要202字節(jié)。
計(jì)算路徑點(diǎn)
路徑點(diǎn)是指一條路徑上的所有點(diǎn)栏账。尋路完成后處理步驟時(shí)帖族，可以折疊多個(gè)步驟到一個(gè)單一的路徑點(diǎn)鐘，通常存儲(chǔ)的是路徑改變方向的點(diǎn)挡爵，或者像城市的主要位置點(diǎn)竖般，而不是存儲(chǔ)一路走來(lái)的每一步。然后使用算法在路徑點(diǎn)之間沿著路徑運(yùn)動(dòng)了讨。
限制路徑長(zhǎng)度
考慮到地圖條件或者指令可能會(huì)發(fā)生變化捻激，存儲(chǔ)一條長(zhǎng)路徑可能意義并不大，因?yàn)橛嘞碌穆窂近c(diǎn)可能根本就不會(huì)被使用到前计。每個(gè)單元格可以在路徑開始的時(shí)候存儲(chǔ)一些合適的步驟數(shù)胞谭，然后在路徑快要走完時(shí)在重新計(jì)算心的路徑。這種方法可以控制每個(gè)單元格的數(shù)據(jù)量男杈。
總結(jié)
路徑在游戲中可能占用很多空間丈屹，尤其是當(dāng)路徑很長(zhǎng)，并且這個(gè)路徑上有很多游戲單元的時(shí)候。路徑壓縮旺垒、路徑點(diǎn)還有信標(biāo)（beacon）都會(huì)在一定程度上減少在一小塊數(shù)據(jù)里存儲(chǔ)很多行路步驟的空間彩库。在一條直線路徑上加入需要存儲(chǔ)路徑點(diǎn)的話，只需要存儲(chǔ)末尾點(diǎn)就可以了先蒋，信標(biāo)是依靠在地圖上特意標(biāo)明的地方之間事先計(jì)算好的路徑上使用骇钦。如果路徑仍然需要占用很大的空間，就要限制路徑的長(zhǎng)度了竞漾，在經(jīng)典的實(shí)時(shí)路徑計(jì)算中是這樣做的：為了節(jié)省空間眯搭，消息可以被忽略并且延遲計(jì)算。
