getSearchTree

简介

getSearchTree是Yuka js库中的一个BFS算法函数，用于搜索图形结构（如ANode），返回根据搜索起点生成的树形结构以及每个节点的距离和父节点。

语法

const { tree, distances, parents } = getSearchTree( startNode, accessNeighbors, isGoalReached );

参数

• startNode（必需）：搜索的起点节点。
• accessNeighbors（必需）：访问相邻节点的函数，返回一个相邻节点的列表。
• isGoalReached（必需）：判断是否到达目标节点的函数，返回true或false。

返回值

一个对象包含以下属性：

• tree：搜索生成的树形结构（类似于BFS输出）。
• distances：每个节点的距离信息对象，包含每个节点到起点的距离。
• parents：每个节点的父节点信息对象，包含每个节点的父节点。

示例

假设我们处理一个迷宫的问题，需要在一个二维场景中寻找从一个节点到达目标节点的最短路径。我们可以声明以下函数：

function createAccessNeighborsFunction( scene ) {

  return function( node ) {

    const { x, y } = node;

    const neighbors = [];

    if ( scene[ y - 1 ][ x ] === 0 ) {

      neighbors.push( { x, y: y - 1 } );

    }

    if ( scene[ y + 1 ][ x ] === 0 ) {

      neighbors.push( { x, y: y + 1 } );

    }

    if ( scene[ y ][ x - 1 ] === 0 ) {

      neighbors.push( { x: x - 1, y } );

    }

    if ( scene[ y ][ x + 1 ] === 0 ) {

      neighbors.push( { x: x + 1, y } );

    }

    return neighbors;

  };

}

function isGoalReachedFunction( node ) {

  return node.x === targetPosition.x && node.y === targetPosition.y;

}

其中，accessNeighborsFunction函数访问相邻节点并返回它们，isGoalReachedFunction函数判断是否到达目标节点。

我们可以定义以下变量：

const scene = [
  [ 0, 0, 1, 0, 0 ],
  [ 0, 0, 0, 0, 0 ],
  [ 0, 1, 1, 1, 0 ],
  [ 0, 0, 1, 0, 0 ],
  [ 0, 0, 0, 0, 0 ],
];

const startPosition = { x: 0, y: 0 };

const targetPosition = { x: 4, y: 4 };

我们可以调用以下代码来执行搜索：

const accessNeighbors = createAccessNeighborsFunction( scene );

const { tree, distances } = getSearchTree( startPosition, accessNeighbors, isGoalReachedFunction );

tree和distances对象将包含树形结构和节点距离信息。