Felix Wiener

Jump Point Search auf verallgemeinerten Spielbrettern

Betreuer: Prof. Dr. Wolfgang Mulzer
Abschluss: Bachelor of Science (B.Sc.)
Abgabedatum: 04.07.2017

Kurzbeschreibung

Jump Point Search (kurz JPS) ist ein neuer Algorithmus in der Wegfindung. Durch seine herausragenden Performance findet er, vor allem in der Spiele-Entwicklung, viel Anwendung.Leider beschränkt sich die Definition dieses Algorithmus' auf quadratische Gitter.

Meine Arbeit beschäftigte sich mit der Idee, den Anwendungsbereich des JPS zu erweitern.Hierfür abstrahierte und mathematisierte ich sowohl seine Entwicklung, als auch seine Handlungsweise,adaptierte dieses Konzept auf regelmäßige Dreiecks-tesselierte Flächen und arbeitete die Kriterien für eine Verallgemeinerung heraus. Den entstandenen Algorithmus analysierte ich stochastisch und testete ihn gegen den "Jack of all trades"-Pathfinder A*.