| | 1 | This page is part of the MAS-documentation. \\ |
| | 2 | For an overview of all MAS-related pages, see the [wiki:doc/tec/mas MAS main page]\\\\ |
| | 3 | |
| | 4 | = Pathfinding = |
| | 5 | |
| | 6 | {{{#!td style="vertical-align:top; text-align:left" |
| | 7 | During the simulation each agent receives target coordinates (see [wiki:/doc/app/agtpar#at_x at_x] and [wiki:/doc/app/agtpar#at_y at_y]). Each agent must then find a path from its current position to its target using the visibility graph. This is accomplished using the '''A^*^-algorithm''' which is a well-known fast pathfinding algorithm (click [http://theory.stanford.edu/~amitp/GameProgramming/ here] for a thorough explanation). For this, \\ |
| | 8 | * the agent's current position and its target are added to the [../agent_preprocessing visibility graph], \\\\ |
| | 9 | * the shortest path between these two points is calculated, \\\\ |
| | 10 | * the navigation points are shifted outward from the obstacle corner to a random position along a "gate" (see [wiki:/doc/app/agtpar#corner_gate_start corner_gate_start] and [wiki:/doc/app/agtpar#corner_gate_width corner_gate_width]) to avoid collisions with obstacles or other agents,\\\\ |
| | 11 | * pathfinding is run again with each successive pair of navigation points along the path to avoid intersection of path sections with obstacles resulting from the outward shift,\\\\ |
| | 12 | * finally, the resulting path is stored in the agent object as a series of intermittent targets.\\ |
| | 13 | Each agent calculates the direction toward its next intermittet target during each agent time step. It will accelerate toward those coordinates. Once the agent has come close enough ([wiki:/doc/app/agtpar#dist_to_int_target dist_to_int_target]) to them, the next intermittent target is chosen. When the final target is reached, the agent is deleted.\\\\ |
| | 14 | '''Recalculation''' of an agent's path occurs when\\ |
| | 15 | * the agent has deviated too far ([wiki:/doc/app/agtpar#max_dist_from_path max_dist_from_path]) from its current path or |
| | 16 | * the path counter has reached its maximum and the target is not yet reached. This can occur because for the purpose of conservation of memory each agent can store a maximum of 15 intermittent targets. |
| | 17 | }}} |
| | 18 | {{{#!td style="text-align:left;style=width: 50px" |
| | 19 | [[Image(pathfinding.gif)]] |
| | 20 | }}} |
