This library contains a behavior that you can use in your simulation to find shortest paths along a network, using the A* algorithm.

A* Search

The A* Algorithm combines Dijkstra's Algorithm for finding shortest paths with a heuristic to guide its search. It attempts to minimize the distance between a starting node and a final node. It can be applied to any problem that can be represented with nodes, such as a social network graph, or a physical grid.

Integrating Into A Simulation

For the behavior to function, you'll need to write at least one custom behavior, and set a number of parameters in globals.json.

Global parameters

The following parameters are needed for the A* behavior to function properly:

• step_cost - number: The cost incurred based on the length of the solution path
• unique_field - string: The field on each node that can function as a unique identifier
• path_field - string: The field returned from each node when the solution path is constructed

-goal - object: The agent field which must match the value to satisfy the goal conditions. With the following shape:

{
  "field": string,
  "value": any
}

Custom behavior

Your optimizing agent must have at least one custom behavior running before @hash/astar/a_star.py. This behavior must determine the valid child nodes based on the current node being explored (state["current_node"]). In the example in this project where the agent must navigate a grid, the valid child nodes correspond to the locations above, below, and to the left and right of the current node.

This behavior must also assign a "heuristic" score to the node. This heuristic is determined by the modeler. In the example, the Euclidean distance to the goal is used.

This list of nodes must then be set on state["next_nodes"] with the proper node definition, as shown below:

Node definition

{
  "<unique_field>": any type that can check for equality,
  "<path_field>": any,
  "h": number // The heuristic score for the node
}

Note that the @hash/astar/a_star.py behavior will add some additional fields to the node:

{
  ...
  "parent": {...}, // The definition of the parent node
  "g": number, // The step score for the node
  "f": number, // The total score for the node
}

Initialization

To begin an A* optimization, intialize an agent with the proper behaviors mentioned above and the following fields:

{
  "behaviors": ["<custom>", "@hash/astar/a_star.py", ...],
  "current_node": {
    ..., // Any other needed fields in your simulation
    "parent": null,
    "f": 0,
    "g": 0,
    "h": 0
  },
  "visited": [],
  "to_visit": []
}