spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

C-/C++-Quelltext

//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

C-/C++-Quelltext

/*
 * 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;
}