Evaluation und Analyse verschiedener Wegfindungsalgorithmen zur Bestimmung ihrer Verwendung in digitalen Spielen
Bachelorarbeit Lars Janson
Die Entwicklung, als auch die Nutzung digitaler Spiele ist in den letzten zwei Jahrzehnten stark gewachsen. Mittlerweile gibt es neben den großen Entwicklerstudios, auch zahlreiche kleinere Spielestudios, die unabhängig sind und nicht im Auftrag eines großen Publisher arbeiten. Doch haben alle Spieleentwickler ähnliche Probleme, eines davon ist die Wegfindung von Charakteren. Das Finden des kürzesten Weges, ohne eine Kollision mit anderen Objekten zu verursachen, ist eine weitreichende Herausforderung in der Entwicklung von digitalen Spielen in den meisten Genres.
Es gibt mehrere Ansätze und zahlreiche, darauf aufbauende, Algorithmen, um diese Herausforderung zu bewältigen. Das Problem der meisten Entwickler ist es, einen Algorithmus zu finden, der ihre Anforderungen erfüllt. Es ist schnell herauszufinden, ob sich ein Algorithmus auf Veränderungen der Spielwelt automatisch anpassen kann oder nicht. Aber das Hauptproblem ist, das neue Anforderungen, wiederum ein Umdenken erfordern. Denn ohne vorherige Erfahrungen wissen Entwickler nicht, wie sich die Algorithmen auf verschieden langen Distanzen, verschiedenen Umgebungen oder auf die Anwendung auf mehrere Charaktere auswirkt. Es fehlt eine Übersicht, wie sich verschiedene Wegfindungsalgorithmen, in verschiedenen Situationen verhalten und mit welchem Gewinn oder Verlust an Berechnungszeit, sie dies tun.
Das Ziel ist es vier verschiedene Wegfindungsalgorithmen in einer einheitlichen Testumgebung zu vergleichen und verschiedene Situationen, wie das dynamische Verändern der Spielwelt, zu simulieren. Das Wechseln der verschiedenen auftretenden Situationen und der Algorithmus, welcher den Weg berechnet, sollen dynamisch, also zur Laufzeit gewechselt werden können. Die Berechnungszeit und die Länge des errechneten Weges, sollen Teil der Evaluierung und der Bestimmung der Verwendung werden. Die Algorithmen sollen in ihrer Implementierung optimiert sein, um weniger Berechnungszeit zu verwenden, aber die Optimierung der Algorithmen soll nicht Teil der Arbeit sein.