Path-Finding

LeijaT · 16. Oktober 2015

Hey Leute,

ich wollte mich mal an ein neues Projekt wagen, um meine Kompetenzen etwas auszubauen. Allerdings habe ich selbst noch nie eine Pathfinding AI programmiert und abgesehen von vermutlich völlig umständlichen Vorstellungen
keine Idee, wie ich mein Vorhaben am besten angehe. Und zwar möchte ich eine Pathfinding AI programmieren (hält sich völlig simpel, vermutlich nichts kompliziertes für jemanden, der sowas schonmal gemacht hat).

Gegeben sei beispielsweise einfach ein weißes Feld mit schwarzen "Wegen" (sagen wir mal diese haben eine Breite von 25 Pixel (weiß nicht ob das relevant ist)) und einem Quadrat von 5 Pixeln.
Das Quadrat soll sich nun den kürzesten Weg von A nach B suchen, wobei Prämisse sei, dass die weiße Fläche nicht betreten werden darf.

Das ganze muss nicht animiert sein o.Ä. - mir geht es hier rein um den Algorithmus. Wie würde ich da am besten anfangen? Ich habe erst überlegt, das komplette Feld zu rastern und dann Feld für Feld abzufragen,
das erschien mir allerdings viel zu aufwändig. Hat da jemand einen sinnvolleren Vorschlag?

123marvin123 · 16. Oktober 2015

Schau dir mal den A*-Algorithmus an.

LeijaT · 16. Oktober 2015

Ja, den habe ich bislang auch ergoogled, bin mir allerdings nicht sicher, ob der für meine Bedürfnisse vielleicht schon viel zu hoch angesetzt ist.

maddin · 17. Oktober 2015

Vielleicht hilft dir ja die die Demo von PathFinding.js. Da wird ganz gut veranschaulicht wie die verschiedenen Algorithmen arbeiten.

LeijaT · 17. Oktober 2015

Zitat von maddin

Vielleicht hilft dir ja die die Demo von PathFinding.js. Da wird ganz gut veranschaulicht wie die verschiedenen Algorithmen arbeiten.

Danke, das ist auf jeden Fall schon mal sehr hilfreich. Also ist das Rastern meiner "Karte" quasi unumgänglich, wenn ich das richtig verstehe.
Das erscheint mir für mein Vorhaben nicht sonderlich produktiv, aber vielleicht geht es auch einfach nicht einfacher (was mich tatsächlich mal verwundern würde ^^)

Damit ihr vielleicht noch die ein oder andere Idee einwerfen könnt, wie man es geschickter angehen kann, hier mein Vorhaben:

Letztlich möchte ich ein Tool schreiben, dass die Laufwege von CS:GO mittels Overview-Map berechnet.
Ich habe mir also quasi vorgestellt eine "simple" Map zu basteln (Weiß = Laufweg, Schwarz = Blockade) und dort dann Start und Ende anzuklicken.
Das Tool soll nun (unter anderem und primär) den kürzesten Laufweg ermitteln.

So eine Map tatsächlich selber zu rastern erscheint mir mehr Arbeit als nötig, daher würde ich das Programm einfach nach Farbe des Bildes suchen lassen (daher schwarz/weiß).
Wenn das Bild jetzt aber sagen wir mal 800x600 Pixel (oder gar größer?) ist, wären das vermutlich zu viele Pixel und die Performance würde vermutlich stark drunter leiden, oder?

Gibt es vielleicht einen sinnvolleren Weg, mein Vorhaben umzusetzen?

maddin · 17. Oktober 2015

Das klingt aber so als wäre ein Pathfinding-Algorithmus genau das was du suchst.
Du musst auch bedenken, das:
a) Das ne Demo für (eine) Javascript Implementierung des Algorithmus ist. Andere Sprachen sind da eventuell schneller.
b) Der auch bei jedem Durchgang etliche Pixel (mit Verzögerung dazwischen) bemalt, was den eigentlichen Vorgang dadurch zwar veranschaulicht, aber deutlich verlangsamt. Steht auch extra in der Repo "The pathfinding speed is slowed down in the demo".

Wenn ich folgenden Code nehme:

JavaScript

var grid = new PF.Grid(800, 600);


var finder = new PF.AStarFinder({
    allowDiagonal: true,
    dontCrossCorners: false,
    heuristic: PF.Heuristic.manhattan,
    weight: 1
});


var timeStart = window.performance.now();
finder.findPath(0, 0, 799, 599, grid);
var duration = window.performance.now() - timeStart;
console.log(duration + "ms");

Alles anzeigen

(sind die Standardeinstellungen von der Seite) und den in der Browser-Konsole auf https://qiao.github.io/PathFinding.js/visual/ laufen lasse, wird der Weg vom 0,0 nach 799,599 in 22.850000000000364ms berechnet. Klar, da sind jetzt keine Hindernisse zwischen. Aber nur mal so um den Vergleich zwischen der Tatsächlichen Rechenzeit zu der Zeit die da Dargestellt wird zu veranschaulichen.

LeijaT · 17. Oktober 2015

Zitat von maddin

b) Der auch bei jedem Durchgang etliche Pixel (mit Verzögerung dazwischen) bemalt, was den eigentlichen Vorgang dadurch zwar veranschaulicht, aber deutlich verlangsamt. Steht auch extra in der Repo "The pathfinding speed is slowed down in the demo

Die Zeit ist auch nicht so relevant. Wobei 22ms ja nun auch echt nicht die Welt sind. Die Berechnung darf meinetwegen auch ruhig ein paar Sekunden brauchen, wobei es im ms-Bereich natürlich schon sehr nett ist.
Ich stehe jetzt nur vor dem Hindernis, wie ich die Karte selbst (möglichst automatisch) rastern lasse.

Ich werde aus dem Beispiels allerdings noch nicht so ganz schlau, wie die Verwendung des ganzen aussieht. Also den Weg sucht er ab, aber wie verwerte ich den dann letztendlich, um meinen Punkt (Männchen)
diesen Weg auch entlanglaufen zu lassen?

maddin · 17. Oktober 2015

Zitat von LeijaT

Also den Weg sucht er ab, aber wie verwerte ich den dann letztendlich, um meinen Punkt (Männchen)
diesen Weg auch entlanglaufen zu lassen?

Wenn du die Javascript Bibliothek nutzt, dann gibt fider.findPath ein Array zurück, das den schnellstmöglichen Weg anhand von Koordinaten im Raster beinhalten. Finding a Path

Du müsstest den dann von Punkt zu Punkt laufen lassen, bis du am ende angekommen bist.

LeijaT · 17. Oktober 2015

Alles klar, danke. Ich werde mich morgen mal intensiv damit befassen und hoffen, dass ich es hinkriege. Sonst melde ich mich nochmal

breadfish.de 12. März 2022