Breadcrumb

 
 

Path finding in 2d games

Title:

Path finding in 2d games

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

[img]
Preview
PDF
2304Kb

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.

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
Date:2003
Thesis Supervisor(s):Grogono, Peter
ID Code:2063
Deposited By:Concordia University Libraries
Deposited On:27 Aug 2009 13:24
Last Modified:08 Dec 2010 10: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

Document Downloads

More statistics for this item...

Concordia University - Footer