| 20 | | '''Concept'''\\\\ |
| 21 | | For agents to be able to find a path through an area containing obstacles (such as a city) some sort of graph is needed on which pathfinding can be performed. Such a graph consists of nodes that indicate physical locations and connections between these nodes annotated with a cost to travel between the two nodes.\\ |
| 22 | | The concept used here is called "visibility graph". It hinges on the idea that pedestrians use '''outer corners''' of obstacles to navigate. All spaces that pedestrians will not or cannot cross, such as buildings, trees, certain types of streets, etc are considered obstacles. The agent will walk toward the next visible corner on their way to their final target, make a turn, and walk toward the next corner. Thus, the nodes are the obstacle corners and a connection is established between two nodes if they are in view of each other and given the cost of the direct distance between the two. \\\\ |
| 23 | | To produce this data,\\ |
| 24 | | 1) the PALM building topographhy is '''converted to polygons''' (one per obstacle) containing all convex and cocave corners as vertices.\\ |
| 25 | | 2) The polygon data is '''simplified''' using the Douglas-Peucker algorithm ([#hershberger1994 Hershberger and Snoeyink, 1994]). To adjust the rate of simplification, see [#tolerance_dp tolerance_dp]. \\ |
| 26 | | 3) All remaining convex polygon vertices are '''added to the graph''' as nodes.\\ |
| 27 | | 4) '''Connections''' are established between each pair of nodes that are visible by each other. The associated cost is set to the direct distance.\\ |
| 28 | | 5) The polygon and graph data is '''output''' to a Fortran binary file that can be read by PALM.\\ |
| 29 | | |
| 30 | | |
| 31 | | '''Creating the visibility graph'''\\\\ |
| 32 | | A tool separate from PALM (Agent Preprocessing Tool for PALM - APT-P) has been developed to calculate the visibility graph. It is a standalone Fortran program (find it at {{{UTIL/agent_preprocessing/agent_preprocessing.f90}}}). \\ |
| 33 | | To use it, |
| 34 | | 1) navigate to the {{{INPUT}}}-folder of your JOB.\\ |
| 35 | | 2) Make sure your Input folder contains the relevant topography information in either an ASCII- or NetCDF-file ([wiki:doc/app/iofiles/pids#topo see here]).\\ |
| 36 | | 3) Make sure your Input folder contains the {{{_p3d}}}-file. In it, if necessary, specify the namelist {{{&prepro_par}}} with the parameters [#flag_2d flag_2d], [#internal_buildings internal_buildings] and [#tolerance_dp tolerance_dp].\\ |
| 37 | | 4) Execute the APT-P by typing |
| 38 | | {{{ |
| 39 | | agent_preprocessing |
| 40 | | }}} |
| 41 | | This will create a file {{{<job_identifier>_nav}}}. This is a Fortran binary file that contains the polygon and visibility graph data and will be read by PALM during the simulation. As long as the area and resulution of the model domain do not change this file can be reused. |
