From: noaccess9 AT aol DOT com (No Access9)
Newsgroups: comp.os.msdos.djgpp
Subject: Re: Find Path
Date: 31 Jul 1997 12:56:42 GMT
Lines: 370
Message-ID: <19970731125601.IAA27943@ladder02.news.aol.com>
NNTP-Posting-Host: ladder02.news.aol.com
References: <19970729202400 DOT QAA08004 AT ladder01 DOT news DOT aol DOT com>
Organization: AOL Bertelsmann Online GmbH & Co. KG http://www.germany.aol.com
To: djgpp AT delorie DOT com
DJ-Gateway: from newsgroup comp.os.msdos.djgpp
Precedence: bulk

Hello,

a big sorry to all people who said to me this is the wrong newsgroup.
A bigger SORRY to all people who said there isn't any bug in djgpp.
But I thought there must be something wrong with djgpp (specially with
the stack routines - like swapping on hard disk) because I had
differences in speed up to 100 times with the same array size. The
only explanation I can see is that some of the array isn't reachable
for my algorithm. Sorry.

I think the problem is that my algorithm uses more memory than would
fit in  the cache of the prozessor. I think this could explain the big
differences in the executation. But that is of course no bug in djgpp it
is
a "feature" in the architecture of a PC. I hope this was my problem and
therefore I solved it by myself.

Now I have used breadth-search instead and now it is very fast. Thanks
to all people who said that I should use this instead. After reading
"Sedgewick" I discovered this for myself.

I have included the source again. Share and enjoy.

Thanks

Dieter

//************************************************************************
************

// Find Path.cpp
//
// Ein Programm von: Dieter Seidel
//                   Einsteinstraße 19
//         D - 72766 Reutlingen
//                   Deutschland

#include <iomanip.h>
#include <iostream.h>
#include <stdlib.h>

int Zeilen,
    Spalten;

enum BOOL {FALSE, TRUE};

struct Minenfeld
{
  BOOL Mine;
};

Minenfeld Minen_Feld     [40][40];
int       Weglaengen_Feld[40][40];

int  Ziel_x,
     Ziel_y;
BOOL Zeige_Zahlen = TRUE;

struct SucheQueue
{
  int         x,
              y;
  SucheQueue *Next;
};

SucheQueue *Suche_Queue;


void ini(void)
{
  int i, j,
      x, y;

  for (i = 0; i < Zeilen; i++)
    for (j = 0; j < Spalten; j++)
      Minen_Feld[i][j].Mine = FALSE;

  for (i = 0; i < Zeilen*Spalten/3; i++)
  {
    do
    {
      x = rand() % Spalten;
      y = rand() % (Zeilen - 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(int x, int y)
{
  Suche_Queue = NULL;

  for (int i = 0; i < Zeilen; i++)
    for (int j = 0; j < Spalten; j++)
      Weglaengen_Feld[i][j] = 0;

  if (x > Spalten - 1 || x < 0 || y > Zeilen - 1 || y < 0)
  {
    cout << endl << "Fehler in Suche_Ini(): Ungültiger Startparameter" <<
flush;
    exit(1);
  }
}


int Maximum(int i, int j)
{
  return (i > j) ? i: j;
}


BOOL Suche_Queue_Empty(void)
{
  if (Suche_Queue == NULL)
    return TRUE;
  else
    return FALSE;
}


int Suche_Laenge(int x, int y)
{
  int max = 0;

  if (x > 0)
    max = Maximum(max, Weglaengen_Feld[y    ][x - 1]);
  if (y > 0)
    max = Maximum(max, Weglaengen_Feld[y - 1][x    ]);
  if (x < Spalten - 1)
    max = Maximum(max, Weglaengen_Feld[y    ][x + 1]);
  if (y < Zeilen - 1)
    max = Maximum(max, Weglaengen_Feld[y + 1][x    ]);

  return max;
}


void Suche_Pop(int &x, int &y)
{
  SucheQueue *tmp;

  if (Suche_Queue == NULL)
  {
    cout << endl << "Fehler in Suche_Pop: Queue bereits leer!" << flush;
    exit(1);
  }

  x = Suche_Queue->x;
  y = Suche_Queue->y;

  tmp = Suche_Queue->Next;
  delete Suche_Queue;
  Suche_Queue = tmp;
}


void Suche_Push(int x, int y)
{
  SucheQueue *tmp;

  if (x >= 0 && x < Spalten &&
      y >= 0 && y < Zeilen  &&
      Minen_Feld[y][x].Mine == FALSE)
  {
    if (Suche_Queue == NULL)
    {
      Suche_Queue       = new SucheQueue;
      Suche_Queue->x    = x;
      Suche_Queue->y    = y;
      Suche_Queue->Next = NULL;
    }
    else
    {
      tmp = Suche_Queue;
      while (Suche_Queue->Next != NULL)
        Suche_Queue = Suche_Queue->Next;
      Suche_Queue->Next       = new SucheQueue;
      Suche_Queue->Next->x    = x;
      Suche_Queue->Next->y    = y;
      Suche_Queue->Next->Next = NULL;
      Suche_Queue = tmp;
    }
  }
}


void Suche_Find_Direction(int &x, int &y)
{
  if (Weglaengen_Feld[y][x] == 0)
    cout << endl << "Fehler in Suche_Find_Direction: Es existiert kein
Pfad!" << endl;
  else
    while (Weglaengen_Feld[y][x] != 2)
      if (y > 0 && Weglaengen_Feld[y - 1][x] < Weglaengen_Feld[y][x]
                && Weglaengen_Feld[y - 1][x] != 0)
        y = y - 1;
      else
        if (x > 0 && Weglaengen_Feld[y][x - 1] < Weglaengen_Feld[y][x]
                  && Weglaengen_Feld[y][x - 1] != 0)
          x = x - 1;
        else
          if (x < Spalten - 1 && Weglaengen_Feld[y][x + 1] <
Weglaengen_Feld[y][x]
                              && Weglaengen_Feld[y][x + 1] != 0)
            x = x + 1;
          else
            y = y + 1;
}


void Suche(int &x, int &y)
{
  Suche_Ini(x, y);

  Weglaengen_Feld[y][x] = 1;

  Suche_Push(x    , y - 1);
  Suche_Push(x - 1, y    );
  Suche_Push(x + 1, y    );
  Suche_Push(x    , y + 1);

  while (Suche_Queue_Empty() == FALSE)
  {
    Suche_Pop(x, y);
    if (Weglaengen_Feld[y][x] == 0)
    {
      Suche_Push(x    , y - 1);
      Suche_Push(x - 1, y    );
      Suche_Push(x + 1, y    );
      Suche_Push(x    , y + 1);

      Weglaengen_Feld[y][x] = Suche_Laenge(x, y) + 1;
    }
  }

  x = Ziel_x;
  y = Ziel_y;
  Suche_Find_Direction(x, y);
}


void Drucke_Minenfeld(int x, int y)
{
  int i, j;

  cout << 'É';
  for (j = 1; j < Spalten + 1; j++)              // Obere Begrenzung
    cout << 'Í';
  cout << '»' << endl << 'º';

  for (i = 0; i < Zeilen; i++)
  {
    for (j = 0; j < Spalten; 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 << 'º' << endl;
    if (i != Zeilen - 1)
      cout << 'º';
  }

  cout << 'È';
  for (j = 1; j < Spalten + 1; j++)              // Untere Begrenzung
    cout << 'Í';
  cout << '¼' << endl;
}


void Drucke_Weglaengen(int x, int y)
{
  int i, j;

  cout << 'É';
  for (j = 1; j < Spalten + 1; j++)              // Obere Begrenzung
    cout << "ÍÍÍÍ";
  cout << '»' << endl << 'º';

  for (i = 0; i < Zeilen; i++)
  {
    for (j = 0; j < Spalten; j++)
    {
      if (i == Ziel_y && j == Ziel_x)
        cout << "ZZZ ";                           // Ziel
      else
        if (i == y && j == x)
          cout << "GGG ";                        // Gegner
        else
          if (Minen_Feld[i][j].Mine == TRUE)
            cout << "### ";                       // Mine
          else
            cout << setw(3) << setprecision(3) << Weglaengen_Feld[i][j] <<
' ';
    }
    cout << 'º' << endl;
    if (i != Zeilen - 1)
      cout << 'º';
  }

  cout << 'È';
  for (j = 1; j < Spalten + 1; j++)              // Untere Begrenzung
    cout << "ÍÍÍÍ";
  cout << '¼' << endl;
}


int main()
{
  int  Seed,
       x, y,
       tmp_x, tmp_y;
  char ch = ' ';

  cout << "Input Lines : ";
  cin >> Zeilen;
  cout << "Input Rows  : ";
  cin >> Spalten;
  cout << "Seed?       : ";
  cin >> Seed;

  srand(Seed);
  Ziel_x  = Spalten/3;                              // Startposition des
Spielers
  Ziel_y  = 1;
  x = Spalten - Spalten/3;                          // Startposition des
Gegners
  y = Zeilen - 1;

  ini();

  cout << "That is the minefield" << endl;
  Drucke_Minenfeld(x, y);
  cout << "Should I start now? q for Quit.";
  cin >> ch;
  if (ch == 'q' || ch == 'Q')
    exit(1);

  cout << endl << "And now the result:" << endl;

  do
  {
    tmp_x = x;
    tmp_y = y;
    Suche(x,y);
    if (Zeige_Zahlen == TRUE)
      Drucke_Weglaengen(tmp_x, tmp_y);
    else
      Drucke_Minenfeld(tmp_x, tmp_y);
    if (x != Ziel_x || y != Ziel_y)
    {
      cout << "Press a key (q for Quit) ";
      cin >> ch;
    }
  }
  while ((x != Ziel_x || y != Ziel_y) && ch != 'q' && ch != 'Q');

  return 0;
}