AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Thema durchsuchen
Ansicht
Themen-Optionen

A* Pathfinding

Ein Thema von Airblader · begonnen am 22. Nov 2005 · letzter Beitrag vom 25. Nov 2005
Antwort Antwort
Seite 2 von 2     12   
Benutzerbild von Airblader
Airblader

Registriert seit: 29. Okt 2004
Ort: Geislingen an der Steige
742 Beiträge
 
#11

Re: A* Pathfinding

  Alt 24. Nov 2005, 22:08
Mhm...die Methode hab ich nu leider nich verstanden
A* versteh ich ja, mir geht es nur um den groben Aufbau, dass es auch performant ist

Problem ist ja nicht nur der Weg (sollte natürlich der möglichst kürzeste sein), sondern auch, dass er Hinternissen halbwegs intelligent ausweicht

air
Ingo Bürk
Es nimmt der Augenblick, was Jahre geben.

Johann Wolfgang von Goethe
  Mit Zitat antworten Zitat
alzaimar
(Moderator)

Registriert seit: 6. Mai 2005
Ort: Berlin
4.956 Beiträge
 
Delphi 2007 Enterprise
 
#12

Re: A* Pathfinding

  Alt 25. Nov 2005, 08:03
Du hast ein Spielfeld, ähnlich wie z.B. ein Schachfeld?
Dann sind die Felder die Knoten, und die Übergänge von einem Feld zum Nachbarn die Kanten. Ein Feld hat ja maximal 8 Nachbarn, also hat jeder Knoten maximal 8 Kanten.
Code:
+---+---+---+
| 1 | 2 | 3 |
+---+---+---+
| 4 | 5*| 6*|
+---+---+---+
| 7 | 8 | 9 |
+---+---+---+
Feld 5 und 6 sind Hindernisse. Die Kanten sind also
(1,2) (2,3) (1,4) (4,7) (7,8) (8,9)
Wenn man schräg laufen darf, kommen noch (2,4) und (4,8) hinzu.
Wenn man in beide Richtungen laufen darf, dann natürlich auch die Inversen der Kanten.
Nun erstellst Du deine Matrix, wo z.B. E[1,2] = E[2,1] = 1 und E[2,5] = MaxInt ist.
Dann den A* oder jeden anderen "single source minimum Path" Algorithmus auf z.B. auf (3->9) loslassen und schon bist du fertig.

Übrigens kann man damit auch 'Berge' darstellen. Wenn der Weg von 1->4 bergauf geht, dann ist E[1,4] > E[4,1]. Der A* Algorithmus findet dann den Weg, der am wenigsten anstrengend ist.
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat
Benutzerbild von Airblader
Airblader

Registriert seit: 29. Okt 2004
Ort: Geislingen an der Steige
742 Beiträge
 
#13

Re: A* Pathfinding

  Alt 25. Nov 2005, 16:28
Naja, meine Spielmatrix hab ich ja, grob gesagt etwa sowas:

Map1 => Fields[X,Y] => Image/Typ/...

Image is z.B. welches Image es im Tileset hat und Typ eben 0/1/2 für begehbar etc.
Der Algo selbst hat mir auch noch keine Sorgen gemacht bzw. meine Matrix - eher eben das grundlegende mit welcher Idee ich rangehen sollte
Werds nu wie gesagt mal mit dem TObjectList (nochmal) versuchen

air
Ingo Bürk
Es nimmt der Augenblick, was Jahre geben.

Johann Wolfgang von Goethe
  Mit Zitat antworten Zitat
Antwort Antwort
Seite 2 von 2     12   


Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 10:14 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz