Wegfindung?

snOOfy

Folgendes Problem:
Jemand ist auf einer Karte, die so aussieht:

0 = frei 1 = wand
Jetzt möchte ich herausfinden, ob er eingesperrt ist (also ob man von seiner Position den Rand der Karte erreichen kann). Das kann er in diesem Beispiel auf allen 0 Feldern außer
000000000
000111000
011101010
001011010
111111111
101100100
000000000

Ich suche einen Algorithmus, der herausfindet, ob es einen Weg zum Rand gibt oder nicht. Kann mir da wer helfen?

CStoll

rekursiv von deiner Position aus alle Nachbarn überprüfen, ob sie (a) schon besucht wurden, (b) eine Wand enthalten oder (c) am Rand liegen (im Fall a und b geht's dort nicht weiter, im Fall c bist du fertig) - wenn du einen gefunden hast, gehst du einen Schritt weiter und startest von vorne.

(am Ende tritt entweder Fall (c) ein (-> Ziel erreicht) oder du stehst am Ausgangspunkt und stellst fest, daß du alle Nachbarn schon überprüft hast (-> Sackgasse))

snOOfy

Ja so ungefähr hab ich mir das auch vorgestellt, aber Rekursion ist nicht so meine Stärke...
Ich komm da immer total durcheinander, weil ich es mir nicht richtig vorstellen kann

Mein Ansatz:

bool WegZumRand(int x, int y)
    {
        if (x==0 || x==iBreite || y == 0 || y == iHoehe)
            return true;
        else    
            return (WegZumRand(x, y-1) || WegZumRand(x, y+1) || WegZumRand(x-1, y) || WegZumRand(x+1, y));
    }

Aber so ist das ja wohl noch nicht richtig, es fehlt das mit der Wand und das mit dem schon besucht...
Kann mir wer sagen, wie ich das machen muss?

cin

So direkt kann ich dir nicht helfen, weil ich ehrlich gesagt grad zu faul bin mich in das Problem einzuarbeiten ;). Allerdings könntest du dir mal den A*-Algorithmus und ein paar Implementationen anschauen. Ist für diesen Fall wohl etwas Overkill, aber falls du mal vorhast eine "Wegfindungs-Routine" auf diese Karte loszulassen, dann ist wohl A* die Lösung deiner Wahl ^^.

Jester

Du kannst auch einfach den Bereich "fluten". Mach Dir ne Liste von Positionen, nennen wir sie die Randgebiete. Am Anfang tuste da nur das Feld rein auf dem Du stehst.

Dann ne Schleife: Solange die Liste mit den Randknoten noch nicht leer nimm den ersten Knoten raus. Schaue Dir alle Nachbarn dieses Knotens an und prüfe, ob man sie betreten kann, ist das der Fall, so prüfe ob Du sie vielleicht schon zuvor besucht hast. Wenn nicht füge den neuen Knoten in die Randliste ein. Der Rand enthält also immer die Felder, von denen aus Du noch nicht weiter gesucht hast.

Sobald Du den Rand erreichst kannste aufhören. Anderenfalls wird die Liste irgendwann leer werden.

MfG Jester

CStoll

snOOfy schrieb:

Aber so ist das ja wohl noch nicht richtig, es fehlt das mit der Wand und das mit dem schon besucht...

Auf Wand kannst du überprüfen, indem du "Karte[x][y]>=1" abfragst, für schonmal besucht empehle ich dir, vor dem Rekursionsschritt eine 2 in die Karte einzutragen (1 steht schon für Wand):

bool WegZumRand(int x, int y)
{
  if (x==0 || x==iBreite || y == 0 || y == iHoehe)
    return true;
  else if(Karte[x][y]>=1)
    return false;
  Karte[x][y]=2;//Position als "besucht" markieren
  return (WegZumRand(x, y-1) || WegZumRand(x, y+1) || WegZumRand(x-1, y) || WegZumRand(x+1, y));
}