Problem mit "Breitensuche"

Shakesbier

Hi!

Zur Zeit beschäftige ich mich mit dem Algorithmus für die sog. Breitensuche.
Mit der Breitensuche soll der kürzesten Weg von einem vordefinierten Startpunkt zu einem Zielpunkt gefunden werden. Auf dem Weg dort hin gibt es Hindernisse, die durch eine Bitmap-Datei eingelesen werden.

Beispiel eines solchen 2D-Umgebung mit Hindernissen: LINK

Der gefundene Weg zum Ziel wird dann in ein neues Bmp-Bild eingezeichent. Nur leider klappt mein Algorithmus noch nicht ganz. Dieses Bild liefert mein Code, wenn ich einen Pfad von der linken oberen Ecke in die rechte untere Ecke suche: LINK

Leider kann ich meinen Fehler im Code nicht finden... Kann mir da eventuell jemand helfen??

Den Suchalgorithmus habe ich folgendermaßen versucht umzusetzen:

1. Füge Startzelle in Queue ein (push)
2. Markiere die Startzelle
3. Nehme die erste Zelle aus der Queue (pop)
4. Falls die Zelle die Zielzelle ist -> Weg gefunden
5. Für jede Nachbarzelle, die noch nicht markiert ist, setze die aktuelle Zelle als Vorgänger und nehme sie in die Queue auf
6. Springe zu Schritt 3, bis der Algorithmus terminiert oder die Queue leer ist.

Da der Quellcode etwas länger ist, hab ich hier nen Link zu meiner "main.cpp" erstellt: main.cpp

Ich hoffe mal mir kann bei diesem speziellen Thema jemand helfen!

Gruß

Bashar

indizierst. Naja, und dass Breitensuche hier nicht wirklich ein geeigneter Algorithmus ist, aber das wirst du schon noch merken.

finix

Du benutzt den falschen Algorithmus. http://de.wikipedia.org/wiki/Algorithmus_von_Dijkstra

finix

Bashar schrieb:

Naja, und dass Breitensuche hier nicht wirklich ein geeigneter Algorithmus ist, aber das wirst du schon noch merken.

Vielleicht für Kurzstrecken-Teleporter

Bashar

finix schrieb:

Du benutzt den falschen Algorithmus. http://de.wikipedia.org/wiki/Algorithmus_von_Dijkstra

Auch falsch
http://de.wikipedia.org/wiki/A*

Turing

Du benutzt den falschen Algorithmus. http://de.wikipedia.org/wiki/Algorithmus_von_Dijkstra

Nimm lieber A* - Suche. Als Heuristik verwendest Du die "Manhattan-Norm" / "Spaltensummennorm".

finix

Dijkstras Algorithmus funktioniert, und ist einem offensichtlichem Anfänger wohl erst einmal zugänglicher.

Konrad Rudolph

finix schrieb:

Dijkstras Algorithmus funktioniert, und ist einem offensichtlichem Anfänger wohl erst einmal zugänglicher.

Breitensuche funktioniert auch und ist ja wohl vor Dijkstra der erste Schritt.

finix

Konrad Rudolph schrieb:

finix schrieb:

Dijkstras Algorithmus funktioniert, und ist einem offensichtlichem Anfänger wohl erst einmal zugänglicher.

Breitensuche funktioniert auch und ist ja wohl vor Dijkstra der erste Schritt.

Das möchte ich sehen.

Konrad Rudolph

finix schrieb:

Konrad Rudolph schrieb:

finix schrieb:

Dijkstras Algorithmus funktioniert, und ist einem offensichtlichem Anfänger wohl erst einmal zugänglicher.

Breitensuche funktioniert auch und ist ja wohl vor Dijkstra der erste Schritt.

Das möchte ich sehen.

Hmm, ich habe wohl das Wörtchen "kürzesten" überlesen. Dann funktioniert Breitensuche natürlich nur noch in Spezialfällen (alle Kanten haben dieselbe Länge). Im einfachen Fall, in dem man durch ein Pixel-Array sucht, funktioniert sie natürlich aber trotzdem, das sollte offensichtlich sein, oder?

finix

Das ist für mich ehrlich gesagt nicht offensichtlich. Mir ist nicht ganz klar wie da ein Pfad herauskommen soll (außer natürlich in einem speziellen Fall ), daher wäre ich dir für eine kurze Erläuterung sehr dankbar.

life

finix schrieb:

Das ist für mich ehrlich gesagt nicht offensichtlich. Mir ist nicht ganz klar wie da ein Pfad herauskommen soll (außer natürlich in einem speziellen Fall ), daher wäre ich dir für eine kurze Erläuterung sehr dankbar.

http://de.wikipedia.org/wiki/Breitensuche

--> Breitensuche liefert kürzeste Weg von einem Knoten s zu allen anderen Knoten, sofern man keine Kantengewichte hat (bzw. alle gleich sind). Legt man hier also ein entsprechendes Grid rein, würd auch Breitensuche ohne weiteres funktionieren.

Der "Fehler" sieht eher so aus als wären im Graphen die Hindernisse garnicht berücksichtigt worden..

Konrad Rudolph

finix schrieb:

Das ist für mich ehrlich gesagt nicht offensichtlich. Mir ist nicht ganz klar wie da ein Pfad herauskommen soll (außer natürlich in einem speziellen Fall ), daher wäre ich dir für eine kurze Erläuterung sehr dankbar.

Na die Breitensuche liefert Dir doch auf Wunsch einen GAG und einen Endknoten. Dann musst Du Dich an den Kanten vom Endknoten aus einfach zur Wurzel hochhangeln und schon hast Du Deinen Pfad vom Ziel zum Start (welcher der kürzeste ist).

Pseudocode für die Breitensuche mit Endknoten und GAG:

Funktion Breitensuche(start, ende)
  W: leere Warteschlange
  B: leerer Baum
  Füge start W hinzu
  Füge start B hinzu
  Wiederhole
    Entnimm v aus W
    markiere v
    Wenn v = ende dann gib B zurück
    Für alle unmarkierten u in Adjazenzknoten(v)
      Füge u W hinzu
      Füge (v, u) B hinzu
    Wenn W leer, dann gib nix zurück

Sollte so klappen.

Shakesbier

life schrieb:

--> Breitensuche liefert kürzeste Weg von einem Knoten s zu allen anderen Knoten, sofern man keine Kantengewichte hat (bzw. alle gleich sind). Legt man hier also ein entsprechendes Grid rein, würd auch Breitensuche ohne weiteres funktionieren.

Der "Fehler" sieht eher so aus als wären im Graphen die Hindernisse garnicht berücksichtigt worden..

Hätte ich vielleicht am Anfang dazu sagen sollen. Genauso ist es nämlich, dass ich mich durch einen Raum mit einer bestimmten Rastergröße bewege, also in Grid ist vorhanden!

An einen anderen Algorithmus wie ja hier auch schon empfohlen wurde, hatte ich auch schon gedacht, aber da ich jetzt mit der Breitensuche angefangen habe, würde ich es auch gerne ersteinmal zum laufen bringen... Danach mache ich mir definitiv mal ein paar Gedanken zur Optimierung!

Nur warum die Hindernisse allen Anschein nach bei mir noch nicht berücksichtigt werden, konnte ich immer noch nicht raus finden...

@ Konrad Rudolph: Genauso habe ich es ja auch versucht (siehe meinen Pseudocode im ersten Beitrag). Und ich denke zumindest, dass ich das in meinem Code auch umgesetzt habe...

Bashar

Shakesbier schrieb:

Nur warum die Hindernisse allen Anschein nach bei mir noch nicht berücksichtigt werden, konnte ich immer noch nicht raus finden...

Bist du der Sache mit der Reihenfolge der Indizes mal nachgegangen?

Shakesbier

Nach stundenlangem debuggen habe ich den Fehler endlich gefunden...

// In dieser Tabelle steht die Reihenfolge in der die Umliegenden Felder abgearbeitet werden sollen

const int DirTable[8][2] = { 
{  0, -1},      // oben
{  1,  0},      // rechts
{  0,  1},      // unten
{ -1, -1},      // links         FEHLER: Hier muss natürlich {-1, 0} hin!!
{  1, -1},      // rechts-oben
{  1,  1},      // rechts-unten
{ -1,  1},      // links-unten
{ -1, -1} };    // links-oben

An der Stelle habe ich natürlich erst am Schluss gesucht.

Danke nochmal für die Hinweise zu effizienteren Algorithmen. Werde ich mir die nächsten Tage mal ansehn!

Problem mit &quot;Breitensuche&quot;

Problem mit "Breitensuche"