DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2016.70

The Explicit Corridor Map: Using the Medial Axis for Real-Time Path Planning and Crowd Simulation

Authors: Wouter van Toll, Atlas F. Cook IV, Marc van Kreveld, and Roland Geraerts

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract

We describe and demonstrate the Explicit Corridor Map (ECM), a navigation mesh for path planning and crowd simulation in virtual environments. For a bounded 2D environment with polygonal obstacles, the ECM is the medial axis of the free space annotated with nearest-obstacle information. It can be used to compute short and smooth paths for disk-shaped characters of any radius. It is also well-defined for multi-layered 3D environments that consist of connected planar layers. We highlight various operations on the ECM, such as dynamic updates, visibility queries, and the computation of paths (indicative routes). We have implemented the ECM as the basis of a real-time crowd simulation framework with path following and collision avoidance. Our implementation has been successfully used to simulate real-life events involving large crowds of heterogeneous characters. The enclosed demo application displays various features of our software.

Cite as

Wouter van Toll, Atlas F. Cook IV, Marc van Kreveld, and Roland Geraerts. The Explicit Corridor Map: Using the Medial Axis for Real-Time Path Planning and Crowd Simulation. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 70:1-70:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{vantoll_et_al:LIPIcs.SoCG.2016.70,
  author =	{van Toll, Wouter and Cook IV, Atlas F. and van Kreveld, Marc and Geraerts, Roland},
  title =	{{The Explicit Corridor Map: Using the Medial Axis for Real-Time Path Planning and Crowd Simulation}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{70:1--70:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.70},
  URN =		{urn:nbn:de:0030-drops-59622},
  doi =		{10.4230/LIPIcs.SoCG.2016.70},
  annote =	{Keywords: Medial axis, Navigation mesh, Path planning, Crowd simulation}
}

Search Results

Documents authored by van Toll, Wouter

The Explicit Corridor Map: Using the Medial Axis for Real-Time Path Planning and Crowd Simulation

Abstract

Cite as

Thanks for your feedback!

Could not send message