Rekursive Wegfindung aus einem Labyrinth
-
Hi, ich hab die Aufgabe aus einem Labyrinth einen Weg zu finden.
Man hat zwei Labyrinthe zur Auswahl (wobei das zweite nicht gelöst werden muss, sondern nur dazu dient, dass man mögliche Probleme erkennt).
Man gibt die Startkoordinaten ein und das ganze soll dann automatisch den Weg finden.den Algorithmus zur berechnung des Weges hab ich glücklicherweise in einem Buch gefunden. Nur mag er bei meiner angepassten Version nicht mehr so richtig.
Ich weiß auch nicht genau, warum es jetzt nicht mehr hinhaut.
(der code ist noch ziemlich unstrukturiert, und enthält noch mehrere testausgaben, also bitte nicht meckern
)#include <iostream> using namespace std; #include "check_number.h" #include "convert_number.h" #include "read_number.h" #include "defines.h" unsigned char LabPat[PAT_CNT][LMAX_Y][LMAX_X+1] = {{"XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", // 0 "X +", // 1 "X XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", // 2 "X XX X", // 3 "X XX XXX XXXXXXXXXXXXXXXXXXXXX X", // 4 "X XX XXX XX X", // 5 "X XX XXX XXXXXXXXXXXXXXXXXX XX X", // 6 "X XX XXX XXXXXXX XXXXXXXXXX XX X", // 7 "X XX XX X XX XX X", // 8 "X XX XX XXXXXXXXXXXXXXXX XXXXX X", // 9 "X XX XX XX XX X", // 10 "X XX XXXXXXXXXXXXXXXXXXXXXX XX X", // 11 "X XX XX X", // 12 "X XXXXXXXXXXXXXXXXXXXXXXXXXXXX X", // 13 "X X", // 14 "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"}, // 15 {"XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", // 0 "X X", // 1 "X XXXXXXXXXXXXXXXX XXXXXXXXXXXXX", // 2 "X XX X", // 3 "X XX XXX XXXXXXXXXXXXXXXXXXXXX X", // 4 "X XX XX XX X", // 5 "X XX XXX XXXXXXX XXXXXXXXXX XX X", // 6 "X XX XXX XXXXXXXXXXXXXXXXXX XX X", // 7 "X XX XX X XX XX X", // 8 "X XX XX XXXXXXXX XXXXXXX XXXXX X", // 9 "X XX XX XX XX X", // 10 "X XX XXXXXXXXXXXXXXXXXXXXXX XX X", // 11 "X XX XX X", // 12 "X XXXXXXXXXXXXXXXXXXXXXXXXXXXX X", // 13 "+ X", // 14 "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"}};// 15 void ausgabe(int lab_number) { for (int y=0;y<LMAX_Y;y++) { for(int x=0; x< LMAX_X;x++) { cout << LabPat[lab_number][y][x]; } cout << endl; } cout << endl; } int weg( int lab_number, int start_y, int start_x, int ziel_y, int ziel_x) { // cout << "\nSuche weg\n"; if( (start_y == ziel_y) && (start_x == ziel_x)) { LabPat[lab_number][start_y][start_x] = 'f'; return 1; } if( LabPat[lab_number][start_y-1][start_x] == ' ') { LabPat[lab_number][start_y][start_x] = '^'; if( weg( lab_number, start_y-1, start_x, ziel_y, ziel_x)) return 1; } if( LabPat[lab_number][start_y+1][start_x] == ' ') { LabPat[lab_number][start_y][start_x] = 'v'; if( weg(lab_number, start_y+1, start_x, ziel_y, ziel_x)) return 1; } if( LabPat[lab_number][start_y][start_x-1] == ' ') { LabPat[lab_number][start_y][start_x] = '<'; if( weg(lab_number, start_y, start_x-1, ziel_y, ziel_x)) return 1; } if( LabPat[lab_number][start_y][start_x+1] == ' ') { LabPat[lab_number][start_y][start_x] = '>'; if( weg( lab_number, start_y, start_x+1, ziel_y, ziel_x)) return 1; } LabPat[lab_number][start_y][start_x] = ' '; return 0; } int main(int argc, char *argv[]) { int start_x, start_y, finish_x, finish_y; unsigned long a,b; if (argc != 3) //überprüfung ob richtige anzahl an koordinaten übergeben wurde { cout << "\nErforderliche Anzahl von Parametern: 2\n"; cout << "Von Ihnen eingegeben Anzahl von Parametern: " << argc-1 << endl; cout << "Bitte erneut Eingeben\n\n"; return 0; } else if ( check_number(argv[1]) == false) { cout << "\nErste Koordinate ungueltig!" << endl; return 0; } else if( check_number(argv[2]) == false) { cout << "\nZweite Koordinate ungueltig" << endl; return 0; } else // strings in int umwandeln cout << "1. Parameter: " << argv[1] << endl; cout << "2. Parameter: " << argv[2] << endl << endl; a= convert_number(argv[1]); b= convert_number(argv[2]); cout << "\n\nLabyrinth waehlen (1 / 2): "; int lab_number = read_number(); if (lab_number <1 || lab_number >2) { cout << "\nEs sind nur zwei Labyrinthe vorhanden\n"; return -1; } else { if (LabPat[lab_number-1][b-1][a-1] == 'X') // startkoordinate auf Wand? { cout << "\nFehler! Koordinate liegt auf einer Wand\n"; } else // Startkoordinate im Labyrinth mit o kennzeichnen { LabPat[lab_number-1][b-1][a-1] = 'o'; cout << "\n\nKoordinaten werden ausgegeben\n" << endl; ausgabe(lab_number-1); } } for (int s =0; s<LMAX_Y;s++) // ziel suchen, dass mit + markiert ist { for ( int t=0;t<LMAX_X;t++) { if (LabPat[lab_number-1][s][t] == '+') { finish_x=t; finish_y=s; cout << "\n Ziel gefunden\n"; } } } start_x = a-1; start_y = b-1; cout << "\na: " << a << " | b: " << b << " | start_x: " << start_x << " | start_y: " << start_y << " | lab_number: " << lab_number << endl; cout << "finish_x: " << finish_x << " | finish_y: " << finish_y << endl; // kleine Testausgabe um die Werte zu überprüfen ausgabe(lab_number-1); if ( weg(lab_number-1, start_y, start_x, finish_y, finish_x)) // der aufruf aus dem buch { ausgabe(lab_number-1); } else cout << "\nKeine Loesung gefunden" << endl; return 0; }readnumber() convert_number und checknumber() sind nur dazu da, die eingelesenen strings auf gültigkeit zu prüfen und das ganze in int umzuwandeln.
ich poste nochmal den code aus dem buch, das was ich dem hinzugefügt hat ist lediglich, dass ich die lab_number mit an weg() übergebe. dies dient dazu, dass man weiß welches Labyrinth benutzt werden soll.
hier der code aus dem buch
der Aufruf aus der mainfunktion:
if( weg( start_z, start_s, ziel_z, ziel_s)) ausgabe(); else printf( "Keine Loesung gefunden!\n");die funktion selbst:
int weg( int start_z, int start_s, int ziel_z, int ziel_s) { if( (start_z == ziel_z) && (start_s == ziel_s)) { labyrinth[start_z][start_s] = '+'; return 1; } if( labyrinth[start_z-1][start_s] == ' ') { labyrinth[start_z][start_s] = '^'; if( weg( start_z-1, start_s, ziel_z, ziel_s)) return 1; } if( labyrinth[start_z+1][start_s] == ' ') { labyrinth[start_z][start_s] = 'v'; if( weg( start_z+1, start_s, ziel_z, ziel_s)) return 1; } if( labyrinth[start_z][start_s-1] == ' ') { labyrinth[start_z][start_s] = '<'; if( weg( start_z, start_s-1, ziel_z, ziel_s)) return 1; } if( labyrinth[start_z][start_s+1] == ' ') { labyrinth[start_z][start_s] = '>'; if( weg( start_z, start_s+1, ziel_z, ziel_s)) return 1; } labyrinth[start_z][start_s] = ' '; return 0; }wer sich den kompletten quellcode mit allen headerdateien ansehen will, ich habe ihn auf http://www.ugod.de/uebung002.rar (Größe 12KB) hochgeladen.
Vielen Dank schonmal an alle, die sich mein Problem anschauen und mir vielleicht bei einer Lösung helfen.
Gruß
Martin
-
ist das nicht einfacher mit einem bool-Array zu lösen?
if(feld[x][y]) { // weiter } else { // sonst weiter }
-
sonst immer eine Strategie einschlagen z.b. immer links alle wände abchecken...
-
Erinnert mich an Kara, den lustigen Marienkäfer
-
ugod schrieb:
int weg( int lab_number, int start_y, int start_x, int ziel_y, int ziel_x)
Äh, kann es sein, dass du die Funktion aus dem Buch nicht korrekt abgetippelt hast?
ugod schrieb:
int weg( int start_z, int start_s, int ziel_z, int ziel_s)
Was ist hier nun mal richtig?
-
das untere ist richtig.
lab_number habe ich eingefügt, damit er das richtige labyrinth nimmt.
im buch hat er ein labyrinth aus einer textdatei eingelesen.gruß
martin