Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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
Identifiers
URN: urn:nbn:se:bth-5481Local ID: oai:bth.se:arkivex5774F7E40C75E086C12573F4006665DFOAI: oai:DiVA.org:bth-5481DiVA: diva2:832863
Uppsok
Technology
Supervisors
Available from: 2015-04-22 Created: 2008-02-19 Last updated: 2015-06-30Bibliographically approved

Open Access in DiVA

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

By organisation
Department of Interaction and System Design
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 203 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: 107 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf