A* Probleme mit den Ecken

Werbeanzeige

Shadow_Men

Frischling

Beiträge: 16

03.08.2013, 13:44

A* Probleme mit den Ecken

Hallo alle Miteinander,

ich versuche derzeit A* zu lernen und stehe jetzt vor 2 Problemen, wo ich keine Lösung finde.
Ich habe den Algorithmus soweit, dass er einen Pfad vom Start bis zum Ziel findet, aber:

1.

(Link)

Wie man sehen kann, ist der Pfad total verwirrt, wenn eine Ecke im Weg ist. Ich habe schon mehrere Themen durchstöber, aber nirgends gab es so einen Fall.

2.

(Link)

Es kann Diagonal durch eine Wand gegangen werden. Ich weis nicht wie ich das umsetzen kann.

Verwendet habe ich die Bibliothek SFML Version 2.0
Habe mal die Source Dateien angehängt, da bei der Formatierung von (cpp)(/cpp) probleme mit neuen Zeilen gab.

Ich hoffe ich einer schafft es mir zu helfen.

»Shadow_Men« hat folgende Dateien angehängt:

Pathfinding.hpp (809 Byte - 89 mal heruntergeladen - zuletzt: Heute, 14:33)
Pathfinding.cpp (5,16 kB - 110 mal heruntergeladen - zuletzt: 28.03.2024, 09:38)

Zum Seitenanfang

Nox

Supermoderator

Beiträge: 5 272

Beruf: Student

03.08.2013, 17:19

Nein normales verhalten sollte es nicht sein. Ist ja eindeutig nicht der optimale Pfad. Es sollte eher so ausschauen: http://commons.wikimedia.org/wiki/File:A…s_animation.gif

@Shadow_Men Darf ich dir ein paar Fragen/Anmerkungen zum Source stellen/machen?

1. _openList scheint ein std::vector<Node> zu sein - warum keine liste? Oder gleich std::priority_queue ?
2. SortNode kannst du auch durch std::sort realisieren oder wenn du ne std::list nutzt eben std::list::sort
3. _currentNode = _openList[0]; _openList.erase(_openList.begin()); kannst du durch _currentNode = _openList.pop() ersetzen
4. Ist int H = 10 * (std::abs(_currentX - goal.x) + std::abs(_currentY - goal.y)); deine Kostenschätzung? Wenn ja warum int? UND die Schätzung ist nicht korrekt. Du musst für einen 2D euklidischen Raum auch die entsprechende Norm 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.

Zum Seitenanfang

Shadow_Men

Frischling

Beiträge: 16

03.08.2013, 18:03

Vielen Dank für die Antwort! :thumbsup:

Ich bin erst vor kurzem von C# auf C++ gewechselt, und kenne noch nicht wirklich alle Funktionen. Ich bin derweil aber noch am Lernen, brauche aber noch einiege Wochen, denn ein Buch lässt sich nun mal nicht in einer Woche durchlesen, sodass man alles versteht und sich einprägt.

1.
Darf ich eine Gegenfrage stellen?
Was ist denn an den anderen Listen besser für den A* Algorithmus?

2.
Wie soll denn die Funktion mit F arbeiten? Bevor ich da wieder großartig das Internet durchsuche, habe ich mich für den Bubblesort entschieden.

3.
Ich habe dies schon vorher mal gesehen, aber dachte das geht nicht, da std::vector::pop() nur den ersten löscht, aber kein Wert zurück gibt.

4.
Ich habe die Formel von dieser Seite. Dort wurde auch gesagt, dass man ganze Zahlen nehmen sollte, weil der Rechner damit schneller arbeitet. Und die Norm ist mir auch nicht bekannt.

Zum Seitenanfang

Nox

Supermoderator

Beiträge: 5 272

Beruf: Student

03.08.2013, 18:56

std::vector ist ne kapselung von einem array == alle Daten werden direkt nacheinander im Speicher allokiert. Das ist wunderbar für schnelle lookups (per Index) und fürs Kopieren. Für das hinzufügen/entfernen von vielen einzelnen Einträgen ist das aber denkbar ungünstig, da immer alle anderen Elemente ebenfalls mitkopiert/verschoben werden müssen.

Beim std::vector::pop_back hast du sogar recht. Das gibt void zurück. std::list::pop hingegen gibt das Objekt was entfernt wird mit aus. Auch gibt es nen std::list::sort was dann auch das sortieren ermöglicht. Aber std::priority_queue kann halt schon gleich sortieren/aktualisieren.

Versuch es mal mit float und der Norm sqrt(x*x + y*y). Die Tips von der Seite würde ich mit vorsicht genießen. A-Star funktioniert nur mit nicht überschätzender (oder wars unterschätzend?) Metrik nicht korrekt. Außerdem sollte man nur Optimierungen durchführen, wenn es funktioniert und zulangsam ist.

P.S: prinzipiell spricht nat nichts dagegen sort etc selbst zu implementieren. Gerade wenn es aber andere verstehen sollen, oder der Code schön kurz und knapp aussehen soll, ist das zurückgreifen auf z.B. stl ne feine Sache (meine persönliche Meinung).

Zum Seitenanfang

TGGC

1x Rätselkönig

Beiträge: 1 799

Beruf: Software Entwickler

03.08.2013, 20:57

Zitat von »LetsGo«

Die besuchten Knoten jedoch sind genau die auf dem Bild zu sehenden.

Nein, sind sie bei korrekter Anwendung nicht.

Zur Schaetzfunktion: deine ist vor allem falsch, weil Punktrechnung vor Strichrechnung geht. Zweites Problem ist, das du auch schraeg gehen kannst und du damit die Weglaenge ueberschaetzt. Das gibt dann auch falsche Ergebnisse. Die Formel mit der Wurzel ist streng genommen auch falsch, aber zumindest unterschaetzt sie den Weg nur. Das ist dann einfach nur ineffizient aber der Weg ist immer noch korrekt, genauso wie max(abs(dx),abs(dy). Die optimale Schaetzfunktion zerlegt den Restweg in einen diagonalen und einen horizontalen/vertikalen Weg und addiert deren Laengen.

Und wenn du nicht durch schraege Ecken gehen willst, dann geh eben nicht durch schraege Ecken. Du brauchst ja bei schraegen Schritten einfach nur abfrage, wie genau die Ecke aussieht und dann in den entsprechenden Faellen eben nicht weitergehen.

Tetris Meeting Mainz | WMK Gamesroom | Schau dem neuen Tetris Großmeister zu

Zum Seitenanfang

TGGC

1x Rätselkönig

Beiträge: 1 799

Beruf: Software Entwickler

04.08.2013, 09:22

Zitat von »LetsGo«

Hmm und welche wären es dann?

Zumindest mal das gesamte Quadrat oberhalb des Dreiecks. Weil man da noch eine waagerechte oder senkrechte Line braucht fuer den kuerzesten Weg.

Tetris Meeting Mainz | WMK Gamesroom | Schau dem neuen Tetris Großmeister zu

Zum Seitenanfang

Shadow_Men

Frischling

Beiträge: 16

04.08.2013, 14:21

Ich habe jetzt std::vector durch std::list ersetzt, Heuristik mit std::sqrt(dx*dx + dy*dy) berechnet und Diagonal verboten. Nun besteht das Problem weiterhin und es ist langsamer geworden. Ich vermute es liegt an der Berechnung von G sowie der Überprüfung ob der Weg über ein anderen Knoten besser ist.

Ich berechne G zurzeit so:

	C-/C++-Quelltext
1	float G = _currentNode.G + 10;

und überprüfe so:

	C-/C++-Quelltext
1 2 3	float DiffG = _currentNode.G + 10; if(DiffG > node->G){node->fromX = _currentNode.posX;node->fromY = _currentNode.posY;node->G = DiffG; node->F = node->G + node->H;}

Zum Seitenanfang

Shadow_Men

Frischling

Beiträge: 16

04.08.2013, 14:54

Ok wie ich gerade feststellen musste liegt der Fehler an der sortier Funktion.
Ich habe diese durch std::list::sort ersetzt und bekomme jetzt nur noch Fehler wegen std::list::merge.

Build Log:

/usr/include/c++/4.7/bits/stl_list.h|1385| erfordert durch »void std::list<_Tp, _Alloc>::merge(std::list<_Tp, _Alloc>&) [with _Tp = Node; _Alloc = std::allocator<Node>; std::list<_Tp, _Alloc> = std::list<Node>]«|
/usr/include/c++/4.7/bits/list.tcc|374| erfordert durch »void std::list<_Tp, _Alloc>::sort() [with _Tp = Node; _Alloc = std::allocator<Node>]«|
/home/nils/Dokumente/C++/Tilemap/src/Pathfinding/Pathfinding.cpp|136| von hier erfordert|
/usr/include/c++/4.7/bits/list.tcc|305|Fehler: keine Übereinstimmung für »operator<« in »__first2.std::_List_iterator<_Tp>::operator*<Node>() < __first1.std::_List_iterator<_Tp>::operator*<Node>()«|
/usr/include/c++/4.7/bits/list.tcc|305|Anmerkung: Kandidaten sind:|
/usr/include/c++/4.7/bits/stl_pair.h|212|Anmerkung: template<class _T1, class _T2> constexpr bool std::operator<(const std::pair<_T1, _T2>&, const std::pair<_T1, _T2>&)|
/usr/include/c++/4.7/bits/stl_pair.h|212|Anmerkung: Herleitung/Ersetzung von Templateargument gescheitert:|
/usr/include/c++/4.7/bits/list.tcc|305|Anmerkung: »Node« ist nicht vom Typ »const std::pair<_T1, _T2>« abgeleitet|
/usr/include/c++/4.7/bits/stl_iterator.h|299|Anmerkung: template<class _Iterator> bool std::operator<(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_Iterator>&)|
/usr/include/c++/4.7/bits/stl_iterator.h|299|Anmerkung: Herleitung/Ersetzung von Templateargument gescheitert:|
/usr/include/c++/4.7/bits/list.tcc|305|Anmerkung: »Node« ist nicht vom Typ »const std::reverse_iterator<_Iterator>« abgeleitet|
/usr/include/c++/4.7/bits/stl_iterator.h|349|Anmerkung: template<class _IteratorL, class _IteratorR> bool std::operator<(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_IteratorR>&)|
/usr/include/c++/4.7/bits/stl_iterator.h|349|Anmerkung: Herleitung/Ersetzung von Templateargument gescheitert:|
/usr/include/c++/4.7/bits/list.tcc|305|Anmerkung: »Node« ist nicht vom Typ »const std::reverse_iterator<_Iterator>« abgeleitet|
/usr/include/c++/4.7/bits/stl_iterator.h|1057|Anmerkung: template<class _IteratorL, class _IteratorR> bool std::operator<(const std::move_iterator<_Iterator>&, const std::move_iterator<_IteratorR>&)|
/usr/include/c++/4.7/bits/stl_iterator.h|1057|Anmerkung: Herleitung/Ersetzung von Templateargument gescheitert:|
/usr/include/c++/4.7/bits/list.tcc|305|Anmerkung: »Node« ist nicht vom Typ »const std::move_iterator<_Iterator>« abgeleitet|
/usr/include/c++/4.7/bits/stl_iterator.h|1063|Anmerkung: template<class _Iterator> bool std::operator<(const std::move_iterator<_Iterator>&, const std::move_iterator<_Iterator>&)|
/usr/include/c++/4.7/bits/stl_iterator.h|1063|Anmerkung: Herleitung/Ersetzung von Templateargument gescheitert:|
/usr/include/c++/4.7/bits/list.tcc|305|Anmerkung: »Node« ist nicht vom Typ »const std::move_iterator<_Iterator>« abgeleitet|
/usr/include/c++/4.7/bits/basic_string.h|2566|Anmerkung: template<class _CharT, class _Traits, class _Alloc> bool std::operator<(const std::basic_string<_CharT, _Traits, _Alloc>&, const std::basic_string<_CharT, _Traits, _Alloc>&)|
/usr/include/c++/4.7/bits/basic_string.h|2566|Anmerkung: Herleitung/Ersetzung von Templateargument gescheitert:|
/usr/include/c++/4.7/bits/list.tcc|305|Anmerkung: »Node« ist nicht vom Typ »const std::basic_string<_CharT, _Traits, _Alloc>« abgeleitet|
/usr/include/c++/4.7/bits/basic_string.h|2578|Anmerkung: template<class _CharT, class _Traits, class _Alloc> bool std::operator<(const std::basic_string<_CharT, _Traits, _Alloc>&, const _CharT*)|
/usr/include/c++/4.7/bits/basic_string.h|2578|Anmerkung: Herleitung/Ersetzung von Templateargument gescheitert:|
/usr/include/c++/4.7/bits/list.tcc|305|Anmerkung: »Node« ist nicht vom Typ »const std::basic_string<_CharT, _Traits, _Alloc>« abgeleitet|
/usr/include/c++/4.7/bits/basic_string.h|2590|Anmerkung: template<class _CharT, class _Traits, class _Alloc> bool std::operator<(const _CharT*, const std::basic_string<_CharT, _Traits, _Alloc>&)|
/usr/include/c++/4.7/bits/basic_string.h|2590|Anmerkung: Herleitung/Ersetzung von Templateargument gescheitert:|
/usr/include/c++/4.7/bits/list.tcc|305|Anmerkung: unpassende Typen »const _CharT*« und »Node«|
/usr/include/c++/4.7/bits/stl_vector.h|1387|Anmerkung: template<class _Tp, class _Alloc> bool std::operator<(const std::vector<_Tp, _Alloc>&, const std::vector<_Tp, _Alloc>&)|
/usr/include/c++/4.7/bits/stl_vector.h|1387|Anmerkung: Herleitung/Ersetzung von Templateargument gescheitert:|
/usr/include/c++/4.7/bits/list.tcc|305|Anmerkung: »Node« ist nicht vom Typ »const std::vector<_Tp, _Alloc>« abgeleitet|
/usr/include/c++/4.7/tuple|808|Anmerkung: template<class ... _TElements, class ... _UElements> bool std::operator<(const std::tuple<_Elements ...>&, const std::tuple<_Elements ...>&)|
/usr/include/c++/4.7/tuple|808|Anmerkung: Herleitung/Ersetzung von Templateargument gescheitert:|
/usr/include/c++/4.7/bits/list.tcc|305|Anmerkung: »Node« ist nicht vom Typ »const std::tuple<_Elements ...>« abgeleitet|
/usr/include/c++/4.7/bits/stl_tree.h|873|Anmerkung: template<class _Key, class _Val, class _KeyOfValue, class _Compare, class _Alloc> bool std::operator<(const std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&, const std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&)|
/usr/include/c++/4.7/bits/stl_tree.h|873|Anmerkung: Herleitung/Ersetzung von Templateargument gescheitert:|
/usr/include/c++/4.7/bits/list.tcc|305|Anmerkung: »Node« ist nicht vom Typ »const std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>« abgeleitet|
/usr/include/c++/4.7/bits/stl_map.h|906|Anmerkung: template<class _Key, class _Tp, class _Compare, class _Alloc> bool std::operator<(const std::map<_Key, _Tp, _Compare, _Alloc>&, const std::map<_Key, _Tp, _Compare, _Alloc>&)|
/usr/include/c++/4.7/bits/stl_map.h|906|Anmerkung: Herleitung/Ersetzung von Templateargument gescheitert:|
/usr/include/c++/4.7/bits/list.tcc|305|Anmerkung: »Node« ist nicht vom Typ »const std::map<_Key, _Tp, _Compare, _Alloc>« abgeleitet|
/usr/include/c++/4.7/bits/stl_multimap.h|822|Anmerkung: template<class _Key, class _Tp, class _Compare, class _Alloc> bool std::operator<(const std::multimap<_Key, _Tp, _Compare, _Alloc>&, const std::multimap<_Key, _Tp, _Compare, _Alloc>&)|
/usr/include/c++/4.7/bits/stl_multimap.h|822|Anmerkung: Herleitung/Ersetzung von Templateargument gescheitert:|
/usr/include/c++/4.7/bits/list.tcc|305|Anmerkung: »Node« ist nicht vom Typ »const std::multimap<_Key, _Tp, _Compare, _Alloc>« abgeleitet|
/usr/include/c++/4.7/bits/stl_list.h|1603|Anmerkung: template<class _Tp, class _Alloc> bool std::operator<(const std::list<_Tp, _Alloc>&, const std::list<_Tp, _Alloc>&)|
/usr/include/c++/4.7/bits/stl_list.h|1603|Anmerkung: Herleitung/Ersetzung von Templateargument gescheitert:|
/usr/include/c++/4.7/bits/list.tcc|305|Anmerkung: »Node« ist nicht vom Typ »const std::list<_Tp, _Alloc>« abgeleitet|
||=== Build finished: 47 errors, 0 warnings (0 minutes, 2 seconds) ===|

Falls sich jemand damit auskennt und mir helfen kann wäre ich ihm sehr dankbar.

Zum Seitenanfang

Spiele Programmierer

Alter Hase

Beiträge: 1 223

Wohnort: Deutschland Bayern

Beruf: Schüler

04.08.2013, 14:56

Von der Geschwindigkeit ist ein Vektor in diesem Anwendungsfall wahrscheinlich besser.
www.baptiste-wicht.com/2012/12/cpp-benchmark-vector-list-deque
Solche Benchmarks lassen sich zwar nicht immer auf einen anderen Anwendungsfall oder Compiler übertragen, aber ich denke nicht, dass der Unterschied hier sehr groß ist.