AABB
AlignmentBehavior
ArriveBehavior
AStar
BFS
BoundingSphere
BVH
BVHNode
Cell
CellSpacePartitioning
CohesionBehavior
CompositeGoal
ConvexHull
Corridor
CostTable
DFS
Dijkstra
Edge
EntityManager
EvadeBehavior
EventDispatcher
Behavior
FollowPathBehavior
FuzzyAND
FuzzyCompositeTerm
FuzzyFAIRLY
FuzzyModule
FuzzyOR
FuzzyRule
FuzzySet
FuzzyTerm
FuzzyVariable
FuzzyVERY
GameEntity
Goal
GoalEvaluator
Graph
GraphUtils
HalfEdge
HeuristicPolicyDijkstra
HeuristicPolicyEuclid
HeuristicPolicyEuclidSquared
HeuristicPolicyManhattan
InterposeBehavior
LeftSCurveFuzzySet
LeftShoulderFuzzySet
LineSegment
Logger
MathUtils
Matrix3
Matrix4
MemoryRecord
MemorySystem
MeshGeometry
MessageDispatcher
MovingEntity
NavEdge
NavMesh
NavMeshLoader
NavNode
Node
NormalDistFuzzySet
OBB
ObstacleAvoidanceBehavior
OffsetPursuitBehavior
OnPathBehavior
Path
Plane
Polygon
Polyhedron
PriorityQueue
PursuitBehavior
Quaternion
Ray
RectangleTriggerRegion
Regular
RightSCurveFuzzySet
RightShoulderFuzzySet
SAT
SeekBehavior
SeparationBehavior
SingletonFuzzySet
Smoother
SphericalTriggerRegion
State
StateMachine
SteeringBehavior
SteeringManager
Task
TaskQueue
Telegram
Think
Time
TriangularFuzzySet
Trigger
TriggerRegion
Vector3
Vehicle
Version
WanderBehavior

getPath

导出

getPath(from, to, graph);

描述

getPath 是 Yuka js 库中的一个函数,它使用广度优先搜索(BFS)算法来查找从给定起始节点 from 到目标节点 to 的最短路径,并返回该路径。

参数

  • from:起始节点,类型为 string
  • to:目标节点,类型为 string
  • graph:表示节点之间关系的图表,类型为 Map。其中,每个键表示一个节点,每个值表示该节点的相邻节点列表。

返回值

如果找到了从 fromto 的可达路径,则返回该路径,类型为 Array。否则,返回空数组 []

示例

import Yuka from 'yuka';

const graph = new Map([
  ['A', ['B', 'C', 'D']],
  ['B', ['A', 'E', 'F']],
  ['C', ['A', 'G']],
  ['D', ['A']],
  ['E', ['B', 'H']],
  ['F', ['B']],
  ['G', ['C']],
  ['H', ['E']]
]);

const path = Yuka.getPath('A', 'H', graph);
console.log(path); // ["A", "B", "E", "H"]

注意事项

  • getPath 函数使用了广度优先搜索算法,因此时间复杂度为 O(|V|+|E|),其中 |V| 表示节点数量,|E| 表示边的数量。在大规模数据集上执行时,会需要较长的计算时间。

  • getPath 函数要求传入的 graph 参数必须是一个 Map 类型。如果提供了其他类型的参数,或者参数无效,则该函数将引发异常。因此,在使用 getPath 函数前,务必检查提供的参数类型是否正确。