Seite 1 von 1
Astar Algorithmus
Verfasst: 28. August 2011 22:36
von Tiim
Hallo Community
Diesmal habe ich ein ganz sonderbares Problem.
Mein Ziel ist es den A* (A star) Algorithmus umzusetzen, und zu visualisieren.
Die "Karte" wird über eine Textdatei "default.map" eingelesen, wobei S der Startpunkt, Z der Zielpunkt und X Mauern sind.
Nun wird mit dem oben genannten Algorithmus der Weg vom Start zum Ziel berechnet, wobei das schon aus unerfindlichen Gründen nicht richtig funktioniert.
Je nachdem wie die Karte aussieht, kommt früher oder Später vom Qt Creator Debugger die Meldung dass ein Signal "SIGABRT" mit der Bedeutung "Aborded" vom Betriebssystem (Ubuntu Natty Warwahl) kommt.
Wenn ich nun im Call Stack so weit in die Tiefe gehe, bis nichts mehr in Assembler steht, befinde ich mich in der Main Funktion bei "return a.exec();"
Hier mal mein gesamter Code (inklusive *.pro und die Map), da ich den Fehler nirgends Lokalisieren kann
Re: Astar Algorithmus
Verfasst: 29. August 2011 08:24
von franzf
Du machst ziemlichen Müll in Map::addNeighbours(). Überprüfe GENAU was du mit den Indizes machst. Du bekommst da relativ viele neue Listen angehangen. Die alloziieren Speicher auf dem HEAP, deshalb hab ich einen std::bad_alloc bekommen.
Lass dir mit qDebug() ausgeben, was in den for-Schleifen grad abgeht, vllt. kriegst du dann auch so ne Ausgabe:
Code: Alles auswählen
append No. 77826 to nodlist
append No. 77827 to nodlist
append No. 77828 to nodlist
append No. 77829 to nodlist
append No. 77830 to nodlist
append No. 77831 to nodlist
append No. 77832 to nodlist
append No. 77833 to nodlist
append No. 77834 to nodlist
append No. 77835 to nodlist
append No. 77836 to nodlist
append No. 77837 to nodlist
append No. 77838 to nodlist
append No. 77839 to nodlist
append No. 77840 to nodlist
append No. 77841 to nodlist
append No. 77842 to nodlist
append No. 77843 to nodlist
append No. 77844 to nodlist
append No. 77845 to nodlist
append No. 77846 to nodlist
append No. 77847 to nodlist
append No. 77848 to nodlist
append No. 77849 to nodlist
append No. 77850 to nodlist
append No. 77851 to nodlist
append No. 77852 to nodlist
append No. 77853 to nodlist
append No. 77854 to nodlist
append No. 77855 to nodlist
append No. 77856 to nodlist
append No. 77857 to nodlist
append No. 77858 to nodlist
append No. 77859 to nodlist
append No. 77860 to nodlist
append No. 77861 to nodlist
append No. 77862 to nodlist
append No. 77863 to nodlist
append No. 77864 to nodlist
append No. 77865 to nodlist
append No. 77866 to nodlist
append No. 77867 to nodlist
append No. 77868 to nodlist
append No. 77869 to nodlist
Ich hab das Programm dann abgeschossen
Wäre so lange weitergelaufen, bis kein neuer Speicher mehr angefordert werden kann.
Da addNeighbours() nur im SLOT(nextstep) aufgerufen wird, bist du am Ende auch in der Event-Loop, deshalb app.exec().
[edit]
Problem liegt an der Abbruchbedingung: in jedem Schleifendurchlauf fügst du ein neues Element an die Liste an, wodurch size() erhöht wird und dadurch bei der nächsten Abfrage der Bedingung diese (natürlich) nicht erfüllt ist. Vor dem "for" einfach die size() in einer eigenen Variable speichern, dann passt das wieder mit der Abbruchbedingung.
Nun kommt es aber zu einem SegFault...
Viel Spaß beim Debuggen
Re: Astar Algorithmus
Verfasst: 29. August 2011 11:59
von Tiim
Hmm gut, das Problem habe ich behoben.
Doch aus irgendeinem Grund sucht sich der Algo einen ganz krummen Weg.
Ich habe im Startpost jetzt die neue Verison hochgeladen, falls jemand sich das ansehen will.
Und fals sich jemand über A* (Astar) schlaumachen will:
Re: Astar Algorithmus
Verfasst: 29. August 2011 13:15
von Tiim
So, hab noch einen kleinen Fehler in der Funktion addNeighbour gefunden und im ersten Post aktualisiert.
Es wird jedoch immer noch ein ganz merkwürdiger Weg gesucht, bis er gefunden wurde.
Re: Astar Algorithmus
Verfasst: 29. August 2011 16:06
von Tiim
Nochmals Update.
Der Weg, ist immer noch sehr Merkwürdig: