Pathfinding mit A*

[Amateurprofi]

Hallo Michael,

wenn die Mauer oben zu ist, dann wirst Du mit Deiner Methode die für den nächsten Schritt verfügbaren Felder zu ermitteln, nicht weiterkommen.
Wenn die Mauer oben zu ist, und du von 2/3 startest, geht das Programm auf 3/3, dann auf 3/2, und dann pendelt es zwischen 3/2 und 3/3 hin und her.

Warum ?:
Weil das Programm immer das erste Feld mit der kürzesten Distanz zum Zielfeld wählt und nicht merkt, daß der Weg über 3/2 bereits erfolglos probiert wurde und daß es eine Alternative gibt.

Die Methode, die Strecke von einem Feld zum Zielfeld zu berechnen, hatte ich Dir ja gegeben und die ist auch korrekt.
Im Prinzip stelle Dir die Strecke von einem Feld zum Zielfeld als die Hypothenuse eines rechtwinkligen Dreiecks vor. Die Katheten sind dann die Strecken von i nach dest.x und von j nach dest.y

dx:=abs(dest.x-i);
dy:=abs(dest.y-j);

hierbei kann natürlich eine der Strecken 0 sein (rein theoretisch auch beide, aber bei Deinem Programm wird diese Situation schon vorher abgefangen)

Die Länge der Hypothenuse (also der Strecke von einem Feld zum Zielfeld) wäre dann Sqrt(dx^2 + dy^2), jedenfalls hat das Herr Pythagoras gesagt.
Da Du aber nicht die Länge der Strecke brauchst, sondern nur die Information, bei welchem Feld die Strecke am kürzesten ist, kannst Du Sqrt() weglassen (andernfalls mußt Du List.F als Single, Double etc. deklarieren).

Geh mal auf die Seite www.matheprisma.uni-wuppertal.de/Module/BackTr
und schau Dir unter "Labyrinth" an wie solch ein Backtracking Verfahren funktioniert.

Gruß, Klaus
Übrigens : wenn Die Mauer offen ist, funktioniert das Programm auch, wenn Du die Position des Zielfeldes auf 6/4 oder 6/3 stellst.