A* Navigation

Overview and Key Concepts

A* (pronounced "A Star") is a search algorithm used to find a path between points. The algorithm uses a grid of nodes that Task Executer objects (travel members) travel through. Each node specifies in which direction travel members can move. The algorithm will look at nodes in the direction of travel and determine which direction is the fastest, including travelling diagonally between nodes. The grid of nodes can be modified by creating barriers restricting where the travel members can move or even influencing them to travel along certain paths.

The General Tab

The General tab has the following properties:

Surround Depth

This number specifies the number of nodes that are placed around the outside of the navigator's outer most barriers. This number must be an integer and be greater than 0.

Smooth Rotations

When checked, travelers will smoothly rotate when turning.

Snap Dividers to Grid

When checked, dividers will snap between points of the A* grid.

Cache Paths

When checked, the A* Navigator will cache paths to be reused in order to save processing time. Note that the A* Navigator can only cache paths if you are not using dynamic barriers. If you need path caching, you should use conditional rules if possible.

Members

The box on the left selects which members lists to view. Clicking the Properties button opens the properties window of the selected member. The box on the right displays all of the objects at the currently selected status.

Icon Description
Click to sample an object in the model to add as a member.
Click to open an object selection window and choose objects to add as members.
Remove the selected member.

The Behavior Tab

Path Routing

Defines how nodes in the travel grid will be searched. Options are as follows:

  • Right Angles Only - The A* path search will only find paths that travel vertically or horizontally. No diagonal travel will be used.
  • Diagonals - The A* path search will allow for diagonal travel. Travelers can simultaneously travel one unit vertically and one unit horizontally.
  • Deep Diagonals - The A* path search will allow for deep diagonal travel. Travelers can simultaneously travel two units vertically and one unit horizontally, or vice versa.

Strict Diagonals

If checked, the traveler will only travel diagonals if the grid travel directions allow the traveler to travel using both direction orderings, namely both "x then y" and "y then x", to get to the diagonal destination. Checking this box will ensure that travelers don't overshorten their path when going around corners.

Collision Avoidance

When checked, travelers will allocate nodes in their path and deallocate them once passed. This prevents two travelers from traveling through the same nodes at the same time.

Ignore Inactive Memebers

When checked, the collision avoidance algorithm will ignore allocations made by inactive travelers. After a traveler has arrived at its destination and ended active travel, the traveler will be essentially invisible to the collision detection algorithm. This means that travelers will run over other travelers that are not actively traveling.

While travelers running over each other is not desirable, it is somewhat complex to figure out what a traveler should do when it is idle to get out of the way of other travelers who need to go to the same spot. In a humans-as-travelers situation, generally people just figure out how to make space for each other without much delay penalty. From this perspective of delay penalties, letting idle travelers ignore each other essentially simulates the same desired behavior as humans naturally getting out of each other's way.

Deallocation Time Offset

Defines an additional time to wait before deallocating a grid node that a traveler is leaving. By default (0.00) a traveler will release its node as soon as it begins to travel to the next node. When this value is greater than zero, the traveler will wait this additional time before releasing the node.

Stop for Turns

When checked, travelers who need to turn to a new direction will stop and rotate to the new direction.

Turn Speed

Defines the turn speed to use when travelers stop and rotate for turns.

Turn Delay

Defines an additional time delay associated with stopping for turns. When the traveler must stop and turn, it will add this delay time to the time it takes to the turn to the new direction.

Route By Travel Time

If checked, the A* search algorithm will use travel time instead of travel distance as the cost function in assessing path desirability. The primary difference in using this is that, when travelers stop for turns, it will calculate the time it takes to turn, and apply that to the cost function.

Default Preferred Path Weight

This is the default path weight for any preferred paths without a custom weight. Valid values are numbers between 0 and 1. Setting a path to have a path weight of 0 will revert the path to using this default value.

The Visual Tab

Use these properties to turn on or off the visiblilty of A* features.

Barriers

When checked, Barriers will be visible.

Grid Bounds

When checked, a blue box is drawn indicating the bounds of the grid.

Grid Nodes

When checked, displays the individual nodes of the grid.

Members

When checked, displays a blue circle under travelers and a blue rectangle under Fixed Resources connected to the A* Navigator.

Allocations

When checked, lines are drawn from travelers to the nodes they have allocated.

Heat Map

When checked, a heat map is generated based on the option selected in the dropdown. The Max Heat Value corresponds with the selected dropdown option and defines the threshold for coloring the heatmap.

Travel Threshold

When checked, red and blue diamonds will be displayed around the highlighted object in the 3D view. When a traveler is given a travel task to travel to this object, the A* Navigator will compute the shortest path between the traveler and any of the nodes marked by a red diamond. The traveler will then begin traveling following this shortest path. As soon as the traveler reaches any of the nodes marked by a blue diamond the traveler has arrived at the object and the travel task is complete.

Debug/Show Routing Algorithm

This checkbox is used primarily for debugging purposes. When checked, the A* search algorithm will save additional data that tracks each traveler's last path finding operation. To see this information:

  1. Check the Debug/Show Routing Algorithm box.
  2. Press the Apply button.
  3. Run the model.
  4. Click or shift-select a traveler. When you select the traveler, you'll see a set of dots on the A* grid that are associated with that traveler's last path finding operation:
    • Green dots represent nodes that are in the A* open set.
    • Red dots represent nodes in the closed set.
    • The blue dot shows the node that is being resolved from the open set to the closed set.
    • Text also appears beside each node showing the formula g + h = f, where g is the cost to get to a node, h is the heuristic calculation to get from the node to the destination, and f is the sum of the two.
  5. Adjust the Completion Percent tracker to see the routing algorithm as it progresses.

The Conditional Rules Tab

Use this tab to define conditional rules by which barriers, dividers, preferred paths, or bridges will be applied in the routing algorithm.

A* Grids

A*'s path search uses grids to resolve travel paths. A grid is a two-dimensional plane that encompasses a travel area. After you've dragged barriers, dividers, etc. into a model, if you reset the model, you will see a grid represented by a blue rectangular border surrounding those objects. The grid is a two-dimensional array of nodes, with a user-defined distance between each node. A* travelers move by traveling from one node in the grid to another. Barriers and dividers determine which adjacent nodes may or may not be traveled to from a given node.

Every A* model has at least one grid. That grid will automatically grow to encompass all the barriers, dividers, preferred paths, etc. that are part of your A* model. Also, you can add additional grids by dragging them from the library on the left. You can move and resize grids in the 3D view as you would any other object. You can also define the node spacing of a grid, as well as its z position, through its Properties pane.

The Grid object uses the following properties panel:

Divider/Path Properties Panels

The Divider and Path objects use the following properties panel:

Barrier Properties Panels

The Barrier object uses the following properties panel: