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.
","abstract_html":"<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>","abstract_has_math":false,"creators":["Shepherd, Jeremiah Jeffrey"],"institution":null,"degree_name":"MS","degree_level":"Campus Access Thesis","degree_discipline":"Computer Science and Engineering","degree_department":null,"school":null,"contributors":["Jijun Tang"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2009,"date_issued":"2009-01-01T08:00:00Z","date_published":"2009-01-01T08:00:00Z","updated_at":"2026-07-24T04:36:50Z","subjects":["Computer Sciences","Electrical and Computer Engineering","Engineering","Physical Sciences and Mathematics","differential constraints","Dubins","motion planning","Path-finding","Real Time Strategy","video game"],"languages":[],"rights":["© 2009, Jeremiah Jeffrey Shepherd"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://scholarcommons.sc.edu/etd/92","outbound_label":"Repository record","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Jijun Tang"]},{"key":"dc:creator","label":"Author","values":["Shepherd, Jeremiah Jeffrey"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science and Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Campus Access Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["MS"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Computer Sciences","Electrical and Computer Engineering","Engineering","Physical Sciences and Mathematics","differential constraints","Dubins","motion planning","Path-finding","Real Time Strategy","video game"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:rights","label":"Dc Rights","values":["© 2009, Jeremiah Jeffrey Shepherd"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://scholarcommons.sc.edu/etd/92"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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.
"]},{"key":"dc:title","label":"Title","values":["Path-Finding With Differential Constraints In Real Time Strategy Video Games"]}]}],"canonical_facts":{"dc:contributor":["Jijun Tang"],"dc:creator":["Shepherd, Jeremiah Jeffrey"],"dc:description.abstract":["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.
"],"dc:identifier":["https://scholarcommons.sc.edu/etd/92"],"dc:rights":["© 2009, Jeremiah Jeffrey Shepherd"],"dc:subject":["Computer Sciences","Electrical and Computer Engineering","Engineering","Physical Sciences and Mathematics","differential constraints","Dubins","motion planning","Path-finding","Real Time Strategy","video game"],"dc:title":["Path-Finding With Differential Constraints In Real Time Strategy Video Games"],"thesis:degree_discipline":["Computer Science and Engineering"],"thesis:degree_level":["Campus Access Thesis"],"thesis:degree_name":["MS"]},"updated_at":"2026-07-24T04:36:50Z"}