Date of Award


Document Type

Campus Access Thesis


Computer Science and Engineering

First Advisor

Jijun Tang


Path-finding is commonly used in video games, and is a critical feature in real time strategies. This game genre uses path-finding to move an agent such as a soldier or a vehicle from one place to another, but currently these paths are unrealistic for agents that possess differential constraints. For example, when a car-like vehicle moves from one place to another it will follow a jagged path, which overlooks differential constraints that determines how it would realistically move. Using differential constraints in agent path-finding has been avoided in video games, since these constraints make path-finding computationally intensive and would slow down game play. I propose an algorithm in which paths with differential constraints can be determined quickly in real time strategies. The method uses a data structure containing precalculated paths found by using Dubins curves, and a modified path-finding algorithm.


© 2009, Jeremiah Jeffrey Shepherd