A central problem of applications dealing with virtual environments is planning a collision-free path for a character. Since environments and their characters are growing more realistic, a character's path needs to be visually convincing, meaning that the path is smooth, short, has some clearance to the obstacles in the environment, and avoids other characters. Up to now, it has proved difficult to meet these criteria simultaneously and in real-time.
We introduce a new data structure, i.e. the Explicit Corridor Map, which allows creating the shortest path, the path that has the largest amount of clearance, or any path in between. Besides being efficient, the corresponding algorithms are surprisingly simple. By integrating the data structure and algorithms into the Indicative Route Method, we show that visually convincing short paths can be obtained in real-time.
Roland Geraerts. Planning Short Paths with Clearance using Explicit Corridors. In IEEE International Conference on Robotics and Automation (ICRA'10), pp. 1997-2004, 2010.
The steps of our algorithm are visualized in the movie below.
The Explicit Corridor
Experiments (a selection)
We extracted 1,000 random corridors from the map. The average running time for extracting an Explicit Corridor was 1.19ms. Shrinking the corridor added 0.54ms. Triangulating this corridor and computing the shortest path added another 1.83ms. Hence, on average, the total time for computing the shortest (minimum-clearance) path in a corridor was 3.56ms. By using the resulting shortest paths as control paths, smooth paths were obtained, increasing the total time to 4.14ms. By having an average traveled distance of 321m, the CPU-load was 0.002% for steering a single character. Consequently, the approach is suitable for steering many characters simultaneously, as occurs in a large crowd.