Astar Algorithmus

[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

[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

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

• Wikipedia
• Tutorial

[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.

[Tiim]

Nochmals Update.

Der Weg, ist immer noch sehr Merkwürdig:

Code: Alles auswählen

   X    
 .S X Z
 .  X .
 ......