简介这是一份基于three.js与Vue实现的3D寻路算法示例项目面向WebGL、前端开发及游戏、VR/AR方向的学习者用于理解如何在三维场景中集成A星、深度优先和广度优先等路径规划算法。项目包含完整前端工程涵盖场景搭建、网格建模、障碍物布局以及算法逻辑与可视化交互通过Vue管理界面状态可切换不同算法并实时观察路径差异。压缩包共71个文件核心为js与vue源码配套png、svg、jpg等图形素材、html入口及工程配置文件整体仅3.56MB目录结构清晰便于直接运行与二次开发。已有776人学习下载。通过学习该示例可掌握three.js基础场景构建、Vue组件化开发与状态管理同时深化对A星启发式搜索、深度优先遍历和广度优先遍历三种算法在三维空间中表现的理解。示例自带Vue CLI工程配置、PWA注册与样式文件适合作为课程设计、技术演示或进阶实战参考。1. 三维网格寻路从格子模型到three.js可执行路径在基于three.js的三维可视化页面里用户点一个目标点场景中的单位需要绕过障碍走过去。二维平面的A算法跑得很顺但一进入three.js的3D坐标系就出问题格子怎么划分、障碍物怎么登记、点击选点怎么准确落到地面、算出来的路径怎么画成线。threePathfinding这个示例把three.js、Vue和A、DFS、BFS放在一起跑通了一条完整链路。压缩包里的源码是标准Vue工程结构入口在index.html和main.js页面逻辑在App.vuethree.js场景与算法实现都在src目录下。这篇按实际结构拆开讲先讲网格建模再讲交互与可视化最后做算法对照和排坑。适合正在做三维可视化、工业数字孪生、WebGL小游戏的人拿这套代码换掉场景和障碍物就能复用。2. 把three.js场景映射成A*搜索网格格子划分、障碍登记与邻居筛选A*搜索的输入不是连续的three.js坐标而是离散网格。threePathfinding中的地图视图被切分成格子阵列可通行状态用一个二维数组记录。动手前先定三件事cellSize取多大、障碍物覆盖哪些格子、斜向移动要不要允许。这三个参数直接决定路径质量和搜索时间。2.1 格子尺寸与坐标换算做一张a星寻路地图第一个要定的就是cellSize也就是单个格子的世界单位边长。cellSize太大窄通道会被吞掉路径贴着墙走太小节点数平方增长搜索时间和内存都上去了。常见做法是先量场景里最小通道的宽度取其三分之一到二分之一。比如单位宽1通道宽3cellSize取1即可如果通道宽10取2到3会让路径更顺滑。three.js场景的x轴和z轴构成水平面y轴作为高度。换算坐标时用Math.floor// cell.js —— 世界坐标与格子坐标互转 const cellSize 1; function worldToCellX(x) { return Math.floor(x / cellSize); } function worldToCellZ(z) { return Math.floor(z / cellSize); }这里要考虑负坐标。Math.floor对负值向负无穷取整-0.5会变成-1。如果地图原点不在世界的(0,0)点换算前要先减掉地图偏移量或者把场景整体平移到正象限否则格子数组会出现负索引。更稳妥的方案是创建场景时就把所有坐标做一次平移让最小坐标落在(0,0)这样所有格子索引都是非负的。2.2 障碍物登记与网格数据接口网格数据用二维数组表示0为可走1为不可走。threePathfinding里的buildGrid函数读取three.js场景内带包围盒的物体把包围盒投影到格子坐标后整块标记// buildGrid.js —— 拿包围盒批量登记障碍 export function buildGrid({ cols 40, rows 40, cellSize 1, boxes [] }) { const grid Array.from({ length: cols }, () Array.from({ length: rows }, () 0) ); boxes.forEach((box) { const minC Math.floor(box.min.x / cellSize); const maxC Math.floor(box.max.x / cellSize); const minR Math.floor(box.min.z / cellSize); const maxR Math.floor(box.max.z / cellSize); for (let c minC; c maxC; c) { for (let r minR; r maxR; r) { if (c 0 c cols r 0 r rows) { grid[c][r] 1; } } } }); return grid; }这段的核心是把three.js的AABB包围盒坐标取整成格子范围双层循环把格子标成1。边界判断不能省物体的包围盒经常超出地图范围。实际项目里障碍物可能是不同高度的柱子或墙体包围盒的min.y和max.y也能参与判断如果某个格子上方的净空高度小于单位高度直接标成不可走这比把所有物体都当实心墙更贴近真实需求。如果不想让路径贴着障碍物边缘走可以在标记时向外多扩一圈常见做法是让minC减1、maxC加1相当于膨胀一格给单位预留半径余量。这个膨胀参数在项目里比调cellSize更直观。2.3 邻居筛选与墙角穿越A*的扩展过程要生成当前格子的邻居列表。基础写法是遍历周围8个格子但允许斜走时要处理墙角穿越。斜穿墙角类似当前格在(3,3)、目标格在(4,4)而(4,3)或(3,4)是障碍物角色直接穿墙过去。getNeighbors里要显式检查这两个正交邻居// neighbors.js —— 带墙角检测的8方向邻居 export function getNeighbors(grid, c, r, allowDiagonal true) { const cols grid.length; const rows grid[0].length; const neighbors []; const dirs4 [[1, 0], [-1, 0], [0, 1], [0, -1]]; const dirs8 [ ...dirs4, [1, 1], [1, -1], [-1, 1], [-1, -1] ]; for (const [dc, dr] of allowDiagonal ? dirs8 : dirs4) { const nc c dc; const nr r dr; if (nc 0 || nc cols || nr 0 || nr rows) continue; if (grid[nc][nr] 1) continue; // 斜向移动时检查两侧正交格防止穿墙角 if (dc ! 0 dr ! 0) { if (grid[c dc][r] 1 || grid[c][r dr] 1) continue; } neighbors.push({ c: nc, r: nr, cost: dc ! 0 dr ! 0 ? 1.414 : 1 }); } return neighbors; }斜走代价取根号2的近似值1.414这样A不会盲目偏爱斜线。如果允许斜走但代价仍设成1路径会出现大量45度折线。三维场景的地形起伏也能用cost惩罚比如到达格与当前格高度差超过某个阈值时把cost乘1.5或者直接标为不可通行这是把二维A扩展到起伏地形最简单的方式不需要真的把网格变成三维体素。2.4 启发式选择与二叉堆开放集A*的效率取决于开放列表的排序方式。threePathfinding里用二叉堆维护f值f g hg是起点到当前格的实际代价h是当前格到目标的估计代价。h的选择直接决定搜索方向三种常见公式各有适用条件启发式公式适用场景曼哈顿|dx| |dy|只允许四方向移动时h不会高估欧几里得sqrt(dx² dy²)允许斜走路径更贴近直线切比雪夫max(|dx|, |dy|)允许八方向但按步数计费时three.js场景里单位可以自由转向一般用欧几里得。h不能高估实际代价否则会错失真正的最短路径。把h乘以权重weight还能改变行为weight大于1时搜索更快但结果可能变长1.0到1.5之间是常见的速度与质量平衡点。// aStar.js —— 基于二叉堆的A*主循环 function aStar(grid, start, goal, options {}) { const { heuristic euclidean, weight 1.0 } options; const startKey start.c , start.r; const goalKey goal.c , goal.r; const gScore new Map([[startKey, 0]]); const cameFrom new Map(); const closedSet new Set(); const openSet new MinHeap(); openSet.push({ f: heuristicCost(start, goal, heuristic), c: start.c, r: start.r }); while (!openSet.isEmpty()) { const current openSet.pop(); const curKey current.c , current.r; if (curKey goalKey) { return reconstructPath(cameFrom, curKey); } if (closedSet.has(curKey)) continue; closedSet.add(curKey); for (const n of getNeighbors(grid, current.c, current.r)) { const nKey n.c , n.r; if (closedSet.has(nKey) || grid[n.c][n.r] 1) continue; const tentativeG gScore.get(curKey) n.cost; if (tentativeG (gScore.get(nKey) ?? Infinity)) { cameFrom.set(nKey, curKey); gScore.set(nKey, tentativeG); openSet.push({ f: tentativeG heuristicCost(n, goal, heuristic) * weight, c: n.c, r: n.r }); } } } return []; // 开放集耗尽说明终点不可达 }closedSet记录已经展开过的格子避免重复处理。?? Infinity给未访问的格子一个无穷大的默认g值。二叉堆里的元素带f、c、r三个字段堆只按f排序同一个格子被多次加入堆时靠closedSet去重。不用数组找最小值的原因是40×40网格上openSet峰值可能有上千个元素线性扫描的时间在复杂场景里会被明显放大换成二叉堆后插入和弹出都是对数级操作这也是把A*用到大型地图的基本要求。3. Vue组件与three.js场景联动点击选点、路径可视化与渲染更新纯three.js也能做交互但换成Vue工程后UI状态、按钮切换、算法选择这些逻辑跟WebGL场景解耦代码好拆。threePathfinding的目录布局已经体现了这种分工。3.1 目录结构与职责划分压缩包里的工程是标准Vue项目结构public/index.html是HTML模板入口src/main.js负责创建Vue根实例同时初始化three.js的Scene、Camera、Renderersrc/components/App.vue持有场景对象引用渲染操作按钮和状态面板src/scss放全局样式src/assets放静态资源vue.config.js管开发服务器代理和构建行为。这里最容易踩的坑不要把THREE.Scene对象放进Vue的data里做响应式。three.js内部对象属性非常多Vue会对data做响应式代理把整个Scene塞进去会产生大量无意义的getter/setter依赖收集页面明显掉帧。常见做法是把scene、camera、renderer放进一个普通对象在App.vue的mounted生命周期里创建并挂到this上不参与响应式更新。只有真正需要传给three.js的坐标和格子数据才放进data。这样组件重渲染时WebGL场景完全不受影响。3.2 Raycaster拾取从屏幕坐标到格子坐标点击canvas选点第一步是把鼠标的屏幕坐标换算成归一化设备坐标再用THREE.Raycaster从相机位置向点击方向发射射线与地面Mesh求交// picker.js —— 点击地面回传格子坐标 const raycaster new THREE.Raycaster(); const pointer new THREE.Vector2(); canvas.addEventListener(click, (event) { const rect canvas.getBoundingClientRect(); pointer.x ((event.clientX - rect.left) / rect.width) * 2 - 1; pointer.y -((event.clientY - rect.top) / rect.height) * 2 1; raycaster.setFromCamera(pointer, camera); const hits raycaster.intersectObject(ground); if (hits.length 0) return; const p hits[0].point; const col Math.floor(p.x / cellSize); const row Math.floor(p.z / cellSize); if (grid[col]?.[row] 1) return; // 落在障碍物上忽略 onPick({ col, row }); });归一化坐标的y方向与屏幕坐标相反所以pointer.y前面要加负号漏掉这一步点击位置会上下颠倒。if (hits.length 0)处理的是相机视角边缘或地面被其他物体遮挡的情况。检查grid[col]?.[row] 1是防止把起点终点设在障碍物里这个验证在三维场景里比二维更关键因为用户点击的可能是墙壁的侧面hits[0].point落在障碍物模型上换算出来的格子自然也是不可走的。3.3 路径描线与沿路径动画算法返回的是格子坐标数组画线前要转换成three.js世界坐标取每个格子中心点// drawPath.js —— 把格子路径画成3D线条 export function drawPath(scene, path, cellSize, heightAt () 0) { const points path.map((p) { const x (p.c 0.5) * cellSize; const z (p.r 0.5) * cellSize; return new THREE.Vector3(x, heightAt(x, z), z); }); const geometry new THREE.BufferGeometry().setFromPoints(points); const material new THREE.LineBasicMaterial({ color: 0x00ffaa }); const line new THREE.Line(geometry, material); scene.add(line); }加0.5是把路径线落在格子正中避免贴边。heightAt作为高度查询函数传入没有地形起伏时直接返回0或地面高度。重复点击会不断add新的Line对象旧线条堆积在场景里会拖慢渲染所以画线前要先按名称或引用移除上一次的结果。路径点很多时折线转角生硬可以改用THREE.CatmullRomCurve3平滑后再采样。如果要让角色沿路径移动在一个动画循环里逐帧插值位置和朝向function animateAlong(pathPoints) { const clock new THREE.Clock(); let index 0; function tick() { const dt clock.getDelta(); index dt / 0.1; // 每段0.1秒走完 if (index pathPoints.length) return; const p pathPoints[Math.floor(index)]; mesh.position.copy(p); renderer.render(scene, camera); requestAnimationFrame(tick); } tick(); }这样寻路结果就变成了可移动的路线而不是一条静态线段。速度由每段耗时控制改成真正的移动速度时用dt * speed / cellSize换算成格子索引增量即可。4. A*、BFS、DFS在同一张网格上的实际差异同一个grid数据换掉搜索策略观察到的结果完全不同。threePathfinding里同时实现了三种算法适合直接对照着看。4.1 三种策略的遍历方式BFS用先进先出队列按层扩散保证路径步数最少但需要在内存里保留一整层的节点网格大时队列很长。DFS用栈一条道走到黑内存占用最小但路径可能绕远路在迷宫型地图里尤其明显。A*用优先队列每次挑f值最小的格子扩展相当于一条被启发式拽着往目标走的搜索扩展节点数通常远小于BFS。在三维场景里这个差异会被放大。单位在开阔区域绕一个L形障碍时BFS会把L形外侧的格子全部扩展一遍A因为启发式指向目标会直奔目标方向只探索真正需要确认的区域。网格越大差距越明显。很多3A游戏里的导航系统本质上就是这套A逻辑的放大版只是加了地图分块和路径平滑。4.2 一次对照实验的读数用40×40网格、8个4×4障碍块起点(0,0)终点(39,39)跑几组数据读数是典型区间算法扩展节点数路径长度说明A*欧几里得weight1约800最短对角线路线终点方向明确A*曼哈顿约1200略长只允许四方向时的最短BFS约1600最短四方向下保证最短但扩展面积大DFS几百到数千明显偏长跟邻居遍历顺序强相关不稳定BFS和禁用斜走的A会给出同样的最短路径因为两者都只允许四方向移动但BFS扩展范围更大。DFS运气好时扩展节点很少路径却可能绕路两倍以上。实际项目里追求路径质量A是性价比最高的选择地图极小且要求实现极简BFS足够DFS一般只用来确认是否存在通路不用于生成正式路径。如果给障碍物做了外扩膨胀扩展节点数还会整体上升路径也会相应远离墙体这个现象在三维场景里比二维更明显因为可走面积被压缩了。4.3 在Vue里切换算法时的参数迁移三种算法共用同一个grid和同一个getNeighbors切换只需要换入口函数。App.vue里的算法切换按钮最终调用的是同一段分发逻辑// solver.js —— 按mode返回不同搜索器 export function solve(grid, start, goal, mode) { if (mode astar) { return aStar(grid, start, goal, { heuristic: euclidean, weight: 1 }); } if (mode bfs) { return bfs(grid, start, goal); } if (mode dfs) { return dfs(grid, start, goal); } }bfs和dfs实现里同样依赖getNeighbors区别只在数据结构bfs用数组做队列shift()出队dfs用数组做栈pop()出栈。切换后最值得注意的是对角移动策略是否一致。A*默认走斜线BFS和DFS也应当开对角否则路径风格完全不同对比没有意义。Vue侧只用mode字符串驱动渲染three.js场景部分不需要任何改动。5. 3D寻路上手坑拾取穿模、高度投影和搜索热区调试最后写几个实际跑demo时最容易翻车的点都是three.js场景里才会遇到的。5.1 射线拾取的命中判断点canvas选地面时如果场景里加了半透明覆盖层或粒子系统raycaster.intersectObject(ground)的hits可能为空或者第一个交点不是地面。多物体场景里可以给ground设置一个唯一的name然后在hits里按name过滤。另一个隐患是点击落在障碍物侧面交点坐标的y值偏高换算成格子坐标后落在障碍物边缘。处理方式先判grid值再根据相交点法线方向判断是否朝上法线y分量大于0.5才认为是水平地面。同一把射线打在不同高度的Mesh上取最近交点还是最远交点也要事先明确否则点击视角边缘时经常会选到背景物体。5.2 路径贴合地形高度地形有起伏时路径点高度不能全取0。heightAt函数最简单的实现是从一个二维高度数组读取再做双线性插值。没有高度图的情况下可以在每个路径点上方朝下发射射线打到地形Mesh上取交点y值function heightAt(x, z) { raycaster.set(new THREE.Vector3(x, 100, z), new THREE.Vector3(0, -1, 0)); const hit raycaster.intersectObject(terrain)[0]; return hit ? hit.point.y : 0; }射线起点y取100是假设场景最高点不会超过这个值实际使用时改成场景包围盒的max.y更稳妥。这个函数在路径点少的时候没问题几百个点逐点打射线会有明显开销应该把结果缓存到Map里key用col _ row。同一个格子只会被查询一次后续直接读缓存。路径线贴地后还可以加一个Y轴偏移避免与地形表面发生z-fighting。5.3 用热图看算法到底扩展了哪些格子调A时最想知道的是路径为什么绕远路、搜索为什么慢。把closedSet里的格子用半透明色块渲染出来一眼就能看出问题A应该只有一条窄带直扑目标如果热区扩散成一大片说明启发式失效通常是h高估或者weight设得过大。这个调试方法比打印坐标直观得多。function renderSearchHeat(expanded, cellSize, scene) { const geometry new THREE.PlaneGeometry(cellSize * 0.8, cellSize * 0.8); const material new THREE.MeshBasicMaterial({ color: 0xff8800, transparent: true, opacity: 0.25 }); const instanced new THREE.InstancedMesh(geometry, material, expanded.length); expanded.forEach((cell, i) { const matrix new THREE.Matrix4().setPosition( (cell.c 0.5) * cellSize, 0.05, (cell.r 0.5) * cellSize ); instanced.setMatrixAt(i, matrix); }); scene.add(instanced); }用InstancedMesh是为了让几千个色块的draw call保持在一次以内直接逐个new Mesh加进场景会卡到个位数帧率。y坐标抬到0.05避免和地面z-fighting透明度25%保证底下网格还能看到。把renderSearchHeat挂到搜索结束后的渲染流程里配合weight和网格密度的调整排除路径误差的速度比反复看console输出高一个量级。本文还有配套的精品资源点击获取