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

search

功能

Dijkstra 算法是一种用于寻找图中最短路径的算法。search 函数使用 Dijkstra 算法查找从起点到终点的最短路径,并返回该路径。

用法

参数

  • startNode: 必选参数。表示起点节点。
  • endNode: 必选参数。表示终点节点。
  • graph: 必选参数。表示图的结构,以邻接表的形式表示。格式为 { [node1]: {[node2]: weight}, [node2]: {[node3]: weight}, ... } ,其中 node 表示节点,weight 表示两个节点之间的距离。
  • callback: 可选参数。查找完成后执行的回调函数。

返回值

该函数返回一个对象,包含以下属性:

  • path: 表示从起点到终点的最短路径,格式为一个数组,每个元素表示一个节点。
  • distance: 表示从起点到终点的最短距离,格式为一个数字。

示例

const graph = { 
  'A': { 'B': 1, 'C': 3 },
  'B': { 'A': 1, 'C': 1, 'D': 2 },
  'C': { 'A': 3, 'B': 1, 'D': 1 },
  'D': { 'B': 2, 'C': 1 }
};

const result = Yuka.search('A', 'D', graph);

console.log(result.path); // ['A', 'B', 'C', 'D']
console.log(result.distance); // 3

异常

当起点或终点不存在于图中时,该函数将抛出一个异常 "Node not found"。

依赖

该函数依赖于 Yuka.js 中的 priority queue 和 result helper 函数。