graph

介绍

Yuka js库中的 NavMesh （导航网格）是一种寻路技术，可用于在3D场景中寻找路径。NavMesh在寻路时使用一组互相连接的三角形，称为“网格”，来表示寻路空间。

在 NavMesh 中，这些网格被组织成一张图或者叫做“导航网格图”。这张图包含了所有可能的路径和路径连接情况，以及各点之间的距离。在这张图上，计算机可以使用最短路径算法来找到最优的路径，从而帮助角色或物体在场景中穿过迷宫、过河、跳过障碍等。

实现

在 Yuka js中，我们可以使用 NavMesh 类创建一个导航网格。导航网格的实现基于众多的网格三角形组成，每个三角形上有点，而绕过这些点的路径就是寻路。

导航网格图构建中需要几个步骤。

1. 首先，我们需要生成一个有三角形组成的多边形墙体，通常成为“polygon soup” （三角网格）。
2. 然后进行光线追踪，寻找多边形之间的可走区域。
3. 最后，我们要构建 triangles ，将所有可行的三角形组成一个导航网格。

在导航网格图构建完成后，我们便可以借助最短路径算法来搜索最优路径了。

使用

以下是导航网格的一个示例，演示了如何在场景中沿着导航网格行进。代码如下：

const navMesh = new NavMesh();

// 添加顶点：
navMesh.addVertex( 0, 0, 0 );
navMesh.addVertex( 1, 0, 0 );
navMesh.addVertex( 0, 1, 0 );
navMesh.addVertex( 1, 1, 0 );

// 添加网格：
navMesh.addTriangle( 0, 1, 2 );
navMesh.addTriangle( 1, 3, 2 );

// 创建导航网格：
navMesh.build();

// 创建一个对象并分配开始和结束点：
const start = new Vector3( 0, 0, 0 );
const end = new Vector3( 1, 1, 0 );
const path = navMesh.findPath( start, end );

在这个例子中，我们首先添加了四个三维点，将它们传递给 NavMesh 对象（ navMesh ）以创建一个网格。然后我们使用 build() 方法来构建导航网格。接着，使用 findPath() 方法，将起点和终点作为参数，便可以获取到一条从起点到终点的最短路径。

总结

通过使用导航网格图，Yuka js库实现了一个简单又实用的寻路算法。无论是在游戏场景、虚拟现实环境或者其他应用场合，导航网格图都是一个高效且灵活的寻路解决方案。