[Zurück]

P. Klaffenböck:
"Pfadsuche in einer Triangulation Reduction im Mammoth Massive Multiplayer Online Research Framework.";
Betreuer/in(nen): G. Raidl; Institut für Computergrafik und Algorithmen, 2014.

Die Suche nach optimalen Pfaden ist ein Bereich der künstlichen Intelligenz, die in vielen Computerspielen eine Rolle spielt. Dabei sollten die berechneten Pfade einerseits natürlich intelligent wirken, die Berechnung selbst sollte aber möglichst wenig Zeit in Anspruch nehmen, weil die zu bewegenden Objekte im Idealfall sofort beginnen sollen sich auf ihre Zielposition zu zu bewegen. Die Spielwelt wird für das Pathfinding in eine Graphenstruktur überführt, in der dann mit dem A*-Algorithmus der kürzeste Pfad zwischen Start- und Zielpunkt gesucht wird. Um mit großen Suchräumen, besser umgehen zu können, wurden einige Methoden entwickelt die Spielwelt oder deren Graphendarstellung zu abstrahieren. Im Rahmen dieser Arbeit wurde eine dieser Abstraktionsmethoden, Triangulation Reduction, im MMO Research Framework Mammoth 1 implementiert und mit zwei konkreten Suchalgorithmen getestet.

Pathfinding is an area in artificial intelligence, that plays an important role in many computer games. On the one hand, the calculated paths should look natural and intelligent. On the other hand it is very important, that the paths are computed very quickly, since the objects should start to move more or less immediately. The game world is usually transformed into a search graph, on which the A* algorithm is used to determine the shortest path between the start and the goal points. To better deal with large search spaces, quite a number of abstractions on the game world or the corresponding graph have been designed. As part of this thesis, one of these abstraction methods, Triangulation Reduction, has been implemented in the MMO Research Framework Mammoth 1, and has been tested with two
concrete search algorithms

http://publik.tuwien.ac.at/files/PubDat_231659.pdf