Abstract

A major problem faced by game developers these days is the ability to effectively plan the motion from a Source object to a Target situated in an environment with several Obstacles . This paper proposes a framework for game design in which all objects have a precalculated bounding box. Polygons with four or more edges (depending on the accuracy desired and the shape of the object) represent the bounding boxes. They are automatically generated at the creation of the object and are filtered to minimize the number of vertices while preserving the overall aspect of the object. The vertices of all the bounding boxes from a region of interest (situated in the vicinity of the direct path from the Source to the Target) are dynamically triangulated using a triangulation algorithm. The result of such a triangulation is a 2D mesh situated in the empty space available for movement. None of the edges generated by triangulation will cross any hard object (source, target, obstacle). A path from the Source to the Target is then derived by navigating on the edges generated by triangulation as well as on the contours of the hard objects. Further smoothing is done by removing redundant points from the discrete path while avoiding collisions.