Path-Finding With Differential Constraints In Real Time Strategy Video Games

<p>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.</p>

Name thesis:degree_name

MS

Level thesis:degree_level

Campus Access Thesis

Discipline thesis:degree_discipline

Computer Science and Engineering

Year

2009

Author dc:creator

• Shepherd, Jeremiah Jeffrey

Contributors dc:contributor

• Jijun Tang

• Computer Sciences
• Electrical and Computer Engineering
• Engineering
• Physical Sciences and Mathematics
• differential constraints
• Dubins
• motion planning
• Path-finding
• Real Time Strategy
• video game

Statement dc:rights

• © 2009, Jeremiah Jeffrey Shepherd

Repository record dc:identifier

https://scholarcommons.sc.edu/etd/92

OAI identifier oai:identifier

oai:scholarcommons.sc.edu:etd-1093