基于校園場景漫游系統的尋路算法設計

張國強 李軍

（湖南涉外經濟學院 信息科學與工程學院 湖南省長沙市 410081）

1 引言

在開發游戲項目時，尋路算法是其中一個不可或缺的重要組成部分。尋路算法的主要目的是在不同地形的限制下，尋找一條消耗代價值最低的路徑，從而節省游戲內人物完成地點移動的時間和負擔。Unity3D 自帶的尋路算法，往往對全程路段都進行了算法規劃，進而給CPU 運行帶來了較大負擔。使得大部分設備無法流暢運行本系統。本文基于此背景之下，引入A*尋路算法，重新對NavMesh 尋路功能，進行設計優化。

2 技術引入

2.1 A*算法簡介

A*算法（A-Star），一種啟發式，精確而又高效的直接尋路算法，基于傳統的Dijkstra 尋路算法的優化改進，于1968年P.E.Hart、N.J.Nilsson 和B.RaPhael 發表的論文之中被提出，在相關領域中被廣泛應用。在沒有預處理的情況下，A*算法是最有效的直接搜索算法。其基本公式為：

（其中F(N)表示初始點經過N 到目標點尋路消耗值估計，G(N)表示從預構設最優集合，即狀態空間中所獲取的初始點到目標點N 的實際尋路消耗值，H(N)是從點N 到目標點的最優解的預估尋路消耗值）。

2.2 曼哈頓距離簡介

在幾何空間中，如何計算兩點距離，將其引入并解決問題，顯得至關重要，在幾何度量空間學中，主要采用了歐氏距離和曼哈頓距離這兩種距離來進行表示。曼哈頓距離：赫爾曼?閔可夫斯基，僅用兩個點在坐標系上的軸差的絕對值來表示，在十九世紀，提出來的幾何學用于，主要表示兩個點在標準坐標系上的絕對軸距總和。

3 算法設計

3.1 尋路算法的分析

本文針對的Unity3D 引擎，如果全程使用其所自帶的NavMesh尋路功能進行尋址。在每次進行尋址時，都會對起點到終點進行靜態的全路程最短路徑搜索，大大耗費了系統資源。A*算法在大部分情況下的處理效率都優于Dijkstra 算法，因此在角色點到各建筑物所在標識點之間的路徑，優先采用A*算法來進行處理，這樣能夠有效提高尋址功能效率。在Unity3D 項目中，物體所呈現的坐標值基本為整數，因此在考慮到尋路算法時，會采用以曼哈頓距離為代價值的A*算法。

圖1：算法設計思路

圖2：三維空間內基于曼哈頓距離的領接節點

圖3：三維空間尋路算法測試

由于是已經固定好的地圖環境，且各大建筑之間存在著主流道路走法。所以將各大建筑物之間的路徑進行線段劃分，將線段兩段為計算節點，以A*算法進行路線規劃，并存入系統中。在進行路徑導航時，先通過實時獲取的坐標軸信息，對臨近建筑坐標點進行尋路，到達后沿當前建筑和目標建筑的預存儲道路進行前行。與NavMesh 組件相比較，主要減少了后期固定建筑點的尋址消耗，在長距離導航的情況下，可以減少大量系統資源（在選取目標地點建筑為臨近建筑的時候，本算法和NavMesh 組件所耗資源相近）。

3.2 代價值函數設計

為了得到A*算法公式中的G(N)和H(N)，必須要計算出兩點之間的距離，并以此小號作為節點所要考慮的優先級，因此編寫了一個GetDistance()的方法，計算尋址所需兩點之間的距離。

G(N)是實際代價值，即當前點和目標點的路徑距離，由兩點之間三維標準坐標軸的進行計算。

H(N)為估計代價值，即當前節點和目標點的路徑代價估計，當前節點和G 計算而出的啟發函數。

如在具體的應用環境下有特定的需求，可以重新設置A*算法公式下的代價函數G(N)和估計代價值H(N)的權重k1和k2。在默認情況下采用k1=k2=1 的權重比例。

3.3 尋路算法實現

如何構建并創造啟發函數H（N），是A*算法和Dijkstra 算法的主要區別，以A*算法為核心思想，Unity3D 所規劃的網格整數坐標點作為節點，設計一個關乎啟發函數H（N）的優先級作為其選取的選取順序，將有可能成為最小消耗路徑的節點壓入優先隊列進行遍歷，從而決定最小消耗值路徑。具體設計思路如下和圖1 所示：

（1）建立了兩個集合，KeyList()（存儲會參加競爭最小消耗值路徑決策的位置點集合）和RbList()（存儲不會參加競爭最小消耗值路徑的位置點集合）。

（2）把初始位置節點（在操作界面中發起尋路的最近的網格整數坐標點）壓入KeyList()，并將其優先級設置為0（最高級優先級）。

（3）若KeyList()為非空集合，選擇KeyList()內優先級最高的節點K，對此節點K 進行判斷。

若節點K 為尋路終點：從節點K 開始逐步回溯追尋其父節點，一直達到起點，并將返回的結果集反向調入到移動類之中，系統中的人物開始根據所尋找的最小消耗值路徑進行路徑尋址。

若節點K 非尋路終點：將節點K 從KeyList()刪除，加入到RbList()中。隨后并將節點K 附近所有的非RbList()集合內領接節點加入KeyList()并設置其父節點為節點K，并將其節點根據曼哈頓距離設置優先級，三維空間內領接節點如圖2 所示，內部方塊為節點K，外部6 方向方塊為子節點。

3.4 導航系統實現

將所設計好的A*算法所倒序返回的節點集合，作為在實際環境中角色移動的唯一依據。創建PlayerNavigation()方法，在此方法下，完成基于A*算法的自動尋路。

（1）構建A-StarPoint 集合，用來接收其返回的節點集合。

（2）撰寫Updata()方法，以0.7f 為實時刷新速率，獲取角色X，Y，Z 三軸坐標。

（3）撰寫Walk()方法，以A-StarPoint 集合是否為空作為依據，依據A-StarPoint 集合頂端節點，進行角色移動。角色在可行區域內，不斷按照頂端節點進行移動，直至集合為空，則到達A*算法結束目的地。

（4）設計WalkMapping 類，用來預處理各大建筑之間的最短路關系。通過人工規劃路線，將道路分割成線段的形式，并在線段路線兩點，設立坐標點，以此為尋路節點，并通過A*算法預處理，將處理結果，以鍵值對的形式存放，兩個建筑的特定路線因此被存儲下來。

用戶在尋路時，根據輸入的實時地點和目標地點，先找到最近的建筑物特定坐標點信息，實時使用PlayerNavigation()方法，獲取用戶當前位置到建筑物特定坐標點的最優路徑，待用戶到達此建筑物特定坐標點后，調用WalkMapping 類里已存放好的建筑物之間移動路徑，進行移動。

4 仿真實驗測試

在Unity3D 引擎下，利用Probuilder 組件建立起1:1:1 的立方體塊群，并在此上面引入本文所設計的本文算法與傳統的Dijkstra算法進行對比。測試環境如圖3（額外展示了被加入KeyList()集合和RbList()集合的節點所在方塊，理論上參與的節點越少，效率越高，對系統資源的占用越少）所示。

通過選取初始節點的不同，使用兩種尋路算法進行測試，測試數據如表1 所示。

表1：本文算法和Dijkstra 算法實驗數據

從表中可以明顯看出，本文算法的耗時要遠低于Dijkstra，且在面對障礙性明顯的路段時，本文算法比Dijkstra 的處理時所使用系統資源更少。根據測試過程中所展示的KeyList()和RbList()所用節點，發現在大多數情況下本文算法所遍歷的節點更少。因此可以得出本文算法在時間復雜度和空間復雜度都是相對Dijkstra 算法更優的算法。

對于與處理好的WalkMapping 類，系統僅需存儲其預定路線，需要的內存和時間極少，此次不做參與測試。

5 結語

Unity3D 引擎中的NavMesh 尋路組件被本文所設計的尋路算法所取締，并后續引入到了校園場景漫游系統中，本算法針對其環境，更加迅速的尋找到最小消耗值路徑，并且降低了系統的資源占用率，大大優化了程序在運行尋址功能時的系統開銷，滿足了所擁有的設備性能較為不足的用戶群體，流暢使用導航功能的需求。但是知識淺薄，技術短缺，本算法仍有許多缺陷不足以及改進空間，后期應學習參考ARA*算法和D*算法對此算法進行改進優化，并考慮在靜態搜索結束后，根據玩家指令所產生的非最小消耗值路徑上的位移，進行實時路徑演變處理，使其尋路效率更高、系統資源占用率更低且更加實時動態化，符合用戶需求。