上一篇文章在原有的A*算法上增加了權值，解決了混合型地圖的最短時間循跡問題。本篇文章我們來討論一下A*算法，在三維地圖上可行性。

目錄

A算法（一）：4方向
A算法（二）：8方向
A算法（三）：雙向策略與類似算法
A算法（四）：權值與混合型地圖
A*算法（五）：在三維地圖的可行性

可行性討論

在二維空間上，我們把地圖分割成許許多多大小一致的正方格。而在三維空間，我們就得考慮高度了。于是一個三維地圖就可以通過許許多多大小一致的正方體來表示。

A*算法用在三維空間無非就是把高度也考慮進去。但是在二維空間里，方格最多只要考慮8個方向，而三維空間的方塊最多得考慮26個方向（3*3*3 - 1），這對于一般的遍歷算法來說，工作量是巨大的。

為了減少遍歷，我們可以嘗試做出一定的犧牲。

第一種策略是減少遍歷方向，之前的文章我們討論過二維地圖的A*算法，4方向只能夠上下左右移動，不能斜著移動，相比于8方向減少了方向的遍歷。類似地，在三維空間，如果不允許斜著飛行，那么只要考慮6個方向就可以了，如下圖。

第二種策略是減少粒度，如下圖，右邊的圖片像素個數從 500 * 300 減少到 250 * 150。遍歷全像素次數大大減少，但代價是圖片變模糊了。

類似的一個三維空間由原來的100 * 100 * 100表示，改用 75 * 75 * 75來表示，遍歷次數就減少了，但代價就是精確度降低。

或許同時使用上述兩種策略會有不錯的效果。

如果A*算法在三維空間可行，那么上一篇文章講到的基于權值的混合型地圖路徑規劃也就不成問題了。

例如下圖，灰色方塊為障礙物，綠色為無風區域（權值為1），紅色為微風區域（權值為10），紫色為大風區域（權值為100），很顯然，天藍色的飛行路徑耗時最短。黃色路徑雖然距離最短但由于經過了大風區域（權值為100），耗時大大增加。

總結

以上是生活随笔為你收集整理的A*算法（五）：在三维地图的可行性的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。