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.

<p>In real-time strategy (RTS) games, the human player faces tasks such as resource allocation, mission planning, and unit coordination. An Artificial Intelligence (AI) system that acts as an opponent against the human player need to be quite powerful, in order to create one cohesive strategy for victory. Even though the goal for an AI system in a computer game is not to defeat the human player, it might still need to act intelligently and look credible. It might however also need to provide just enough difficulty, so that both novice and expert players appreciates the game. The behavior of computer controlled opponents in RTS games of today has to a large extent been based on static algorithms and structures. Furthermore, the AI in RTS games performs the worst at the strategic level, and many of the problems can be tracked to its static nature. By introducing an adaptive AI at the strategic level, many of the problems could possibly be solved, the illusion of intelligence might be strengthened, and the entertainment value could perhaps be increased.</p><p>The aim of this dissertation has been to investigate how dynamic scripting, a technique for achieving adaptation in computer games, possibly could be applied at the strategic level in an RTS game. The dynamic scripting technique proposed by Spronck, et al. (2003), was originally intended for computer role-playing games (CRPGs), where it was used for online creation of scripts to control non-player characters (NPCs). The focus in this dissertation has been to investigate: (1) how the structure of dynamic scripting possibly could be modified to fit the strategic level in an RTS game, (2) how the adaptation time possibly could be lowered, and (3) how the performance of dynamic scripting possibly could be throttled.</p><p>A new structure for applying dynamic scripting has been proposed: a goal-rule hierarchy, where goals are used as domain knowledge for selecting rules. A rule is seen as a strategy for achieving a goal, and a goal can in turn be realized by several different rules. The adaptation process operates on the probability of selecting a specific rule as strategy for a specific goal. Rules can be realized by sub-goals, which create a hierarchical system. Further, a rule can be coupled with preconditions, which if false initiates goals with the purpose of fulfilling them. This introduces planning.</p><p>Results have shown that it can be more effective, with regard to adaptation time, re-adaptation time, and performance, to have equal punishment and reward factors, or to have higher punishments than rewards, compared to having higher rewards than punishments. It has also been shown that by increasing the learning rate, or including the derivative, both adaptation, and re-adaptation times, can effectively be lowered.</p><p>Finally, this dissertation has shown that by applying a fitness-mapping function, the performance of the AI can effectively be throttled. Results have shown that learning rate, and maximum weight setting, also can be used to vary the performance, but not to negative performance levels.</p>

In real-time strategy (RTS) games, the human player faces tasks such as resource allocation, mission planning, and unit coordination. An Artificial Intelligence (AI) system that acts as an opponent against the human player need to be quite powerful, in order to create one cohesive strategy for victory. Even though the goal for an AI system in a computer game is not to defeat the human player, it might still need to act intelligently and look credible. It might however also need to provide just enough difficulty, so that both novice and expert players appreciates the game. The behavior of computer controlled opponents in RTS games of today has to a large extent been based on static algorithms and structures. Furthermore, the AI in RTS games performs the worst at the strategic level, and many of the problems can be tracked to its static nature. By introducing an adaptive AI at the strategic level, many of the problems could possibly be solved, the illusion of intelligence might be strengthened, and the entertainment value could perhaps be increased. The aim of this dissertation has been to investigate how dynamic scripting, a technique for achieving adaptation in computer games, possibly could be applied at the strategic level in an RTS game. The dynamic scripting technique proposed by Spronck, et al. (2003), was originally intended for computer role-playing games (CRPGs), where it was used for online creation of scripts to control non-player characters (NPCs). The focus in this dissertation has been to investigate: (1) how the structure of dynamic scripting possibly could be modified to fit the strategic level in an RTS game, (2) how the adaptation time possibly could be lowered, and (3) how the performance of dynamic scripting possibly could be throttled. A new structure for applying dynamic scripting has been proposed: a goal-rule hierarchy, where goals are used as domain knowledge for selecting rules. A rule is seen as a strategy for achieving a goal, and a goal can in turn be realized by several different rules. The adaptation process operates on the probability of selecting a specific rule as strategy for a specific goal. Rules can be realized by sub-goals, which create a hierarchical system. Further, a rule can be coupled with preconditions, which if false initiates goals with the purpose of fulfilling them. This introduces planning. Results have shown that it can be more effective, with regard to adaptation time, re-adaptation time, and performance, to have equal punishment and reward factors, or to have higher punishments than rewards, compared to having higher rewards than punishments. It has also been shown that by increasing the learning rate, or including the derivative, both adaptation, and re-adaptation times, can effectively be lowered. Finally, this dissertation has shown that by applying a fitness-mapping function, the performance of the AI can effectively be throttled. Results have shown that learning rate, and maximum weight setting, also can be used to vary the performance, but not to negative performance levels.