#1 15.02.2005 19:57:07

Chris
ExtremeMember
Ort: Erlangen, Bay
Registriert: 24.01.2005
Beiträge: 694
Web-Seite

A* Pathfinding Klasse

Tja, wie der Name schon sagt eine A* Wegfind-Klasse.

Einfach einbinden und TPathfinder steht als Klasse zur verfügung.

Code:

procedure LoadFromBMPFast(filename : string; toleranz : integer);


und schon wird ein Terrain aus einem Bitmap geladen und in die Klasse mit eingebunden. (Sehr praktisch für Heightmaps)
Toleranz ist der max. Wert (=Höenunterschied) bei dem der Punkt als nicht begehbar definiert wird.

Code:

function getPathAB(const a,b : TPoint) : TNodeList;


Gibt ein Array of TPoint zurück in dem die einzelnen Wegpunkte stehen.

bei Fragen helfe ich gerne.

mfg Chris


Attachments:
Attachment Icon PathFind.pas, Größe: 8,770 bytes, Downloads: 1,039

Nimm meinen Rat an - ich brauch ihn sowieso nicht

Offline

 

#2 15.02.2005 23:14:36

maximov
Member
Ort: Hamburg
Registriert: 25.01.2005
Beiträge: 84

Re: A* Pathfinding Klasse

A* is cool  :blues:

Sieht aber relativ rudimentär aus  smile  Hast du mal die performance getestet? IMO kann diese implementierung nicht sonderlich schnell sein *duck* Das suchen in der openList ist soo relativ ungesund.

Mein A* sah am anfang ähnlich aus (wenn auch mit entkoppeltem kanten-bewertungs-callback) und ich konnte ihn min. um den faktor 10 beschleunigen, bzw. die komplexitätsstufe verringern.

Ich hab leider die links nicht mehr aber zu A* gibts haufenweise gute optimierungs ratschläge.


maximov (aka maDXam or IDKFA)

Offline

 

#3 17.02.2005 12:55:00

Chris
ExtremeMember
Ort: Erlangen, Bay
Registriert: 24.01.2005
Beiträge: 694
Web-Seite

Re: A* Pathfinding Klasse

ne extrem schnell is der natürlich nicht.
Binäre Bäume kann man natürlich noch verwenden.

Vorallem is der sehr langsam wenn man versucht nen unmöglichen weg zu finden. Das könnte man noch die 'FloodFill' methode einbauen.

Aber für meine momentanen Zwecke reicht es (noch).
und zum verstehen von A* ist die Klasse auch ganz gut, weil wirklich nur die basics enthalten sind.

zur performance:
512x512 Map: ca. 0.001 sec. (Athlon 1800 MHz. 1GB RAM)

mfg Chris


Nimm meinen Rat an - ich brauch ihn sowieso nicht

Offline

 

#4 17.02.2005 13:06:44

maximov
Member
Ort: Hamburg
Registriert: 25.01.2005
Beiträge: 84

Re: A* Pathfinding Klasse

Zitat:

ne..zur performance:
512x512 Map: ca. 0.001 sec. (Athlon 1800 MHz. 1GB RAM)

das sagt so erstmal nix: nur wenn du von a(0,0) nach b(511,511) getestet hast.

Aber hast schon recht; so lange man keine echtzeigberechnung braucht, is die geschwindigkeit bei solchen werten nicht allzu wichtig.


maximov (aka maDXam or IDKFA)

Offline

 

#5 17.02.2005 16:59:38

Chris
ExtremeMember
Ort: Erlangen, Bay
Registriert: 24.01.2005
Beiträge: 694
Web-Seite

Re: A* Pathfinding Klasse

genau big_smile

mfg Chris


Nimm meinen Rat an - ich brauch ihn sowieso nicht

Offline

 

Brett Fußzeile

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson