This paper presents different path-finding algorithms for simulating pedestrian dynamics in building models. Starting from a given model (scenario), we show how to automatically derive a visibility graph. This graph is used as the underlying structure for routing pedestrians from their sources to their destinations. Based on this graph, we search for fastest routes by means of a conventional Dijkstra algorithm where we assign dynamically changing travel times as edge weights. To update the shortest paths due to changing edge weights, we introduce a heuristic A*algorithm, which is faster in finding optimal paths. We compare the results of our approach to a variant where we assign Euclidean distances as static edge weights. Additionally, we show that the A* algorithm has a better performance in finding the shortest path for most cases.
«
This paper presents different path-finding algorithms for simulating pedestrian dynamics in building models. Starting from a given model (scenario), we show how to automatically derive a visibility graph. This graph is used as the underlying structure for routing pedestrians from their sources to their destinations. Based on this graph, we search for fastest routes by means of a conventional Dijkstra algorithm where we assign dynamically changing travel times as edge weights. To update the short...
»