Dieses Programm sucht auf einer vorher zu definierenden (selbst zu editierenden oder zu ladenden) Karte den 'kürzesten' Weg vom Starpunkt (graues Quadrat) zum Zielpunkt (grünes Quadrat). Dabei werden verschiedene Geländetypen bzw. Geländewegkosten berücksichtigt. Die Geländekosten gehen vom normalen Weg (Kosten=1) bis zum Gebirge (Kosten=7), Mauern sind nicht überwindbar und müssen umgangen werden.
Das Programm benutzt im Prinzip den bekannten A* - Suchalgorithmus. Das heißt im Prinzip werden von jeder X,Y- Position aus alle umliegenden Felder auf bisherige Kosten und zu erwartende Kosten bis zum Ziel hin untersucht. Als nächste X,Y-Position wird diejenige mit den bisher geringsten Gesamtkosten untersucht. Dazu wird aus Geschwindigkeitsgründen ein sogenannter Priority-Queue benutzt.
Wenn "optimize" aktiviert ist wird jeder Knoten gegebenenfalls mehrfach untersucht und bei geringeren Kosten des aktuellen Weges durch diesen ersetzt.
Während der Suche kann durch Rechtsklick auf ein beliebige Position deren Eigenschaften (Kosten usw.) untersucht werden.
Solche Wegfindeverfahren werden üblicherweise in Computer- Strategiespielen eingesetzt.
Für den tatsächlichen Einsatz in diesem Bereich wären noch einige kleinere Optimierungen nötig. Zum Beispiel ist die Option "optimize" relativ zeitaufwendig wenn Ersetzungen vorgenommen werden.
Kommentare, Tipps usw. bitte an heiko.zuegel@web.de
Funktionen der Buttons:
Test : vollständige Suche durchführen
GO : neue Suche starten
Next : nächsten Suchschritt durchführen
Play : ganze Suche langsam durchführen
Stop : Suche abbrechen
Clear: Anzeige von letzter Suche löschen
Download: PathFinder (300KB)
Links zum Thema:
Stout, W. Bryan. "Smart Moves: Intelligent Pathfinding" (Oktober/November 1996).
Pottinger, Dave C. "The Future of Game AI" (August 2000).
Steven Woodcock's Game AI Page
Gamasutra.com
Zurück zu meiner Homepage