Skip to content

Latest commit

 

History

History
151 lines (108 loc) · 6.36 KB

README.md

File metadata and controls

151 lines (108 loc) · 6.36 KB
Raw

Simple model of pedestrian traffic

By Yaroslav Sergienko.

Examples

Here the shortest path from Airport subway station to Kochnovsky proesd is shown with different settings of A* algorithm:

Zones:

Squeezing allowed, euclidean heuristic:

No diagonal moves, manhattan heuristic:

Cutting corners, no heuristic:

Description

Firstly, XML dump of target area is loaded from Open Street Map. After that raster map of pedestrian zones is generated. Examples of zones: footways, crosswalks, roads, grass, buildings, fence, water, gates (public or private). Each zone has corresponding cost of passing. And finally Dijkstra algorithm is applied to calculate shortest paths to some point, for example, subway station. This allows to calculate all shortest pedestrian paths from all buildings.

Files

  • results/*.png --- results of algorithm with different settings.
  • aeroport.osm --- XML map downloaded from OSM.
  • map2matrix.ipynb --- Jupyter notebook, which generates map.png and map.pgm from aeroport.osm.
  • map.pgm --- raster in binary format without header, just pixel values, one byte per pixel; width and height are provided through command-line.
  • map.png --- png of previous file with zones encoded with colors for debug.
  • tree.c --- C source of routines for working with tree structure.
  • calc_paths.c --- C source of program, which calculates shortest paths.

Zones list

Paths costs are stored as 64-bit integer numbers. Prices are applied per-pixel. PRICE_MAX constant has a value of 2^32.

Zone id Price Name
0 MAX barriers
20 MAX / 2 private gates
40 MAX / 4 entrance
60 MAX / 8 special landuse
80 40 grass
100 10 default
120 1 footway
128 MAX / 16 buildings of unknown number of floors
129 MAX / 16 buildings with one floor
130 MAX / 16 buildings with two floors
... ... ...

Calculating paths

Arguments

gcc -lm calc_paths.c
./a.out 2700 2100 1107 1021 300 300 d e
arg global value description
1 width 2700 width of map.pgm
2 height 2100 height of map.pgm
3 sx 1107 start X
4 sy 1021 start Y
5 gx 300 goal X
6 gy 300 goal Y
7 diagonal d n --- no diagonal moves, d --- diagonal moves allowed, c --- can cut corners, s --- can squeeze
8 heuristic m n --- none, m --- manhattan, o --- octile (diagonal), e --- euclid, c --- chebyshev

To produce adequate results, start and goal must belong to zones with price like footways, so graphic editor software may be needed to find precise start and goal coordinates (use map.png file for that).

You cannot use manhattan heuristic with diagonal mode not set to n because the metric produces overestimated results.

Result

Result is saved in a res_map.ppm file, which has netpbm image format. It can be displayed and converted into other formats, for example, by ImageMagick toolboox.

Colors have following meaning:

  • red --- shortest path,
  • green --- CLOSED,
  • blue --- OPEN,
  • grayscale --- unvisited.

Data structure

The main data structure is a binary prefix tree where keys are binary representations of path costs (of fixed length TREE_H * TREE_X). All path costs are supposed to be integer numbers.

Each node correspons to TREE_D consequtive entries of tree_t type in the tree array. Each entry contain id of child tree node or zero if child is not yet created. Tree entries start from index 1 (because index zero corresponds to missing nodes).

On the last level entries contain pixel coordinates which have corresponding calculated path cost. If there are several pixels with same path cost, they form linked list by using next_cell array.

Tree nodes are never destroyed, but it is allowed to have multiple entries for the same pixel.

Pixel coordinates are encoded as y * width + x.

constant description
TREE_D number of children of each tree node
TREE_X TREE_D be equal to 2^TREE_X
TREE_M bit mask of tree children; must be equal to 2^TREE_X - 1
TREE_H height of the tree; max value the tree can handle is TREE_D ^ TREE_H
TREE_MAX_SIZE used to allocate space for tree structures; is equal to maximum node count multiplied by TREE_D
type alias description
dist_t uint64_t used to store path prices
map_t uint8_t zones ids
status_t utint8_t leaf status: UNSET, OPEN or CLOSED
tree_t uint32_t tree nodes ids
type global description
size_t width, height, wh width, height, and width * height
dist_t[wh] dists calculated path costs for each pixel of map
map_t[wh] map zones ids from map.pgm
status_t[wh] statuses pixel statuses
tree_t[TREE_MAX_SIZE] tree tree entries
tree_t[wh] next_cell next pixel with same path cost
tree_t tree_size number of nodes in tree

There is a special structure tree_pos_t which is a reference to some pixel with information about all parent tree nodes. It has field finished which is set to 1 when there is no pixel with larger path cost.

routine params description
add_to_tree tree_t ix, dist_t val adds pixel ix with distance val to tree
init_tree tree_t ix initializes tree with single pixel ix with path cost 0
next_pos tree_pos_t *tp updates pixel reference to point to the next pixel with smallest path cost

Algorithm

  1. Initialize tree (init_tree and other).
  2. Find pixel ix with smallest path cost (next_pos).
  3. If ix status is CLOSED, then ignore duplicate entry, goto 2.
  4. For each its neighbor pixel pos (make_closed)
    • Calculate new approximation of path cost.
    • If its status is UNSET, make it OPEN and set path cost.
    • If its status is OPEN, update path cost if new cost is less.
  5. Change status of pixel ix to CLOSED.