DelphiX + A*

[Die Muhkuh]

Hi,


hätte jemand eine Idee, wie man DelphiX mit A* verwenden könnte? Ich möchte ein Sprite von 0,0 nach 5,5 (beispiel) schicken und dabei soll es den kürzesten weg nehmen. Mein Problem ist nur, das sich das ganze spielfeld mit Sprites aufgebaut wird. Also keine Bitmaps etc.

Bin für jede Idee dankbar^^..


*MFG*

Manu

[Nonsense]

Für A* brauchst du eine Matrix. Die kleinste Matrix wäre das Pixelformat. Damit musst du dann arbeiten.

[mimi]

und wie genau ???

ich habe jetzt z.b. so eine map:

Delphi-Quellcode:

TMap = record
  x,y,typ,tex:Integer;
  begabar:Boolean;
end;

Map:array of TMAp;

und nun möchte ich gerne ein objekt von 6,7 nach 9,10 bewegen, wie geht das ???
kannst du evtl, ein kleines beispiel erstellen ???

[Nonsense]

Ich versteh dein Problem nicht. :gruebel:
Du brauchst doch den A* Algorithmus nur praktisch anwenden.

[Die Muhkuh]

Hi Nonsense,

könntest du uns mal ein beispiel machen?

[Nonsense]

Du wirst doch sicher schon mit A* gearbeitet haben, bzw. in der Theorie kennen (woraus folgt, dass die praktische Umsetzung mit halbwegs passablen Object Pascal Kenntnissen kein Problem ist)?
Bitte sag mir mal, wo _konkret_ Dein Problem ist. Ich kann Dir überhaupt nicht folgen.

[Die Muhkuh]

Hi Nonsense,

mein Problem ist, das ich nicht weiß wie ich A* verwende. Ich hab mit zwar schon die Beispiele angeguckt, bekomme sie aber nicht auf DelphiX übertragen.

[maximov]

Zitat:

Zitat von Spider

Hi Nonsense,

mein Problem ist, das ich nicht weiß wie ich A* verwende. Ich hab mit zwar schon die Beispiele angeguckt, bekomme sie aber nicht auf DelphiX übertragen.

Du musst A* auch nicht auf delphiX übertragen, sondern an das modell, was deinem spiel zu grunde liegt, andocken! Und auf garkeinen fall auf pixel-metrik arbeiten, denn dann wird es so elendig lange dauern bis ein weg gefunden wurde, dass ihr alt werdet. Im schlimmsten fall arbeitet man mit A* auf tile-ebene und es macht sinn, wenn die A* implementierung eine Template-methode erwartet, in der der algorythmus dann die kosten für tile (kante) abfragt. Somit hat nur diese Abfarge-template-callback-methode mit eurem spiel zu tun und der rest hat den algo nicht zu interessieren.

Du sagts, du willst den kürzesten weg. A* ist allerdings auf den güstigsten weg ausgelegt. Ist zwar in den meisten fällen das gleiche, aber wenn man kosten (zB. für hügel oder so) verteilt dann eben nicht. Will man tatsächlich die kürzeste strecke, dann kann man die heuristik überbewerten, sodass kürzere strecken auch günstiger werden. Dies ist im übrigen auch eine sehr gute optimierungs möglichkeit, da sich so die anzahl der knoten sehr stark verringert.

Viel spass!


PS: wenns brennt und garnicht geht, dann kann ich euch ein 'quick & dirty' beispeil geben.

[weißer Zwerg]

A* *schüttel*, kommt mir bekannt vor. Da ich iM nicht an meine Unterlagen dazu komme, versuche ich mal mein Gehirn zu strapazieren:

A* soll den kürzesten Weg zwischen zwei Punkten ermitteln. Bei den Punkten die dazwischen liegen, braucht man die gültigen Verbindungen zwischen diesen. Die Verbindungen (= Kanten) bekommen Gewichte (oder die Punkte selber?). Vom Startpunkt wird der Punkt gewählt, der mit dem geringsten Gewicht zu erreichen ist. Die anderen möglichen Punkte werden in eine Liste eingetragen. Dies wird solange wiederholt bis man am Zielknoten ist. Dabei addieren sich die Gewichte für alle Verbindungen (= Kosten). Ist in der Liste ein Punkt, der mit weniger Kosten zu erreichen ist als einer vom aktuellen, wird dieser Punt gewählt.
Man muss zusätzlich sicherstellen, dass wenn man auf zwei Wegen zu einem Zwischenpunkt kommt, dass derjenige mit den geringeren Kosten gewählt wird.

Das war erstmal alles, was mir dazu eingefallen ist.

MfG wZ

[mimi]

verstehe ich nicht ganz.... ich habe schon einige beispiele gesehen auch für delphiX aber ich verstehe sie leider nicht ganz.... wenn ich jetzt so eine map habe:

Delphi-Quellcode:

TMap = record
Typ, tex:Integer;
Begebear:Boolean;

end;