Alle Wege zum Ziel finden

[ISAS]

Durch Backtracking kann man ja EINEN Weg finden lassen, der zum Ziel führt. Ich will aber nun alle Wege finden lassen, die zum Ziel führen, aber ohne einmal zurückgegangen zu sein. Also, hab hier ein Bsp, wie ich das meine:
http://members.nudsl.at/a0347601/wegberechnung2.bmp


Erklärung zu dem Bild:

Grün -> Startpunkt
Blau -> Ziel
Rot -> Hinderniss
Grau -> Weg, ohne zurückgehen


Was er nun tun soll:

1. Alle Wege ohne Zurückgehen berechnen und makieren (Sprich: Alle Grauen)

PS: Später wird dann der kürzeste Weg daraus berechnet

[shmia]

Zitat:

Zitat von ISAS

Durch Backtracking kann man ja EINEN Weg finden lassen, der zum Ziel führt.

Oder man findet den kürzesten bzw. optimalsten Weg.
http://www.laurentianum.waf-online.de/backtr.htm
Wenn du alle Wege finden willst, dann nennt man das Tiefensuche.

[Chewie]

Zitat:

Zitat von shmia

Wenn du alle Wege finden willst, dann nennt man das Tiefensuche.

Auch wenn meine KI-Vorlesung noch nicht allzuweit fortgeschritten ist: Tiefensuche ist doch so wie die Breitensuche eine Möglichkeit, einen Suchbaum, der alle Lösungen enthält, abzuarbeiten, solange, bis eine Lösung gefunden ist. Wenn man dies solange wiederholen würde, bis man am Ende des Baumes angelangt ist, hätte man alle Lösungen. Aber wie kann man bestimmen, wann man den ganzen Baum durchsucht hat?
Und mit der Tiefensuche würde das sowieso nicht immer gehen, da diese nicht vollständig ist (d.h. es wird nicht immer eine Lösung gefunden, wenn eine vorhanden ist).

[ISAS]

Hab ja geschrieben, dass ich später den kürzesten Weg finden will. Habs nun anders gemacht. Pathfinding bzw A* algo heisst das Zauberwort. Zwar hab ich das überhaupt nicht verstanden und auch viele Hilfsmittel haben mir nichts gebracht, aber folgendes Bild hilft doch sehr.

Bild

Wenn das Bild dann so "aussieht", dann is eigentlich schon alles geschafft. Der Spieler muss nur noch schauen, wo nebenan die kleinste Zahl ist und diese nehmen.

Delphi-Quellcode:

weg:=-1;

for k:=0 to 85 do begin  //So hoch, kann die höchste Entfernung sein
gehen:=true;
weg:=weg+1;
for i:=0 to 15 do       //Laenge
for j:=0 to 13 do begin //Breite

 if  Laby[i,j]=weg then
 if gehen then begin
  if Laby[i+1,j]>=weg then Laby[i+1,j]:=weg+1; //Alle angrenzenden
  if Laby[i-1,j]>=weg then Laby[i-1,j]:=weg+1; //Felder werden um
  if Laby[i,j+1]>=weg then Laby[i,j+1]:=weg+1; //1 erhöht, solange
  if Laby[i,j-1]>=weg then Laby[i,j-1]:=weg+1; //sie noch keine Zahl haben
 end;

end;
end;

Lösung besteht aus 3 for-schleifen, die je nach Grösse des Labyrinths variiren

[negaH]

Wenn du A* benutzt hast dann beantwortet dies aber nicht deine Frage. Du wolltest einen Algo. der die ALLE möglichen Wege aufzeichnet. Nun A* findet am Schluß nur einen Weg, den kürzesten. Übrigens ist A* ein typischer Backtracking Algorithmus.

Gruß Hagen