Wegfindungsroutine in Delphi

Ragnara · Hält's aus hier Beiträge: 7 D6 Pers

Hi, ich schreibe an einem RPG und brauche nun einen Wegfindungs-Algorithmus für die NPCs. Dabei hatte ich an A* gedacht. Leider finde ich fast nur Demos in C(++) dazu - oder ich durchblicke den Code nicht richtig. Kann mir jemand helfen ?

Ich arbeite mit einer selbstgeschriebenen Map-Klasse, die ein dynamisches zweidimensionales Tiles-Array hat. Das Tiles-Format ist etwa:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:

type TMapTile = packed record
    Index: Word;                     //Nummer der verwendeten Tile-Grafik
    Data: TMapTileData;           //Für bestimmte Verhaltensweisen, s.u.
    MoreData: array[1..4] of LongInt;  //Parameter für die in Data gespeicherten Verhaltensflags
end;

type TMapTileData = set of (mtdSolid, mtdTransparent,...);

Ich brauche keine unterschiedlichen Terrainkosten, es gibt nur begehbar und solide. Die NPCs besitzen alle die Properties XPos und YPos vom Typ Word. Diagonale Bewegung ist nicht geplant.

Danke im Vorraus !

EDIT: Ein einfacherer Algorithmus würde es natürlich auch tun. Er muss nur
a) zum Ziel führen und
b) die Performance des Games nicht stark verlangsamen.
Wenn der NPC ein paar mal vor ne Wand rennt oder kurz im Kreis rennt, ist das zwar nicht erwünscht, aber ich könnte damit leben, wenns nicht anders geht. Nur helft mir ! :cry:

_________________
cya

maximus · Beiträge: 896 Win XP, Suse 8.1 Delphi 4/7/8 alles prof

hi.

Ich hab den A* letztens mit delphi umgesetzt was auch prima geht, auch mit unterschiedlichen tile-kosten und überschäzter heuristic. Nur leider ist er noch kein bisschen optimiert, was beim A* sehr wichtig ist, da hunderte NPCs ja ihre wege finden wollen. Aber da gibt es recht effektive optimierungs möglichkeiten. zB. die berechnungen über mehrere frames verteilen etc.

Wenn du dennoch interesse hast sag bescheid, dann geb ich dir mein 'dirty-A*' test-programm :wink:

mfg.

_________________
mfg.
mâximôv

Udontknow · Beiträge: 2596 Win7 D2006 WIN32, .NET (C#)

Hallo!

Hier habe ich ein Tutorial über Rekursion geschrieben, daß sich auch mit Wegfindung beschäftigt (allerdings nicht via A*). Es ist evtl. für dich interessant.

Das Demo-Programm mit Sourcen kannst du hier downloaden.

@Maximus: Selbst wenn hunderte Entitäten ihren Weg finden sollen, wird ja nicht bei jedem Frame dieser hundertmal neu ermittelt. Nur wenn es plötzlich Hindernisse gibt, müsste man neu ermitteln.

Cu,
Udontknow

maximus · Beiträge: 896 Win XP, Suse 8.1 Delphi 4/7/8 alles prof

Udontknow hat folgendes geschrieben:

@Maximus: Selbst wenn hunderte Entitäten ihren Weg finden sollen, wird ja nicht bei jedem Frame dieser hundertmal neu ermittelt. Nur wenn es plötzlich Hindernisse gibt, müsste man neu ermitteln.

Is schon richtig. Aber bevor ich performance verschenke, optimiere ich lieber ein wenig, denn man kann nie genug davon haben :wink:

...man könnte zur optimieren und zeitverteilten berechnung auch mikro-threads einsetzen, nur die hab ich mit delphi noch nicht ausprobiert.

cu.

_________________
mfg.
mâximôv

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme