1. 項(xiàng)目概述與核心價(jià)值最近在重構(gòu)一個(gè)2D小游戲的NPC移動(dòng)邏輯發(fā)現(xiàn)之前用的簡(jiǎn)單隨機(jī)游走或者直線追蹤在遇到稍微復(fù)雜點(diǎn)的地圖比如有樹(shù)林、河流、墻壁這些障礙物時(shí)表現(xiàn)就特別“蠢”。角色要么卡在墻角不停抽搐要么對(duì)著一條河直沖過(guò)去然后掉頭毫無(wú)智能可言。這讓我下定決心要把經(jīng)典的A星A*尋路算法給集成進(jìn)去。A星算法在游戲開(kāi)發(fā)里可以說(shuō)是智能尋路的基石從早期的《星際爭(zhēng)霸》、《魔獸爭(zhēng)霸3》到現(xiàn)在的各種開(kāi)放世界RPG和MOBA游戲背后都有它的身影。它解決的問(wèn)題非常明確在一個(gè)由格子或者更復(fù)雜的導(dǎo)航網(wǎng)格構(gòu)成的地圖上為游戲角色找到一條從起點(diǎn)到終點(diǎn)的、避開(kāi)所有障礙物的、同時(shí)又是最短或接近最短的路徑。你可能聽(tīng)說(shuō)過(guò)Dijkstra算法或者廣度優(yōu)先搜索BFS它們也能找最短路徑但效率在游戲這種實(shí)時(shí)性要求極高的場(chǎng)景下往往不夠看。A星算法的聰明之處在于它引入了一個(gè)“啟發(fā)式”的預(yù)估成本讓搜索過(guò)程變得有方向性像是一個(gè)有經(jīng)驗(yàn)的向?qū)Ф皇菬o(wú)頭蒼蠅一樣亂撞。這次我就用C#從最基礎(chǔ)的概念開(kāi)始手把手實(shí)現(xiàn)一個(gè)干凈、高效、可復(fù)用的A星尋路模塊。無(wú)論你是想給自己的獨(dú)立游戲增加點(diǎn)智能NPC還是單純對(duì)算法如何在游戲中落地感到好奇跟著走一遍你都能獲得一個(gè)可以直接拿來(lái)用的解決方案并且徹底理解其背后的每一個(gè)決策。2. A星算法核心原理深度拆解要?jiǎng)邮謱?shí)現(xiàn)必須先吃透原理。A星算法之所以強(qiáng)大是因?yàn)樗擅畹亟Y(jié)合了“已知成本”和“預(yù)估成本”。2.1 算法核心三要素G、H、F值我們可以把尋路過(guò)程想象成在一個(gè)陌生的城市里找一家特定的餐廳。你手里有一張不完整的地圖已知部分道路還有一個(gè)手機(jī)導(dǎo)航APP它知道所有道路但你需要付費(fèi)解鎖完整信息。A星算法就是你大腦里的那個(gè)“混合導(dǎo)航系統(tǒng)”。G值實(shí)際代價(jià) 這代表從起點(diǎn)走到當(dāng)前格子已經(jīng)花費(fèi)的“真實(shí)成本”。通常就是走過(guò)的步數(shù)如果地形有差異比如草地走得慢公路走得快也可以把移動(dòng)速度折算進(jìn)去。在我們的基礎(chǔ)實(shí)現(xiàn)里可以簡(jiǎn)單認(rèn)為從一個(gè)格子走到其上下左右相鄰的格子G值增加1走到斜角相鄰的格子G值增加約1.414即√2以模擬更長(zhǎng)的對(duì)角線距離。G值記錄的是確鑿無(wú)疑的、已經(jīng)發(fā)生的代價(jià)。H值啟發(fā)代價(jià)/預(yù)估代價(jià) 這是從當(dāng)前格子到終點(diǎn)的“直線距離”估算成本。注意這是“估算”因?yàn)橹虚g可能有墻你不能真的穿過(guò)去。最常用的估算方法是曼哈頓距離適用于只能上下左右移動(dòng)的四方向?qū)ぢ泛蜌W幾里得距離適用于可以八方向移動(dòng)的尋路。H值就像那個(gè)導(dǎo)航APP給你的“直線距離剩余”提示它引導(dǎo)你朝著終點(diǎn)的大致方向前進(jìn)避免搜索跑偏。F值總代價(jià) 這是A星做決策的核心依據(jù)。F G H。算法在每一步都會(huì)優(yōu)先選擇F值最小的格子作為下一個(gè)探索目標(biāo)。這很好理解既要考慮已經(jīng)走了多遠(yuǎn)G不能太大也要考慮離目標(biāo)還有多遠(yuǎn)H不能太大兩者加起來(lái)最小的就是當(dāng)前看來(lái)“性價(jià)比”最高的下一步。注意 H值啟發(fā)函數(shù)的選擇至關(guān)重要它必須滿足“可采納性”即永遠(yuǎn)不能高估到達(dá)終點(diǎn)的實(shí)際成本。如果H值高估了算法可能找不到最短路徑但如果H值嚴(yán)重低估比如恒為0A星就退化成了Dijkstra算法效率降低。曼哈頓距離和歐幾里得距離都是可采納的。2.2 算法運(yùn)行流程與兩大列表算法維護(hù)兩個(gè)關(guān)鍵列表來(lái)管理搜索過(guò)程開(kāi)放列表Open List 一個(gè)待檢查的格子“候選隊(duì)列”。它通常被實(shí)現(xiàn)為一個(gè)優(yōu)先隊(duì)列Priority Queue以確保每次都能快速取出F值最小的格子。一開(kāi)始只有起點(diǎn)在開(kāi)放列表中。關(guān)閉列表Closed List 一個(gè)已經(jīng)檢查過(guò)、無(wú)需再考慮的格子集合。通常用HashSet或布爾數(shù)組標(biāo)記查找效率高。已經(jīng)處理過(guò)的格子會(huì)被移入關(guān)閉列表防止算法在原地打轉(zhuǎn)或陷入循環(huán)。算法的主循環(huán)步驟如下這個(gè)過(guò)程直到找到終點(diǎn)或開(kāi)放列表為空意味著無(wú)路可走才會(huì)結(jié)束從開(kāi)放列表中取出F值最小的格子我們稱它為“當(dāng)前格”。將“當(dāng)前格”移入關(guān)閉列表。檢查“當(dāng)前格”的所有鄰居格通常是上下左右或加上四個(gè)斜角共八個(gè)方向。對(duì)每一個(gè)鄰居格如果它是障礙物或者在關(guān)閉列表中則忽略它。如果它不在開(kāi)放列表中就把它加入并設(shè)置它的“父節(jié)點(diǎn)”為當(dāng)前格同時(shí)計(jì)算它的G、H、F值。如果它已經(jīng)在開(kāi)放列表中檢查通過(guò)當(dāng)前格到達(dá)它是否是一條更優(yōu)的路徑即新的G值是否比它原有的G值更小。如果是則更新這個(gè)鄰居格的G值、F值并將其“父節(jié)點(diǎn)”改為當(dāng)前格。如果終點(diǎn)被加入了開(kāi)放列表則路徑找到循環(huán)結(jié)束。如果開(kāi)放列表空了還沒(méi)找到終點(diǎn)則路徑不存在。路徑回溯很簡(jiǎn)單從終點(diǎn)開(kāi)始根據(jù)每個(gè)格子的“父節(jié)點(diǎn)”指針一路向前追溯到起點(diǎn)這個(gè)反向序列就是找到的最短路徑最后反轉(zhuǎn)一下即可。3. C#實(shí)現(xiàn)從數(shù)據(jù)結(jié)構(gòu)到完整類設(shè)計(jì)理解了原理我們用C#來(lái)把它具體化。一個(gè)好的實(shí)現(xiàn)應(yīng)該職責(zé)清晰便于集成到游戲引擎如Unity或任何C#項(xiàng)目中。3.1 定義核心數(shù)據(jù)結(jié)構(gòu)PathNode首先我們需要一個(gè)類來(lái)代表地圖上的每一個(gè)格子節(jié)點(diǎn)。public class PathNode { // 節(jié)點(diǎn)在地圖網(wǎng)格中的坐標(biāo) public int X { get; } public int Y { get; } // 尋路核心三要素 public float G { get; set; } // 從起點(diǎn)到本節(jié)點(diǎn)的實(shí)際代價(jià) public float H { get; set; } // 從本節(jié)點(diǎn)到終點(diǎn)的預(yù)估代價(jià) public float F G H; // 總代價(jià)使用屬性簡(jiǎn)化 // 是否為障礙物 public bool IsWalkable { get; set; } true; // 父節(jié)點(diǎn)用于最終路徑回溯 public PathNode Parent { get; set; } // 構(gòu)造函數(shù) public PathNode(int x, int y) { X x; Y y; } // 重寫(xiě)Equals和GetHashCode便于在集合中使用 public override bool Equals(object obj) obj is PathNode other X other.X Y other.Y; public override int GetHashCode() HashCode.Combine(X, Y); }這里有幾個(gè)設(shè)計(jì)點(diǎn)F屬性被設(shè)計(jì)為只讀由G和H計(jì)算得出保證了數(shù)據(jù)一致性。Equals和GetHashCode的重寫(xiě)至關(guān)重要因?yàn)楹竺嫖覀儠?huì)將PathNode放入HashSet關(guān)閉列表和作為字典的鍵正確的哈希和相等性判斷能極大提升性能。IsWalkable屬性允許我們動(dòng)態(tài)改變地圖的通行狀態(tài)。3.2 實(shí)現(xiàn)A星尋路核心類AStarPathfinder這是算法的主類。我們將采用面向?qū)ο蟮姆绞绞蛊淇梢耘渲貌煌膯l(fā)函數(shù)和移動(dòng)方式。using System.Collections.Generic; public class AStarPathfinder { // 地圖網(wǎng)格假設(shè)我們已經(jīng)有一個(gè)二維的PathNode數(shù)組 private PathNode[,] _grid; private int _gridWidth _grid.GetLength(0); private int _gridHeight _grid.GetLength(1); // 定義移動(dòng)方向四方向或八方向 private readonly (int dx, int dy)[] _directions; public AStarPathfinder(PathNode[,] grid, bool allowDiagonal true) { _grid grid; // 根據(jù)參數(shù)初始化移動(dòng)方向 if (allowDiagonal) { // 八方向上、下、左、右、左上、右上、左下、右下 _directions new (int, int)[] { (0, 1), (0, -1), (-1, 0), (1, 0), (-1, 1), (1, 1), (-1, -1), (1, -1) }; } else { // 四方向上、下、左、右 _directions new (int, int)[] { (0, 1), (0, -1), (-1, 0), (1, 0) }; } } // 核心尋路方法 public ListPathNode FindPath(int startX, int startY, int endX, int endY) { // 邊界和有效性檢查 if (!IsWithinGrid(startX, startY) || !IsWithinGrid(endX, endY)) return null; var startNode _grid[startX, startY]; var endNode _grid[endX, endY]; if (!startNode.IsWalkable || !endNode.IsWalkable) return null; // 起點(diǎn)或終點(diǎn)不可通行 // 初始化開(kāi)放列表使用優(yōu)先隊(duì)列和關(guān)閉列表 var openSet new PriorityQueuePathNode, float(); var closedSet new HashSetPathNode(); // 重置起點(diǎn)代價(jià) startNode.G 0; startNode.H CalculateHeuristic(startNode, endNode); openSet.Enqueue(startNode, startNode.F); while (openSet.Count 0) { // 取出當(dāng)前F值最小的節(jié)點(diǎn) var currentNode openSet.Dequeue(); // 如果到達(dá)終點(diǎn)回溯路徑 if (currentNode.Equals(endNode)) { return RetracePath(startNode, endNode); } closedSet.Add(currentNode); // 遍歷鄰居 foreach (var direction in _directions) { int neighborX currentNode.X direction.dx; int neighborY currentNode.Y direction.dy; if (!IsWithinGrid(neighborX, neighborY)) continue; var neighborNode _grid[neighborX, neighborY]; // 檢查鄰居是否不可通行或已在關(guān)閉列表 if (!neighborNode.IsWalkable || closedSet.Contains(neighborNode)) continue; // 計(jì)算從當(dāng)前節(jié)點(diǎn)到鄰居節(jié)點(diǎn)的移動(dòng)代價(jià) // 基礎(chǔ)代價(jià)為1對(duì)角線代價(jià)約為1.414 float moveCost (direction.dx ! 0 direction.dy ! 0) ? 1.414f : 1.0f; float newGCost currentNode.G moveCost; // 如果鄰居不在開(kāi)放列表中或者找到更優(yōu)路徑 if (newGCost neighborNode.G || !openSet.UnorderedItems.Any(item item.Element.Equals(neighborNode))) { // 更新鄰居節(jié)點(diǎn)的代價(jià)和父節(jié)點(diǎn) neighborNode.G newGCost; neighborNode.H CalculateHeuristic(neighborNode, endNode); neighborNode.Parent currentNode; // 如果鄰居是新的加入開(kāi)放列表如果已存在需要更新其在優(yōu)先隊(duì)列中的優(yōu)先級(jí)。 // 注意.NET 6的PriorityQueue沒(méi)有直接的更新優(yōu)先級(jí)方法這里簡(jiǎn)化處理先刪除再插入或使用更復(fù)雜的結(jié)構(gòu)。 // 為了簡(jiǎn)單演示我們這里選擇直接重新入隊(duì)對(duì)于小規(guī)模網(wǎng)格可以接受但存在重復(fù)節(jié)點(diǎn)。 // 生產(chǎn)環(huán)境應(yīng)考慮使用支持更新優(yōu)先級(jí)的優(yōu)先隊(duì)列實(shí)現(xiàn)。 openSet.Enqueue(neighborNode, neighborNode.F); } } } // 開(kāi)放列表為空未找到路徑 return null; } // 回溯構(gòu)建路徑 private ListPathNode RetracePath(PathNode startNode, PathNode endNode) { ListPathNode path new ListPathNode(); PathNode currentNode endNode; while (!currentNode.Equals(startNode)) { path.Add(currentNode); currentNode currentNode.Parent; } path.Reverse(); // 反轉(zhuǎn)得到從起點(diǎn)到終點(diǎn)的順序 return path; } // 啟發(fā)函數(shù)計(jì)算這里使用歐幾里得距離適用于八方向 private float CalculateHeuristic(PathNode a, PathNode b) { int dx Math.Abs(a.X - b.X); int dy Math.Abs(a.Y - b.Y); // 歐幾里得距離 return (float)Math.Sqrt(dx * dx dy * dy); // 曼哈頓距離適用于四方向 return dx dy; // 切比雪夫距離適用于八方向且對(duì)角線代價(jià)為1 return Math.Max(dx, dy); } // 輔助方法檢查坐標(biāo)是否在地圖內(nèi) private bool IsWithinGrid(int x, int y) { return x 0 x _gridWidth y 0 y _gridHeight; } }代碼關(guān)鍵點(diǎn)與避坑指南優(yōu)先隊(duì)列的選擇 .NET 6 引入了PriorityQueueTElement, TPriority我們直接使用它作為開(kāi)放列表。它的Enqueue和Dequeue操作是O(log n)的效率很高。但請(qǐng)注意它沒(méi)有內(nèi)置的“更新優(yōu)先級(jí)”方法。在上面的代碼中當(dāng)發(fā)現(xiàn)一條通往已有開(kāi)放節(jié)點(diǎn)更優(yōu)的路徑時(shí)我們選擇了直接重新入隊(duì)。這會(huì)導(dǎo)致開(kāi)放列表中存在同一個(gè)節(jié)點(diǎn)的多個(gè)副本但最終Dequeue出來(lái)的是優(yōu)先級(jí)最高F值最小的那個(gè)不影響正確性只是略微增加內(nèi)存和計(jì)算開(kāi)銷。對(duì)于性能要求極高的游戲你需要自己實(shí)現(xiàn)一個(gè)支持DecreaseKey操作的優(yōu)先隊(duì)列例如基于斐波那契堆。關(guān)閉列表使用HashSetHashSetPathNode的Contains操作平均是O(1)比用List快得多這是性能關(guān)鍵。啟發(fā)函數(shù)的選擇 代碼中使用了歐幾里得距離它對(duì)于八方向移動(dòng)是“可采納”且相對(duì)準(zhǔn)確的。如果你限制為四方向移動(dòng)應(yīng)切換為曼哈頓距離這樣更高效且不會(huì)高估。對(duì)角線移動(dòng)代價(jià) 我們給對(duì)角線移動(dòng)設(shè)置了1.414的代價(jià)這比上下左右的1要大符合幾何事實(shí)。這能防止尋路結(jié)果出現(xiàn)“鋸齒狀”路徑而更傾向于先走直線。路徑回溯 從終點(diǎn)通過(guò)Parent指針?lè)聪蜃匪莸狡瘘c(diǎn)再反轉(zhuǎn)列表這是標(biāo)準(zhǔn)操作。3.3 集成到游戲循環(huán)一個(gè)簡(jiǎn)單的Unity示例假設(shè)你在Unity中使用你需要將世界坐標(biāo)轉(zhuǎn)換為網(wǎng)格坐標(biāo)并在每幀或需要時(shí)為角色計(jì)算路徑。// 掛在游戲管理器或某個(gè)控制器上 public class GamePathfindingSystem : MonoBehaviour { public int gridWidth 50; public int gridHeight 50; public float cellSize 1.0f; private PathNode[,] _grid; private AStarPathfinder _pathfinder; void Start() { InitializeGrid(); _pathfinder new AStarPathfinder(_grid, true); // 允許對(duì)角線移動(dòng) } void InitializeGrid() { _grid new PathNode[gridWidth, gridHeight]; for (int x 0; x gridWidth; x) { for (int y 0; y gridHeight; y) { _grid[x, y] new PathNode(x, y); // 這里可以根據(jù)你的游戲地圖信息如碰撞體來(lái)設(shè)置IsWalkable // 例如通過(guò)Physics2D.OverlapBox檢查該位置是否有障礙物 Vector2 worldPos GridToWorld(x, y); Collider2D hit Physics2D.OverlapBox(worldPos, Vector2.one * cellSize * 0.9f, 0, obstacleLayerMask); _grid[x, y].IsWalkable (hit null); } } } // 為某個(gè)角色請(qǐng)求路徑 public ListVector2 RequestPath(Vector2 startWorldPos, Vector2 targetWorldPos) { var startNode WorldToGrid(startWorldPos); var endNode WorldToGrid(targetWorldPos); var nodePath _pathfinder.FindPath(startNode.x, startNode.y, endNode.x, endNode.y); if (nodePath null) return null; // 將節(jié)點(diǎn)路徑轉(zhuǎn)換回世界坐標(biāo)路徑 ListVector2 worldPath new ListVector2(); foreach (var node in nodePath) { worldPath.Add(GridToWorld(node.X, node.Y)); } return worldPath; } private Vector2 GridToWorld(int x, int y) new Vector2(x * cellSize, y * cellSize); private (int x, int y) WorldToGrid(Vector2 worldPos) (Mathf.FloorToInt(worldPos.x / cellSize), Mathf.FloorToInt(worldPos.y / cellSize)); }在角色控制器中你可以這樣使用public class NPCMovement : MonoBehaviour { public GamePathfindingSystem pathfindingSystem; public float speed 3.0f; private ListVector2 _currentPath; private int _currentPathIndex; public void SetDestination(Vector2 targetPosition) { _currentPath pathfindingSystem.RequestPath(transform.position, targetPosition); _currentPathIndex 0; } void Update() { if (_currentPath ! null _currentPathIndex _currentPath.Count) { Vector2 target _currentPath[_currentPathIndex]; transform.position Vector2.MoveTowards(transform.position, target, speed * Time.deltaTime); if (Vector2.Distance(transform.position, target) 0.05f) { _currentPathIndex; // 如果到達(dá)路徑終點(diǎn) if (_currentPathIndex _currentPath.Count) { _currentPath null; // 到達(dá)目的地可以觸發(fā)后續(xù)行為 } } } } }4. 性能優(yōu)化與高級(jí)技巧基礎(chǔ)的A星跑起來(lái)后面對(duì)大地圖或大量單位同時(shí)尋路性能可能成為瓶頸。下面是一些實(shí)戰(zhàn)中非常有效的優(yōu)化手段。4.1 使用更高效的數(shù)據(jù)結(jié)構(gòu)我們之前提到了優(yōu)先隊(duì)列更新優(yōu)先級(jí)的問(wèn)題。一個(gè)成熟的方案是使用二叉堆Binary Heap并配合一個(gè)字典來(lái)跟蹤每個(gè)節(jié)點(diǎn)在堆中的索引從而實(shí)現(xiàn)高效的DecreaseKey操作。網(wǎng)上有很多C#的開(kāi)源實(shí)現(xiàn)比如OptimizedPriorityQueue。替換后當(dāng)需要更新一個(gè)已在開(kāi)放列表中的節(jié)點(diǎn)的F值時(shí)你可以直接更新它的G值并調(diào)用DecreaseKey方法而不是重復(fù)入隊(duì)這能顯著減少開(kāi)放列表的大小和操作次數(shù)。4.2 分層尋路與路點(diǎn)圖對(duì)于超大型地圖如開(kāi)放世界對(duì)整個(gè)網(wǎng)格進(jìn)行A星搜索是不現(xiàn)實(shí)的。這時(shí)需要分層尋路。高層尋路 將地圖劃分為大的區(qū)域房間、街區(qū)先用A星在這些大區(qū)域之間找一條粗略路徑。底層尋路 在角色當(dāng)前所在區(qū)域和下一個(gè)目標(biāo)區(qū)域之間使用網(wǎng)格A星進(jìn)行精細(xì)尋路。 另一種方法是使用導(dǎo)航網(wǎng)格NavMesh或預(yù)計(jì)算的路點(diǎn)圖Waypoint Graph。你不再使用均勻網(wǎng)格而是將地圖抽象成由凸多邊形NavMesh或關(guān)鍵位置點(diǎn)Waypoint及其連接關(guān)系構(gòu)成的圖。A星算法可以同樣應(yīng)用在這個(gè)圖上搜索的節(jié)點(diǎn)數(shù)大大減少效率飛躍提升。Unity內(nèi)置的NavMesh系統(tǒng)就是基于這個(gè)原理。4.3 方向搜索與跳點(diǎn)搜索這是對(duì)標(biāo)準(zhǔn)A星搜索鄰居過(guò)程的優(yōu)化。方向搜索 在遍歷鄰居時(shí)如果不是起點(diǎn)可以先判斷父節(jié)點(diǎn)的方向。如果當(dāng)前移動(dòng)方向是直線可以優(yōu)先考慮繼續(xù)沿該方向搜索因?yàn)橹本€路徑通常更優(yōu)。這可以減少不必要的拐彎評(píng)估。跳點(diǎn)搜索JPS 這是A星在均勻網(wǎng)格上的一個(gè)革命性優(yōu)化。它的核心思想是“跳過(guò)”那些沒(méi)有決策意義的格子。例如在一條空曠的直線上算法不會(huì)一步步檢查每個(gè)格子而是直接“跳”到這條直線的盡頭遇到障礙物或地圖邊緣或者一個(gè)“拐點(diǎn)”。JPS在開(kāi)闊地帶能將性能提升一個(gè)數(shù)量級(jí)但在障礙物極其密集如迷宮的地形中優(yōu)勢(shì)不明顯。實(shí)現(xiàn)JPS比標(biāo)準(zhǔn)A星復(fù)雜需要識(shí)別“強(qiáng)迫鄰居”和“跳點(diǎn)”。4.4 路徑平滑與移動(dòng)優(yōu)化A星基于網(wǎng)格尋出的路徑往往是“網(wǎng)格對(duì)齊”的會(huì)有一格一格的直角拐點(diǎn)看起來(lái)不自然。路徑平滑 找到路徑后可以進(jìn)行一次后處理。常用的是漏斗算法。你可以把路徑節(jié)點(diǎn)看作一系列多邊形的頂點(diǎn)然后嘗試“拉緊”這條路徑讓角色走更直接的通道消除不必要的鋸齒。一個(gè)簡(jiǎn)單的實(shí)現(xiàn)是遍歷路徑從起點(diǎn)開(kāi)始檢查能否“看到”后面的某個(gè)點(diǎn)即兩點(diǎn)連線不穿過(guò)障礙物如果能就跳過(guò)中間的點(diǎn)。移動(dòng)優(yōu)化 在角色移動(dòng)時(shí)不要僵硬地逐格走向路徑點(diǎn)?？梢允褂棉D(zhuǎn)向行為Steering Behaviors如“尋求Seek”結(jié)合“避開(kāi)障礙Obstacle Avoidance”讓移動(dòng)更平滑、更智能。這樣即使路徑略有偏差角色也能自然地繞開(kāi)動(dòng)態(tài)的小障礙。5. 常見(jiàn)問(wèn)題、調(diào)試與實(shí)戰(zhàn)心得在實(shí)際集成A星的過(guò)程中你肯定會(huì)遇到一些“坑”。下面是我踩過(guò)的一些以及解決方法。5.1 路徑為什么看起來(lái)“很蠢”現(xiàn)象 路徑繞遠(yuǎn)路或者貼著障礙物走很不自然的折線。排查檢查啟發(fā)函數(shù)H 如果你用了八方向移動(dòng)但啟發(fā)函數(shù)用的是曼哈頓距離它會(huì)嚴(yán)重高估對(duì)角線方向的成本導(dǎo)致算法“不敢”走對(duì)角線從而走出階梯狀的路徑。確保移動(dòng)方式與啟發(fā)函數(shù)匹配。檢查移動(dòng)代價(jià) 對(duì)角線移動(dòng)代價(jià)是否設(shè)置正確如果也設(shè)為1那么算法會(huì)認(rèn)為走斜線和走直線一樣“便宜”可能導(dǎo)致路徑在某些情況下不夠直。使用1.414是更合理的。檢查地圖數(shù)據(jù) 用調(diào)試?yán)L圖把IsWalkable為false的格子畫(huà)出來(lái)看看你的障礙物地圖是否和場(chǎng)景中的碰撞體精確對(duì)應(yīng)。有時(shí)候碰撞體比視覺(jué)模型大一點(diǎn)會(huì)導(dǎo)致可行走區(qū)域比預(yù)期小。路徑平滑 如上所述原始網(wǎng)格路徑就是這樣的?？紤]增加路徑平滑后處理。5.2 性能突然變差卡頓明顯現(xiàn)象 平時(shí)很流暢角色走到某個(gè)復(fù)雜區(qū)域或同時(shí)多個(gè)單位尋路時(shí)幀率下降。排查與優(yōu)化Profiler是朋友 使用Unity Profiler或.NET的性能分析工具鎖定是CPU的哪一部分耗時(shí)最多。通常是FindPath里的循環(huán)。限制尋路頻率 不要每幀都為每個(gè)AI尋路?？梢悦縉秒如0.5秒尋路一次或者當(dāng)目標(biāo)移動(dòng)超過(guò)一定距離后再重新尋路。使用協(xié)程分幀計(jì)算 如果單次尋路計(jì)算量很大可以把FindPath放入?yún)f(xié)程每幀只計(jì)算一部分比如處理開(kāi)放列表中的100個(gè)節(jié)點(diǎn)避免單幀卡頓。地圖粒度 你的網(wǎng)格是不是太細(xì)了將cellSize從0.5調(diào)到1.0網(wǎng)格節(jié)點(diǎn)數(shù)會(huì)變?yōu)樵瓉?lái)的1/4尋路速度能快很多。需要在精度和性能間權(quán)衡?？紤]分層或預(yù)計(jì)算 對(duì)于靜態(tài)地圖是否可以預(yù)計(jì)算一些關(guān)鍵點(diǎn)之間的路徑5.3 動(dòng)態(tài)障礙物處理我們的基礎(chǔ)實(shí)現(xiàn)中IsWalkable是在初始化時(shí)設(shè)置的。如果游戲中有可移動(dòng)的障礙物比如其他NPC、可推箱子需要?jiǎng)討B(tài)更新。方案 為AStarPathfinder或PathNode提供一個(gè)更新方法。當(dāng)動(dòng)態(tài)障礙物移動(dòng)時(shí)更新它影響的所有格子的IsWalkable狀態(tài)。更高效的做法是在尋路時(shí)進(jìn)行實(shí)時(shí)碰撞檢測(cè)但這會(huì)增加每次評(píng)估鄰居時(shí)的開(kāi)銷。一個(gè)折中方案是使用局部避障A星負(fù)責(zé)規(guī)劃全局靜態(tài)路徑當(dāng)角色接近動(dòng)態(tài)障礙物時(shí)用簡(jiǎn)單的物理轉(zhuǎn)向或局部重新規(guī)劃來(lái)避開(kāi)。5.4 調(diào)試可視化在開(kāi)發(fā)階段將算法過(guò)程可視化是理解問(wèn)題和調(diào)試的終極武器。繪制網(wǎng)格 在Unity的OnDrawGizmos中用不同顏色繪制所有格子可行走/不可行走。繪制開(kāi)放/關(guān)閉列表 在尋路過(guò)程中將開(kāi)放列表中的格子用黃色半透明方塊繪制關(guān)閉列表中的用紅色半透明繪制。你可以清晰地看到算法的“探索前沿”。繪制最終路徑 用綠色線條或方塊連接路徑上的所有點(diǎn)。繪制G/H/F值 在屏幕上每個(gè)格子旁顯示其G、H、F值這對(duì)于深入理解算法決策過(guò)程非常有幫助。實(shí)現(xiàn)A星尋路從理解原理到寫(xiě)出可工作的代碼再到優(yōu)化和集成是一個(gè)典型的“學(xué)以致用”的過(guò)程。它不僅僅是一個(gè)算法更是一套解決空間搜索問(wèn)題的思維方式。當(dāng)你看到自己控制的角色或NPC在復(fù)雜的地圖中流暢、智能地穿梭時(shí)那種成就感是實(shí)實(shí)在在的。希望這篇從原理到實(shí)戰(zhàn)的詳細(xì)拆解能幫你少走彎路順利地把這個(gè)強(qiáng)大的工具應(yīng)用到你的C#游戲項(xiàng)目中去。記住第一步是先讓基礎(chǔ)版本跑起來(lái)畫(huà)出路徑然后再逐步考慮優(yōu)化和擴(kuò)展。動(dòng)手試試吧