Login | Register

Path finding in 2d games


Path finding in 2d games

Mandachescu, Cosmin Adrian (2003) Path finding in 2d games. Masters thesis, Concordia University.



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.

Divisions:Concordia University > Faculty of Engineering and Computer Science > Computer Science and Software Engineering
Item Type:Thesis (Masters)
Authors:Mandachescu, Cosmin Adrian
Pagination:x, 71 leaves : ill. ; 29 cm.
Institution:Concordia University
Degree Name:Theses (M.Comp.Sc.)
Program:Computer Science and Software Engineering
Thesis Supervisor(s):Grogono, Peter
ID Code:2063
Deposited By: Concordia University Libraries
Deposited On:27 Aug 2009 17:24
Last Modified:08 Dec 2010 15:24
Related URLs:
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.

Repository Staff Only: item control page


Downloads per month over past year

Back to top Back to top