From: noaccess9 AT aol DOT com (No Access9) Newsgroups: comp.os.msdos.djgpp Subject: Find Path Date: 29 Jul 1997 20:24:50 GMT Message-ID: <19970729202400.QAA08004@ladder01.news.aol.com> NNTP-Posting-Host: ladder01.news.aol.com Organization: AOL Bertelsmann Online GmbH & Co. KG http://www.germany.aol.com Lines: 276 To: djgpp AT delorie DOT com DJ-Gateway: from newsgroup comp.os.msdos.djgpp Precedence: bulk Hello, I have written a program to detect the shortest path in a minefield. I have included the C++ Source so you can run this under DOS. Sorry, but most of the comments are in German. To understand the output of the program, here is a short explanation: Z is the aim G is the start # is a mine, you have to go around this - is space, you can travel on this I think the program works fine, but I have problems to understand the immense difference in speed. For example: If you start this with 11 Lines and 11 Rows and with Seed 9 then a move will only take 3 seconds to compute. But if I start this again with 11 Lines and 11 Rows but now with Seed 7 then it will take 5 Minutes for a move. My problem is that I can't understand why it takes so much longer only because the mines are layed differently. So I assume there is a bug in djgpp V2.7.2.1. But there may also be a problem with my recursion. So if you have a better one it would be nice to hear about that. I tried this for a short moment with Turbo C++ and there seems no such difference in computation time. But I may be wrong. Please eMail me, because I doesn't read this newsgroup very often. Thanks Dieter //*********************************************************************************** // Find Path.cpp // // Copyright: Dieter Seidel // Einsteinstraße 19 // D - 72766 Reutlingen // Reutlingen // #include #include #include unsigned _stklen = 1048576; // 1 MByte Stack int Lines, Rows; enum BOOL {FALSE, TRUE}; struct Minenfeld { BOOL Mine; BOOL Besucht; }; Minenfeld Minen_Feld[50][50]; int Ziel_x, Ziel_y, Abbruch; // Max. Tiefe für Tiefen_Suche long int Max_Rekursionen, // Zähler für die Rekursionstiefe Anzahl_Rekursionen = 500000; // Max. so viele Rekursionen BOOL Max_Rekursionen_Erreicht = FALSE; // Zu viele Rekursionen erreicht? void ini(void) { int i, j, x, y; for (i = 0; i < Lines; i++) for (j = 0; j < Rows; j++) Minen_Feld[i][j].Mine = FALSE; for (i = 0; i < Lines*Rows/3; i++) { do { x = rand() % Rows; y = rand() % (Lines - 1); } while (Minen_Feld[y][x].Mine == TRUE); Minen_Feld[y][x].Mine = TRUE; } Minen_Feld[Ziel_y][Ziel_x].Mine = FALSE; } void Suche_Ini(void) { Max_Rekursionen = 0; if (Max_Rekursionen_Erreicht == TRUE) cout << endl << "Fehler Tiefen_Suche(): Zu viele Rekursionen!" << flush; Max_Rekursionen_Erreicht = FALSE; for (int i = 0; i < Lines; i++) for (int j = 0; j < Rows; j++) Minen_Feld[i][j].Besucht = Minen_Feld[i][j].Mine; } int Tiefen_Suche(int x, int y, int Tiefe) { //Max_Rekursionen++; //if (Max_Rekursionen > Anzahl_Rekursionen) // Zu viele Rekursionsaufrufe //{ // Max_Rekursionen_Erreicht = TRUE; // return Abbruch + 10; //} if (Tiefe >= Abbruch) // Zu große Rekursionstiefe { cout << "Fehler: Tiefe >= Abbruch" << flush; return Abbruch + 11; } if (x > Rows - 1 || x < 0) // Ungültige x-Position return Abbruch + 20; if (y > Lines - 1 || y < 0) // Ungültige y-Position return Abbruch + 21; if (Minen_Feld[y][x].Besucht == TRUE) // War bereits hier oder eine Mine ist hier return Abbruch + 22; if (x == Ziel_x && y == Ziel_y) // Ziel erreicht return Tiefe + 1; Minen_Feld[y][x].Besucht = TRUE; int x1 = Tiefen_Suche(x - 1, y , Tiefe + 1); int x2 = Tiefen_Suche(x + 1, y , Tiefe + 1); int y1 = Tiefen_Suche(x , y - 1, Tiefe + 1); int y2 = Tiefen_Suche(x , y + 1, Tiefe + 1); Minen_Feld[y][x].Besucht = FALSE; if (y1 <= x1 && y1 <= x2 && y1 <= y2) return y1; if (x1 <= x2 && x1 <= y1 && x1 <= y2) return x1; if (x2 <= x1 && x2 <= y1 && x2 <= y2) return x2; if (y2 <= x1 && y2 <= x2 && y2 <= y1) return y2; cout << endl << "Fehler in Tiefen_Suche(): Ungültiger return-Wert!!!" << flush; return Abbruch + 40; } int Suche(int &x, int &y) { Suche_Ini(); int Ergebnis_1 = Tiefen_Suche(x - 1, y , 0); Suche_Ini(); int Ergebnis_2 = Tiefen_Suche(x + 1, y , 0); Suche_Ini(); int Ergebnis_3 = Tiefen_Suche(x , y - 1, 0); Suche_Ini(); int Ergebnis_4 = Tiefen_Suche(x , y + 1, 0); if (Ergebnis_3 <= Ergebnis_1 && Ergebnis_3 <= Ergebnis_2 && Ergebnis_3 <= Ergebnis_4) { y = y - 1; return Ergebnis_3; } if (Ergebnis_1 <= Ergebnis_2 && Ergebnis_1 <= Ergebnis_3 && Ergebnis_1 <= Ergebnis_4) { x = x - 1; return Ergebnis_1; } if (Ergebnis_2 <= Ergebnis_1 && Ergebnis_2 <= Ergebnis_3 && Ergebnis_2 <= Ergebnis_4) { x = x + 1; return Ergebnis_2; } if (Ergebnis_4 <= Ergebnis_1 && Ergebnis_4 <= Ergebnis_2 && Ergebnis_4 <= Ergebnis_3) { y = y + 1; return Ergebnis_4; } cout << endl << "Fehler in Suche()" << flush; return 0; } void Drucke_Minenfeld(int x, int y) { int i, j; for (j = 0; j < Rows + 2; j++) // Obere Begrenzung cout << 'X'; cout << endl << 'X'; for (i = 0; i < Lines; i++) { for (j = 0; j < Rows; j++) { if (i == Ziel_y && j == Ziel_x) cout << 'Z'; // Ziel else if (i == y && j == x) cout << 'G'; // Gegner else if (Minen_Feld[i][j].Mine == TRUE) cout << '#'; // Mine else cout << '-'; // Leerer Raum } cout << 'X' << endl; if (i != Lines - 1) cout << 'X'; } for (j = 0; j < Rows + 2; j++) // Untere Begrenzung cout << 'X'; cout << endl; } int main() { int x, y, seed; char ch; cout << "Input Lines : "; cin >> Lines; cout << "Input Rows : "; cin >> Rows; cout << "Input Seed : "; cin >> seed; srand(seed); ini(); Abbruch = Lines * Rows; Ziel_x = Rows/3, Ziel_y = 1, x = Rows - Rows/3; // Startposition des Gegners y = Lines - 1; cout << "And that is the Minefield." << endl; cout << "Lines: " << Lines << " Rows: " << Rows << endl << endl; Drucke_Minenfeld(x, y); cout << endl << "To start press a key. for Quit" << endl; cin >> ch; if (ch == 'q' || ch == 'Q') exit(1); while ((x !=Ziel_x || y !=Ziel_y) && ch != 'q' && ch != 'Q') { cout << endl << "Number of steps: "; cout << Suche(x, y); cout << " with x: " << x << " and y: " << y << endl << endl; Drucke_Minenfeld(x, y); cout << "Press a key"; cin >> ch; } return 0; }