A* Pathfinding

[alzaimar]

Ick stell mich jetz mal ganz dumm und frage: Du hast einen (gerichteten) Graphen und willst einen Weg von a nach b finden? Oder den Kürzesten? Und Du brauchst eine geeignete Datenstruktur? Sehe ich das richtig?
If Antwort = Nein Then ClickWeg Ansonsten hilft hier die 'mathematische' Definition eines Graphen. Das ist ein Tupel, bestehend aus Knoten (Nodes) und Kanten (Edges). Knoten könnten man einfach als Zahlen von 0...N-1 definieren. Die Kanten als Matrix E [0..N-1,0..N-1]. E[i,j] beschreibt dann die Entfernung, um von i nach j zu gelangen, also die 'Länge' der Kante von i nach j. Ein Wert von +Maxint würde z.B. bedeuten, das man gar nicht direkt von i nach j gelangen kann. Achtung: Wir definieren hier wirklich nur die Kanten des Graphen, also nicht Wege über diverse Knoten.

Damit kann man dann sehr schnell arbeiten. Ein Weg von i nach j würde z.B. als ein Array of Integer definiert. Ein Weg von Knoten #1 zum Knoten #5 würde z.B. so aussehen: [1,2,8,5]. Ich komme also von 1 über 2 und 8 nach 5.

Ich kenne den A*-Algorithmus leider nicht, und ich schäme mich dafür, weil es zur Allgemeinbildung gehört, sonst könnte ich Dir hier besser helfen. Ich weiss nur, das der A* der derzeit beste Algorithmus ist, um das Problem des 'shortest Path' zu lösen. Es gibt aber noch recht einfache Alternativen...