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:
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.
When checked, travelers will smoothly rotate when turning.
Snap Dividers to Grid
When checked, dividers will snap between points of the A* grid.
When checked, the A* Navigator will cache paths to be reused in order to save processing time.
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.
|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
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.
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.
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.
Defines the turn speed to use when travelers stop and rotate for turns.
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. 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.
When checked, Barriers will be visible.
When checked, a blue box is drawn indicating the bounds of the grid.
When checked, displays the individual nodes of the grid.
When checked, displays a blue circle under travelers and a blue rectangle under Fixed Resources connected to the A* Navigator.
When checked, lines are drawn from travelers to the nodes they have allocated.
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.
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:
- Check the Debug/Show Routing Algorithm box.
- Press the Apply button.
- Run the model.
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
- 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.
- 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*'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: