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:
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 preferred paths. Any newly created preferred paths will be given this value for their path weight.
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:
You can access a Divider or Path's properties by double-clicking on it, or through Quick Properties:
Check this box to make a barrier conditional, and define the condition that is required for the barrier to be applied. When a barrier is conditional, its condition is reevaluated at the beginning of every travel task. If the condition returns false (0), then the barrier will not be applied in the route calculation algorithm, and the traveler will travel as if the barrier did not exist. Conditional barriers let you define certain barriers as only applicable for certain travelers, or based on certain model conditions.
Check this box to make the divider/path apply in two directions instead of just one.
Define x,y positions of each point.
|Add a point to the end.|
|Remove the selected point.|
|Reorder the selected point up or down in the list.|
Preferred Paths only. This is the path weight added to the nodes associated with the path.
Bridges only. When checked, this is the distance that will use for traversing the Bridge instead of the actual distance.
You can access a Barrier's properties by double-clicking on it, or through Quick Properties:
Check this box to make a barrier conditional, and define the condition that is required for the barrier to be applied. This is the same as the condition described above under Divider/Path Properties.
Specify the size and position of the barrier.
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 Quick Properties pane.
This is the distance (in model units) between nodes in the grid. Smaller spacing will allow travel members to move more smoothly and direct, however, more nodes will require more processing time to calculate paths.
Sets the current Grid Z of the 3D view to the Z position of this grid.