有時(shí)候，影響計(jì)算尋路路徑的不是時(shí)間，而是計(jì)算路徑所需的上百個(gè)單元格所占的空間。尋路是需要內(nèi)存來運(yùn)行尋路算法，還需要額外內(nèi)存來存儲尋到的路徑。運(yùn)行尋路算法（A*,開集或閉集）所需的臨時(shí)空間經(jīng)常會比存儲這些尋到的路徑所需的空間更大。通過在同一時(shí)間內(nèi)只進(jìn)行一條路徑計(jì)算來限制游戲中的計(jì)算量，可以將你需要的臨時(shí)空間降到最少。另外，對開集閉集的數(shù)據(jù)結(jié)構(gòu)的選擇也會對減少你所需的臨時(shí)內(nèi)存產(chǎn)生很大的影響。在本章中將會轉(zhuǎn)而關(guān)注通過生成的路徑減少使用的空間。

位置vs方向

一條路徑可以是一堆位置或者一堆方向，位置需要更多的空間，但是它的優(yōu)勢在于它很容易決定一條路徑上的一個(gè)任意的位置點(diǎn)或者方向而不用遍歷這條路徑。當(dāng)存儲方向的時(shí)候，只需要這個(gè)方向就可以很容易的決定；而位置只能通過遵循某個(gè)方向經(jīng)由整條路徑才能決定，在傳統(tǒng)的柵格化地圖中，位置可能使用兩個(gè)16位的整數(shù)來存儲，這樣的話，每一步存儲都需要32字節(jié)。因?yàn)樗懈俚姆较蛩孕枰目臻g就更少。如果一個(gè)單元格只能在四個(gè)方向上移動，每一步只需要2字節(jié)；如果單元格可以在六個(gè)或者八個(gè)方向上移動，每一步就會需要3字節(jié)。這些存儲在存儲位置上的路徑點(diǎn)在路徑中是非常重要的。Hannu Kankaanpaa建議你可以通過存儲絕對的方向(比如”向北”)而不是存儲這些相對方向(比如”右轉(zhuǎn)60度”)來進(jìn)一步的減少存儲所需的空間。一些相對方向可能讓一些單元格難以理解。比如說如果你的單元格在想北方移動，那它下一步就不大可能向南移動。在一個(gè)六方向的游戲中，你只有五個(gè)有意義的方向。在一些地圖中你可能只有3個(gè)方向(直走，左轉(zhuǎn)60度，右轉(zhuǎn)60度)有意義。但是在一些其他的地圖中右轉(zhuǎn)120度可能才是一個(gè)有效的移動(比如通過Z字形路線爬一座陡峭的山)。

路徑壓縮

一旦一個(gè)路徑被找到，它將會通過某種方式被壓縮。我們可以使用一個(gè)通用的壓縮算法，但是我們不會在這篇文章中討論這個(gè)算法。一個(gè)針對具體路徑的壓縮算法可以用來縮短基于位置的路徑或者基于方向的路徑。在做決定之前，考慮你游戲中的具體的典型路徑來決定哪一種壓縮算法最適合你所尋到的路徑。同時(shí) 也要考慮在你游戲中實(shí)施(或者調(diào)試)的可行性，代碼的體積還有這個(gè)壓縮算法是否真的很重要。如果你有 個(gè)300單元格的限制，在同一時(shí)間只有50個(gè)單元格在移動，并且路徑很短(只有100步)，那么所需要的內(nèi)存可能最多只有50k，那么你就不需要再考慮使用路徑的壓縮算法了。

位置點(diǎn)存儲

在一張地圖中如果障礙是尋路的主要影響因子而不是地形，那么就可以將路徑分成很多條線段，如果是這種情況的話，那么一條路徑只需要包括這些線段集合的各個(gè)終點(diǎn)位置(有時(shí)也被稱為路徑點(diǎn))。運(yùn)動就是由檢查這條路徑的下一個(gè)終點(diǎn)位置并沿著直線向終點(diǎn)移動組成。

方向存儲

當(dāng)方向被存儲的時(shí)候，它可能是在一排中多次出現(xiàn)的方向，你可以利用那種常見的模式使用較少的空間去存儲那條路徑。

一種最好的存儲路徑方式是同時(shí)存儲這個(gè)方向和指明單元格將在這個(gè)方向上移動多少次的數(shù)字。不同于位置存儲的優(yōu)化，當(dāng)這個(gè)方向在這一排中并沒有多次使用的時(shí)候這種優(yōu)化可能會變得很糟。當(dāng)然，對于很多直線路徑的位置存儲這種方式很有效，由于線可以不與的行走方向之一對齊，這種情況并不適用方向存儲的壓縮。當(dāng)有多種可選方向時(shí)，你可以選擇清除“一直直走”作為一個(gè)可行的方向。Hannu Kankaanpaa指出在一個(gè)八方向圖中，你可以清除直走，后退還有135度左，右轉(zhuǎn)（假設(shè)你的地圖允許這樣），然后你可以僅僅使用2字節(jié)去存儲每個(gè)方向。

另一種存儲路徑的方法是使用可變長度的編碼。這是指使用一個(gè)單字節(jié)去存儲大部分的一般性步驟比如說：直走。使用數(shù)字1去標(biāo)記轉(zhuǎn)向，在跟上一個(gè)數(shù)字1使用一些字節(jié)去表示轉(zhuǎn)向，在一個(gè)4向圖中，你只可以左轉(zhuǎn)或者右轉(zhuǎn)，所以你可能需要使用10來表示左轉(zhuǎn)11來表示右轉(zhuǎn)。

可變長度編碼更為通用，可能比游程編碼工作起來更好，但是對于長直型的路徑就不如混合編碼了。這個(gè)(北向，六步直走，左轉(zhuǎn)，直走三步，右轉(zhuǎn)，直走5步，左轉(zhuǎn)，直走六步)的序列被使用長編碼的[(North,6),(WEST,3),(NORTH,5),(WEST,2)]所代替。如果每個(gè)方向占用2字節(jié)，美短距離占用8字節(jié)，這條路徑需要40字節(jié)去存儲。如果使用可變長度編碼，你需要使用1個(gè)字節(jié)去存儲各個(gè)步驟2個(gè)字節(jié)去存儲每次轉(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é)就可以存儲這條路徑。但是使用可變長度編碼在遇到較長的路徑可能需要使用更多的空間。如果使用游程編碼這個(gè)序列(north,直走200步)是[(NORTH,200)]只需要10個(gè)字節(jié)，同樣的序列如果使用可變長度編碼就變成[NORTH 0 0...],總共需要202字節(jié)。

計(jì)算路徑點(diǎn)

路徑點(diǎn)是指一條路徑上的所有點(diǎn)。尋路完成后處理步驟時(shí)，可以折疊多個(gè)步驟到一個(gè)單一的路徑點(diǎn)鐘，通常存儲的是路徑改變方向的點(diǎn)，或者像城市的主要位置點(diǎn)，而不是存儲一路走來的每一步。然后使用算法在路徑點(diǎn)之間沿著路徑運(yùn)動。

限制路徑長度

考慮到地圖條件或者指令可能會發(fā)生變化，存儲一條長路徑可能意義并不大，因?yàn)橛嘞碌穆窂近c(diǎn)可能根本就不會被使用到。每個(gè)單元格可以在路徑開始的時(shí)候存儲一些合適的步驟數(shù)，然后在路徑快要走完時(shí)在重新計(jì)算心的路徑。這種方法可以控制每個(gè)單元格的數(shù)據(jù)量。

總結(jié)

路徑在游戲中可能占用很多空間，尤其是當(dāng)路徑很長，并且這個(gè)路徑上有很多游戲單元的時(shí)候。路徑壓縮、路徑點(diǎn)還有信標(biāo)（beacon）都會在一定程度上減少在一小塊數(shù)據(jù)里存儲很多行路步驟的空間。在一條直線路徑上加入需要存儲路徑點(diǎn)的話，只需要存儲末尾點(diǎn)就可以了，信標(biāo)是依靠在地圖上特意標(biāo)明的地方之間事先計(jì)算好的路徑上使用。如果路徑仍然需要占用很大的空間，就要限制路徑的長度了，在經(jīng)典的實(shí)時(shí)路徑計(jì)算中是這樣做的：為了節(jié)省空間，消息可以被忽略并且延遲計(jì)算。

總結(jié)

以上是生活随笔為你收集整理的关于寻路算法的一些思考（6）：预先计算好的路径的所用空间的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。