Abstract In many virtual environment applications, paths have to be planned for characters to traverse from a start to a goal position in the virtual world while avoiding obstacles. Contemporary applications require a path planner that is fast (to ensure real-time interaction with the environment) and flexible (to avoid local hazards such as small and dynamic obstacles). In addition, paths need to be smooth and short to ensure natural looking motions. Current path planning techniques do not obey these criteria simultaneously. For example, A* approaches generate unnatural looking paths, potential field-based methods are too slow, and sampling-based path planning techniques are inflexible. We propose a new technique, the Corridor Map Method (CMM), which satisfies all criteria. In an off-line construction phase, the CMM creates a system of collision-free corridors for the static obstacles in an environment. In the query phase, paths can be planned inside the corridors for different types of characters while avoiding dynamic obstacles. Experiments show that high-quality paths for single characters or groups of characters can be obtained in real-time. Reference Roland Geraerts and Mark H. Overmars. The Corridor Map Method: A general framework for Real-Time High-Quality Path Planning. In Computer Animation and Virtual Worlds (CAVW), 18: 107-119, 2007. Full text: [pdf]         High-quality corridor map     Corridor     Path Test environments We used the following two test environments and corresponding roadmaps (click on a picture to enlarge):                    Environments      High-quality roadmaps Results The Corridor Map Method enables the extraction of high-quality paths within 1 ms cpu time per second traversed time of the path. Smooth paths Paths avoiding moving obstacles Short paths The corridor maps were generated by a new method described here. The following picture shows another example output of the method. A short path is displayed.