View Related Documents

Abstract

Planning corridors among obstacles has arisen as a central problem in game design. Instead of devising a one-dimensional motion path for a moving entity, it is possible to let it move in a corridor, where the exact motion path is determined by a local planner. In this paper we introduce a quantitative measure for the quality of such corridors. We analyze the structure of optimal corridors amidst point obstacles and polygonal obstacles in the plane, and propose an algorithm to compute approximations for optimal corridors according to our measure.
This work has been supported in part by the IST Programme of the EU as Shared-cost RTD (FET Open) Projects under Contract No IST-2001-39250 (MOVIE — Motion Planning in Virtual Environments) and IST-006413 (ACS - Algorithms for Complex Shapes) , and by the Hermann Minkowski–Minerva Center for Geometry at Tel Aviv University.

Fulltext Preview

Image of the first page of the fulltext document