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!

A* Algorithmus - Frage zur Sortierung der offenen Liste für die noch zu untersuchenden Knoten [solved]

Werbeanzeige

Fireball

Alter Hase

  • »Fireball« ist der Autor dieses Themas

Beiträge: 415

Wohnort: Werne

Beruf: Dipl. Inf.

  • Private Nachricht senden

1

04.09.2013, 13:10

A* Algorithmus - Frage zur Sortierung der offenen Liste für die noch zu untersuchenden Knoten [solved]

Hallo zusammen,

ich bin gerade dabei einen A* in C++ zu implementieren, diesen benötige ich um einem Spieler ordentlich Zombies auf den Hals zu hetzen.

Nun stellt sich mir die Frage wie ich am schnellsten die Liste mit den noch zu untersuchenden Knoten sortiere. Mir schwebt da ein binary heap vor.

Kann ich für diesen Zweck:

C-/C++-Quelltext

 
1

std::sort_heap (v.begin(),v.end());


aus der STL benutzen, oder ist die dafür nicht geeignet?

Schöne Grüße

fb

Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von »Fireball« (10.11.2013, 04:09) aus folgendem Grund: Hinweise der Community befolgt.

Oberon

Treue Seele

Beiträge: 181

Wohnort: Österreich

Beruf: Student

  • Private Nachricht senden

2

04.09.2013, 17:12

Am besten hältst du die Liste immer sortiert, verwendest also push_heap, pop_heap usw. (siehe http://en.cppreference.com/w/cpp/algorithm#Heap_operations). Alternativ könntest du auch ein std::multiset benutzen.
oberon00.github.io

Nox

Supermoderator

Beiträge: 5 272

Beruf: Student

  • Private Nachricht senden

3

04.09.2013, 19:40

Wir hatten es neulich von A* und dabei festgestellt, dass std::vector besser geeignet zu sein scheint (ich habe ja auch auf std::list getippt). Auch empfiehlt sich ggf ein Blick auf std::priority_queue . Allerdings haben wir da glaube ich nicht die Geschwindigkeit von einem heap betrachtet :hmm:
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.

Fireball

Alter Hase

  • »Fireball« ist der Autor dieses Themas

Beiträge: 415

Wohnort: Werne

Beruf: Dipl. Inf.

  • Private Nachricht senden

4

04.09.2013, 20:49

Hallo,

ich habe heute viel im Netz darüber gelesen und werde mal loslegen, dass Problem mit der Sortierung jedoch erst einmal hinten anstellen.
Bei mir werden normale Arrays zum Einsatz kommen, weil meine Map statisch ist. Ich mache es mir erstmal so leicht wie möglich.

Ich werde meine Ergebnisse hier zusammen tragen :-)


Schöne Grüße

fb

TGGC

1x Rätselkönig

Beiträge: 1 799

Beruf: Software Entwickler

  • Private Nachricht senden

5

04.09.2013, 21:22

Am effizientesten ist (wie schon erwaehnt) sowas hier: http://de.wikipedia.org/wiki/Vorrangwarteschlange
Wie gut die stl das kann haengt von deiner konkreten Implementierung ab.
Tetris Meeting Mainz | WMK Gamesroom | Schau dem neuen Tetris Großmeister zu

Fireball

Alter Hase

  • »Fireball« ist der Autor dieses Themas

Beiträge: 415

Wohnort: Werne

Beruf: Dipl. Inf.

  • Private Nachricht senden

6

24.10.2013, 22:59

Eigentlich wollte ich meinen A* präsentieren, doch ich habe noch einen Fehler gefunden, ich poste das Ergebnis wenn ich ihn gefixt habe.

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »Fireball« (24.10.2013, 23:14) aus folgendem Grund: fehler

TGGC

1x Rätselkönig

Beiträge: 1 799

Beruf: Software Entwickler

  • Private Nachricht senden

7

25.10.2013, 09:02

Dann muss dein A* aber ziemlich kompliziert sein. Ich weiss nicht obs sinnvoll ist sowas dann zu praesentieren. A* gibt auf wikipedia mit 10 Zeilen Pseudocode.
Tetris Meeting Mainz | WMK Gamesroom | Schau dem neuen Tetris Großmeister zu

Fireball

Alter Hase

  • »Fireball« ist der Autor dieses Themas

Beiträge: 415

Wohnort: Werne

Beruf: Dipl. Inf.

  • Private Nachricht senden

8

25.10.2013, 10:22

Zitat von »TGGC«

Dann muss dein A* aber ziemlich kompliziert sein. Ich weiss nicht obs sinnvoll ist sowas dann zu praesentieren. A* gibt auf wikipedia mit 10 Zeilen Pseudocode.



na gut dann halt nicht :-)

Checkmateing

Community-Fossil

Beiträge: 2 218

  • Private Nachricht senden

9

25.10.2013, 14:03

Zitat von »TGGC«

Ich weiss nicht obs sinnvoll ist sowas dann zu praesentieren. A* gibt auf wikipedia mit 10 Zeilen Pseudocode.

Ich halte es für sinnvoll und würde dahingehend sehr gerne Fireballs Algorithmus sehen, man kann diesen ja noch gemeinsam verbessern.
Wo stecke denn dann auch der Spaß? "Das gibts da besser" ist für mich ziemlich grau/langweilig.

MfG
Check
Das gibt Übersicht! Stay gold.

anti-freak

Alter Hase

Beiträge: 635

  • Private Nachricht senden

10

28.10.2013, 16:20

Würde es auch begrüßen, mal etwas Code zu sehen, sodass man vll ein wenig vergleichen kann (nicht jeder hat die selben Anforderungen, aber das Grundprinzip bleibt wohl identisch).

Werbeanzeige

Ähnliche Themen