Found

Found 是一个由 Dijkstra 算法实现的路径搜索库，用于在有向加权图中查找最短路径。它可以帮助你找到两点之间的最短路径，以及两点之间的距离。

安装

使用 npm 安装:

npm install yuka-found

或者，直接从 Github 下载源码，将 dist/found.min.js 加入到你的项目中。

<script src="path/to/found.min.js"></script>

使用

在使用前需要先创建 Graph（图） 对象。Graph 对象包含节点（Node） 和边（Edge），我们需要使用 Graph 对象来创建节点和边。

import { Graph, Node, Edge } from 'yuka';

// 创建一个空的图
const graph = new Graph();

// 创建两个节点
const node1 = new Node( 'node1' );
const node2 = new Node( 'node2' );

// 创建一条边
const edge = new Edge( node1, node2, 10 );

// 将节点和边添加到图中
graph.add( node1, node2, edge );

之后，我们可以调用 Dijkstra 方法来查找最短路径。该方法接受四个参数：起点、终点、权重计算回调、距离计算回调。

graph.nodes.forEach( node => node.reset() );

const dijkstra = new Dijkstra();
const path = dijkstra.search( node1, node2, getCost, getDistance );

console.log( path );

其中，getCost 回调用于计算两个节点之间的权重，getDistance 回调用于计算两个节点之间的距离。

function getCost( nodeA, nodeB, edge ) {

    // 计算两个节点之间的权重
    return edge.cost;

}

function getDistance( nodeA, nodeB ) {

    // 计算两个节点之间的距离
    return nodeA.position.distanceTo( nodeB.position );

}

API

Dijkstra( reverse )

• reverse - 是否搜索反向图。默认为 false。

search( start, goal, getCost, getDistance )

• start - 查找的起点。
• goal - 查找的终点。
• geCost - 权重计算回调函数。
• getDistance - 距离计算回调函数。

返回值：指定起点和终点的最短路径。

Node( name )

• name - 节点的名称。

cost

节点的开销值，用于计算两个节点之间的权重。

reset()

重置节点的状态，使它可以被再次搜索。

Edge( from, to, cost )

• from - 起点节点。
• to - 终点节点。
• cost - 边的开销值，用于计算两个节点之间的权重。

示例

可以在 CodePen 上查看 Found 的在线演示示例。

<div id="output"></div>

<script src="https://cdn.jsdelivr.net/npm/yuka/build/yuka.module.js"></script>
<script src="https://unpkg.com/yuka-found@1.0.2/dist/found.min.js"></script>
<script>

const Vector3 = yuka.Vector3;
const Graph = yuka.Graph;
const Node = yuka.Node;
const Edge = yuka.Edge;
const Dijkstra = yuka.Dijkstra;

// 创建图
const size = 10;
const graph = new Graph();

for ( let i = 0; i < size * size; i ++ ) {

    const x = i % size;
    const y = Math.floor( i / size );
    const node = new Node( `${x},${y}` );
    node.position.set( x, 0, y );

    graph.add( node );

}

for ( let i = 0; i < size * size; i ++ ) {

    const x1 = i % size;
    const y1 = Math.floor( i / size );

    // 右连通边
    const x2 = x1 + 1;
    const y2 = y1;

    if ( x2 < size ) {

        const node1 = graph.getNodeById( `${x1},${y1}` );
        const node2 = graph.getNodeById( `${x2},${y2}` );

        const edge = new Edge( node1, node2, 1 );
        graph.add( edge );

    }

    // 下连通边
    const x3 = x1;
    const y3 = y1 + 1;

    if ( y3 < size ) {

        const node1 = graph.getNodeById( `${x1},${y1}` );
        const node2 = graph.getNodeById( `${x3},${y3}` );

        const edge = new Edge( node1, node2, 1 );
        graph.add( edge );

    }

}

// 查找最短路径
const start = graph.getNodeById( '0,0' );
const end = graph.getNodeById( '9,9' );

graph.nodes.forEach( node => node.reset() );

const dijkstra = new Dijkstra();
const path = dijkstra.search( start, end, getCost, getDistance );

console.log( path );

function getCost( nodeA, nodeB ) {

    return nodeB.cost;

}

function getDistance( nodeA, nodeB ) {

    const a = nodeA.position;
    const b = nodeB.position;

    return Math.sqrt( ( b.x - a.x ) ** 2 + ( b.z - a.z ) ** 2 );

}

// 输出结果
const output = document.getElementById( 'output' );

for ( let i = 0; i < path.length; i ++ ) {

    output.innerHTML += `${path[ i ].id} -> `;

}

</script>