最初的Unity導航系統很不完善,隻能靜态烘焙場景圖的可行走區域,而且必須在本地儲存場景的NavMesh資料,難以運作時動态計算;這使得鮮有開發者願意再嘗試Unity内置的導航功能,轉向了AStar尋路算法的研究。
但實際上AStar算法真的适合大多數開發情況且性能較優麼?
了解過AStar算法的都知道,它是基于格子來周遊計算行走權重的,算法複雜度其實是相對較高的,受到格子密度,地圖大小和路線長度的的影響較大。
AStar更适合的是政策性尋路,該算法更有利于找出最短路徑的最優解,能夠達到足夠的精确性。
而Unity的NavMesh是用的拐角點算法,随便找一個場景烘焙一下便可得知,例如:
烘焙出來的NavMesh區域隻在障礙物邊緣與平面邊緣存在頂點,而不會像AStar一樣均勻的布滿整個平面;如果是一個無任何障礙物的平面,那就隻會有平面邊緣的幾個頂點,算法效率是相對較高的,并不會因為地圖變大而有明顯算法複雜度上的變化。
相反,NavMesh的缺點也正是AStar的優點,那就是難以保證尋路的最優解,更多的時候是用于AI能夠更快計算出繞過障礙物朝向目标前進的路徑。
對于場景不變的靜态地圖來說,Unity最初的NavMesh已經能夠滿足需求,但如果地圖随機生成或障礙物的位置随時變化,此時靜态NavMesh一下子就捉襟見肘了。
好在随着Unity版本的更新,關于動态烘焙的方法也已經能有效實作,這樣無論是以怎樣千變萬化的方式生成的随機地圖,随機地圖在遊戲中如何建構重組,都能動态重新整理出NavMesh的可行走區域。
1 using UnityEngine;
2 using UnityEngine.AI;
3 using System.Collections.Generic;
4
5 // Tagging component for use with the LocalNavMeshBuilder
6 // Supports mesh-filter and terrain - can be extended to physics and/or primitives
7 [DefaultExecutionOrder(-200)]
8 public class NavMeshSourceTag : MonoBehaviour
9 {
10 // Global containers for all active mesh/terrain tags
11 public static List<MeshFilter> m_Meshes = new List<MeshFilter>();
12 public static List<Terrain> m_Terrains = new List<Terrain>();
13
14 void OnEnable()
15 {
16 var m = GetComponent<MeshFilter>();
17 if (m != null)
18 {
19 m_Meshes.Add(m);
20 }
21
22 var t = GetComponent<Terrain>();
23 if (t != null)
24 {
25 m_Terrains.Add(t);
26 }
27 }
28
29 void OnDisable()
30 {
31 var m = GetComponent<MeshFilter>();
32 if (m != null)
33 {
34 m_Meshes.Remove(m);
35 }
36
37 var t = GetComponent<Terrain>();
38 if (t != null)
39 {
40 m_Terrains.Remove(t);
41 }
42 }
43
44 // Collect all the navmesh build sources for enabled objects tagged by this component
45 public static void Collect(ref List<NavMeshBuildSource> sources)
46 {
47 sources.Clear();
48
49 for (var i = 0; i < m_Meshes.Count; ++i)
50 {
51 var mf = m_Meshes[i];
52 if (mf == null) continue;
53
54 var m = mf.sharedMesh;
55 if (m == null) continue;
56
57 var s = new NavMeshBuildSource();
58 s.shape = NavMeshBuildSourceShape.Mesh;
59 s.sourceObject = m;
60 s.transform = mf.transform.localToWorldMatrix;
61 s.area = 0;
62 sources.Add(s);
63 }
64
65 for (var i = 0; i < m_Terrains.Count; ++i)
66 {
67 var t = m_Terrains[i];
68 if (t == null) continue;
69
70 var s = new NavMeshBuildSource();
71 s.shape = NavMeshBuildSourceShape.Terrain;
72 s.sourceObject = t.terrainData;
73 // Terrain system only supports translation - so we pass translation only to back-end
74 s.transform = Matrix4x4.TRS(t.transform.position, Quaternion.identity, Vector3.one);
75 s.area = 0;
76 sources.Add(s);
77 }
78 }
79 }
複制
NavMeshSourceTag類是為了收集需要錄入烘焙清單的模型網格資料和地形資料,用的是一個全局的靜态資料清單來存儲,需要挂載在場景的網格物件上,标記哪些物件的網格在生成資料時需要考慮在内。
複制
1 using UnityEngine;
2 using UnityEngine.AI;
3 using System.Collections;
4 using System.Collections.Generic;
5 using NavMeshBuilder = UnityEngine.AI.NavMeshBuilder;
6
7 // Build and update a localized navmesh from the sources marked by NavMeshSourceTag
8 [DefaultExecutionOrder(-102)]
9 public class LocalNavMeshBuilder : MonoBehaviour
10 {
11 // The center of the build
12 public Transform m_Tracked;
13
14 // The size of the build bounds
15 public Vector3 m_Size = new Vector3(80.0f, 20.0f, 80.0f);
16
17 NavMeshData m_NavMesh;
18 AsyncOperation m_Operation;
19 NavMeshDataInstance m_Instance;
20 List<NavMeshBuildSource> m_Sources = new List<NavMeshBuildSource>();
21
22 IEnumerator Start()
23 {
24 while (true)
25 {
26 UpdateNavMesh(true);
27 yield return m_Operation;
28 }
29 }
30
31 void OnEnable()
32 {
33 Bake();
34 }
35
36 void OnDisable()
37 {
38 //Unload navmesh and clear handle
39 m_Instance.Remove();
40 }
41
42 /// <summary>
43 /// 按範圍動态更新NavMesh
44 /// </summary>
45 /// <param name="asyncUpdate">是否異步加載</param>
46 void UpdateNavMesh(bool asyncUpdate = false)
47 {
48 NavMeshSourceTag.Collect(ref m_Sources);
49 var defaultBuildSettings = NavMesh.GetSettingsByID(0);
50 var bounds = QuantizedBounds();
51
52 if (asyncUpdate)
53 m_Operation = NavMeshBuilder.UpdateNavMeshDataAsync(m_NavMesh, defaultBuildSettings, m_Sources, bounds);
54 else
55 NavMeshBuilder.UpdateNavMeshData(m_NavMesh, defaultBuildSettings, m_Sources, bounds);
56 }
57
58 static Vector3 Quantize(Vector3 v, Vector3 quant)
59 {
60 float x = quant.x * Mathf.Floor(v.x / quant.x);
61 float y = quant.y * Mathf.Floor(v.y / quant.y);
62 float z = quant.z * Mathf.Floor(v.z / quant.z);
63 return new Vector3(x, y, z);
64 }
65
66 Bounds QuantizedBounds()
67 {
68 // Quantize the bounds to update only when theres a 10% change in size
69 var center = m_Tracked ? m_Tracked.position : transform.position;
70 return new Bounds(Quantize(center, 0.1f * m_Size), m_Size);
71 }
72
73 //選擇物體時在Scene中繪制Bound區域
74 void OnDrawGizmosSelected()
75 {
76 if (m_NavMesh)
77 {
78 Gizmos.color = Color.green;
79 Gizmos.DrawWireCube(m_NavMesh.sourceBounds.center, m_NavMesh.sourceBounds.size);
80 }
81
82 Gizmos.color = Color.yellow;
83 var bounds = QuantizedBounds();
84 Gizmos.DrawWireCube(bounds.center, bounds.size);
85
86 Gizmos.color = Color.green;
87 var center = m_Tracked ? m_Tracked.position : transform.position;
88 Gizmos.DrawWireCube(center, m_Size);
89 }
90
91 //動态烘焙NavMesh
92 public void Bake()
93 {
94 // Construct and add navmesh
95 m_NavMesh = new NavMeshData();
96 m_Instance = NavMesh.AddNavMeshData(m_NavMesh);
97 if (m_Tracked == null)
98 m_Tracked = transform;
99 UpdateNavMesh(false);
100 }
101 }
複制
将之前收集到的網格物件的源資料動态重新整理生成NavMesh,用法示例:
1 using UnityEngine;
2
3 public class LocalNavMeshCtrl : MonoBehaviour
4 {
5 public LocalNavMeshBuilder Bulider;
6 public float Offse;
7 void Awake()
8 {
9 EventManager.AddListener<EnterRoomEvent>(EnterRoomHanlder);
10 }
11
12 private void EnterRoomHanlder(EnterRoomEvent e)
13 {
14 if (Bulider != null)
15 {
16 var rooms = BattleUtils.MapMgr.Rooms;
17 if (rooms.ContainsKey(e.RoomIndex) && rooms[e.RoomIndex].RoomType == RoomType.Battle)
18 {
19 Bulider.m_Tracked = rooms[e.RoomIndex].transform;
20 var size = PTBattleMgr.CurRoomCtrl.Size;
21 Bulider.m_Size = new Vector3(size.x * 4 + Offse, 10, size.y * 4 + Offse);
22 }
23 }
24 }
25
26 private void OnDestroy()
27 {
28 EventManager.RemoveListener<EnterRoomEvent>(EnterRoomHanlder);
29 }
30 }
複制
例如進入某一房間或區域就按照該房間區域的大小進行NavMesh的動态烘焙,可以非常友善的改變烘焙的範圍和中心點等,也可以考慮讓該烘焙範圍一直跟随玩家的Transform運動。
一個區域内的NavMesh動态烘焙完成後,很多AI可能需要在NavMesh中取随機點進行導航的目标點的設定或巡邏等,可以寫一個擴充方法得到NavMesh的頂點資料,取任何一個三角内的點即可:
1 public static Vector3 GetNavMeshRandomPos(this GameObject obj)
2 {
3 NavMeshTriangulation navMeshData = NavMesh.CalculateTriangulation();
4
5 int t = Random.Range(0, navMeshData.indices.Length - 3);
6
7 Vector3 point = Vector3.Lerp(navMeshData.vertices[navMeshData.indices[t]], navMeshData.vertices[navMeshData.indices[t + 1]], Random.value);
8 point = Vector3.Lerp(point, navMeshData.vertices[navMeshData.indices[t + 2]], Random.value);
9
10 return point;
11 }
複制