C ++ Maze Problem

**tetraflare** · 12-04-2002

ok now i have a serious question... on my maze ( posted below)

i need to have the maze tracel to the end in the FASTEST possible path... ( how would i make a pointer to do this...or do i even need a pointer? )

a few things first off...

1) the number 177 is the acsii character for wall in my maze. all other numbers are arrows except 40, which is the end.

2) right now it makes like 7000 moves to get to the end, how can i make it so it wont backtrack? or try to go through walls?

****** I strongly reccomend you compile and run, it may not work the first time or so, ust keep trying, a rand is messed up somewhere so please beae with me. ****************

here it is

#include <iostream>
#include <ctime>
#include <cstdlib>
#include <windows.h>
using namespace std;
unsigned long stepInt = 0;
const int size = 40;
int arraybox[size][size];
int r = 1, c = 1;
void print(void);
void move(void);
void walls(void);
int main()
{
int yo=1;

for (int i = 0; i < size + 1; i++) { //intiailizes box
arraybox[i][0] =177;
arraybox[i][size-1] = 177;
arraybox[0][i] = 177;
arraybox[size-1][i] = 177;
}
walls();
print();
cout << "\nProccessing\n";
for (int y = 0; y < 50; y++) {

Sleep(10);

cout << '.';
}
move();
cout << endl << "Steps: " << stepInt << endl;
//steps counts # of moves it takes
cin >> yo;

return 0;

}

void print()
{

for (int l = 0; l < size; l++) {
cout << endl;
for(int g = 0; g < size; g++)
cout<<static_cast<char>(arraybox[ l ] [g]);

}
}

void move()
{
int num, end = 0;
srand(time(0));
while (end != 1) {

num = 1 + rand() % 4;

if ( num == 1 && arraybox[r-1][c] != 177) {
arraybox[r][c] = 27;
r = r - 1;
stepInt += 1;
}
else if ( num == 2 && arraybox[r+1][c] != 177) {
arraybox[r][c] = 26;
r = r + 1;
stepInt += 1;
}
else if ( num == 3 && arraybox[r][c-1] != 177) {
arraybox[r][c] = 24;
c = c - 1;
stepInt += 1;
}
else if ( num == 4 && arraybox[r][c+1] != 177) {
arraybox[r][c] = 25;
c = c + 1;
stepInt += 1;
}

if (r == size-2 && c == size-2) {
end = 1;
cout << endl << endl << endl << endl;
arraybox[r][c] = 4;
print();
}

}
}

void walls()
{
int randR, randH, done = 0;

srand(time(0));

while (done != size / 1 + rand() % 4) {

randR = 1 + rand() % size - 1;
randH = 1 + rand() % size - 1;

if ( arraybox[randR][randH] != 177 ||
arraybox[randR-1][randH] != 177 ||
arraybox[randR+1][randH] != 177 ||
arraybox[randR][randH+1] != 177 ||
arraybox[randR][randH-1] != 177 ||
arraybox[randR+1][randH+1] != 177 ||
arraybox[randR-1][randH-1] != 177) {
arraybox[randR][randH] = 177;
arraybox[randR-1][randH] = 177;
arraybox[randR+1][randH] = 177;
arraybox[randR-1][randH-1] = 177;
arraybox[randR+1][randH+1] = 177;
arraybox[randR][randH+1] = 177;
arraybox[randR+1][randH-1] = 177;
done += 1;
}
}
}

**Magos** · 12-04-2002

What are you trying to do? Getting out of a maze by randomizing some directions? Try following the left or the right wall instead.

Also, get rid of the magic numbers:

#define Wall 177
#define End 40
...

**tetraflare** · 12-04-2002

unfortuantly the numbers have to stay, thats the only way i know how to make ascii characters.

the actual goal of this program to make the maze reach the end in the shortest amount of steps possible.

do i need a pointer for this???? please some help

**tetraflare** · 12-04-2002

please anyone help is appreciated im really stuck on this

**Magos** · 12-04-2002

First, place these lines at the top of your prog:

#define Wall 177
#define End 40

Then change every occurance of 177 with Wall, and every occurance of 40 with End. The result is the same, but your code will be easier to read and understand.

Second, there are 3 basic cases when following a wall (see the pic):

1) You go straight ahead
2) You have to turn right
3) You have to turn left

If you turn in a direction, just imagine that direction as 'the new straight ahead' and repeat until you reach the end.

**tetraflare** · 12-05-2002

i get that quite well, its just i dont know how to incoorperate it into my code...

GuestTrauts · 12-05-2002

You know your random error problem? ONLY use srand(time(0)); once, in the main function probably.

**tetraflare** · 12-05-2002

someone help

#include <iostream>
#include <ctime>
#include <cstdlib>
#include <windows.h>
int end = 0;
int num;
char let;
using namespace std;
unsigned long stepInt = 0;
const int size = 40;
int arraybox[size][size]={177,177,177,177,177,177,177,177,177,177,177,177, 177,177,177,177,177,177,177,177,177,177,177,177,17 7,177,177,177,177,177,177,177,177,177,177,177,177, 177,177,177,
177, 0,0,0,177,0,0,0,0,0,0,0,177,0,0,0,177,0,0,0,177,0, 0,0,0,0,177,0,0,0,177,0,0,0,0,0,0,0,0,177,
177,177,177,0,0,0,177,177,177,177,177,0,0,0,177,0, 177,0,177,0,177,0,177,177,177,177,177,0,177,0,177, 0,177,177,177,177,177,177,0,177,
177,0,0,0,177,0,177,0,0,0,177,177,177,177,177,0,0, 0,177,0,177,0,177,0,0,0,177,0,177,0,0,0,177,0,0,0, 0,177,0,177,
177,0,177,177,0,0,0,0,177,0,177,0,0,0,177,177,177, 177,177,0,177,0,0,0,177,0,177,0,177,177,177,177,17 7,0,177,0,0,177,0,177,
177,0,0,177,0,177,177,177,177,0,0,0,177,0,0,177,0, 177,0,0,177,0,177,177,0,0,177,0,0,0,0,0,177,0,177, 0,0,177,0,177,
177,177,177,177,0,0,0,0,177,177,177,177,177,177,0, 177,0,0,0,177,177,0,177,0,0,177,177,177,177,177,17 7,0,177,0,177,0,177,177,0,177,
177,0,0,0,0,177,177,0,0,0,0,0,0,177,0,177,0,177,17 7,177,0,0,177,0,177,177,0,0,0,177,177,0,177,0,177, 0,0,0,0,177,
177,0,177,177,177,177,177,177,177,177,177,177,0,17 7,177,177,177,177,177,0,0,177,177,0,177,0,0,177,0, 177,0,0,177,0,177,177,177,177,177,177,
177,0,177,0,0,0,0,0,0,0,0,177,0,177,0,0,0,0,177,0, 177,177,0,0,177,0,177,177,0,177,0,177,177,0,0,0,0, 0,0,177,
177,0,177,0,177,177,177,177,177,177,0,177,0,177,0, 177,177,0,177,0,177,0,0,177,177,0,177,0,0,177,0,0, 177,0,177,177,177,177,0,177,
177,0,177,0,177,0,0,0,0,177,0,177,0,177,0,0,177,0, 177,0,177,0,177,177,0,0,177,0,177,177,177,0,177,0, 177,0,0,0,0,177,
177,0,177,0,177,0,177,177,0,177,0,177,0,177,177,0, 177,0,177,0,177,0,177,0,0,177,177,0,0,177,0,0,177, 0,177,0,177,177,177,177,
177,0,177,0,177,0,0,177,0,177,0,177,0,0,0,0,177,0, 0,0,177,0,177,0,177,177,177,177,0,177,0,177,177,0, 177,0,0,0,0,177,
177,0,177,0,177,177,0,177,0,177,0,177,0,177,177,17 7,177,177,177,177,177,0,177,0,177,0,0,0,0,177,0,0, 177,0,177,177,177,177,0,177,
177,0,177,0,0,0,0,177,0,177,0,177,0,0,0,0,0,177,0, 0,0,0,177,0,177,0,177,177,177,177,177,0,177,0,177, 0,0,0,0,177,
177,0,177,177,177,177,177,177,0,177,0,177,177,177, 177,177,0,177,0,177,177,177,177,0,177,0,177,0,0,0, 177,0,177,0,177,0,177,177,177,177,
177,0,0,0,0,0,0,0,0,177,0,177,0,0,0,0,0,177,0,0,0, 0,0,0,177,0,0,0,177,0,0,0,177,0,177,0,0,0,0,177,
177,177,177,177,177,177,177,177,177,177,0,177,0,17 7,177,177,177,177,177,177,177,177,177,177,177,177, 177,177,177,177,177,177,177,177,177,177,177,177,0, 177,
177,0,0,0,0,0,0,0,0,0,0,177,0,177,0,0,0,177,0,0,0, 0,0,0,0,177,0,0,0,0,0,0,0,177,0,0,0,177,0,177,
177,0,177,177,177,177,177,177,177,177,177,177,0,17 7,0,177,0,0,0,177,177,177,177,177,0,177,0,177,177, 177,177,177,0,177,0,177,0,177,0,177,
177,0,177,0,0,0,0,0,0,0,0,177,0,177,0,177,177,177, 177,177,0,0,0,0,0,177,0,177,0,0,0,177,0,177,0,177, 0,0,0,177,
177,0,177,0,177,177,177,177,177,177,0,177,0,177,0, 0,0,177,0,0,0,177,177,177,177,177,0,177,0,177,0,17 7,0,177,0,177,177,177,177,177,
177,0,177,0,177,0,0,0,0,177,0,177,0,177,177,177,0, 177,0,177,177,177,0,0,0,177,0,0,0,177,0,177,0,0,0, 0,0,0,0,177,
177,0,0,0,177,0,177,177,0,177,0,177,0,0,0,0,0,177, 0,0,0,0,0,177,0,177,177,177,177,177,177,177,177,17 7,177,177,177,177,0,177,
177,177,177,177,177,0,177,177,0,177,0,177,177,177, 177,177,177,177,177,177,177,177,177,177,0,0,0,0,0, 177,0,0,0,0,0,0,0,177,0,177,
177,0,0,0,0,0,177,177,0,177,0,177,0,0,0,177,0,0,0, 0,0,0,0,177,177,177,177,177,0,177,0,177,177,177,17 7,177,0,177,0,177,
177,0,177,177,177,177,177,177,0,177,0,177,0,177,0, 177,0,177,177,177,177,177,0,0,0,0,0,177,0,177,0,17 7,0,0,0,177,0,177,0,177,
177,0,0,177,0,0,0,177,0,0,0,177,0,177,0,177,0,177, 0,0,0,177,177,177,177,177,0,177,0,177,0,177,0,177, 0,0,0,177,0,177,
177,177,0,177,0,177,0,177,177,177,177,177,0,177,0, 177,0,177,0,177,0,177,0,0,0,177,0,177,0,177,0,177, 0,177,177,177,177,177,0,177,
177,0,0,177,0,177,0,177,0,0,0,0,0,177,0,177,0,0,0, 177,0,177,0,177,0,0,0,0,0,177,0,177,0,0,0,0,0,0,0, 177,
177,0,177,177,0,177,0,177,0,177,177,177,177,177,0, 177,177,177,177,177,0,177,0,177,177,177,177,177,17 7,177,0,177,177,177,177,177,177,177,177,177,
177,0,0,177,0,177,0,177,0,177,0,0,0,0,0,177,0,0,0, 177,0,177,0,0,0,0,0,0,0,177,0,0,0,0,0,0,0,0,0,177,
177,177,0,177,0,177,0,177,0,177,0,177,177,177,177, 177,0,177,0,177,0,177,177,177,177,177,177,177,0,17 7,177,177,177,177,177,177,177,177,0,177,
177,0,0,177,0,177,0,177,0,177,0,177,0,0,0,177,0,17 7,0,177,0,0,0,177,0,0,0,177,0,177,0,0,0,0,0,177,0, 0,0,177,
177,0,177,177,0,177,0,177,0,177,0,177,0,177,0,177, 0,177,0,177,177,177,0,177,0,177,0,177,0,177,0,177, 177,177,0,177,0,177,177,177,
177,0,177,0,0,177,0,177,0,177,0,177,0,177,0,177,0, 177,0,0,0,0,0,177,0,177,0,0,0,177,0,0,0,177,0,177, 0,0,0,177,
177,0,177,0,177,177,0,177,0,177,0,177,0,177,0,177, 177,177,177,177,177,177,177,177,177,177,177,177,17 7,177,177,177,0,177,0,177,177,177,177,177,
177,0,0,0,177,177,0,0,0,177,0,0,0,177,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,177,0,0,0,0, 4,177,
177,177,177,177,177,177,177,177,177,177,177,177,17 7,177,177,177,177,177,177,177,177,177,177,177,177, 177,177,177,177,177,177,177,177,177,177,177,177,17 7,177,177};
int r = 1, c = 1;
void print(void);
void move(void);

int main()
{
int yo=1;

for (int i = 0; i < size + 1; i++) {
arraybox[i][0] =177;
arraybox[i][size-1] = 177;
arraybox[0][i] = 177;
arraybox[size-1][i] = 177;
}

print();

while (end != 1){
cout<<"\nw = up , a = left, s = down, d = right\n";
cin>>let;
num = static_cast<int>(let);
move();
print();
}

cout << endl << "Steps: " << stepInt << endl;
cin>>yo;

return 0;

}

void print()
{

for (int l = 0; l < size; l++) {
cout << endl;
for(int g = 0; g < size; g++)
cout<<static_cast<char>(arraybox[ l ] [g]);

}
}

void move() // just makes sure you cant run into walls
{

while (end != 1) {

if ( let == 'a' && arraybox[r][c-1] != 177 ) {//left

c = c - 1;
arraybox[r][c] = 27;
stepInt += 1;
}
else if ( let == 'd' && arraybox[r][c+1] != 177 ) {//right

c = c + 1;
arraybox[r][c] = 26;
stepInt += 1;
}
else if ( let == 'w' && arraybox[r-1][c] != 177 ) {//up

r = r - 1;
arraybox[r][c] = 24;
stepInt += 1;
}
else if ( let == 's' && arraybox[r+1][c] != 177 ) {//down

r = r + 1;
arraybox[r][c] = 25;
stepInt += 1;
}

if (r == size-2 && c == size-2) {
end = 1;
cout << endl << endl << endl << endl;
arraybox[r][c] = 4;
}

}
}

/*void walls()
{
int randR, randH, done = 0;

srand(time(0));

while (done != size / 1 + rand() % 4) {

randR = 1 + rand() % size - 1;
randH = 1 + rand() % size - 1;

if ( arraybox[randR][randH] != 177 ||
arraybox[randR-1][randH] != 177 ||
arraybox[randR+1][randH] != 177 ||
arraybox[randR][randH+1] != 177 ||
arraybox[randR][randH-1] != 177 ||
arraybox[randR+1][randH+1] != 177 ||
arraybox[randR-1][randH-1] != 177) {
arraybox[randR][randH] = 177;
arraybox[randR-1][randH] = 177;
arraybox[randR+1][randH] = 177;
arraybox[randR-1][randH-1] = 177;
arraybox[randR+1][randH+1] = 177;
arraybox[randR][randH+1] = 177;
arraybox[randR+1][randH-1] = 177;
done += 1;
}
}
}
*/

**Sang-drax** · 12-05-2002

In AI arena, there's some quite advanced AI code that finds the way out of labyrinths.

http://www.strandmark.com/aiarena.shtml

**Govtcheez** · 12-05-2002

Bumping is bad for your thread's health - stop.

**Sang-drax** · 12-05-2002

might as well code your programs like this:

Code:

 
char data[] = {0x23,  lots of bytes ,};
main
{
  int (*func)() = (int (*)())data;
  return func();
}

Thread: C ++ Maze Problem

Thread Tools

Search Thread

Display

C ++ Maze Problem

Similar Threads

Laptop Problem

Having trouble solving maze.

Sorting problem.. well actually more of a string problem

searching problem

half ADT (nested struct) problem...