Changes between Version 2 and Version 3 of doc/tec/mas


Ignore:
Timestamp:
Aug 2, 2018 10:01:45 AM (7 years ago)
Author:
sward
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • doc/tec/mas

    v2 v3  
    66== Navigation ==
    77
    8 This section contains information concerning agent navigation. This includes preprocessing (creation of a visibility graph) and online steps (during simulation).
     8This section contains information concerning agent navigation. This includes preprocessing and online steps .
    99
    1010=== Visibility graph ===
    11 Prior to a simulation using the MAS navigation information for the agents must be preprocessed. The result is a navigation graph that agents can use to find their way around obstacles toward their target.
     11Prior to a simulation using the MAS navigation information for the agents must be preprocessed. The result is a navigation mesh (visibility graph) that agents can use to find their way around obstacles toward their target.
    1212
    1313'''Concept'''\\\\
     14For 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.\\
     15The 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. \\\\
     16To produce this data,\\
     171) the PALM building topographhy is '''converted to polygons''' (one per obstacle) containing all convex and cocave corners as vertices.\\
     182) 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]. \\
     193) All remaining convex polygon vertices are added to the graph as nodes.\\
     204) Connections are established between each pair of nodes that are visible by each other. The associated cost is set to the direct distance.\\
     215) The polygon and graph data is output to a Fortran binary file that can be read by PALM.\\
    1422
    1523
    1624'''Creating the visibility graph'''\\\\
    1725A tool separate from PALM has been developed to calculate the visibility graph. It is a standalone Fortran program (find it at {{{UTIL/nav_mesh/nav_mesh.f90}}}). \\
    18 '''The usage of this tool is subject to chage! The following description is preliminary!'''
     26''' The usage of this tool is subject to chage! The following description is preliminary! '''
    1927
    20281) Copy {{{nav_mesh.f90}}} to the {{{INPUT}}}-folder of your JOB.\\
     
    3139}}}
    3240This 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.
     41
     42== Pathfinding ==
     43
     44During 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^*^(A-star)-algorithm''' which is a well-known fast pathfinding algorithm (click [#http://theory.stanford.edu/~amitp/GameProgramming/ here] for a thorough explanation).
     45
     46
     47
     48
     49
     50
     51
     52
     53
     54
     55
    3356
    3457''L'', ''u'',,∗,, as well as
     
    5780}}}
    5881== References ==
     82* [=#hershberger1994] '''Hershberger J, Snoeyink J''' 1994. An O(''n''log''n'') implementation of the Douglas-Peucker algorithm for line simplification. SCG '94 Proceedings of the tenth annual symposium on Computational geometry. 383-384. [https://doi.org/10.1145/177424.178097 doi]
    5983* [=#detering1985] '''Detering HW, Etling D.''' 1985. Application of the ''E''-''ε'' turbulence model to the atmospheric boundary layer. Bound.-Lay. Meteorol. 33: 113–133.