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

Geheim

Treue Seele

  • »Geheim« ist der Autor dieses Themas

Beiträge: 202

Wohnort: Salzburg

Beruf: Schüler

  • Private Nachricht senden

21

08.06.2012, 19:05

Zitat von »Mastermind«

Ich versteh sowieso nicht warum alle immer A* implementieren müssen.

Zum Üben und damit ich versteh wie und warum es funktioniert. Außerdem freut man sich wenn man es geschafft hat und ist stolz darauf. Und es ist lustig sich dann damit zu spielen.

Zitat von »Spiele Programmierer«

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

Das setzt G, F, und H.
Und das berechnet die Distanz.
StartBLock = Der Block von dem gerade alles berechnet wird
GoalBlock = Der ZielBlock

Braucht ihr nochwas?

Mastermind

unregistriert

22

08.06.2012, 19:11

Mein Vorschlag lief darauf hinaus, dass du zum Üben den Algorithmus von Dijkstra implementierst, der einfacher ist. Nicht dass du jede Tätikeit einstellst.

Offensichtlich hast du A* eben nicht verstanden, sonst hättet du es ja korrekt implementiert. Das Argument zieht also nicht.

Nox

Supermoderator

Beiträge: 5 272

Beruf: Student

  • Private Nachricht senden

23

08.06.2012, 19:21

Ich tippe mal darauf, dass du die Trennung von bisherigen Kosten, geschätzen Kosten und dem Sortierwert (bisher+geschätzt) nicht ordentlich implementiert hast. Warum gibst du uns eig nur Bruchstücke? Komm gib doch einfach mal den gesamten Krams. Ansonsten kann ich dir einen funktionierenden einfach an den Kopf klatschen (nebenbei ist eine Liste nicht ideal für die Kosten. Lieber eine priority_queue oder eine map nutzen).
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.

Geheim

Treue Seele

  • »Geheim« ist der Autor dieses Themas

Beiträge: 202

Wohnort: Salzburg

Beruf: Schüler

  • Private Nachricht senden

24

08.06.2012, 19:28

So hier alles was ich hab.

Nox

Supermoderator

Beiträge: 5 272

Beruf: Student

  • Private Nachricht senden

25

08.06.2012, 19:48

Ein wenig gruselig...
1. würde ich den Algo auslagern (Trennung von Logik und Darstellung)
2. Also sowas nenne ich mal risikofreudiges Design:

C-/C++-Quelltext

 
1
2

    while(Finish == false && Impossible == false)
        Algorithmus(ClosedList.back(), Myqueue.back());
Warum existieren Finish und Impossible in der Klasse? Warum wird nicht einfach überprüft,
ob die closedlist den Zielknoten als letztes enthält?
3.Diese ewig vielen Bedingungen kann man leicht reduzieren. Z.B. durch Nutzung einer Nachbarnliste ala "neighbours[][] = { {1,1},{1,0},...};"
4.

C-/C++-Quelltext

 
1

OpenList.back().SetG(StartBlock.GetF() - StartBlock.GetH());
schaut seltsam aus, weil somit für alle Knoten der G Wert gleich wäre?
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.

Geheim

Treue Seele

  • »Geheim« ist der Autor dieses Themas

Beiträge: 202

Wohnort: Salzburg

Beruf: Schüler

  • Private Nachricht senden

26

08.06.2012, 20:01

Ja ich weiß der Code ist gruselig^^

Zitat von »Nox«



C-/C++-Quelltext



1







OpenList.back().SetG(StartBlock.GetF() - StartBlock.GetH());



schaut seltsam aus, weil somit für alle Knoten der G Wert gleich wäre?

StartBlock ist ein Parameter und es wird immer OpenList.back() übergeben, um Code zu sparen.

Checkmateing

Community-Fossil

Beiträge: 2 218

  • Private Nachricht senden

27

08.06.2012, 20:18

Um Code zu sparen? Solang die Performance keine großen Abstriche macht: Lieber zu viel und funktionierend als zu wenig und falsch, oder? :huh:

MfG
Check
Das gibt Übersicht! Stay gold.

Geheim

Treue Seele

  • »Geheim« ist der Autor dieses Themas

Beiträge: 202

Wohnort: Salzburg

Beruf: Schüler

  • Private Nachricht senden

28

08.06.2012, 20:44

Ja eh ;) Aber es ist doch dasselbe, als würde ich 8 mal denselben Code hinschreiben... Es funktioniert ja auch beides

Nox

Supermoderator

Beiträge: 5 272

Beruf: Student

  • Private Nachricht senden

29

08.06.2012, 20:45

Gebt mir ein wenig Zeit. Ich gehe das mal gedanklich durch.

EDIT: also...du scheinst mit "Available" die noch offenen Knoten zu sperren. Du darfst aber nur die geschlossenen sperren. Daher muss man beim Einfügen auch darauf achten den alten Eintrag zu löschen (es kann nämlich sein, dass ein anderer Weg zum Knoten kürzer ist, aber erst später entdeckt wird) und bei SetG wird "OpenList.back().SetG(StartBlock.GetF() - StartBlock.GetH());" verwendet, was aber glaube ich einfach nur "StartBlock.GetG()" entspricht, oder?

Versuch mal http://codepad.org/60tCZh0D . Es wird sicherlich nicht auf Anhieb klappen, aber schon eher auf die richtige Richtung bzw. näher am Original oder zumindest als Inspiration dienen.

EDIT2: eine zusammengerafte Variante von was eigenem findet ihr hier: http://codepad.org/y6vmioVB . Allerdings ist das gerade schnell zusammengekürzt und ein wenig optimiert.
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.

Dieser Beitrag wurde bereits 3 mal editiert, zuletzt von »Nox« (08.06.2012, 22:07)

Geheim

Treue Seele

  • »Geheim« ist der Autor dieses Themas

Beiträge: 202

Wohnort: Salzburg

Beruf: Schüler

  • Private Nachricht senden

30

08.06.2012, 22:30

Hey Nox,
Vielen Dank, dass du dir Zeit genommen hast den Code anzuschauen und sogar auszubessern ;)
Ich hab sogar 3 neue Dinge dadurch gelernt: auto, fabs und dass so eine Zuweißung funktioniert: Finish = ClosedList.back() == GoalBlock;

Ich kann alles gut nachvollziehen bis auf eine kleine Sache:

C-/C++-Quelltext

 
1
2
3
4

int int_x = static_cast<int>(CurrentBlock.GetX() / 20.f +0.5f);

if(fabs(it->GetX() - new_x*20.f) < 0.001f && fabs(it->GetY() - new_y*20.f) < 0.001f)
    it = OpenList.erase(it);

Warum +0.5f und warum <0.0001f? xD

Btw: Gibt es einen Unterschied zwischen static_cast<int> und (int) ?

Werbeanzeige

Ähnliche Themen