戰(zhàn)：從A*算法到性能優(yōu)化與動(dòng)態(tài)障礙處理)
1. 項(xiàng)目概述當(dāng)Laya游戲需要“聰明”的NPC在LayaAir引擎開發(fā)2D或3D游戲時(shí)尤其是RPG、SLG、塔防這類需要角色自主移動(dòng)的游戲一個(gè)繞不開的核心需求就是如何讓游戲里的NPC、怪物或者單位能夠智能地找到從A點(diǎn)到B點(diǎn)的路徑并且能優(yōu)雅地繞開障礙物這就是我們常說的“尋路”Pathfinding。你可能嘗試過用簡(jiǎn)單的直線移動(dòng)但一堵墻、一棵樹就能讓角色卡住顯得非?！吧怠?。你也可能手動(dòng)預(yù)設(shè)好固定路線但一旦場(chǎng)景動(dòng)態(tài)變化比如玩家建造了一堵墻預(yù)設(shè)路線就失效了。這時(shí)一個(gè)可靠、高效的AI尋路系統(tǒng)就成了項(xiàng)目從“玩具Demo”邁向“可玩產(chǎn)品”的關(guān)鍵一步。LayaAir本身是一個(gè)優(yōu)秀的渲染與框架引擎但在復(fù)雜的AI尋路領(lǐng)域它并沒有內(nèi)置一個(gè)開箱即用的、功能完善的解決方案。官方提供的laya.ai包中的尋路模塊相對(duì)基礎(chǔ)面對(duì)復(fù)雜地形、動(dòng)態(tài)障礙、多單位尋路等實(shí)際開發(fā)中的高頻需求往往需要開發(fā)者投入大量精力進(jìn)行二次開發(fā)和優(yōu)化。因此尋找并集成一套成熟的第三方尋路方案或者基于成熟算法自建一套幾乎是中大型Laya游戲的必經(jīng)之路。這個(gè)“Laya游戲開發(fā)中AI尋路解決方案”要解決的就是在Laya生態(tài)下如何為游戲角色賦予“認(rèn)路”的智慧。它不僅僅是調(diào)用一個(gè)findPath()函數(shù)更涉及到網(wǎng)格劃分、算法選型、性能優(yōu)化、動(dòng)態(tài)障礙處理、與Laya渲染循環(huán)的整合、不同游戲類型如2D俯視角、3D第三人稱的適配等一系列環(huán)環(huán)相扣的問題。接下來我將結(jié)合多年項(xiàng)目實(shí)戰(zhàn)經(jīng)驗(yàn)為你拆解構(gòu)建這套方案的核心思路、技術(shù)細(xì)節(jié)與避坑指南。2. 尋路方案核心選型網(wǎng)格、算法與數(shù)據(jù)結(jié)構(gòu)在動(dòng)手寫代碼之前選對(duì)底層方案決定了后續(xù)開發(fā)的效率和最終效果的上限。尋路方案的核心三要素是世界表示法用什么描述可行走區(qū)域、尋路算法用什么計(jì)算路徑、數(shù)據(jù)結(jié)構(gòu)如何高效存儲(chǔ)和查詢。2.1 世界表示法網(wǎng)格Grid vs 導(dǎo)航網(wǎng)格NavMesh vs 點(diǎn)陣Waypoint對(duì)于Laya游戲尤其是2D游戲或俯視角3D游戲網(wǎng)格Grid是最常見、最易上手的選擇。它將游戲世界劃分為均勻的二維方格在3D中可能是體素每個(gè)格子標(biāo)記為“可行走”或“不可行走”。其優(yōu)勢(shì)在于實(shí)現(xiàn)簡(jiǎn)單、概念直觀、動(dòng)態(tài)更新障礙物非常方便只需修改格子狀態(tài)。Laya官方laya.ai.PathFinder默認(rèn)就支持網(wǎng)格尋路。缺點(diǎn)是路徑不夠平滑鋸齒狀且內(nèi)存占用與網(wǎng)格分辨率成正比大世界高精度網(wǎng)格開銷大。導(dǎo)航網(wǎng)格NavMesh在3D游戲中更為強(qiáng)大。它用一系列凸多邊形來覆蓋所有可行走區(qū)域角色可以在多邊形內(nèi)部任意點(diǎn)自由移動(dòng)路徑天生平滑且更符合真實(shí)地形。Unity的NavMesh系統(tǒng)就是典型代表。在Laya中實(shí)現(xiàn)完整的NavMesh需要較復(fù)雜的幾何計(jì)算和第三方庫(kù)支持如recast-detour的JavaScript端口復(fù)雜度高但效果最好適合復(fù)雜的3D場(chǎng)景。點(diǎn)陣Waypoint則是在場(chǎng)景中手動(dòng)或自動(dòng)放置一系列路徑點(diǎn)角色只能在點(diǎn)與點(diǎn)之間移動(dòng)。它非常輕量適合固定路線明顯的游戲如賽車、平臺(tái)跳躍但靈活度最低無法處理動(dòng)態(tài)障礙。實(shí)操心得對(duì)于大多數(shù)Laya項(xiàng)目尤其是剛接觸尋路的團(tuán)隊(duì)從基于網(wǎng)格的A*算法開始是最穩(wěn)妥的。它足夠解決80%的問題社區(qū)資源豐富調(diào)試可視化也容易。我們可以先用較粗的網(wǎng)格保證性能后期再考慮結(jié)合導(dǎo)航網(wǎng)格或分層尋路HPA*進(jìn)行優(yōu)化。2.2 尋路算法為什么A*是絕對(duì)主力談到網(wǎng)格尋路就離不開A*A-Star算法。它之所以是業(yè)界標(biāo)準(zhǔn)是因?yàn)樗凇懊つ俊钡腄ijkstra算法和“激進(jìn)”的貪心最佳優(yōu)先搜索Greedy Best-First-Search之間取得了完美平衡。簡(jiǎn)單來說A*為每個(gè)待評(píng)估的網(wǎng)格節(jié)點(diǎn)計(jì)算一個(gè)代價(jià)函數(shù)F G H。G值從起點(diǎn)移動(dòng)到當(dāng)前節(jié)點(diǎn)的實(shí)際代價(jià)。H值啟發(fā)式估計(jì)從當(dāng)前節(jié)點(diǎn)到終點(diǎn)的預(yù)估代價(jià)常用曼哈頓距離適用于4方向移動(dòng)或歐幾里得距離適用于8方向或任意方向。F值總預(yù)估代價(jià)。算法總是優(yōu)先探索F值最小的節(jié)點(diǎn)從而高效地找到最短路徑。// 一個(gè)非常簡(jiǎn)化的A*節(jié)點(diǎn)類結(jié)構(gòu)示意 class AStarNode { constructor(x, y) { this.x x; // 網(wǎng)格X坐標(biāo) this.y y; // 網(wǎng)格Y坐標(biāo) this.g 0; // 起點(diǎn)到本節(jié)點(diǎn)的實(shí)際代價(jià) this.h 0; // 本節(jié)點(diǎn)到終點(diǎn)的預(yù)估代價(jià) this.f 0; // g h this.parent null; // 父節(jié)點(diǎn)用于回溯路徑 this.walkable true; // 是否可行走 } }相較于廣度優(yōu)先搜索BFSA通過啟發(fā)函數(shù)H大幅減少了需要搜索的節(jié)點(diǎn)數(shù)量速度更快。相較于深度優(yōu)先搜索DFSA能保證找到最優(yōu)解如果啟發(fā)函數(shù)H是可采納的即從不高估實(shí)際代價(jià)。注意事項(xiàng)啟發(fā)函數(shù)H的選擇直接影響效率和路徑“自然度”。在允許斜向移動(dòng)的8方向網(wǎng)格中使用對(duì)角線距離Chebyshev距離或Octile距離會(huì)比簡(jiǎn)單的歐幾里得距離更準(zhǔn)確計(jì)算也更快。同時(shí)確保H永遠(yuǎn)不大于實(shí)際剩余代價(jià)否則A*可能找不到最優(yōu)解。2.3 數(shù)據(jù)結(jié)構(gòu)優(yōu)化開放列表OpenList的性能關(guān)鍵A*算法需要頻繁地從“開放列表”待考察節(jié)點(diǎn)集合中取出F值最小的節(jié)點(diǎn)。如果使用普通的數(shù)組每次查找都需要遍歷性能是O(n)在大型網(wǎng)格上將是災(zāi)難。因此優(yōu)先隊(duì)列Priority Queue特別是二叉堆Binary Heap是實(shí)現(xiàn)開放列表的標(biāo)準(zhǔn)數(shù)據(jù)結(jié)構(gòu)。插入和刪除最小元素的操作復(fù)雜度為O(log n)能極大提升A*的性能。在JavaScript中我們可以自己實(shí)現(xiàn)一個(gè)最小堆或者利用一些庫(kù)。// 基于數(shù)組的二叉堆最小堆簡(jiǎn)化實(shí)現(xiàn)用于開放列表 class MinHeap { constructor() { this.heap []; } // 插入節(jié)點(diǎn)并上浮調(diào)整 push(node) { this.heap.push(node); this._siftUp(this.heap.length - 1); } // 彈出堆頂F值最小的節(jié)點(diǎn) pop() { if (this.heap.length 0) return null; const top this.heap[0]; const bottom this.heap.pop(); if (this.heap.length 0) { this.heap[0] bottom; this._siftDown(0); } return top; } // 上浮和下沉調(diào)整方法省略... }此外還需要一個(gè)快速查找節(jié)點(diǎn)狀態(tài)的數(shù)據(jù)結(jié)構(gòu)通常用一個(gè)二維數(shù)組或字典來映射網(wǎng)格坐標(biāo)到節(jié)點(diǎn)對(duì)象用于判斷節(jié)點(diǎn)是否在開放或關(guān)閉列表中這就是“關(guān)閉列表”的實(shí)質(zhì)它避免了昂貴的數(shù)組查找。3. 在Laya中實(shí)現(xiàn)網(wǎng)格A*尋路從理論到代碼理解了核心原理我們開始在Laya項(xiàng)目中落地。我們將構(gòu)建一個(gè)比官方更靈活、功能更完善的網(wǎng)格A*尋路模塊。3.1 構(gòu)建尋路網(wǎng)格與地圖數(shù)據(jù)首先我們需要將游戲世界轉(zhuǎn)換為網(wǎng)格。這通常需要一個(gè)“地圖數(shù)據(jù)”它可能來自TileMap的碰撞層、或者由美術(shù)在編輯器中繪制、或者通過代碼動(dòng)態(tài)生成。// Laya中一個(gè)簡(jiǎn)單的網(wǎng)格尋路管理器 class GridPathfinding { private _grid: number[][]; // 二維數(shù)組0可走1不可走障礙 private _gridWidth: number; private _gridHeight: number; private _cellSize: number; // 每個(gè)網(wǎng)格單元的世界坐標(biāo)大小 /** * 初始化網(wǎng)格 * param width 網(wǎng)格列數(shù) * param height 網(wǎng)格行數(shù) * param cellSize 單元格大小像素或世界單位 * param obstacleData 初始障礙數(shù)據(jù)可后續(xù)動(dòng)態(tài)更新 */ constructor(width: number, height: number, cellSize: number, obstacleData?: number[][]) { this._gridWidth width; this._gridHeight height; this._cellSize cellSize; this._grid []; // 初始化所有格子為可行走 for (let i 0; i height; i) { this._grid[i] []; for (let j 0; j width; j) { this._grid[i][j] 0; // 0表示可行走 } } // 如果有初始障礙數(shù)據(jù)則設(shè)置 if (obstacleData) { this.setObstacles(obstacleData); } } // 世界坐標(biāo)轉(zhuǎn)換為網(wǎng)格坐標(biāo) worldToGrid(wx: number, wy: number): {x: number, y: number} { return { x: Math.floor(wx / this._cellSize), y: Math.floor(wy / this._cellSize) }; } // 網(wǎng)格坐標(biāo)轉(zhuǎn)換為世界坐標(biāo)通常返回格子中心點(diǎn) gridToWorld(gx: number, gy: number): {x: number, y: number} { return { x: gx * this._cellSize this._cellSize * 0.5, y: gy * this._cellSize this._cellSize * 0.5 }; } // 動(dòng)態(tài)設(shè)置或清除障礙 setObstacle(gridX: number, gridY: number, isObstacle: boolean): void { if (this.isInsideGrid(gridX, gridY)) { this._grid[gridY][gridX] isObstacle ? 1 : 0; } } // ... 其他工具方法 }3.2 實(shí)現(xiàn)A*尋路核心算法接下來我們實(shí)現(xiàn)A*算法的核心。這里我們實(shí)現(xiàn)一個(gè)支持8方向移動(dòng)允許斜走的版本并考慮斜走代價(jià)略高符合真實(shí)移動(dòng)。class AStarFinder { private _grid: number[][]; private _heuristic: (dx: number, dy: number) number; // 啟發(fā)函數(shù) private _diagonalCost: number Math.SQRT2; // 斜向移動(dòng)代價(jià)約1.414 constructor(grid: number[][]) { this._grid grid; // 默認(rèn)使用歐幾里得距離作為啟發(fā)函數(shù)對(duì)于8方向使用對(duì)角線距離(octile)更優(yōu) this._heuristic function(dx, dy) { // Octile distance: D * (dx dy) (D2 - 2*D) * min(dx, dy) // 假設(shè)直線代價(jià)D1對(duì)角線代價(jià)D2√2 const D 1; const D2 this._diagonalCost; dx Math.abs(dx); dy Math.abs(dy); return D * (dx dy) (D2 - 2 * D) * Math.min(dx, dy); }.bind(this); } findPath(startGrid: {x: number, y: number}, endGrid: {x: number, y: number}): {x: number, y: number}[] { // 0. 邊界檢查起點(diǎn)終點(diǎn)是否合法、是否相同、是否不可行走 if (!this._isWalkable(startGrid.x, startGrid.y) || !this._isWalkable(endGrid.x, endGrid.y)) { return []; } if (startGrid.x endGrid.x startGrid.y endGrid.y) { return [startGrid]; } // 1. 初始化開放列表二叉堆和關(guān)閉集合 const openList new MinHeap(); const closedSet new Set(); // 使用字符串鍵 x,y 來快速查找 const nodeGrid: AStarNode[][] []; // 存儲(chǔ)所有節(jié)點(diǎn)信息 // 初始化節(jié)點(diǎn)網(wǎng)格 for (let y 0; y this._grid.length; y) { nodeGrid[y] []; for (let x 0; x this._grid[0].length; x) { nodeGrid[y][x] new AStarNode(x, y, this._grid[y][x] 0); } } const startNode nodeGrid[startGrid.y][startGrid.x]; const endNode nodeGrid[endGrid.y][endGrid.x]; startNode.g 0; startNode.h this._heuristic(Math.abs(startNode.x - endNode.x), Math.abs(startNode.y - endNode.y)); startNode.f startNode.g startNode.h; openList.push(startNode); // 8個(gè)方向的向量上、下、左、右、左上、右上、左下、右下 const directions [ {x: 0, y: -1}, {x: 0, y: 1}, {x: -1, y: 0}, {x: 1, y: 0}, {x: -1, y: -1}, {x: 1, y: -1}, {x: -1, y: 1}, {x: 1, y: 1} ]; // 2. 主循環(huán) while (!openList.isEmpty()) { const currentNode openList.pop(); // 取出F值最小的節(jié)點(diǎn) const nodeKey ${currentNode.x},${currentNode.y}; closedSet.add(nodeKey); // 找到終點(diǎn)了 if (currentNode endNode) { return this._retracePath(startNode, endNode); } // 3. 遍歷鄰居節(jié)點(diǎn) for (const dir of directions) { const neighborX currentNode.x dir.x; const neighborY currentNode.y dir.y; // 檢查鄰居是否有效且可行走 if (!this._isInsideGrid(neighborX, neighborY) || !this._isWalkable(neighborX, neighborY)) { continue; } const neighborNode nodeGrid[neighborY][neighborX]; const neighborKey ${neighborX},${neighborY}; if (closedSet.has(neighborKey)) { continue; // 已在關(guān)閉列表中跳過 } // 計(jì)算從當(dāng)前節(jié)點(diǎn)移動(dòng)到鄰居節(jié)點(diǎn)的代價(jià) // 如果是斜向移動(dòng)檢查對(duì)角線是否被阻擋防止“切墻角” const isDiagonal dir.x ! 0 dir.y ! 0; let moveCost isDiagonal ? this._diagonalCost : 1; if (isDiagonal) { // 如果斜角方向的兩個(gè)相鄰格子至少有一個(gè)是障礙則不允許斜向移動(dòng) const c1Walkable this._isWalkable(currentNode.x dir.x, currentNode.y); const c2Walkable this._isWalkable(currentNode.x, currentNode.y dir.y); if (!c1Walkable || !c2Walkable) { continue; } } const newG currentNode.g moveCost; // 如果鄰居不在開放列表或者找到更優(yōu)路徑 if (!neighborNode.isInOpenList || newG neighborNode.g) { neighborNode.g newG; neighborNode.h this._heuristic(Math.abs(neighborX - endNode.x), Math.abs(neighborY - endNode.y)); neighborNode.f neighborNode.g neighborNode.h; neighborNode.parent currentNode; if (!neighborNode.isInOpenList) { neighborNode.isInOpenList true; openList.push(neighborNode); } else { // 如果節(jié)點(diǎn)已在堆中且G值更新需要調(diào)整堆的位置這里簡(jiǎn)化處理實(shí)際需要decreaseKey操作 // 一個(gè)簡(jiǎn)單但低效的方法是重新插入因?yàn)镴avaScript堆實(shí)現(xiàn)通常不提供decreaseKey。 // 更好的做法是記錄節(jié)點(diǎn)在堆中的索引并實(shí)現(xiàn)上浮。 openList.updateItem(neighborNode); // 假設(shè)我們的堆支持更新 } } } } // 開放列表為空未找到路徑 return []; } private _retracePath(startNode: AStarNode, endNode: AStarNode): {x: number, y: number}[] { const path: {x: number, y: number}[] []; let currentNode: AStarNode | null endNode; while (currentNode ! null currentNode ! startNode) { path.unshift({x: currentNode.x, y: currentNode.y}); // 從終點(diǎn)向前插入 currentNode currentNode.parent; } path.unshift({x: startNode.x, y: startNode.y}); // 加入起點(diǎn) return path; } private _isInsideGrid(x: number, y: number): boolean { return x 0 x this._grid[0].length y 0 y this._grid.length; } private _isWalkable(x: number, y: number): boolean { return this._isInsideGrid(x, y) this._grid[y][x] 0; } }3.3 路徑平滑與角色移動(dòng)A*找到的路徑是基于網(wǎng)格中心的折線直接讓角色按這個(gè)路徑移動(dòng)會(huì)產(chǎn)生生硬的“格子步”感。我們需要進(jìn)行路徑平滑。最簡(jiǎn)單的平滑方法是拐點(diǎn)篩選從起點(diǎn)開始檢查當(dāng)前點(diǎn)到后續(xù)某個(gè)點(diǎn)之間是否有直接視線無碰撞如果沒有障礙就跳過中間點(diǎn)。這可以消除路徑中的冗余拐點(diǎn)。// 簡(jiǎn)單的視線檢測(cè)平滑 function smoothPath(originalPath: {x: number, y: number}[], grid: GridPathfinding): {x: number, y: number}[] { if (originalPath.length 2) return originalPath; const smoothed: {x: number, y: number}[] []; let currentIndex 0; smoothed.push(originalPath[currentIndex]); while (currentIndex originalPath.length - 1) { let furthestVisible currentIndex 1; // 從當(dāng)前點(diǎn)向后找看最遠(yuǎn)能無碰撞連接到哪個(gè)點(diǎn) for (let i currentIndex 2; i originalPath.length; i) { if (this._hasLineOfSight(originalPath[currentIndex], originalPath[i], grid)) { furthestVisible i; } else { break; // 一旦遇到障礙停止 } } smoothed.push(originalPath[furthestVisible]); currentIndex furthestVisible; } return smoothed; } // Bresenham算法檢查兩點(diǎn)間網(wǎng)格是否全部可通行 private _hasLineOfSight(start: {x: number, y: number}, end: {x: number, y: number}, grid: GridPathfinding): boolean { let x0 start.x, y0 start.y; let x1 end.x, y1 end.y; const dx Math.abs(x1 - x0); const dy Math.abs(y1 - y0); const sx x0 x1 ? 1 : -1; const sy y0 y1 ? 1 : -1; let err dx - dy; while (true) { // 檢查當(dāng)前網(wǎng)格點(diǎn)是否可行走 if (!grid.isWalkable(x0, y0)) { return false; } if (x0 x1 y0 y1) break; const e2 2 * err; if (e2 -dy) { err - dy; x0 sx; } if (e2 dx) { err dx; y0 sy; } } return true; }得到平滑后的世界坐標(biāo)路徑點(diǎn)后就可以使用Laya的Tween或自己寫移動(dòng)邏輯讓角色逐點(diǎn)移動(dòng)了。記得要處理到達(dá)每個(gè)路點(diǎn)的小范圍容差以及移動(dòng)中的旋轉(zhuǎn)朝向LookAt問題。4. 性能優(yōu)化與高級(jí)特性實(shí)戰(zhàn)當(dāng)游戲中有大量單位同時(shí)尋路時(shí)基礎(chǔ)的A*可能成為性能瓶頸。以下是一些關(guān)鍵的優(yōu)化策略和高級(jí)功能實(shí)現(xiàn)思路。4.1 性能優(yōu)化四板斧空間換時(shí)間路徑緩存與共享。對(duì)于靜態(tài)場(chǎng)景中頻繁請(qǐng)求的相同起點(diǎn)終點(diǎn)比如所有小怪出生點(diǎn)走向玩家可以緩存計(jì)算結(jié)果。對(duì)于多個(gè)單位走向同一目標(biāo)如RTS中所有士兵攻擊一個(gè)建筑可以使用流場(chǎng)尋路Flow Field或Dijkstra算法一次性計(jì)算整個(gè)網(wǎng)格到目標(biāo)點(diǎn)的代價(jià)然后每個(gè)單位根據(jù)本地代價(jià)梯度移動(dòng)即可這比每個(gè)單位單獨(dú)跑A*高效得多。降低搜索規(guī)模使用更粗的導(dǎo)航網(wǎng)格Hierarchical Pathfinding。先在一個(gè)粗糙的低分辨率網(wǎng)格上進(jìn)行高層尋路找到大致區(qū)域再在目標(biāo)區(qū)域的高精度網(wǎng)格上進(jìn)行精細(xì)尋路。這能極大減少搜索節(jié)點(diǎn)數(shù)。算法優(yōu)化使用更高效的A*變種。Jump Point Search (JPS)算法在均勻網(wǎng)格上可以跳過大量對(duì)稱路徑特別適合無障礙或障礙稀疏的網(wǎng)格能提升一個(gè)數(shù)量級(jí)的性能。但在障礙密集的動(dòng)態(tài)環(huán)境中優(yōu)勢(shì)不明顯。限制與異步避免卡頓。為單次A*搜索設(shè)置最大迭代次數(shù)或時(shí)間預(yù)算超時(shí)則返回當(dāng)前最優(yōu)路徑或失敗。將耗時(shí)的尋路計(jì)算放入Web Worker中異步執(zhí)行避免阻塞主線程導(dǎo)致游戲卡頓。這是提升游戲流暢度的關(guān)鍵。// 偽代碼在Laya中使用Web Worker進(jìn)行異步尋路 class AsyncPathFinder { private _worker: Worker; constructor() { // 假設(shè)尋路Worker代碼在pathfinder.worker.js中 this._worker new Worker(pathfinder.worker.js); this._worker.onmessage (e) { const { taskId, path } e.data; // 根據(jù)taskId找到對(duì)應(yīng)的回調(diào)函數(shù)并處理路徑 this._handlePathResult(taskId, path); }; } requestPathAsync(start, end, callback): number { const taskId this._generateTaskId(); this._worker.postMessage({ type: findPath, taskId: taskId, start: start, end: end, gridData: this._grid.getData() // 傳遞網(wǎng)格數(shù)據(jù) }); // 存儲(chǔ)callback等待worker返回結(jié)果后調(diào)用 this._pendingTasks[taskId] callback; return taskId; } }4.2 處理動(dòng)態(tài)障礙物游戲中的障礙物常常是動(dòng)態(tài)的如可破壞的墻、玩家建造的建筑。我們的尋路系統(tǒng)必須能快速響應(yīng)。實(shí)時(shí)更新網(wǎng)格當(dāng)動(dòng)態(tài)障礙物出現(xiàn)或消失時(shí)立即調(diào)用GridPathfinding.setObstacle()更新對(duì)應(yīng)網(wǎng)格狀態(tài)。局部重規(guī)劃對(duì)于正在移動(dòng)中的單位如果前方路徑上突然出現(xiàn)新障礙不需要從頭開始尋路?？梢詮漠?dāng)前位置開始執(zhí)行一次目標(biāo)不變的A*搜索。因?yàn)榇蟛糠峙f路徑可能仍然有效局部重規(guī)劃比全局重規(guī)劃快得多。避障與碰撞尋路解決的是宏觀路徑微觀上的單位間避免碰撞還需要局部避障Local Avoidance算法如RVOReciprocal Velocity Obstacles或其簡(jiǎn)化版。這通常與尋路系統(tǒng)配合使用尋路給出大方向局部避障處理瞬間的擁擠和穿插。4.3 不同游戲類型的適配要點(diǎn)2D俯視角/等距視角這是網(wǎng)格A*最自然的應(yīng)用場(chǎng)景。注意網(wǎng)格坐標(biāo)與等距世界坐標(biāo)的轉(zhuǎn)換。移動(dòng)時(shí)角色的速度、動(dòng)畫需要與網(wǎng)格移動(dòng)同步。3D場(chǎng)景如果地面不平坦簡(jiǎn)單的2D網(wǎng)格可能不夠。需要考慮高度圖Heightmap或真正的3D導(dǎo)航網(wǎng)格。移動(dòng)時(shí)角色的Y坐標(biāo)需要根據(jù)路徑點(diǎn)所在位置的地形高度進(jìn)行插值避免“穿地”或“漂浮”。RTS即時(shí)戰(zhàn)略游戲海量單位是最大挑戰(zhàn)。必須采用流場(chǎng)尋路Flow Field或分層尋路HPA*。同時(shí)要處理單位編隊(duì)移動(dòng)、保持陣型等高級(jí)AI行為。RPG/ARPG游戲NPC的尋路可能還需要結(jié)合行為樹Behavior Tree或狀態(tài)機(jī)根據(jù)不同的AI狀態(tài)巡邏、追擊、逃跑選擇不同的尋路目標(biāo)或參數(shù)。5. 常見問題、調(diào)試技巧與避坑指南在實(shí)際開發(fā)中你會(huì)遇到各種各樣奇怪的問題。這里記錄一些典型的“坑”和解決方法。5.1 尋路問題排查清單問題現(xiàn)象可能原因排查與解決思路角色卡住不動(dòng)不尋路1. 起點(diǎn)或終點(diǎn)被標(biāo)記為障礙。2. 起點(diǎn)終點(diǎn)相同。3. 尋路算法返回空數(shù)組。4. 移動(dòng)邏輯未正確觸發(fā)或路徑點(diǎn)列表為空。1. 打印起點(diǎn)終點(diǎn)的網(wǎng)格坐標(biāo)和 walkable 狀態(tài)。2. 檢查尋路函數(shù)返回值確保是有效路徑。3. 在場(chǎng)景中可視化網(wǎng)格和障礙物確認(rèn)數(shù)據(jù)正確。角色移動(dòng)路徑很“蠢”繞遠(yuǎn)路或貼墻走1. 啟發(fā)函數(shù) H 值權(quán)重不合適或計(jì)算有誤。2. 移動(dòng)代價(jià)G值設(shè)置不合理如斜向移動(dòng)代價(jià)過高。3. 路徑平滑算法未啟用或失效。4. 網(wǎng)格精度太低無法描述狹窄通道。1. 檢查 H 值計(jì)算函數(shù)確保其可采納不高估。2. 調(diào)整斜向移動(dòng)代價(jià)通常設(shè)為 sqrt(2) ≈ 1.414。3. 啟用并調(diào)試路徑平滑函數(shù)檢查視線檢測(cè)是否因障礙物判斷太嚴(yán)格而失敗。4. 適當(dāng)提高網(wǎng)格分辨率或?qū)﹃P(guān)鍵區(qū)域使用更高精度的網(wǎng)格。大量單位同時(shí)尋路時(shí)游戲嚴(yán)重卡頓1. 主線程同步進(jìn)行復(fù)雜A*計(jì)算。2. 未對(duì)相同尋路請(qǐng)求進(jìn)行緩存。3. 網(wǎng)格過大算法搜索節(jié)點(diǎn)過多。1.必須將尋路放入 Web Worker。2. 實(shí)現(xiàn)路徑緩存機(jī)制對(duì)于靜態(tài)場(chǎng)景的相同請(qǐng)求直接返回緩存結(jié)果。3. 考慮使用更粗的導(dǎo)航網(wǎng)格進(jìn)行分層尋路或改用流場(chǎng)尋路處理群體移動(dòng)。動(dòng)態(tài)障礙物更新后單位仍走被堵住的舊路1. 單位持有的路徑是舊的未因障礙物更新而重新規(guī)劃。2. 局部重規(guī)劃邏輯未觸發(fā)或失敗。1. 為每個(gè)移動(dòng)單位增加“路徑有效性檢查”定期或當(dāng)靠近舊路徑下一點(diǎn)時(shí)檢測(cè)前方是否暢通不通則觸發(fā)重尋路。2. 實(shí)現(xiàn)一個(gè)全局或局部的“導(dǎo)航網(wǎng)格更新事件”系統(tǒng)通知受影響單位重新規(guī)劃。單位移動(dòng)時(shí)“抖動(dòng)”或頻繁輕微調(diào)整方向1. 到達(dá)路徑點(diǎn)的判斷容差太小。2. 每幀移動(dòng)速度不一致幀率影響。3. 局部避障與全局路徑的指令沖突。1. 增大“到達(dá)”容差例如距離目標(biāo)點(diǎn)小于0.1個(gè)單位即視為到達(dá)。2. 使用基于時(shí)間的移動(dòng)velocity * deltaTime而非每幀固定距離。3. 確保局部避障的力度適中不要過度偏離全局路徑或者讓局部避障只處理非常近的威脅。5.2 調(diào)試與可視化技巧“看不見”的尋路邏輯是調(diào)試的難點(diǎn)。必須讓它們可視化。繪制調(diào)試網(wǎng)格在Laya的渲染后階段Laya.stage.on監(jiān)聽Event.RENDER后使用Graphics繪制網(wǎng)格線、用不同顏色填充可行走/不可行走格子、高亮顯示當(dāng)前尋路搜索過的節(jié)點(diǎn)開放列表和關(guān)閉列表以及最終計(jì)算出的路徑。這是最直接的調(diào)試手段。關(guān)鍵數(shù)據(jù)打印在尋路開始時(shí)打印起點(diǎn)、終點(diǎn)坐標(biāo)和狀態(tài)尋路結(jié)束后打印路徑長(zhǎng)度、搜索節(jié)點(diǎn)數(shù)、耗時(shí)。這有助于性能分析和邏輯驗(yàn)證。錄制與回放對(duì)于偶發(fā)的尋路異?？梢杂涗浵掳l(fā)生問題前后幾幀的游戲狀態(tài)單位位置、障礙物狀態(tài)、尋路請(qǐng)求參數(shù)便于離線復(fù)盤。5.3 我踩過的幾個(gè)“坑”“切墻角”問題早期實(shí)現(xiàn)8方向A*時(shí)沒有檢查斜向移動(dòng)時(shí)相鄰格子的阻擋情況導(dǎo)致單位可以緊貼著障礙物的對(duì)角線“擠”過去看起來像是穿過了墻角。解決方法就是在斜向移動(dòng)前判斷(xdx, y)和(x, ydy)兩個(gè)格子是否都可通行。Web Worker數(shù)據(jù)傳遞開銷第一次使用Web Worker時(shí)每幀都把巨大的網(wǎng)格二維數(shù)組通過postMessage傳遞造成了巨大的序列化/反序列化開銷。后來改為只在初始化時(shí)傳遞一次網(wǎng)格數(shù)據(jù)后續(xù)只傳遞變化的部分delta或者使用Transferable Objects如ArrayBuffer來傳遞數(shù)據(jù)性能提升顯著。移動(dòng)與動(dòng)畫不同步尋路系統(tǒng)給出的路徑點(diǎn)世界坐標(biāo)直接用來驅(qū)動(dòng)角色的x, y屬性。但角色的移動(dòng)動(dòng)畫播放速度是固定的導(dǎo)致角色可能“滑步”。解決辦法是根據(jù)角色移動(dòng)速度計(jì)算每幀應(yīng)播放的動(dòng)畫幀或者使用動(dòng)畫狀態(tài)機(jī)根據(jù)實(shí)際速度混合不同的移動(dòng)動(dòng)畫走、跑、慢走。構(gòu)建一個(gè)健壯的Laya AI尋路解決方案是一個(gè)從基礎(chǔ)算法到工程優(yōu)化再到與具體游戲邏輯深度融合的過程。它沒有唯一的“標(biāo)準(zhǔn)答案”但遵循“網(wǎng)格/A*打底、異步計(jì)算保流暢、動(dòng)態(tài)更新要及時(shí)、高級(jí)需求再升級(jí)”這條路徑能讓你在大多數(shù)項(xiàng)目中穩(wěn)步推進(jìn)。最終一個(gè)優(yōu)秀的尋路系統(tǒng)會(huì)讓游戲世界的居民真正“活”起來而這正是沉浸感的重要來源之一。 Laya游戲AI尋路實(shí)戰(zhàn)：從A*算法到性能優(yōu)化與動(dòng)態(tài)障礙處理
1. 項(xiàng)目概述當(dāng)Laya游戲需要“聰明”的NPC在LayaAir引擎開發(fā)2D或3D游戲時(shí)尤其是RPG、SLG、塔防這類需要角色自主移動(dòng)的游戲一個(gè)繞不開的核心需求就是如何讓游戲里的NPC、怪物或者單位能夠智能地找到從A點(diǎn)到B點(diǎn)的路徑并且能優(yōu)雅地繞開障礙物這就是我們常說的“尋路”Pathfinding。你可能嘗試過用簡(jiǎn)單的直線移動(dòng)但一堵墻、一棵樹就能讓角色卡住顯得非?！吧怠?。你也可能手動(dòng)預(yù)設(shè)好固定路線但一旦場(chǎng)景動(dòng)態(tài)變化比如玩家建造了一堵墻預(yù)設(shè)路線就失效了。這時(shí)一個(gè)可靠、高效的AI尋路系統(tǒng)就成了項(xiàng)目從“玩具Demo”邁向“可玩產(chǎn)品”的關(guān)鍵一步。LayaAir本身是一個(gè)優(yōu)秀的渲染與框架引擎但在復(fù)雜的AI尋路領(lǐng)域它并沒有內(nèi)置一個(gè)開箱即用的、功能完善的解決方案。官方提供的laya.ai包中的尋路模塊相對(duì)基礎(chǔ)面對(duì)復(fù)雜地形、動(dòng)態(tài)障礙、多單位尋路等實(shí)際開發(fā)中的高頻需求往往需要開發(fā)者投入大量精力進(jìn)行二次開發(fā)和優(yōu)化。因此尋找并集成一套成熟的第三方尋路方案或者基于成熟算法自建一套幾乎是中大型Laya游戲的必經(jīng)之路。這個(gè)“Laya游戲開發(fā)中AI尋路解決方案”要解決的就是在Laya生態(tài)下如何為游戲角色賦予“認(rèn)路”的智慧。它不僅僅是調(diào)用一個(gè)findPath()函數(shù)更涉及到網(wǎng)格劃分、算法選型、性能優(yōu)化、動(dòng)態(tài)障礙處理、與Laya渲染循環(huán)的整合、不同游戲類型如2D俯視角、3D第三人稱的適配等一系列環(huán)環(huán)相扣的問題。接下來我將結(jié)合多年項(xiàng)目實(shí)戰(zhàn)經(jīng)驗(yàn)為你拆解構(gòu)建這套方案的核心思路、技術(shù)細(xì)節(jié)與避坑指南。2. 尋路方案核心選型網(wǎng)格、算法與數(shù)據(jù)結(jié)構(gòu)在動(dòng)手寫代碼之前選對(duì)底層方案決定了后續(xù)開發(fā)的效率和最終效果的上限。尋路方案的核心三要素是世界表示法用什么描述可行走區(qū)域、尋路算法用什么計(jì)算路徑、數(shù)據(jù)結(jié)構(gòu)如何高效存儲(chǔ)和查詢。2.1 世界表示法網(wǎng)格Grid vs 導(dǎo)航網(wǎng)格NavMesh vs 點(diǎn)陣Waypoint對(duì)于Laya游戲尤其是2D游戲或俯視角3D游戲網(wǎng)格Grid是最常見、最易上手的選擇。它將游戲世界劃分為均勻的二維方格在3D中可能是體素每個(gè)格子標(biāo)記為“可行走”或“不可行走”。其優(yōu)勢(shì)在于實(shí)現(xiàn)簡(jiǎn)單、概念直觀、動(dòng)態(tài)更新障礙物非常方便只需修改格子狀態(tài)。Laya官方laya.ai.PathFinder默認(rèn)就支持網(wǎng)格尋路。缺點(diǎn)是路徑不夠平滑鋸齒狀且內(nèi)存占用與網(wǎng)格分辨率成正比大世界高精度網(wǎng)格開銷大。導(dǎo)航網(wǎng)格NavMesh在3D游戲中更為強(qiáng)大。它用一系列凸多邊形來覆蓋所有可行走區(qū)域角色可以在多邊形內(nèi)部任意點(diǎn)自由移動(dòng)路徑天生平滑且更符合真實(shí)地形。Unity的NavMesh系統(tǒng)就是典型代表。在Laya中實(shí)現(xiàn)完整的NavMesh需要較復(fù)雜的幾何計(jì)算和第三方庫(kù)支持如recast-detour的JavaScript端口復(fù)雜度高但效果最好適合復(fù)雜的3D場(chǎng)景。點(diǎn)陣Waypoint則是在場(chǎng)景中手動(dòng)或自動(dòng)放置一系列路徑點(diǎn)角色只能在點(diǎn)與點(diǎn)之間移動(dòng)。它非常輕量適合固定路線明顯的游戲如賽車、平臺(tái)跳躍但靈活度最低無法處理動(dòng)態(tài)障礙。實(shí)操心得對(duì)于大多數(shù)Laya項(xiàng)目尤其是剛接觸尋路的團(tuán)隊(duì)從基于網(wǎng)格的A*算法開始是最穩(wěn)妥的。它足夠解決80%的問題社區(qū)資源豐富調(diào)試可視化也容易。我們可以先用較粗的網(wǎng)格保證性能后期再考慮結(jié)合導(dǎo)航網(wǎng)格或分層尋路HPA*進(jìn)行優(yōu)化。2.2 尋路算法為什么A*是絕對(duì)主力談到網(wǎng)格尋路就離不開A*A-Star算法。它之所以是業(yè)界標(biāo)準(zhǔn)是因?yàn)樗凇懊つ俊钡腄ijkstra算法和“激進(jìn)”的貪心最佳優(yōu)先搜索Greedy Best-First-Search之間取得了完美平衡。簡(jiǎn)單來說A*為每個(gè)待評(píng)估的網(wǎng)格節(jié)點(diǎn)計(jì)算一個(gè)代價(jià)函數(shù)F G H。G值從起點(diǎn)移動(dòng)到當(dāng)前節(jié)點(diǎn)的實(shí)際代價(jià)。H值啟發(fā)式估計(jì)從當(dāng)前節(jié)點(diǎn)到終點(diǎn)的預(yù)估代價(jià)常用曼哈頓距離適用于4方向移動(dòng)或歐幾里得距離適用于8方向或任意方向。F值總預(yù)估代價(jià)。算法總是優(yōu)先探索F值最小的節(jié)點(diǎn)從而高效地找到最短路徑。// 一個(gè)非常簡(jiǎn)化的A*節(jié)點(diǎn)類結(jié)構(gòu)示意 class AStarNode { constructor(x, y) { this.x x; // 網(wǎng)格X坐標(biāo) this.y y; // 網(wǎng)格Y坐標(biāo) this.g 0; // 起點(diǎn)到本節(jié)點(diǎn)的實(shí)際代價(jià) this.h 0; // 本節(jié)點(diǎn)到終點(diǎn)的預(yù)估代價(jià) this.f 0; // g h this.parent null; // 父節(jié)點(diǎn)用于回溯路徑 this.walkable true; // 是否可行走 } }相較于廣度優(yōu)先搜索BFSA通過啟發(fā)函數(shù)H大幅減少了需要搜索的節(jié)點(diǎn)數(shù)量速度更快。相較于深度優(yōu)先搜索DFSA能保證找到最優(yōu)解如果啟發(fā)函數(shù)H是可采納的即從不高估實(shí)際代價(jià)。注意事項(xiàng)啟發(fā)函數(shù)H的選擇直接影響效率和路徑“自然度”。在允許斜向移動(dòng)的8方向網(wǎng)格中使用對(duì)角線距離Chebyshev距離或Octile距離會(huì)比簡(jiǎn)單的歐幾里得距離更準(zhǔn)確計(jì)算也更快。同時(shí)確保H永遠(yuǎn)不大于實(shí)際剩余代價(jià)否則A*可能找不到最優(yōu)解。2.3 數(shù)據(jù)結(jié)構(gòu)優(yōu)化開放列表OpenList的性能關(guān)鍵A*算法需要頻繁地從“開放列表”待考察節(jié)點(diǎn)集合中取出F值最小的節(jié)點(diǎn)。如果使用普通的數(shù)組每次查找都需要遍歷性能是O(n)在大型網(wǎng)格上將是災(zāi)難。因此優(yōu)先隊(duì)列Priority Queue特別是二叉堆Binary Heap是實(shí)現(xiàn)開放列表的標(biāo)準(zhǔn)數(shù)據(jù)結(jié)構(gòu)。插入和刪除最小元素的操作復(fù)雜度為O(log n)能極大提升A*的性能。在JavaScript中我們可以自己實(shí)現(xiàn)一個(gè)最小堆或者利用一些庫(kù)。// 基于數(shù)組的二叉堆最小堆簡(jiǎn)化實(shí)現(xiàn)用于開放列表 class MinHeap { constructor() { this.heap []; } // 插入節(jié)點(diǎn)并上浮調(diào)整 push(node) { this.heap.push(node); this._siftUp(this.heap.length - 1); } // 彈出堆頂F值最小的節(jié)點(diǎn) pop() { if (this.heap.length 0) return null; const top this.heap[0]; const bottom this.heap.pop(); if (this.heap.length 0) { this.heap[0] bottom; this._siftDown(0); } return top; } // 上浮和下沉調(diào)整方法省略... }此外還需要一個(gè)快速查找節(jié)點(diǎn)狀態(tài)的數(shù)據(jù)結(jié)構(gòu)通常用一個(gè)二維數(shù)組或字典來映射網(wǎng)格坐標(biāo)到節(jié)點(diǎn)對(duì)象用于判斷節(jié)點(diǎn)是否在開放或關(guān)閉列表中這就是“關(guān)閉列表”的實(shí)質(zhì)它避免了昂貴的數(shù)組查找。3. 在Laya中實(shí)現(xiàn)網(wǎng)格A*尋路從理論到代碼理解了核心原理我們開始在Laya項(xiàng)目中落地。我們將構(gòu)建一個(gè)比官方更靈活、功能更完善的網(wǎng)格A*尋路模塊。3.1 構(gòu)建尋路網(wǎng)格與地圖數(shù)據(jù)首先我們需要將游戲世界轉(zhuǎn)換為網(wǎng)格。這通常需要一個(gè)“地圖數(shù)據(jù)”它可能來自TileMap的碰撞層、或者由美術(shù)在編輯器中繪制、或者通過代碼動(dòng)態(tài)生成。// Laya中一個(gè)簡(jiǎn)單的網(wǎng)格尋路管理器 class GridPathfinding { private _grid: number[][]; // 二維數(shù)組0可走1不可走障礙 private _gridWidth: number; private _gridHeight: number; private _cellSize: number; // 每個(gè)網(wǎng)格單元的世界坐標(biāo)大小 /** * 初始化網(wǎng)格 * param width 網(wǎng)格列數(shù) * param height 網(wǎng)格行數(shù) * param cellSize 單元格大小像素或世界單位 * param obstacleData 初始障礙數(shù)據(jù)可后續(xù)動(dòng)態(tài)更新 */ constructor(width: number, height: number, cellSize: number, obstacleData?: number[][]) { this._gridWidth width; this._gridHeight height; this._cellSize cellSize; this._grid []; // 初始化所有格子為可行走 for (let i 0; i height; i) { this._grid[i] []; for (let j 0; j width; j) { this._grid[i][j] 0; // 0表示可行走 } } // 如果有初始障礙數(shù)據(jù)則設(shè)置 if (obstacleData) { this.setObstacles(obstacleData); } } // 世界坐標(biāo)轉(zhuǎn)換為網(wǎng)格坐標(biāo) worldToGrid(wx: number, wy: number): {x: number, y: number} { return { x: Math.floor(wx / this._cellSize), y: Math.floor(wy / this._cellSize) }; } // 網(wǎng)格坐標(biāo)轉(zhuǎn)換為世界坐標(biāo)通常返回格子中心點(diǎn) gridToWorld(gx: number, gy: number): {x: number, y: number} { return { x: gx * this._cellSize this._cellSize * 0.5, y: gy * this._cellSize this._cellSize * 0.5 }; } // 動(dòng)態(tài)設(shè)置或清除障礙 setObstacle(gridX: number, gridY: number, isObstacle: boolean): void { if (this.isInsideGrid(gridX, gridY)) { this._grid[gridY][gridX] isObstacle ? 1 : 0; } } // ... 其他工具方法 }3.2 實(shí)現(xiàn)A*尋路核心算法接下來我們實(shí)現(xiàn)A*算法的核心。這里我們實(shí)現(xiàn)一個(gè)支持8方向移動(dòng)允許斜走的版本并考慮斜走代價(jià)略高符合真實(shí)移動(dòng)。class AStarFinder { private _grid: number[][]; private _heuristic: (dx: number, dy: number) number; // 啟發(fā)函數(shù) private _diagonalCost: number Math.SQRT2; // 斜向移動(dòng)代價(jià)約1.414 constructor(grid: number[][]) { this._grid grid; // 默認(rèn)使用歐幾里得距離作為啟發(fā)函數(shù)對(duì)于8方向使用對(duì)角線距離(octile)更優(yōu) this._heuristic function(dx, dy) { // Octile distance: D * (dx dy) (D2 - 2*D) * min(dx, dy) // 假設(shè)直線代價(jià)D1對(duì)角線代價(jià)D2√2 const D 1; const D2 this._diagonalCost; dx Math.abs(dx); dy Math.abs(dy); return D * (dx dy) (D2 - 2 * D) * Math.min(dx, dy); }.bind(this); } findPath(startGrid: {x: number, y: number}, endGrid: {x: number, y: number}): {x: number, y: number}[] { // 0. 邊界檢查起點(diǎn)終點(diǎn)是否合法、是否相同、是否不可行走 if (!this._isWalkable(startGrid.x, startGrid.y) || !this._isWalkable(endGrid.x, endGrid.y)) { return []; } if (startGrid.x endGrid.x startGrid.y endGrid.y) { return [startGrid]; } // 1. 初始化開放列表二叉堆和關(guān)閉集合 const openList new MinHeap(); const closedSet new Set(); // 使用字符串鍵 x,y 來快速查找 const nodeGrid: AStarNode[][] []; // 存儲(chǔ)所有節(jié)點(diǎn)信息 // 初始化節(jié)點(diǎn)網(wǎng)格 for (let y 0; y this._grid.length; y) { nodeGrid[y] []; for (let x 0; x this._grid[0].length; x) { nodeGrid[y][x] new AStarNode(x, y, this._grid[y][x] 0); } } const startNode nodeGrid[startGrid.y][startGrid.x]; const endNode nodeGrid[endGrid.y][endGrid.x]; startNode.g 0; startNode.h this._heuristic(Math.abs(startNode.x - endNode.x), Math.abs(startNode.y - endNode.y)); startNode.f startNode.g startNode.h; openList.push(startNode); // 8個(gè)方向的向量上、下、左、右、左上、右上、左下、右下 const directions [ {x: 0, y: -1}, {x: 0, y: 1}, {x: -1, y: 0}, {x: 1, y: 0}, {x: -1, y: -1}, {x: 1, y: -1}, {x: -1, y: 1}, {x: 1, y: 1} ]; // 2. 主循環(huán) while (!openList.isEmpty()) { const currentNode openList.pop(); // 取出F值最小的節(jié)點(diǎn) const nodeKey ${currentNode.x},${currentNode.y}; closedSet.add(nodeKey); // 找到終點(diǎn)了 if (currentNode endNode) { return this._retracePath(startNode, endNode); } // 3. 遍歷鄰居節(jié)點(diǎn) for (const dir of directions) { const neighborX currentNode.x dir.x; const neighborY currentNode.y dir.y; // 檢查鄰居是否有效且可行走 if (!this._isInsideGrid(neighborX, neighborY) || !this._isWalkable(neighborX, neighborY)) { continue; } const neighborNode nodeGrid[neighborY][neighborX]; const neighborKey ${neighborX},${neighborY}; if (closedSet.has(neighborKey)) { continue; // 已在關(guān)閉列表中跳過 } // 計(jì)算從當(dāng)前節(jié)點(diǎn)移動(dòng)到鄰居節(jié)點(diǎn)的代價(jià) // 如果是斜向移動(dòng)檢查對(duì)角線是否被阻擋防止“切墻角” const isDiagonal dir.x ! 0 dir.y ! 0; let moveCost isDiagonal ? this._diagonalCost : 1; if (isDiagonal) { // 如果斜角方向的兩個(gè)相鄰格子至少有一個(gè)是障礙則不允許斜向移動(dòng) const c1Walkable this._isWalkable(currentNode.x dir.x, currentNode.y); const c2Walkable this._isWalkable(currentNode.x, currentNode.y dir.y); if (!c1Walkable || !c2Walkable) { continue; } } const newG currentNode.g moveCost; // 如果鄰居不在開放列表或者找到更優(yōu)路徑 if (!neighborNode.isInOpenList || newG neighborNode.g) { neighborNode.g newG; neighborNode.h this._heuristic(Math.abs(neighborX - endNode.x), Math.abs(neighborY - endNode.y)); neighborNode.f neighborNode.g neighborNode.h; neighborNode.parent currentNode; if (!neighborNode.isInOpenList) { neighborNode.isInOpenList true; openList.push(neighborNode); } else { // 如果節(jié)點(diǎn)已在堆中且G值更新需要調(diào)整堆的位置這里簡(jiǎn)化處理實(shí)際需要decreaseKey操作 // 一個(gè)簡(jiǎn)單但低效的方法是重新插入因?yàn)镴avaScript堆實(shí)現(xiàn)通常不提供decreaseKey。 // 更好的做法是記錄節(jié)點(diǎn)在堆中的索引并實(shí)現(xiàn)上浮。 openList.updateItem(neighborNode); // 假設(shè)我們的堆支持更新 } } } } // 開放列表為空未找到路徑 return []; } private _retracePath(startNode: AStarNode, endNode: AStarNode): {x: number, y: number}[] { const path: {x: number, y: number}[] []; let currentNode: AStarNode | null endNode; while (currentNode ! null currentNode ! startNode) { path.unshift({x: currentNode.x, y: currentNode.y}); // 從終點(diǎn)向前插入 currentNode currentNode.parent; } path.unshift({x: startNode.x, y: startNode.y}); // 加入起點(diǎn) return path; } private _isInsideGrid(x: number, y: number): boolean { return x 0 x this._grid[0].length y 0 y this._grid.length; } private _isWalkable(x: number, y: number): boolean { return this._isInsideGrid(x, y) this._grid[y][x] 0; } }3.3 路徑平滑與角色移動(dòng)A*找到的路徑是基于網(wǎng)格中心的折線直接讓角色按這個(gè)路徑移動(dòng)會(huì)產(chǎn)生生硬的“格子步”感。我們需要進(jìn)行路徑平滑。最簡(jiǎn)單的平滑方法是拐點(diǎn)篩選從起點(diǎn)開始檢查當(dāng)前點(diǎn)到后續(xù)某個(gè)點(diǎn)之間是否有直接視線無碰撞如果沒有障礙就跳過中間點(diǎn)。這可以消除路徑中的冗余拐點(diǎn)。// 簡(jiǎn)單的視線檢測(cè)平滑 function smoothPath(originalPath: {x: number, y: number}[], grid: GridPathfinding): {x: number, y: number}[] { if (originalPath.length 2) return originalPath; const smoothed: {x: number, y: number}[] []; let currentIndex 0; smoothed.push(originalPath[currentIndex]); while (currentIndex originalPath.length - 1) { let furthestVisible currentIndex 1; // 從當(dāng)前點(diǎn)向后找看最遠(yuǎn)能無碰撞連接到哪個(gè)點(diǎn) for (let i currentIndex 2; i originalPath.length; i) { if (this._hasLineOfSight(originalPath[currentIndex], originalPath[i], grid)) { furthestVisible i; } else { break; // 一旦遇到障礙停止 } } smoothed.push(originalPath[furthestVisible]); currentIndex furthestVisible; } return smoothed; } // Bresenham算法檢查兩點(diǎn)間網(wǎng)格是否全部可通行 private _hasLineOfSight(start: {x: number, y: number}, end: {x: number, y: number}, grid: GridPathfinding): boolean { let x0 start.x, y0 start.y; let x1 end.x, y1 end.y; const dx Math.abs(x1 - x0); const dy Math.abs(y1 - y0); const sx x0 x1 ? 1 : -1; const sy y0 y1 ? 1 : -1; let err dx - dy; while (true) { // 檢查當(dāng)前網(wǎng)格點(diǎn)是否可行走 if (!grid.isWalkable(x0, y0)) { return false; } if (x0 x1 y0 y1) break; const e2 2 * err; if (e2 -dy) { err - dy; x0 sx; } if (e2 dx) { err dx; y0 sy; } } return true; }得到平滑后的世界坐標(biāo)路徑點(diǎn)后就可以使用Laya的Tween或自己寫移動(dòng)邏輯讓角色逐點(diǎn)移動(dòng)了。記得要處理到達(dá)每個(gè)路點(diǎn)的小范圍容差以及移動(dòng)中的旋轉(zhuǎn)朝向LookAt問題。4. 性能優(yōu)化與高級(jí)特性實(shí)戰(zhàn)當(dāng)游戲中有大量單位同時(shí)尋路時(shí)基礎(chǔ)的A*可能成為性能瓶頸。以下是一些關(guān)鍵的優(yōu)化策略和高級(jí)功能實(shí)現(xiàn)思路。4.1 性能優(yōu)化四板斧空間換時(shí)間路徑緩存與共享。對(duì)于靜態(tài)場(chǎng)景中頻繁請(qǐng)求的相同起點(diǎn)終點(diǎn)比如所有小怪出生點(diǎn)走向玩家可以緩存計(jì)算結(jié)果。對(duì)于多個(gè)單位走向同一目標(biāo)如RTS中所有士兵攻擊一個(gè)建筑可以使用流場(chǎng)尋路Flow Field或Dijkstra算法一次性計(jì)算整個(gè)網(wǎng)格到目標(biāo)點(diǎn)的代價(jià)然后每個(gè)單位根據(jù)本地代價(jià)梯度移動(dòng)即可這比每個(gè)單位單獨(dú)跑A*高效得多。降低搜索規(guī)模使用更粗的導(dǎo)航網(wǎng)格Hierarchical Pathfinding。先在一個(gè)粗糙的低分辨率網(wǎng)格上進(jìn)行高層尋路找到大致區(qū)域再在目標(biāo)區(qū)域的高精度網(wǎng)格上進(jìn)行精細(xì)尋路。這能極大減少搜索節(jié)點(diǎn)數(shù)。算法優(yōu)化使用更高效的A*變種。Jump Point Search (JPS)算法在均勻網(wǎng)格上可以跳過大量對(duì)稱路徑特別適合無障礙或障礙稀疏的網(wǎng)格能提升一個(gè)數(shù)量級(jí)的性能。但在障礙密集的動(dòng)態(tài)環(huán)境中優(yōu)勢(shì)不明顯。限制與異步避免卡頓。為單次A*搜索設(shè)置最大迭代次數(shù)或時(shí)間預(yù)算超時(shí)則返回當(dāng)前最優(yōu)路徑或失敗。將耗時(shí)的尋路計(jì)算放入Web Worker中異步執(zhí)行避免阻塞主線程導(dǎo)致游戲卡頓。這是提升游戲流暢度的關(guān)鍵。// 偽代碼在Laya中使用Web Worker進(jìn)行異步尋路 class AsyncPathFinder { private _worker: Worker; constructor() { // 假設(shè)尋路Worker代碼在pathfinder.worker.js中 this._worker new Worker(pathfinder.worker.js); this._worker.onmessage (e) { const { taskId, path } e.data; // 根據(jù)taskId找到對(duì)應(yīng)的回調(diào)函數(shù)并處理路徑 this._handlePathResult(taskId, path); }; } requestPathAsync(start, end, callback): number { const taskId this._generateTaskId(); this._worker.postMessage({ type: findPath, taskId: taskId, start: start, end: end, gridData: this._grid.getData() // 傳遞網(wǎng)格數(shù)據(jù) }); // 存儲(chǔ)callback等待worker返回結(jié)果后調(diào)用 this._pendingTasks[taskId] callback; return taskId; } }4.2 處理動(dòng)態(tài)障礙物游戲中的障礙物常常是動(dòng)態(tài)的如可破壞的墻、玩家建造的建筑。我們的尋路系統(tǒng)必須能快速響應(yīng)。實(shí)時(shí)更新網(wǎng)格當(dāng)動(dòng)態(tài)障礙物出現(xiàn)或消失時(shí)立即調(diào)用GridPathfinding.setObstacle()更新對(duì)應(yīng)網(wǎng)格狀態(tài)。局部重規(guī)劃對(duì)于正在移動(dòng)中的單位如果前方路徑上突然出現(xiàn)新障礙不需要從頭開始尋路?？梢詮漠?dāng)前位置開始執(zhí)行一次目標(biāo)不變的A*搜索。因?yàn)榇蟛糠峙f路徑可能仍然有效局部重規(guī)劃比全局重規(guī)劃快得多。避障與碰撞尋路解決的是宏觀路徑微觀上的單位間避免碰撞還需要局部避障Local Avoidance算法如RVOReciprocal Velocity Obstacles或其簡(jiǎn)化版。這通常與尋路系統(tǒng)配合使用尋路給出大方向局部避障處理瞬間的擁擠和穿插。4.3 不同游戲類型的適配要點(diǎn)2D俯視角/等距視角這是網(wǎng)格A*最自然的應(yīng)用場(chǎng)景。注意網(wǎng)格坐標(biāo)與等距世界坐標(biāo)的轉(zhuǎn)換。移動(dòng)時(shí)角色的速度、動(dòng)畫需要與網(wǎng)格移動(dòng)同步。3D場(chǎng)景如果地面不平坦簡(jiǎn)單的2D網(wǎng)格可能不夠。需要考慮高度圖Heightmap或真正的3D導(dǎo)航網(wǎng)格。移動(dòng)時(shí)角色的Y坐標(biāo)需要根據(jù)路徑點(diǎn)所在位置的地形高度進(jìn)行插值避免“穿地”或“漂浮”。RTS即時(shí)戰(zhàn)略游戲海量單位是最大挑戰(zhàn)。必須采用流場(chǎng)尋路Flow Field或分層尋路HPA*。同時(shí)要處理單位編隊(duì)移動(dòng)、保持陣型等高級(jí)AI行為。RPG/ARPG游戲NPC的尋路可能還需要結(jié)合行為樹Behavior Tree或狀態(tài)機(jī)根據(jù)不同的AI狀態(tài)巡邏、追擊、逃跑選擇不同的尋路目標(biāo)或參數(shù)。5. 常見問題、調(diào)試技巧與避坑指南在實(shí)際開發(fā)中你會(huì)遇到各種各樣奇怪的問題。這里記錄一些典型的“坑”和解決方法。5.1 尋路問題排查清單問題現(xiàn)象可能原因排查與解決思路角色卡住不動(dòng)不尋路1. 起點(diǎn)或終點(diǎn)被標(biāo)記為障礙。2. 起點(diǎn)終點(diǎn)相同。3. 尋路算法返回空數(shù)組。4. 移動(dòng)邏輯未正確觸發(fā)或路徑點(diǎn)列表為空。1. 打印起點(diǎn)終點(diǎn)的網(wǎng)格坐標(biāo)和 walkable 狀態(tài)。2. 檢查尋路函數(shù)返回值確保是有效路徑。3. 在場(chǎng)景中可視化網(wǎng)格和障礙物確認(rèn)數(shù)據(jù)正確。角色移動(dòng)路徑很“蠢”繞遠(yuǎn)路或貼墻走1. 啟發(fā)函數(shù) H 值權(quán)重不合適或計(jì)算有誤。2. 移動(dòng)代價(jià)G值設(shè)置不合理如斜向移動(dòng)代價(jià)過高。3. 路徑平滑算法未啟用或失效。4. 網(wǎng)格精度太低無法描述狹窄通道。1. 檢查 H 值計(jì)算函數(shù)確保其可采納不高估。2. 調(diào)整斜向移動(dòng)代價(jià)通常設(shè)為 sqrt(2) ≈ 1.414。3. 啟用并調(diào)試路徑平滑函數(shù)檢查視線檢測(cè)是否因障礙物判斷太嚴(yán)格而失敗。4. 適當(dāng)提高網(wǎng)格分辨率或?qū)﹃P(guān)鍵區(qū)域使用更高精度的網(wǎng)格。大量單位同時(shí)尋路時(shí)游戲嚴(yán)重卡頓1. 主線程同步進(jìn)行復(fù)雜A*計(jì)算。2. 未對(duì)相同尋路請(qǐng)求進(jìn)行緩存。3. 網(wǎng)格過大算法搜索節(jié)點(diǎn)過多。1.必須將尋路放入 Web Worker。2. 實(shí)現(xiàn)路徑緩存機(jī)制對(duì)于靜態(tài)場(chǎng)景的相同請(qǐng)求直接返回緩存結(jié)果。3. 考慮使用更粗的導(dǎo)航網(wǎng)格進(jìn)行分層尋路或改用流場(chǎng)尋路處理群體移動(dòng)。動(dòng)態(tài)障礙物更新后單位仍走被堵住的舊路1. 單位持有的路徑是舊的未因障礙物更新而重新規(guī)劃。2. 局部重規(guī)劃邏輯未觸發(fā)或失敗。1. 為每個(gè)移動(dòng)單位增加“路徑有效性檢查”定期或當(dāng)靠近舊路徑下一點(diǎn)時(shí)檢測(cè)前方是否暢通不通則觸發(fā)重尋路。2. 實(shí)現(xiàn)一個(gè)全局或局部的“導(dǎo)航網(wǎng)格更新事件”系統(tǒng)通知受影響單位重新規(guī)劃。單位移動(dòng)時(shí)“抖動(dòng)”或頻繁輕微調(diào)整方向1. 到達(dá)路徑點(diǎn)的判斷容差太小。2. 每幀移動(dòng)速度不一致幀率影響。3. 局部避障與全局路徑的指令沖突。1. 增大“到達(dá)”容差例如距離目標(biāo)點(diǎn)小于0.1個(gè)單位即視為到達(dá)。2. 使用基于時(shí)間的移動(dòng)velocity * deltaTime而非每幀固定距離。3. 確保局部避障的力度適中不要過度偏離全局路徑或者讓局部避障只處理非常近的威脅。5.2 調(diào)試與可視化技巧“看不見”的尋路邏輯是調(diào)試的難點(diǎn)。必須讓它們可視化。繪制調(diào)試網(wǎng)格在Laya的渲染后階段Laya.stage.on監(jiān)聽Event.RENDER后使用Graphics繪制網(wǎng)格線、用不同顏色填充可行走/不可行走格子、高亮顯示當(dāng)前尋路搜索過的節(jié)點(diǎn)開放列表和關(guān)閉列表以及最終計(jì)算出的路徑。這是最直接的調(diào)試手段。關(guān)鍵數(shù)據(jù)打印在尋路開始時(shí)打印起點(diǎn)、終點(diǎn)坐標(biāo)和狀態(tài)尋路結(jié)束后打印路徑長(zhǎng)度、搜索節(jié)點(diǎn)數(shù)、耗時(shí)。這有助于性能分析和邏輯驗(yàn)證。錄制與回放對(duì)于偶發(fā)的尋路異?？梢杂涗浵掳l(fā)生問題前后幾幀的游戲狀態(tài)單位位置、障礙物狀態(tài)、尋路請(qǐng)求參數(shù)便于離線復(fù)盤。5.3 我踩過的幾個(gè)“坑”“切墻角”問題早期實(shí)現(xiàn)8方向A*時(shí)沒有檢查斜向移動(dòng)時(shí)相鄰格子的阻擋情況導(dǎo)致單位可以緊貼著障礙物的對(duì)角線“擠”過去看起來像是穿過了墻角。解決方法就是在斜向移動(dòng)前判斷(xdx, y)和(x, ydy)兩個(gè)格子是否都可通行。Web Worker數(shù)據(jù)傳遞開銷第一次使用Web Worker時(shí)每幀都把巨大的網(wǎng)格二維數(shù)組通過postMessage傳遞造成了巨大的序列化/反序列化開銷。后來改為只在初始化時(shí)傳遞一次網(wǎng)格數(shù)據(jù)后續(xù)只傳遞變化的部分delta或者使用Transferable Objects如ArrayBuffer來傳遞數(shù)據(jù)性能提升顯著。移動(dòng)與動(dòng)畫不同步尋路系統(tǒng)給出的路徑點(diǎn)世界坐標(biāo)直接用來驅(qū)動(dòng)角色的x, y屬性。但角色的移動(dòng)動(dòng)畫播放速度是固定的導(dǎo)致角色可能“滑步”。解決辦法是根據(jù)角色移動(dòng)速度計(jì)算每幀應(yīng)播放的動(dòng)畫幀或者使用動(dòng)畫狀態(tài)機(jī)根據(jù)實(shí)際速度混合不同的移動(dòng)動(dòng)畫走、跑、慢走。構(gòu)建一個(gè)健壯的Laya AI尋路解決方案是一個(gè)從基礎(chǔ)算法到工程優(yōu)化再到與具體游戲邏輯深度融合的過程。它沒有唯一的“標(biāo)準(zhǔn)答案”但遵循“網(wǎng)格/A*打底、異步計(jì)算保流暢、動(dòng)態(tài)更新要及時(shí)、高級(jí)需求再升級(jí)”這條路徑能讓你在大多數(shù)項(xiàng)目中穩(wěn)步推進(jìn)。最終一個(gè)優(yōu)秀的尋路系統(tǒng)會(huì)讓游戲世界的居民真正“活”起來而這正是沉浸感的重要來源之一。