wegsuche in delphi?

[Tryer]

Hier findst Du ein recht gutes Tutorial zum A*-Algorithmus, auf dessen Basis hab ich selber auch erfolgreich eine Wegsuche realisiert. Falls Du danach festgestellt hast das der Algorithmus für Dich brauchbar ist hilft Dir das folgende vielleicht etwas weiter.

Der A* Algorithmus an sich ist eine Kombintion verschiedener anderer Algorithmen, er hat den Vorteil recht schnell zu sein und findet den Weg zum Ziel auf jeden Fall (so es denn einen gibt). Wenn er einen Weg findet dann ist das auf jeden Fall auch der günstigste Weg (entsprechend der Definition der Wegkosten).

Durch die Reihenfolge in der man neue potentielle Wegpunkte während der Suche aufnimmt lässt sich in gewissem Rahmen die Form des Weges (mgl. eckig (handlich für Browsergames), mgl. diagonal, ..) beeinflussen.
Die Übernahme neuer potentieller Wegpunkte ist der Knackpunkt des Algorithmus. Hier lassen sich auch leicht Erweiterungen wie z.B. Wurmlöcher oder Strassen (k.A. was Du für ein Spiel proggst)mit einpflegen die dann in die Berechnung des optimalen Weges mit einfliessen.

Du solltest in jedem Fall dem Hinweis im Tutorial folgen und einen binären Suchbaum (BinHeap) für die offenen Wegpunkte verwenden, das bringt einiges an Performance.
Wenn zu einem Zeitpunkt immer nur ein Weg gesucht werden soll dann bietet es sich an innerhalb der Map auch sofort die Daten für die Wegsuche mit abzulegen, das kostet zwar Speicherplatz aber es beschleunigt die Suche nochmal enorm da nicht immer wieder Referenzen zwischen Kartendaten und Wegdaten hergestellt werden müssen.

Ich habs bei mir so realisiert:

Delphi-Quellcode:

  TCoords = packed record
    case LongInt of
     0: (Y, X: Word);
     1: (XY: DWord);     
  end;

  PPMapItem = ^PMapItem;
  PMapItem = ^TMapItem;
  TMapItem = record
    Parent: PMapItem;     // Feld von dem dieses Feld erreicht wurde (>Weg<)
    Coord: TCoords;       // Map-Koordinaten (entspricht Array-Index)
    GCost: Byte;          // Fixe Einflugkosten für dieses Feld (Terrainkosten)
    GWCost: LongWord;     // Flugkosten vom Start zu diesem Punkt
    HCost: LongWord;      // angenommene Flugkosten bis Ziel (Heuristic)
    Region: Byte;         // Durchflugberechtigung?
    BinHeapPos: LongWord; // Position im BinHeap (für schnelleres ReSort nach Änderung von GWCost)
    IsClosed: Boolean;    // Feld als Wegpunkt übernommen?
  end;

  TMapArray = array of array of TMapItem;

Durch das "IsClosed" spare ich mir zusätzlich auch die Liste der übernommenen Wegpunkte, das bringt nochmal einiges an Performance da ich bei neu übernommenen Wegpunkten nicht suchen muss ob diese bereits einmal erreicht wurden.

MfG,
Tryer