Change search
ReferencesLink to record
Permanent link

Direct link
Pathfinding with Hard Constraints: Mobile Systems and Real Time Strategy Games Combined
Blekinge Institute of Technology, School of Engineering, Department of Interaction and System Design.
Blekinge Institute of Technology, School of Engineering, Department of Interaction and System Design.
2008 (English)Independent thesis Advanced level (degree of Master (One Year))Student thesis
Abstract [en]

There is an abundance of pathfinding solutions, but are any of those solutions suitable for usage in a real time strategy (RTS) game designed for mobile systems with limited processing and storage capabilities (such as the Nintendo DS, PSP, cellular phones, etc.)? The RTS domain puts great requirements on the pathfinding mechanics used in the game; in the form of de- mands on responsiveness and path optimality. Furthermore, the Nintendo DS, and its portable, distant relatives, bring hard con- straints on the processing- and memory resources available to said mechanics. This master thesis aims to find a pathfinding solution well suited to function within the above mentioned, narrow domain. From a broad selection of candidate solutions, a few promising subjects are treated to an investigative empirical study; with the goal of finding the best “fitting” solution, considering the domain. The empirical study shows that the triangle-based TRA* solution and the hierarchical-abstraction influenced Minimal Memory so- lution are both very promising candidates. Depending on how one exactly defines the domain, either one of the solutions could be considered the ‘best’ choice. Since the overall performance of TRA* showed a slight advantage, this solution was further inves- tigated by running an implementation on one of the intended domain platforms; the Nintendo DS. This paper is structured to serve as a guide, of sorts, to some very interesting, and diverse, pathfinding solutions. In the spirit of this effort, all of the more important aspects of these solu- tions, and the pathfinding domain as a whole, are thoroughly explained.

Place, publisher, year, edition, pages
2008. , 68 p.
Keyword [en]
Pathfinding, Nintendo DS, RTS-game.
National Category
Computer Science
URN: urn:nbn:se:bth-5481Local ID: diva2:832863
Available from: 2015-04-22 Created: 2008-02-19 Last updated: 2015-06-30Bibliographically approved

Open Access in DiVA

fulltext(718 kB)85 downloads
File information
File name FULLTEXT01.pdfFile size 718 kBChecksum SHA-512
Type fulltextMimetype application/pdf

By organisation
Department of Interaction and System Design
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 85 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 50 hits
ReferencesLink to record
Permanent link

Direct link