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

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 <iostream.h>
#include <stdlib.h>
#include <time.h>

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. <q> 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;
}

- Raw text -