AStar Pathfinding Lab

[Travis]

Dank eines guten Tutorials über den A* Algorithmus und der Hilfe einiger User bezüglich der PB-Syntax kann ich hier nun mein erstes kleines Tool vorstellen. Es handelt sich um einen Experimentierkasten zum Thema Pathfinding. Es beinhaltet eine editierbare Testumgebung und bietet die Möglichkeit verschiedene Berechnungsmethoden und mögliche Wegrichtungen 'on-the-fly' auszuprobieren.

Screenshot, Executable und Source gibt's hier ---> http://travis.bplaced.net/Tools.html <----

[dige]

Stark scheint auch gut zu funktionieren.

[STARGÅTE]

Nette sache , nur wird man ihn wahrscheinlich nicht in Strategiespielen einsetzen können,
weil deine Procedure FindPath(), was ja vermutlich der Kern der sache ist, bei großen Karten (200+ Felder) und "unglückliche" Wegen zu langsam wird und schon mal 200ms dauert.
Hängt natürlich von der Methode ab, die man wählt, manche schaffens auch dort unter 10ms zu bleiben.

Was ich damit sagen will ist:
Wenn du wirklich nur ein Tool erstellen wolltest, zum darstellen der verschiedenen Methoden die es gibt einen Weg zu berechnen, dann ist dir das sehr gut gelungen
Unter Belastung wird man jedoch die Prozedur nicht nutzen können.

[Travis]

thx. Ja, das mit der Performance wird sicherlich noch interessant. Es muss halt an die Bedürfnisse angepasst werden. Man muss die Pfade auch nicht ständig neu berechnen. Evtl nur wenn sich Pfade kreuzen, oder Hindernisse auftauchen. Meine Testumgebung schluckt aber auch viel Zeit, wenn viel gezeichnet wird. Aber das wird schon..

[STARGÅTE]

jo das zeichnen habe ich ja herausgenommen, habe wirklich nur die Zeit um deine FindPath() gemessen.

Für Einsatzzwecke würde ich noch folgendes vorschlagen:

• Threads benutzen, sodass der Weg "in ruhe" im Hintergrund berechnet wird, und das Hauptprogramm nicht gestört wird, und wenn der Weg gefunden ist, kann ihn das Hauptprogramm nutzen.
  Stichworte: ThreadSafe, und Thread-Feste Prozeduren, Mutex, usw.
• Die Weg-Bäume von beiden Seiten (Start und Ziel) wachsen lassen. Zur zeit wächst dein Baum (egal welche Methode) ja immer vom Start zum Ziel. Würde nun aber auch vom Ziel ein Baum wachsen und der Weg dann der erste kontackt beider Bäume sein, wäre die Berechung vorallem bei großen Karten schneller.

Wo ich immer Probleme bei meinen Projekten hatte, war, wie ich bewegliche Hindernisse (Einheiten) dort einfließen lassen soll.
Wie du ja richtig sagtest, muss man eigentlich nur ein mal den Weg berechnen lassen. Das funktioniert aber nur solange wie die Karte statisch ist. Klar sind einheiten nicht so groß, als dass sie die Weg so unglaublich doll ändern würden.
Aber es gibt ja auch u.u. so eine Art Eingänge, und wenn dann dort mehrere Einheiten hinfahren, während ich meinen Weg ablaufe, dann kommts zur Kollision, und die Einheiten drängeln sich "dumm" aneinander vorbei.

Bin auf weitere Ergebnisse sehr gespannt