Du bist nicht angemeldet.

Werbeanzeige

Fireball

Alter Hase

  • »Fireball« ist der Autor dieses Themas

Beiträge: 421

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.

Nox

Supermoderator

Beiträge: 5 282

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: 421

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 813

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.

Fireball

Alter Hase

  • »Fireball« ist der Autor dieses Themas

Beiträge: 421

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 813

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.

Fireball

Alter Hase

  • »Fireball« ist der Autor dieses Themas

Beiträge: 421

Wohnort: Werne

Beruf: Dipl. Inf.

  • Private Nachricht senden

8

25.10.2013, 10:22

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 :-)

9

25.10.2013, 14:03

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

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