C++

Forum

 
I'm stuck

imafailure (27)
p
Last edited on
jonnin (11331)
without trying to unravel what you did ...

the basic maze algorithm is this: try to move west. if can't, try to move north. if can't, try to move east. If can't try to move south. You have to tie this to a back-tracking concept that prevents going west down a dead end hallway, then going east once, then going west again, then east again, forever. It has to know where it has been and which direction it is on at every location, in other words. An easy way to do that is to have a second copy of the maze map and each location has something like X (never visited) or W/N/E/S as the last direction attempted from that spot. You also need to detect if there is no solution. Another way to do the same thing is recursion, where the call stack tracks where you have been and what you did last at that position, if you are comfortable with recursion.

trying to solve it by moving randomly has a very low probability of success unless you are very, very patient.

how to move the robot? the robot should have an x/y position, you just update that as you move.
Last edited on
imafailure (27)
p
Last edited on
jonnin (11331)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
ok. 

to move the robot...

struct botloc  //a custom type holding the robot position (this goes above main). 
{
   int x;
   int y;
};

botloc robotlocation; //create a variable of your custom type
robotlocation.x = 3;
robotlocation.y = 5; //some arbitrary starting position. 

... //unimportant code 
maze[robotlocation.x][robotlocation.y] = robot; //initialize to above
...
//actually move the thing
maze[robotlocation.x][robotlocation.y] = space; //remove old location marker
robotlocation.x++; //move one slot in the x dimension, for an example. you can modify x and y as needed here.  
//just update its position somehow...
maze[robotlocation.x][robotlocation.y] = robot; //set new position in your maze

the above lines could be put into a function "move_robot" if you wanted to do that.  
Or in a loop, applying the search logic.




Last edited on
imafailure (27)
p
Last edited on
whitenite1 (1785)
@imafailure

I made a few small changes to your code. It will now move the robot around the maze, and exit.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
 
#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;
const int SIZE=10;

enum value {space, wall, ext, robot};
bool valid = false;
int maze [SIZE][SIZE];

struct loc{
	int x;
	int y;
};

loc roblo;
void createmaze();
void showmaze();
bool robmov();

int main ()
{
	createmaze();
	bool out = false;
	do
	{
		showmaze();
		out = robmov();
	}while(!out);
	cout << "Exiting the maze.." << endl;
	return 0;
}

void createmaze(){
	roblo.x = 0;
	roblo.y = 2;
	for (int i=0; i<SIZE; i++)
	{
		for (int j=0; j<SIZE; j++) 
		{
			maze[i][j] = wall;
		}
	}
	//line 1
	maze[0][2]=space;
	//line2
	maze[1][2]=space;
	maze[1][3]=space;
	maze[1][4]=space;
	//line3
	maze[2][3]=space;
	maze[2][4]=space;
	maze[2][5]=space;
	//line4
	maze[3][3]=space;
	maze[3][5]=space;
	//line5
	maze[4][2]=space;
	maze[4][3]=space;
	maze[4][5]=space;
	maze[4][1]=space;
	//line6
	maze[5][2]=space;
	maze[5][5]=space;
	maze[5][8]=space;
	//line7
	maze[6][2]=space;
	maze[6][5]=space;
	maze[6][6]=space;
	maze[6][7]=space;
	maze[6][8]=space;
	//line8
	maze[7][2]=space;
	//line9
	maze[8][2]=space;
	maze[8][3]=space;
	maze[8][4]=space;
	maze[8][5]=space;
	maze[8][6]=space;
	maze[8][7]=space;
	maze[8][8]=space;
	//line10
	maze[9][8]=space;
	//exits
	maze[9][9]=ext;
	maze[5][9]=ext;

	maze[roblo.x][roblo.y] = robot;
}

void showmaze(){

	for (int i=0; i<SIZE; i++)
	{
		for (int j=0; j<SIZE; j++)
		{
			if (maze[i][j] == wall)
			{
				cout << "+";
			}
			if (maze[i][j] == space || maze[i][j] == 5)
			{
				cout << " ";
			}
			if (maze[i][j] == ext)
			{
				cout << "}";
			}
			if (maze[i][j]==robot)
			{
				cout << "*";
			}
		}
		cout << endl;
	}
	cout << endl << endl;
}

bool robmov()
{
	if(maze[roblo.x+1][roblo.y] == ext || maze[roblo.x][roblo.y+1] == ext)
		return true;
	maze[roblo.x][roblo.y] = 5;
	
	if(maze[roblo.x+1][roblo.y] == space && roblo.x+1 < SIZE)
		roblo.x++;
	else if(maze[roblo.x][roblo.y+1] == space && roblo.y+1 < SIZE)
		roblo.y++;
	else if(maze[roblo.x-1][roblo.y] == space && roblo.x-1 >=0 )
		roblo.x--;
	else if(maze[roblo.x][roblo.y-1] == space && roblo.y-1 >=0)
		roblo.y--;
	maze[roblo.x][roblo.y] = robot;
}


And this robmov() function, will find the other exit in the maze
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
bool robmov()
{
	if(maze[roblo.x+1][roblo.y] == ext || maze[roblo.x][roblo.y+1] == ext)
		return true;
	maze[roblo.x][roblo.y] = 5;
	
	if(maze[roblo.x][roblo.y+1] == space && roblo.y+1 < SIZE)
		roblo.y++;
	else if(maze[roblo.x+1][roblo.y] == space && roblo.x+1 < SIZE)
		roblo.x++;
	else if(maze[roblo.x-1][roblo.y] == space && roblo.x-1 >=0 )
		roblo.x--;
	else if(maze[roblo.x][roblo.y-1] == space && roblo.y-1 >=0)
		roblo.y--;
	maze[roblo.x][roblo.y] = robot;
}
Last edited on
imafailure (27)
p
Last edited on
imafailure (27)
Where you put
if (maze[i][j] == space || maze[i][j] == 5)
{
cout << " ";
}
and
maze[roblo.x][roblo.y] = 5;
how does this work? I tried tweaking around with it and it has to be there and only be 5 but I can't figure out why
whitenite1 (1785)
@imafailure

I put a 5 at the robot location to signify where the robot had been. The loop is to check if the maze location is a space or a previous robot location, then print a " " on the screen at either find.
imafailure (27)
p
Last edited on
imafailure (27)
p
Last edited on
whitenite1 (1785)
@imafailure

This maze works and it's using your maze create positions.
I blocked at position 3,5 and it still found exit. Try it

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
 
#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

const int SIZE = 10;

enum value {space, wall, ext, robot};

// Easier way to visualize maze, and to make changes, quicker
int maze[SIZE][SIZE] =
{
	{1,1,3,1,1,1,1,1,1,1},
	{1,1,0,0,0,1,1,1,1,1},
	{1,1,1,0,0,0,1,1,1,1},
	{1,1,1,0,1,0,1,1,1,1},
	{1,0,0,0,1,0,1,1,1,1},
	{1,1,0,1,1,0,1,1,0,2},
	{1,1,0,1,1,0,0,0,0,1},
	{1,1,0,1,1,1,1,1,1,1},
	{1,1,0,0,0,0,0,0,0,1},
	{1,1,1,1,1,1,1,1,0,2}
};

struct loc
{
	int x;
	int y;
};

loc roblo;

void createmaze();
void showmaze();
bool robmov();

int main ()
{
	srand((unsigned)time(0));
	// Robot starting position
	roblo.x = 0;
	roblo.y = 2;

	bool out = false;
	do
	{
		out = robmov();
		showmaze();
	}while(!out);
	cout << "Exiting the maze.." << endl;
	return 0;
}

void showmaze(){

	for (int i=0; i<SIZE; i++)
	{
		for (int j=0; j<SIZE; j++)
		{
			if (maze[i][j] == wall)
			{
				cout << "+";
			}
			if (maze[i][j] == space || maze[i][j] == 5)
			{
				cout << " ";
			}
			if (maze[i][j] == ext)
			{
				cout << "}";
			}
			if (maze[i][j]==robot)
			{
				cout << "*";
			}
		}
		cout << endl;
	}
	cout << endl << endl;
}

bool robmov()
{
	int move = rand()%50; // To take a different route, sometimes
	int ok = 0;
	if(maze[roblo.x+1][roblo.y] == ext || maze[roblo.x][roblo.y+1] == ext)
	{
		maze[roblo.x][roblo.y] = 5;
		if(maze[roblo.x+1][roblo.y] == ext)
			maze[roblo.x+1][roblo.y] = robot;
		else if(maze[roblo.x][roblo.y+1] == ext)
			maze[roblo.x][roblo.y+1] = robot;
		return true;
	}

	if(maze[roblo.x][roblo.y+1] == space && roblo.y+1 < SIZE && move < 25)
	{
		maze[roblo.x][roblo.y] = 5;
		roblo.y++;
		ok =  1;
	}
	else if(maze[roblo.x+1][roblo.y] == space && roblo.x+1 < SIZE)
	{
		maze[roblo.x][roblo.y] = 5;
		roblo.x++;
		ok =  1;
	}
	else if(maze[roblo.x-1][roblo.y] == space && roblo.x-1 >=0 )
	{
		maze[roblo.x][roblo.y] = 5;
		roblo.x--;
		ok =  1;
	}
	else if(maze[roblo.x][roblo.y-1] == space && roblo.y-1 >=0)
	{
		maze[roblo.x][roblo.y] = 5;
		roblo.y--;
		ok =  1;
	}
	if(!ok)
	{

		if(maze[roblo.x+1][roblo.y] == 5  && roblo.x+1 < SIZE)
		{
			maze[roblo.x+1][roblo.y] = space;
		}
		else if(maze[roblo.x][roblo.y+1] == 5 && roblo.y+1 < SIZE)
		{
			maze[roblo.x][roblo.y+1] = space;
		}
		else if(maze[roblo.x-1][roblo.y] == 5 && roblo.x-1 >= 0)
		{
			maze[roblo.x-1][roblo.y] = space;
		}
		if(maze[roblo.x][roblo.y-1] == 5 && roblo.y-1 >= 0)
		{
			maze[roblo.x][roblo.y-1] = space;
		}
	}
	maze[roblo.x][roblo.y] = robot;
	return false;
}
Last edited on
imafailure (27)
p
Last edited on
imafailure (27)
p
Last edited on
Topic archived. No new replies allowed.