Inlämning av Examensarbete / Submission of Thesis

Samuel Erdtman; Johan Fylling MCS-2008:02, pp. 68. TEK/avd. för interaktion och systemdesign, 2008.

The work

Författare / Author: Samuel Erdtman, Johan Fylling,
Titel / Title: Pathfinding with Hard Constraints: Mobile Systems and Real Time Strategy Games Combined
Abstrakt Abstract:

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

Ämnesord / Subject: Datavetenskap - Computer Science\Artificial Intelligence

Nyckelord / Keywords: Pathfinding, Nintendo DS, RTS-game.

Publication info

Dokument id / Document id:
Program:/ Programme Civilingenjör i datateknik, programvaruteknik/
Registreringsdatum / Date of registration: 02/20/2008
Uppsatstyp / Type of thesis: D-Uppsats/Magister/Master


Handledare / Supervisor: Rune Gustavsson
Examinator / Examiner: Guohua Bai
Organisation / Organisation: Blekinge Institute of Technology
Institution / School: TEK/avd. för interaktion och systemdesign
S-372 25 Ronneby
+46 455 38 50 00
I samarbete med / In co-operation with: Pixelknights

Files & Access

Bifogad uppsats fil(er) / Files attached: master_thesis-samuel_erdtman_and_johan_fylling.pdf (735 kB, öppnas i nytt fönster)