| 9 | | |
| 10 | | == Navigation == |
| 11 | | |
| 12 | | This section contains information concerning agent navigation. This includes preprocessing and online steps . |
| 13 | | |
| 14 | | |
| 15 | | |
| 16 | | === Pathfinding === |
| 17 | | |
| 18 | | {{{#!td style="vertical-align:top; text-align:left" |
| 19 | | 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, \\ |
| 20 | | * the agent's current position and its target are added to the visibility graph, \\\\ |
| 21 | | * the shortest path between these two points is calculated, \\\\ |
| 22 | | * 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,\\\\ |
| 23 | | * 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,\\\\ |
| 24 | | * finally, the resulting path is stored in the agent object as a series of intermittent targets.\\ |
| 25 | | 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.\\\\ |
| 26 | | '''Recalculation''' of an agent's path occurs when\\ |
| 27 | | * the agent has deviated too far ([wiki:/doc/app/agtpar#max_dist_from_path max_dist_from_path]) from its current path or |
| 28 | | * 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. |
| 29 | | }}} |
| 30 | | {{{#!td style="text-align:left;style=width: 50px" |
| 31 | | [[Image(pathfinding.gif)]] |
| 32 | | }}} |
| 106 | | == NAMELIST group name: {{{prepro_par}}}== |
| 107 | | |
| 108 | | ||='''Parameter Name''' =||='''[wiki:/doc/app/fortrantypes FORTRAN Type]''' =||='''Default Value''' =||='''Explanation''' =|| |
| 109 | | |---------------- |
| 110 | | {{{#!td style="vertical-align:top; text-align:left;width: 150px" |
| 111 | | [=#flag_2d '''flag_2d''] |
| 112 | | }}} |
| 113 | | {{{#!td style="vertical-align:top; text-align:left;style="width: 50px" |
| 114 | | L |
| 115 | | }}} |
| 116 | | {{{#!td style="vertical-align:top; text-align:left;style="width: 75px" |
| 117 | | .F. |
| 118 | | }}} |
| 119 | | {{{#!td |
| 120 | | Flag to force usage of 2d-buildings.\\\\ |
| 121 | | If set to .T., this flag forces the usage of buildings_2d even if buildings_3d is available. See [wiki:doc/app/iofiles/pids#topo here] for information on topography and building input. |
| 122 | | }}} |
| 123 | | |---------------- |
| 124 | | {{{#!td style="vertical-align:top; text-align:left;width: 150px" |
| 125 | | [=#internal_buildings '''internal_buildings''] |
| 126 | | }}} |
| 127 | | {{{#!td style="vertical-align:top; text-align:left;style="width: 50px" |
| 128 | | L |
| 129 | | }}} |
| 130 | | {{{#!td style="vertical-align:top; text-align:left;style="width: 75px" |
| 131 | | .F. |
| 132 | | }}} |
| 133 | | {{{#!td |
| 134 | | Flag to control usage of buildings within courtyards.\\\\ |
| 135 | | By default, buildings completely surrounded by another building are excluded from the visibility graph as pedestrians can neither reach nor leave enclosed areas such as courtyards. If '''internal_buildings = .T.''', buildings within courtyards are allowed. The resulting navigation nodes can, however, never be connected to nodes outside of the courtyard. In such cases, be sure to set the target of a agent group originating inside a courtyard also within that same courtyard. |
| 136 | | }}} |
| 137 | | |---------------- |
| 138 | | {{{#!td style="vertical-align:top; text-align:left;width: 150px" |
| 139 | | [=#tolerance_dp '''tolerance_dp''] |
| 140 | | }}} |
| 141 | | {{{#!td style="vertical-align:top; text-align:left;style="width: 50px" |
| 142 | | R * 3 |
| 143 | | }}} |
| 144 | | {{{#!td style="vertical-align:top; text-align:left;style="width: 75px" |
| 145 | | 1.41, \\0.7, \\0.35 |
| 146 | | }}} |
| 147 | | {{{#!td |
| 148 | | Tolerance for simplification of building polygons during preprocessing.\\\\ |
| 149 | | Each building is stored as a counter-clockwise sorted polygon. Initially each building polygon consists of all inner and outer corners of the PALM topography as vertices. Due to the rastered nature of this grid this may be a very large number of vertices. The Douglas-Peucker-Algorithm ([#hershberger1994 Hershberger and Snoeyink, 1994]) is used to reduce the number of vertices.\\ |
| 150 | | This algorithm recursively approximates a polygon section as a straight line connecting the end points of that section. If the greatest distance between this line and any vertex between the end points is smaller than '''tolerance_dp''', the approximation is accepted and all vertices in between are deleted. Otherwise, the segment is split into two segments at the vertex of greatest distance and the process is repeated.\\\\ |
| 151 | | '''tolerance_dp''' is internally multiplied with {{{SQRT( dx*dy )}}}. If a building is left with less than 4 vertices after simplification using '''tolerance_dp(0)''', it is reset and the process is repeated with '''tolerance_dp(1)''', then '''tolerance_dp(2)''', if necessary.\\\\ |
| 152 | | '''NOTE:''' The APT-P produces an ASCII output-file {{{topo.txt}}}. The polygon data is stored in this file. After execution of the tool, please check the polygon representation. If you are not satisfied, adjust '''tolerance_dp''' and rerun the tool. |
| 153 | | }}} |
| 154 | | |
