#1 28.11.2006 17:05:45

simon
ProMember
Ort: Düsseldorf
Registriert: 03.06.2006
Beiträge: 168

graphen, ai und wie finde ich nun den Weg?

ich arbeite gerade an einer AI die Graph basierend arbeiten soll
leider stecke ich gerade etwas fest:

ich hab schon:
-variablen für das ganze (hab diese mal hier hin kopiert)
-ich hab auch schon nen alg. der mir die graphen in den speicher lädt
(dh ich stelle Nodes auf und die Software verbindet das alles - wenn
zwischen den Nodes nichts im Wege steht)

Code: delphi

t3d         = tv_3dvector;

tnodestree = record
  lineid : integer;
end;
tnodestreearray = array of tnodestree;


 tnodes = record
    pos         : t3d;
    tree        : tnodestreearray;
 end;
tnodearray = array of tnodes;




jetzt fehlt mir nur noch ein Algo. der mir den kürzesten (naja muss net immer der kürzeste sein;) ) Weg von Punkt A nach B wiedergiebt.

Problem  - ich weiss nicht so genau wie ich den Graphen nun untersuchen muss, so dass es nicht zuviel Zeit und RAM frisst - und das Ergebniss soll ja auch nach was aussehen;) nicht das die Gegner vor die Wand laufen  :idea:

hab mir mal dieses Tut. durgelesen:
http://wiki.delphigl.com/index.php/Tutorial_pathfinding2
komme aber trotzdem nicht weiter sad
(laut des Tutorials hänge ich bei: "Erzeugung des Netzwerkes" fest:(  )

hat das jemand mal gemacht und kann mir vieleicht ein paar Tips geben?
:doof:


grrr

Offline

 

#2 28.11.2006 17:44:38

Coolcat
ProGuru
Ort: Aachen, NRW
Registriert: 24.01.2005
Beiträge: 2780
Web-Seite

Re: graphen, ai und wie finde ich nun den Weg?

Im DelphiGL-Tutorial fehlt genau das eignetlich wichtige wink
Schau mal hier:
http://de.wikipedia.org/wiki/A%2A

ansonsten google mal nach A-Stern (bzw. A*)

Coolcat


My software never has bugs. It just develops random features.

Offline

 

#3 28.11.2006 17:49:48

JorEl
ExtremeMember
Registriert: 29.01.2005
Beiträge: 894

Re: graphen, ai und wie finde ich nun den Weg?

Wenn du wirklich den kürzesten Weg suchst, dann musst du prinzipiell in einer Rekursion alle Möglichkeiten durchspielen und jede einzelne durch eine Kostenfunktion (in diesem Fall wohl nur die Distanz) bewerten. Kann natürlich je nach Anzahl der Kanten sehr zeitintensiv werden - möglicherweise reicht es aber für deine Zwecke schon aus wenn du dir ein paar mögliche Wege ermittelst, danach abbrichst und aus den vorhandenen Lösungen die beste wählst.

Die Rekursion sollte eigentlich kein Problem sein. Vom aktuellen Knoten aus gehst du mit der Rekusion alle Kanten durch zu Knoten die noch nicht besucht wurden (um zu verhindern, dass du ewig im Kreis läufst). Sobald du eine mögliche Lösung hast fügst du diese in die Ergebnismenge ein, inklusive der Entfernung die man bei dieser Strecke zurücklegen müsste. Am Ende suchst du dir dann die Lösung mit minimaler Distanz raus und verwendest diese.

JorEl


Jesus hat gesagt - selig sind die, die da Leid erfahren, denn sie sollen getröstet werden... Ford Prefect hat gesagt - es ist unheimlich wichtig, dass wir miteinander reden und einen trinken.

Offline

 

#4 28.11.2006 19:09:50

simon
ProMember
Ort: Düsseldorf
Registriert: 03.06.2006
Beiträge: 168

Re: graphen, ai und wie finde ich nun den Weg?

Coolcat - genau das wichtigste fehlt;) -werde mal googlel

JorEl-> das Problem ist ja es ist alles für einen Egoshooter - da er im dunkeln spielt, sind die Levels riesieg(der polycount bleibt niedrig, da man eh wenig sieht;) und net so weit gerendert wird;)) -> und da haben wir hunderte (in manchen Fällen weit über 1000)von Knotenpunkten und auch nicht auf einer sondern auf mehreren Ebenen. desweiteren hab ich bis auf die "Distance" auch noch den "Bodenbelag"  in jedem Knotenpunkt gespeichert -
daher meine Frage, ob jemand schon mal sowas gemacht hat smile 
hab mal hier im Forum gesucht und bin über:
http://delphidev.de/phpBB2/viewtopic.php?t=786
gestolppert  - benutzt diese Software nicht so eine Art Graphen?? - der scheint mir ja recht komplex zu sein


grrr

Offline

 

#5 29.11.2006 12:44:14

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

Re: graphen, ai und wie finde ich nun den Weg?

A* ist im grunde ein optimierter Djikstra (schreibt man das so) Algorithmus.

Einfach mal nach A* suchen. Damit kannst du, wenn gut programmiert einen extrem schnellen wegsuch Algo schreiben der kantengewichtung benutzt.
(Kantengewichtung ist dein bodenbelag)

Im Prinzip ist der A* eine Breitensuche im Graphen. Also das heißt du nimmst alle knoten die mit dem Start verbunden sind und schaust ob diese dein ziel sind. Wenn nicht fügst du sie in die OpenList ein. jezt nimmst du den nächsten punkt aus deiner openliste und schreibst alle seine 'nachbarn' in die liste. der punkt selbst kommt in eine close liste. das machst du so lange bis der grade untersuchte punkt dein ziel ist. dann hast du einen weg.

Der Trick bei a* ist dann einfach dass du nicht irgendeinen Knoten aus der OpenList nimmst sondern den der den besten wert hat. Der Wert sind die geschätzten kosten(zb. euklidischer abstand) zum Ziel + Die Kosten die der Knoten schon hat (= wie weit der knoten vom start weg ist)
Wichtig dabei ist dass deine schätzfunktion für den abstand zum ziel niemals den wirklichen pfad überschätzt. sonst bekommst du längere pfade als eigentlich nötig.

Die Schätzfunktion wird in der A* literatur Heuristik genannt.

wenn du noch fragen hast frag einfach

mfg Chris


Nimm meinen Rat an - ich brauch ihn sowieso nicht

Offline

 

Brett Fußzeile

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson