Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

Fragen zu A* Algorithmus

Werbeanzeige

Mastermind

unregistriert

11

08.06.2012, 17:54

Zitat von »Spiele Programmierer«

Ich denke, du verwendest die Manhattenlänge.

Du musst in die Länge schon die Diagonalen miteinbeziehen
Wenn X und Y Koordianten des Vektors zum Ziel sind:
Max = max(abs(X), abs(Y))
Min = min(abs(X), abs(Y))
Distanz = Min * 141 + (Max - Min) * 100


Was für eine Art Black Magic soll das denn sein?

Spiele Programmierer

Alter Hase

Beiträge: 1 223

Wohnort: Deutschland Bayern

Beruf: Schüler

  • Private Nachricht senden

12

08.06.2012, 18:20

Keine Schwarze Magie, sondern ein einfaches System zum bestimmen des Abstandes. ;)

Jeder kürzester Weg zum Ziel(ohne Hindernisse) kann aus einem waagrechten\senkrechten und ein diagonalen Stück bestehen.
Die Länge der diagonalen Strecke ist "min(abs(X), abs(Y))"
und der Geraden "max(abs(X), abs(Y)) - min(abs(X), abs(Y))"
In einem Feld von links nach rechts sind es 100 Längeneinheiten und diagonal sind es 141 (Da sqrt(2) ≈ 1,41...)
Jetzt einfach: DiagonaleStrecke * 141 + GeradeStrecke * 100 = Entfernung

Geheim

Treue Seele

  • »Geheim« ist der Autor dieses Themas

Beiträge: 202

Wohnort: Salzburg

Beruf: Schüler

  • Private Nachricht senden

13

08.06.2012, 18:22

F = Der schon zurückgelegte Weg (G) + der geschätzte Weg, den de rBlock noch machen muss (H)
Und ich berechne es mit dem Satz des Pythagoras :D

Spiele Programmierer

Alter Hase

Beiträge: 1 223

Wohnort: Deutschland Bayern

Beruf: Schüler

  • Private Nachricht senden

14

08.06.2012, 18:28

Satz des Pythagoras ist da aber nicht richtig.
Und außerdem könnten je nach Dimensionierung von F Rundungsfehler auftretten.
Auch ist Gleitkommaarithmetik langsamer. Besonders die Wurzel.

Der Satz des Pythagoras geht von direkter Verbindung aus.
In Wirklichkeit existiert sie aber gar nicht, da du dich höchstens diagonal bewegen kannst.
Siehe Bild. (Gelb: Pythagoras - Rot: Algorithmus)
»Spiele Programmierer« hat folgendes Bild angehängt:
  • Demonstration.gif

Nox

Supermoderator

Beiträge: 5 272

Beruf: Student

  • Private Nachricht senden

15

08.06.2012, 18:34

Die euklidische Norm ist definitiv eine gültige Heuristik und ich wäre mir nicht so sicher, ob mind. 4 Bedingungen/Sprünge wirklich schneller ist.
PRO Lernkurs "Wie benutze ich eine Doku richtig"!
CONTRA lasst mal die anderen machen!
networklibbenc - Netzwerklibs im Vergleich | syncsys - Netzwerk lib (MMO-ready) | Schleichfahrt Remake | Firegalaxy | Sammelsurium rund um FPGA&Co.

Mastermind

unregistriert

16

08.06.2012, 18:37

Zitat von »Spiele Programmierer«

Satz des Pythagoras ist da aber nicht richtig.
Und außerdem könnten je nach Dimensionierung von F Rundungsfehler auftretten.
Auch ist Gleitkommaarithmetik langsamer. Besonders die Wurzel.

Der Satz des Pythagoras geht von direkter Verbindung aus.
In Wirklichkeit existiert sie aber gar nicht, da du dich höchstens diagonal bewegen kannst.
Siehe Bild. (Gelb: Pythagoras - Rot: Algorithmus)


Hmm, also sqrt(2) hätte ich eventuell erkennen können, allerdings ist deine Skalierung nach Längeneinheiten doch eher willkürlich.

Ich bin gar nicht mal so sicher, dass für eine CPU Sprünge (max, min, jedes abs) wirklich leichter zu verkraften sind als eine Wunzel.

Und als Heuristik ist Euklid sehr wohl geeignet, da es die Entfernung wenn dann unterschätzt.

Gnarf, der Nox war schneller.

Geheim

Treue Seele

  • »Geheim« ist der Autor dieses Themas

Beiträge: 202

Wohnort: Salzburg

Beruf: Schüler

  • Private Nachricht senden

17

08.06.2012, 18:37

Also liegt das Problem nur an der Berechnung des Schätzweges?
Und wie sollte der dann Aussehen? ^^

Nox

Supermoderator

Beiträge: 5 272

Beruf: Student

  • Private Nachricht senden

18

08.06.2012, 18:48

Am besten du bemühst mal codepad.org o.ä. ansonsten fischen wir noch nächste Woche im trüben, aber eigentlich kann es nur an einer falschen Reihenfolge der untersuchten Knoten liegen, was eben auf die Kosten oder Sortierung schließen lässt.
PRO Lernkurs "Wie benutze ich eine Doku richtig"!
CONTRA lasst mal die anderen machen!
networklibbenc - Netzwerklibs im Vergleich | syncsys - Netzwerk lib (MMO-ready) | Schleichfahrt Remake | Firegalaxy | Sammelsurium rund um FPGA&Co.

Mastermind

unregistriert

19

08.06.2012, 18:53

Ich versteh sowieso nicht warum alle immer A* implementieren müssen. Der Algorithmus von Dijkstra ist effizient und für die hier zu Debatte stehende Problemgröße sicher hinreichend schnell. Wenn man den verstanden und am laufen hat, kann man immer noch ausbauen.

Spiele Programmierer

Alter Hase

Beiträge: 1 223

Wohnort: Deutschland Bayern

Beruf: Schüler

  • Private Nachricht senden

20

08.06.2012, 18:57

Ok, ihr habt recht.
Schneller ist es wirklich nicht.
Rasch in C# ausprobiert, ist der zweite Druchlauf mit 5ns gegen 7,5ns schneller wie der Erste.

C#-Quelltext

 
1
2
3
4
5

int AbsX = Math.Abs(X);
int AbsY = Math.Abs(Y);
int Min = Math.Min(AbsX, AbsY);
int Max = Math.Max(AbsX, AbsY);
int Dist = Min * 100 + (Max - Min) * 141;


C#-Quelltext

 
1
2
3
4

double Xfloat = (double)X;
double Yfloat = (double)Y;
double DistFloat = Math.Sqrt(Xfloat * Xfloat + Yfloat * Yfloat);
int Dist = (int)DistFloat;


Ob A* mit dem Algo anstatt Pythagoras aber immer den selben besten Weg findet, wäre ich mir gerade nicht so sicher.

@Geheim
Wie wäre es, wenn du mal den Code von GetF rausrückst? :)

Werbeanzeige

Ähnliche Themen