AStar

Definition

AStar is a Kompute implementation of A* search algorithmto find the shortest path between two vertices of given Graph. This class is internally used by RandomPathBehavior however may be used manually as well.

Usage

// create a Graph
var graph = new Kompute.Graph();

// define vertices
var vertex1 = new Kompute.Vector3D(100, 0, 0);
var vertex2 = new Kompute.Vector3D(200, 0, 0);
var vertex3 = new Kompute.Vector3D(300, 0, 0);

// add vertices to graph
graph.addVertex(vertex1);
graph.addVertex(vertex2);
graph.addVertex(vertex3);

// add edges to graph
graph.addEdge(vertex1, vertex2);
graph.addEdge(vertex2, vertex3);

// create an instance of AStar
var aStar = new Kompute.AStar(graph);

// Find the shortest path from vertex1 to vertex3
var path = aStar.findShortestPath(vertex1, vertex3);

// findShortesPath returns false if there's not a possible path
console.log(aStar.findShortestPath(vertex3, vertex1); // prints false

In order to pipe the output of AStar to PathFollowingBehavior aStar.path property may be used:

var pathFollowingBehavior = new Kompute.PathFollowingBehavior({
  satisfactionRadius: 5,
  path: aStar.path
});

steerable.setBehavior(pathFollowingBehavior);

This refreshes the PathFollowingBehavior everytime the shortest path is computed.

Integrating jump

A JumpDescriptor may be inserted into the Graph in order to automatically activate jump behavior while following the Path constructed by the AStar. See here.

Visualising

AStar instances may be visualised via DebugHelper#visualiseAStar API. See here.

Cost Modifier

A cost modifier function may be passed to AStar#findShortestPath API. The numeric return value of this function is then added to the original cost of given path segment while computing the path. This is useful for calculating the shortest path while preventing certain entities on the way:

aStar.findShortestPath(v1, v2, function(p1X, p1Y, p1Z, p2X, p2Y, p2Z){
  // check if entity intersects with the line segment defined from (p1X, p1Y, p1Z) to (p2X, p2Y, p2Z)
  if (entityIsOnTheWay(...)){
    return Infinity; // Make this path segment expensive
  }

  return 0; // Do not modify the current cost of the path segment
});