Authors: Jeremiah J. Shepherd, Dr. Jijun Tang, Dr. Jason O’Kane
Path-finding is commonly used in video games, and is a critical feature in real time strategies. This 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 motion constraints. For example, in these games when a car-like vehicle moves from one place to another it will follow a jagged path, which overlooks motion constraints that determine how the vehicle realistically moves. Using motion constraints in agent path-finding has been avoided in video games, since these constraints make this task difficult and would slow down game play. In this paper we present an algorithm in which paths with motion constraints can be determined quickly in real time strategies. The method uses a data
structure containing precalculated paths found by rapidly exploring random trees (RRT). Our experimental results support our claim that this method could be implemented in real time strategies.