簡介Three.js算法尋路示例是一份面向前端開發(fā)者的3D路徑規(guī)劃項目融合Three.js、Vue框架以及A*、BFS、DFS等常見尋路算法。資源從三維場景搭建到路徑搜索實現(xiàn)均有完整代碼幫助讀者理解啟發(fā)式搜索與圖遍歷在實際障礙環(huán)境中的性能差異適用于游戲開發(fā)、虛擬現(xiàn)實、交互式應用等場景。壓縮包共71個文件大小約3.56MB包含大量用于場景貼圖與界面元素的PNG、SVG、JPG圖片以及負責邏輯的JS文件、構(gòu)建界面的Vue組件和說明用的HTML、MD文檔其中圖片用于場景裝飾與界面展示腳本與組件承載核心算法與交互邏輯目錄結(jié)構(gòu)清晰。已有778人學習下載適合希望將WebGL三維渲染與算法編程結(jié)合的開發(fā)者研讀。通過運行示例并對比不同算法讀者能掌握在3D空間布置障礙、計算最短路徑及優(yōu)化尋路效率的完整實現(xiàn)思路。1. three.js算法尋路示例為什么在三維場景里尋路不只是調(diào)一個庫很多人第一次接觸 three.js 尋路示例時會覺得這就是「把 2D 地圖換成 3D 場景然后跑一遍 A*」。真動手才發(fā)現(xiàn)坑全在坐標系換算、障礙物數(shù)據(jù)提取和路徑回填上。二維尋路面對的是.block數(shù)組三維場景里的障礙物是各種不規(guī)則幾何體你要先回答「哪些地方能走」才能談「怎么走」。這個示例要解決的正是從 three.js 場景到可尋路數(shù)據(jù)結(jié)構(gòu)、再到 A* 算法與路徑可視化的完整鏈路適合用 three.js 做室內(nèi)導航、游戲 Demo、數(shù)字孿生巡檢路線的開發(fā)者參考。我習慣把這類項目拆成四步場景網(wǎng)格化、地圖數(shù)據(jù)生成、A* 尋路、路徑回填與角色移動。前兩步最容易被跳過也恰恰是整條鏈路里最容易出問題的地方。下面按這個順序展開每一步都給出可以直接跑的代碼和參數(shù)說明。2. 先選尋路圖網(wǎng)格、導航網(wǎng)格還是關鍵點2.1 三種尋路圖對比誰更適合這個示例尋路的第一步不是寫算法而是決定「算法跑在什么數(shù)據(jù)結(jié)構(gòu)上」。常見的做法有三種。第一種是網(wǎng)格圖Grid Graph把場景拆成均勻格子每個格子標記為可走或不可走。優(yōu)點是實現(xiàn)簡單、調(diào)試直觀、熱更容易缺點是精度受格子大小限制角色走路徑時會有一段一段的折線感。第二種是導航網(wǎng)格NavMesh用凸多邊形覆蓋可走區(qū)域路徑質(zhì)量和內(nèi)存表現(xiàn)都好但構(gòu)建和動態(tài)更新成本高three.js 里沒有內(nèi)置的 NavMesh 工具需要依賴較大體量的庫。第三種是關鍵點圖Waypoint Graph手工放置路徑點并連線適合固定路線比如展廳講解動線但不適合開放空間。從復現(xiàn)成本來看網(wǎng)格圖最適合做「示例」——場景里放幾個障礙物用 100 行代碼就能把場景變成地圖數(shù)據(jù)。這個示例選網(wǎng)格圖不是因為它是萬能解而是因為它能把尋路的核心邏輯完整暴露出來也讓后面替換成 NavMesh 時能看清差異。方案數(shù)據(jù)量動態(tài)更新路徑平滑度實現(xiàn)成本網(wǎng)格圖中等容易一般低導航網(wǎng)格小困難好高關鍵點圖很小取決于點位取決于布線低2.2 示例中的坐標系約定把 three.js 的 XZ 平面當成地圖3D 場景默認是 Y 軸向上的人在地面行走時只關心 X 和 Z 兩個軸。所以示例里把 XZ 平面當成「地圖平面」Y 軸只負責抬高路徑和角色。這個約定是整篇代碼的基礎你需要在一開始就想明白所有尋路計算都在二維空間進行只有渲染時才把坐標映射回三維。下面這段代碼搭建了最基礎的試驗場一個地面、兩個障礙物、一個起點標記和一個終點標記。我通常會把地面和障礙物參數(shù)集中放在一個配置對象里方便后面調(diào)格子大小和場景尺寸。// scene-setup.js const config { groundSize: 20, // 地面邊長單位米 gridSize: 1, // 尋路格子邊長單位米 obstacles: [ // 障礙物在地面坐標系的中心位置和尺寸 { x: -3, z: -2, w: 3, d: 2 }, { x: 4, z: 1, w: 2, d: 4 } ] }; const scene new THREE.Scene(); scene.background new THREE.Color(0xf0f0f0); // 地面用 GridHelper 輔助對齊再用 PlaneGeometry 做物理邊界 const gridHelper new THREE.GridHelper(config.groundSize, config.groundSize / config.gridSize); scene.add(gridHelper); const groundMat new THREE.MeshStandardMaterial({ color: 0xdddddd, side: THREE.DoubleSide }); const ground new THREE.Mesh( new THREE.PlaneGeometry(config.groundSize, config.groundSize), groundMat ); ground.rotation.x -Math.PI / 2; ground.position.y 0; scene.add(ground); // 障礙物按配置生成立方體y 方向高度僅影響視覺效果 config.obstacles.forEach((ob) { const box new THREE.Mesh( new THREE.BoxGeometry(ob.w, 1, ob.d), new THREE.MeshStandardMaterial({ color: 0xcc4444 }) ); box.position.set(ob.x, 0.5, ob.z); scene.add(box); });這段代碼里的config對象是后面所有邏輯的數(shù)據(jù)源頭地面尺寸決定數(shù)組行列數(shù)障礙物位置決定哪些格子不可走。ground.rotation.x -Math.PI / 2把平面從豎直轉(zhuǎn)為水平這是 three.js 里地面常用的處理方式。GridHelper只是視覺輔助真正的尋路數(shù)據(jù)不依賴它。這樣一個場景跑起來后你看到的只是一個普通的三維空間但它的邏輯結(jié)構(gòu)已經(jīng)具備可走的平面區(qū)域明確、障礙物坐標明確。下一步要做的就是把視覺世界翻譯成尋路算法能直接使用的二維數(shù)組。3. 搭試驗場把 three.js 場景轉(zhuǎn)成尋路用的二維地圖3.1 網(wǎng)格化過程從連續(xù)坐標到離散格子尋路算法不認識「米」和「厘米」它只認識「格子」。網(wǎng)格化要解決兩個問題一是把地面劃成多少行多少列二是每個格子對應的三維坐標范圍是多少。示例里地面是 20x20格子邊長是 1所以地圖是 20 行 x 20 列數(shù)組下標從 0 到 19。這里有一個容易犯迷糊的地方three.js 的世界坐標原點在地面正中心所以 X、Z 的范圍是 -10 到 10而數(shù)組下標是從 0 開始的。把世界坐標轉(zhuǎn)成數(shù)組下標需要做一次偏移和取整反過來把格子下標轉(zhuǎn)回世界坐標時要加上半個格子偏移讓路徑點落在格子中心而不是格子角上。// grid-map.js function worldToGrid(wx, wz, config) { const half config.groundSize / 2; const col Math.floor((wx half) / config.gridSize); const row Math.floor((wz half) / config.gridSize); return { row, col }; } function gridToWorld(row, col, config) { const half config.groundSize / 2; const x col * config.gridSize - half config.gridSize / 2; const z row * config.gridSize - half config.gridSize / 2; return { x, z }; } function buildMap(config) { const size config.groundSize / config.gridSize; const map []; for (let r 0; r size; r) { map.push(new Array(size).fill(0)); // 0 表示可走 } config.obstacles.forEach((ob) { const minX ob.x - ob.w / 2; const maxX ob.x ob.w / 2; const minZ ob.z - ob.d / 2; const maxZ ob.z ob.d / 2; for (let r 0; r size; r) { for (let c 0; c size; c) { const { x, z } gridToWorld(r, c, config); if (x minX x maxX z minZ z maxZ) { map[r][c] 1; // 1 表示不可走 } } } }); return map; }worldToGrid和gridToWorld是一對反函數(shù)調(diào)試時經(jīng)常要用它們互推驗證。buildMap里判斷格子是否被障礙物覆蓋時用的是「格子中心點是否在障礙物矩形內(nèi)」的邏輯。這樣做速度快但如果格子邊長比障礙物尺寸大很多會出現(xiàn)障礙物邊緣格子被誤標的情況后續(xù)章節(jié)會專門講這個避坑點。3.2 用 Raycaster 檢查真實障礙物讓地圖數(shù)據(jù)不靠手算手寫障礙物配置在前期的可行性驗證階段足夠用但真實場景里你往往拿不到干凈的坐標列表只有一堆 three.js 網(wǎng)格對象。這時候就不能再手動枚舉障礙物了我一般用Raycaster從場景里動態(tài)探測網(wǎng)格化和發(fā)射線檢測配合把「視覺上的碰撞體」直接變成「地圖上的障礙格」。// generate-map-by-raycast.js function detectObstacles(scene, config, height 1) { const size config.groundSize / config.gridSize; const map []; const raycaster new THREE.Raycaster(); const down new THREE.Vector3(0, -1, 0); for (let r 0; r size; r) { const rowData []; for (let c 0; c size; c) { const { x, z } gridToWorld(r, c, config); const origin new THREE.Vector3(x, height, z); raycaster.set(origin, down); const hits raycaster.intersectObjects(scene.children, false); const blocked hits.some((hit) hit.object ! groundRef); rowData.push(blocked ? 1 : 0); } map.push(rowData); } return map; }Raycaster從每個格子中心的正上方往下打一條射線如果射線先撞到的東西不是地面就認為這個格子被障礙物擋住了。height參數(shù)決定射線起點距離地面的高度示例里取 1 米對應障礙物高度的一半。注意groundRef需要是你保存的地面對象引用否則射線會把地面本身也算成障礙物。這個方法比手寫配置慢每次生成地圖要對每個格子做一次射線檢測20x20 的網(wǎng)格是 400 次體感不明顯如果網(wǎng)格細到 0.1 米200x200 就是 4 萬次會明顯卡頓。常見做法是場景加載和障礙物變化時才調(diào)用一次而不是每幀都跑。4. A* 在 three.js 坐標系里落地二維數(shù)組上的核心算法4.1 從起點到終點的 A* 實現(xiàn)OpenList、代價與啟發(fā)函數(shù)地圖數(shù)據(jù)準備好后A* 算法本身并不復雜。它維護兩個關鍵集合已探索的格子closedSet待探索的格子openList。每個格子記錄三個值從起點走到這里的實際代價g這個格子到終點的估算代價h兩者之和f。每次從openList里取出f最小的格子繼續(xù)擴展直到命中終點。下面是我在這個示例里用的實現(xiàn)刻意不用外部庫方便你看清每一步// astar-path.js function findPath(map, start, end) { const rows map.length; const cols map[0].length; const openList []; const closed new Set(); const cameFrom new Map(); const gScore {}; const fScore {}; const key (r, c) ${r},${c}; const startKey key(start.row, start.col); const endKey key(end.row, end.col); gScore[startKey] 0; fScore[startKey] heuristic(start, end); openList.push({ ...start, g: 0, f: fScore[startKey] }); while (openList.length 0) { openList.sort((a, b) a.f - b.f); const current openList.shift(); const curKey key(current.row, current.col); if (curKey endKey) { return reconstructPath(cameFrom, endKey); } closed.add(curKey); for (const neighbor of getNeighbors(current, map)) { const nKey key(neighbor.row, neighbor.col); if (closed.has(nKey) || map[neighbor.row][neighbor.col] 1) continue; const tentativeG current.g 1; if (tentativeG (gScore[nKey] ?? Infinity)) { cameFrom.set(nKey, curKey); gScore[nKey] tentativeG; fScore[nKey] tentativeG heuristic(neighbor, end); openList.push({ ...neighbor, g: tentativeG, f: fScore[nKey] }); } } } return null; // 無可行路徑 } function heuristic(a, b) { // 曼哈頓距離適合四方向移動 return Math.abs(a.row - b.row) Math.abs(a.col - b.col); } function getNeighbors(node, map) { const dirs [[-1, 0], [1, 0], [0, -1], [0, 1]]; const result []; for (const [dr, dc] of dirs) { const nr node.row dr; const nc node.col dc; if (nr 0 nr map.length nc 0 nc map[0].length) { result.push({ row: nr, col: nc }); } } return result; }這段代碼的代價計算很關鍵每一步的實際代價g固定 1因為當前只允許上下左右四個方向移動如果未來放開八個方向代價就要改成直走 1、斜走 1.414heuristic也要同步換成歐幾里得距離或切比雪夫距離。openList.sort每輪都排序在示例規(guī)模下沒問題地圖特別大時應該改用優(yōu)先隊列否則性能會隨節(jié)點數(shù)上升明顯劣化。4.2 四方向還是八方向路徑質(zhì)量與安全性的取舍這個示例默認只做四方向也就是角色只能沿 X 軸或 Z 軸方向移動。這樣路徑永遠是橫平豎直的安全性高不會出現(xiàn)斜穿障礙物角落的情況代價是路徑長度偏長、視覺上不夠自然。八方向允許斜著走路徑更短、更直但引入了一個經(jīng)典問題斜穿墻角。比如一個拐角處的障礙格它的右上角格子理論上可以從左上角斜著走到但角色實際移動時可能會貼著障礙物邊緣擦過去物理上不合理。常見做法是在八方向?qū)ぢ窌r加一個「拐角檢查」如果當前要向斜方向走先確認相鄰的正方向格子是否可走如果兩個正方向都被擋住就不允許斜走。實現(xiàn)時可以把getNeighbors換成下面的邏輯function getNeighbors8(node, map) { const rows map.length; const cols map[0].length; const dirs [ [-1, 0], [1, 0], [0, -1], [0, 1], [-1, -1], [-1, 1], [1, -1], [1, 1] ]; const result []; for (const [dr, dc] of dirs) { const nr node.row dr; const nc node.col dc; if (nr 0 || nr rows || nc 0 || nc cols) continue; if (map[nr][nc] 1) continue; // 斜向時檢查相鄰正方向是否存在障礙物防止穿墻 if (dr ! 0 dc ! 0) { if (map[node.row dr][node.col] 1 || map[node.row][node.col dc] 1) { continue; } } result.push({ row: nr, col: nc }); } return result; }這里斜向判定用的是「兩個正方向都要可走」的保守策略。用了getNeighbors8之后heuristic也應該從曼哈頓距離換成歐幾里得距離不然 A* 會傾向于先走正方向再走斜方向搜索效率降低。實際調(diào)試時可以在四方向和八方向之間來回切換對比路徑走向和長度差異你會更直觀地理解這兩種模式的代價模型。5. 路徑回填與角色移動把尋路結(jié)果畫進三維場景5.1 坐標回填數(shù)組下標重新變回 three.js 世界坐標A* 返回的是一串{ row, col }格子下標這些下標還不能直接丟給 three.js 渲染必須經(jīng)過gridToWorld轉(zhuǎn)換回世界坐標。常見的坑是忘記加 0.5 格偏移導致路徑點落在格子邊角角色走在邊界上時會和障礙物產(chǎn)生視覺穿插。// apply-path.js function buildPathPoints(path, config, height 0.5) { if (!path) return []; return path.map(({ row, col }) { const { x, z } gridToWorld(row, col, config); return new THREE.Vector3(x, height, z); }); }height參數(shù)把路徑抬高到地面上方 0.5 米這個值需要和角色模型的大小匹配。比如角色是一個半徑 0.3 米的圓柱體重心抬高 0.5 米就正好讓圓柱底部貼地如果角色換成更高的模型這個值要相應調(diào)整。拿到路徑點數(shù)組后我通常再用THREE.CatmullRomCurve3做一次曲線插值把折線變成平滑曲線。這樣角色移動時不會在每個格子中心點突然轉(zhuǎn)向視覺上自然很多。需要說明的是曲線平滑只改變視覺路徑不會改變尋路結(jié)果實際碰撞檢測仍然以格子為準。// smooth-path.js function createSmoothLine(points, segmentsPerPoint 8) { const curve new THREE.CatmullRomCurve3(points, false, catmullrom, 0.5); const curvePoints curve.getPoints(points.length * segmentsPerPoint); const geometry new THREE.BufferGeometry().setFromPoints(curvePoints); return new THREE.Line(geometry, new THREE.LineBasicMaterial({ color: 0x2255ff })); }CatmullRomCurve3的第三個參數(shù)0.5是張力系數(shù)數(shù)值越大曲線越緊貼原始折線越小越松弛。如果設置的張力太后路徑會切穿障礙物角落張力不足則會出現(xiàn)多余的繞彎。這里沒有完美數(shù)值只能用一兩個簡單障礙物場景反復驗證曲線沒有超出可走區(qū)域。5.2 角色沿路徑移動時間參數(shù)與速度控制路徑畫出來只是靜態(tài)展示要讓示例「活」起來還需要讓角色從起點移動到終點。常見的做法是用curve.getPointAt(t)獲取曲線上某一位置坐標其中t從 0 變化到 1而每幀t的增長速度由角色移動速度和路徑總長度決定。// move-along-path.js let t 0; const speed 2; // 單位米/秒 function updateMove(delta, curve, robot) { const totalLength curve.getLength(); const segment (speed * delta) / totalLength; t Math.min(t segment, 1); const pos curve.getPointAt(t); robot.position.copy(pos); // 讓角色朝向路徑方向需要先采樣下一幀位置 const lookAhead curve.getPointAt(Math.min(t 0.01, 1)); robot.lookAt(lookAhead); }delta是 requestAnimationFrame 里計算出的上一幀耗時直接用它乘速度能讓移動速度與幀率無關。curve.getPointAt是基于弧長均勻采樣不會出現(xiàn)曲線拐彎處移動過快或過慢的問題這一點比getPoint(t)更適合移動控制。讓角色lookAt下一點是為了讓它始終面朝路徑方向如果角色模型的方向軸不是 Z 軸正方向你可能需要再旋轉(zhuǎn) 180 度或 90 度。6. three.js 尋路示例里躲不開的避坑與排查6.1 格子坐標與世界坐標偏移了半個格子現(xiàn)象起點標記和終點標記都放在格子中心但角色實際走的路徑明顯偏向格子的某一側(cè)沿著障礙物邊緣擦過去。原因worldToGrid用Math.floor取整把世界坐標映射到了格子的左下角索引但gridToWorld直接按col * gridSize計算沒有加半格偏移導致同一個世界坐標和格子坐標之間往返映射相差半個格子。解決統(tǒng)一使用本文里的gridToWorld帶 gridSize / 2的版本。調(diào)試時可以寫幾個斷言比如驗證gridToWorld(0, 0)的結(jié)果在worldToGrid之后仍然回到(0, 0)這一致性。6.2 對角線路徑穿過障礙物墻角現(xiàn)象使用八方向?qū)ぢ泛舐窂皆谡系K物拐角處斜著穿過角色看起來擦著墻角過去。原因只檢查了目標格子是否可走沒有檢查斜向移動時兩側(cè)的格子。這是一個非常典型的翻車點幾乎每個第一次做八方向的人都遇到過。解決在斜向移動時強制要求兩個正方向鄰居都可行走。也就是把getNeighbors8里的拐角檢查補上。如果你是先寫完了findPath才發(fā)現(xiàn)這個問題不要僥幸加檢查后再重新生成路徑。6.3 地圖數(shù)據(jù)比視覺場景更小或更大現(xiàn)象地圖邊界和地面不完全對齊角色走到地圖邊緣時懸空或陷進地面。原因buildMap里的格子中心點判斷在障礙物貼著地圖邊緣時會把地圖之外的區(qū)域也算成可行走區(qū)域或者在地面邊緣用 Raycaster 檢測時射線被地面之外的環(huán)境誤傷。解決buildMap遍歷時把邊界判斷加上確保col和row只在有效索引范圍內(nèi)。另 一種做法是把網(wǎng)格范圍縮小半個格子讓最外圍格子中心始終落在場景地面積以內(nèi)。6.4 角色移動時在路徑轉(zhuǎn)折點抖動現(xiàn)象角色到達某個路徑點后轉(zhuǎn)向時會出現(xiàn)輕微抖動或停頓尤其在用CatmullRomCurve3平滑后的路徑上更明顯。原因時間參數(shù)t按弧長均勻推進但lookAt采樣點在曲線曲率大的地方跨越了過大的角度導致模型瞬間旋轉(zhuǎn)幅度超出預期看起來像抖動。如果你用的是普通直線插值而不是弧長插值這種情況更容易出現(xiàn)。解決一是給lookAt加一個旋轉(zhuǎn)插值不直接硬切朝向而是用lerp或四元數(shù)slerp做平滑過渡二是檢查路徑點是不是存在幾乎重合的重復點去重后再生成曲線。7. 讓示例進階動態(tài)障礙、平滑路線與驗證方法7.1 動態(tài)障礙物觸發(fā)的局部重尋路靜態(tài)地圖跑通之后下一步一般是讓障礙物可以移動比如巡檢場景里臨時出現(xiàn)的車輛。常見做法是保留場景里所有動態(tài)障礙物對象每幀或每隔幾幀更新它們在網(wǎng)格地圖上的標記如果發(fā)現(xiàn)角色當前路徑上的某個格子被占據(jù)就重新執(zhí)行一次findPath。實現(xiàn)上不必全圖重掃——我一般只在障礙物位置變化時把它新舊兩個位置所占的格子做增量更新。地圖數(shù)組里預先存一個occupiedBy字段記錄當前占用者是誰這樣移除和添加劇烈運動時不容易誤清他人的格子。要注意的是重尋路次數(shù)不能太頻繁路徑代價大時它可以成為性能瓶頸至少限制到每秒檢測兩次。7.2 驗證路徑質(zhì)量的三個指標路徑能跑通不代表路徑合格。我通常在把示例交給下一個環(huán)節(jié)之前做三件驗證的事。第一檢查路徑是否與所有障礙物邊界保持至少一個格子的安全距離這一步用腳標遍歷路徑點即可。第二計算路徑實際長度與曼哈頓距離的比值在無障礙場景里這個比值應該接近 1偏離過大多半是啟發(fā)函數(shù)出了問題。第三在角色移動過程中持續(xù)做射線檢測確認角色模型每一幀都沒有與障礙物相交這比靜態(tài)檢查更能發(fā)現(xiàn)平滑曲線穿模。function validatePath(path, map) { if (!path) return false; for (let i 0; i path.length; i) { const cell path[i]; if (map[cell.row][cell.col] 1) return false; } return true; }這一步看起來樸素但它往往是最后一個能攔住問題的手段。很多路徑在生成時是合法的卻因為平滑處理或角色尺寸比格子大實際移動時發(fā)生了穿插。7.3 最后的實戰(zhàn)習慣我做過幾個 three.js 尋路類的演示項目踩得最多的不是 A* 本身而是坐標系和數(shù)據(jù)映射這類「看起來簡單、錯起來難查」的地方?，F(xiàn)在的習慣是每寫一步轉(zhuǎn)換函數(shù)都要配一個斷言函數(shù)絕不靠肉眼去驗證坐標對不對。網(wǎng)格尺寸越大系統(tǒng)看起來越流暢但它掩蓋的路徑抖動越嚴重尺寸越小路徑越精細但性能和內(nèi)存會成倍上漲。建議先從相對粗的格子啟動再逐步加密直到路徑開起來自然為止。希望這篇 three.js 算法尋路示例的拆解能幫你少走幾段彎路回頭可以把自己的驗證和坑經(jīng)驗也在評論區(qū)里講出來互相補盲。本文還有配套的精品資源點擊獲取