Mail Archives: djgpp/1997/08/03/17:02:11
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;
}
- Raw text -