wegsuche in delphi?

[sweetmusic]

Hallo,

ich habe vor einiger Zeit begonnen ein Spiel zu programmieren und möchte es nun erweitern.
Dazu bräuchte ich aber eine Wegsuche, so wie man sie zB mit Prolog programmieren kann.
Habt ihr einen Tipp für mich, wie ich das in Delphi umsetzen kann?

Vielen Dank!

[fiasko]

Was ist denn

Zitat von sweetmusic:

so wie man sie zB mit Prolog programmieren kann.

? (Ja ich kenne Prolog) Zur not schreibst du einfach einen Prolog Intepreter in Delphi

[Luckie]

Warum sollte da snichta uch mit Delphi gehen?

Da aber viele Spiele in C/C++ geschrieben sind, würde ich mich bei der Suche mit Google (delphi wegsuche) nach Codeschnippslen nicht unbedingt auf Delphi beschränken.

[sweetmusic]

mh, das heißt also, dass ihr mir auch keinen direkten Vorschlag machen könnt...

Habt ihr schon mal etwas von A*-Pathfinding gehört?
Scheint eine ziemlich verbreitete Methode zu sein...

[fiasko]

Hätten wir schon, aber du sagst ja nicht wie du das in Prolog gemacht hast :-)

Das A*-Pathfinding ermittelt dir aus einer Menge von Knoten und Kantenbewertungen die kürzeste Strecke zu jedem Knoten von einem Startknoten aus. Ob du das verwenden kannst hängt davon ab wie dein Spielfeld aussieht (ich meine im Rechner).

[Nicodius]

do machst ne procedure (die nen Timer zu hilfe nimmt .... --> dann berrechnest du den kürzesten weg ... das umzusetzen ist ja nict so schwer oder?

[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

[sweetmusic]

danke für die tipps!

Ich hab nun auch schon ein paar Seiten im Netz gefunden, die mir helfen könnten..
Jetzt muss ich nur noch meine Kenntnisse in der Listenprogrammierung auffrischen
ich hoffe, dass es jetzt alles klappt.

Liebe Grüße

[DaFox]

Hi,

zum Thema A*: Der Entwickler, Ausgabe 03.2002 bzw. gleich Der Weg ist das Ziel - Pathfinding mit A*

Gruß,
Markus