Einen freien Weg mit Wegpunkten finden

[Flogo]

Wieder mal geht es bei mir um ein 2D Spiel:

Ich verschiebe bis jetzt Figuren indem ich ihnen ein Ziel (Point) gebe und sie bei jedem Zeichnen der Szene(wird über Timer gesteuert) einen Schritt in Richtung dieses Zieles machen lasse.

Jetzt ergibt sich aber das Problem, dass nicht alle Bereiche der Szene zum Laufen freigegeben sein sollen. Im Moment läuft die Figur gerade auf das Ziel zu und bleibt dann stehen, wenn es nicht weiter geht. Es sind also nur direkte Weg möglich.

Ich stell mir als Lösung soetwas vor wie

Delphi-Quellcode:

if direkterWegMöglich then macheEinenSchritt // alte Variante
else macheEinenSchrittZumNächstenWegPunktInDerRichtigenRichtung

Mein Problem liegt in der zweiten Zeile (*surprise*):
- Wie entscheide ich zu welchem Wegpunkt ich muss?
- Wie vermeide ich Sackgassen?
- könnte man das auch mit vordefinierten Wegpfaden machen und wäre das besser?

Ich bin über jede Anregung oder Alternative dankbar

[Ratte]

Such mal nach [google]"A*" Delphi[/google]!

Ratte

[mirage228]

Zitat von Ratte:

Such mal nach [google]"A*" Delphi[/google]!

Ratte

Ähm, ich glaube es gibt ziemlich viele Seiten die ein Wort mit einem großen A am anfang und Delphi im Text haben...

mfG
mirage228

[xineohp]

wobei du mit A* nicht weit kommen wirst, weil Sonderzeichen (*) ignoriert werden und der Rest (A) ein zu häufiges Wort ist ...

[xineohp]

Ich glaube er meint den Algorithmus, welcher afaik "A*" heißt. Nur wie man nach dem Suchen soll ist mir ein Rätsel.

[OregonGhost]

Wie wär's mit [google]"A Star Algorithm"[/google]?
Auch eine Suche nach [google]"A algorithm"[/google] (der Stern wird ja auch auf den Seiten ignoriert) liefert vernünftige Ergebnisse.

Ganz generell empfehle ich folgenden Artikel: Gamasutra - Smart Moves: Intelligent Path-Finding. Da wird auch A* abgehandelt, und es ist eine (in Delphi geschriebene) Demo herunterladbar.

[nailor]

um das zu lesen muss man sich aber bei denen anmelden. (nur so als hinweis, sollte nicht wirklich abhalten)

[xineohp]

auch hier wurde das ganze schonmal erwähnt: http://www.delphipraxis.net/internal...ect.php?t=2280
und in der c't 8.2003 aus Seite 168 (Scheinintelligenz) war auch mal ein interessanter Artikel dazu.

[OregonGhost]

Zitat von nailor:

um das zu lesen muss man sich aber bei denen anmelden. (nur so als hinweis, sollte nicht wirklich abhalten)

Tja, sowas merkt man nicht, wenn man überall dauerangemeldet ist 8)

Wenn man Spiele entwickeln will, lohnt es sich aber ohnehin auf jeden Fall, bei Gamasutra.com und Gamedev.net angemeldet zu sein...

[Thebe]

die GameDev Variante: http://www.gamedev.net/reference/pro...eatures/astar/