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 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.
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.|
Defines how nodes in the travel grid will be searched. Options are as follows:
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.
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.
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.
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.
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.
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.
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.
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:
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:
The Divider and Path objects use the following properties panel:
The Barrier object uses the following properties panel: