Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!
Werbeanzeige
C-/C++-Quelltext |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
//start: stadt[1] CPoint{10,20} //ziel: stadt[110] CPoint{560,200} //als ergebnis hätte ich da gern dann zb: stadt[1] CPoint{10,20} //Startstadt 1. knoten:stadt[6] CPoint{30,60} 2. knoten:stadt[29] CPoint{130,90} 3. knoten:stadt[42] CPoint{240,120} . . . stadt[110] CPoint{560,200} //Zielstadt |
Administrator
C-/C++-Quelltext |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
/* * Algorithmus zur Rekonstruktion des kürzesten Pfades * --------------------------------------------------- * P: berechneter kürzester Pfad * start: Startknoten * node: Zielknoten */ reconstruct_shortest_path (start, node, graph) { if (node != start) { push(node, P); // Lese den Vorgänger des aktuellen Knoten aus predecessor := getPredecessor(node, graph); reconstruct_shortest_path (start, predecessor, graph) } else return P; } /* * Der eigentliche A*-Algorithmus * ------------------------------ * graph: Zu untersuchender Graph * start: Startknoten * goal: Der Zielknoten * h: Heuristikfunktion zum Schätzen des Abstandes eines Knotens bis zum Ziel * S: Prioritätswarteschlange der Knoten, deren f-Wert bereits bekannt ist * N: Liste aller bereits besuchten Knoten */ A-Star (graph, start, goal, h, S, N) { insert (start,S); while not isEmpty(S) { current_node := pop(S); if current_node in N then // Es existiert kein Pfad vom Start zum Ziel return fail; insert (current_node, N); if (current_node == goal) then return reconstruct_shortest_path(start,goal, graph); else { // Finde alle vom aktuellen Knoten aus erreichbaren Knoten successors := expand(current_node, graph); // Speichere Vorgänger des expandierten Knotens im Graph save_predecessor_in_graph(current_node, graph) forall s in sucessors do { // Speichere Knoten von dem aus s erkundet wurde predecessor(s) := current_node; // Berechne und speichere die f-Kosten f(s) := g(s) + h(s); insert(s,S); } } } // Es konnte kein Pfad gefunden werden return fail; } |
Administrator
Zitat
Wendet man den A*-Algorithmus auf einem Knoten u an, so werden zuerst alle von diesem Knoten aus erreichbaren Nachbarn berechnet. Danach wird durch die Heuristik für jeden dieser Nachbarn eine Schätzung abgegeben, wie teuer es ist, von ihm aus zum Ziel zu kommen. Für jeden dieser Nachbarknoten v addiert der A*-Algorithmus nun die von der Heuristik geschätzten Kosten bis zum Ziel zu den Kosten, um vom Knoten u zu eben jenem Knoten v zu kommen. Die Vorgehensweise des Algorithmus lässt sich dabei durch folgende Gleichung beschreiben:
f(v) = g(v) + h(v)
Hierbei steht h(v) für die von der Heuristik für Knoten v geschätzten Kosten bis zum Ziel, g(v) für die bisherigen gesamten Wegkosten um vom Knoten bei dem man den A*-Algorithmus gestartet hat zum Knoten v zu kommen, und f(v) steht für die wahrscheinlich zu erwartenden Kosten, wenn man vom Startknoten aus über seine aktuelle Position (u) zu dem entsprechenden Nachbarn (v) weitergeht, um von dort aus irgendwie weiter zum Ziel zu gelangen. Im nächsten Schritt wird nun der Knoten weiter untersucht, welcher den geringsten f-Wert besitzt.
Werbeanzeige