C++

Forum

 
Am i implementing this maze program correctly?

kingkush (282)
I am attempting to write a program which will solve how to get out of an array maze. Im not sure if I am implementing it properly.It compiles fine but im not sure how to check if the "playerMarker" has gone through a certain path already to avoid an infinite loop.


Edit:
Also do i have to subtract or add one to the pair that is being worked on when it hits a wall? I think right now it storing the location of the wall.

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
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
 
  #include <stack>
#include <iostream>

using namespace std;

int main()
{
const char *playerMarker = "S"; //What player is marked as on board
const char *wallMarker = "X"; //What the walls are marked as on board
const char *endMarker = "E"; //What the end is marked as on the board
    
//stack for player moves
std::stack<std::pair <int, int> > playerLocationMoves;
    
// pair and stack for player location
std::pair <int, int> pos;
std::stack<std::pair <int, int> > playerLocation;
    
//pair and stack for end location
std::pair <int, int> endPos;
std::stack<std::pair <int, int> > EndLocation;
    
    
const int SIZE = (15 * 15);
    
//Variables to hold pair numbers
int pair1;
int pair2;
    
//Row * Coloumn
char arrMaze [SIZE][SIZE] =
{
        //   0    1    2    3    4    5   6    7    8   9    0    1   2    3    4
    /*0*/ {'X', 'X', 'X', 'X', 'X', 'X','X', 'X', 'X','X', 'X', 'X','X', 'X', 'X'},
    /*1*/ {'X', 'S', 'X', 'X', 'X', 'X','X', 'X', 'X',' ', 'X', 'X','X', 'X', 'X'},
    /*2*/ {'X', ' ', ' ', ' ', ' ', 'X','X', 'X', 'X',' ', 'X', ' ','X', 'X', 'X'},
    /*3*/ {'X', 'X', ' ', 'X', 'X', 'X','X', 'X', 'X',' ', 'X', ' ','X', 'X', 'X'},
    /*4*/ {'X', ' ', ' ', 'X', 'X', 'X','X', 'X', ' ',' ', ' ', ' ','X', 'X', 'X'},
    /*5*/ {'X', ' ', 'X', 'X', 'X', 'X','X', ' ', ' ','X', 'X', 'X','X', 'X', 'X'},
    /*6*/ {'X', ' ', 'X', ' ', 'X', 'X','X', ' ', ' ',' ', 'X', 'X','X', 'X', 'X'},
    /*7*/ {'X', ' ', 'X', ' ', 'X', 'X','X', ' ', 'X',' ', 'X', 'X','X', 'X', 'X'},
    /*8*/ {'X', ' ', ' ', ' ', 'X', 'X','X', ' ', 'X',' ', 'X', ' ',' ', ' ', 'X'},
    /*9*/ {'X', 'X', ' ', ' ', 'X', 'X','X', ' ', 'X',' ', 'X', ' ','X', ' ', 'X'},
    /*0*/ {'X', 'X', ' ', ' ', ' ', ' ',' ', ' ', 'X',' ', 'X', ' ','X', ' ', 'X'},
    /*1*/ {'X', 'X', ' ', 'X', 'X', 'X','X', 'X', 'X',' ', 'X', ' ','X', ' ', 'X'},
    /*2*/ {'X', 'X', ' ', 'X', 'X', 'X','X', 'X', 'X',' ', ' ', ' ','X', ' ', 'X'},
    /*3*/ {'X', 'X', ' ', 'X', 'X', 'X','X', 'X', 'X','X', 'X', ' ','X', 'E', 'X'},
    /*4*/ {'X', 'X', 'X', 'X', 'X', 'X','X', 'X', 'X','X', 'X', 'X','X', 'X', 'X'}};
    
    for(int i = 0; i < SIZE; i++)
    {
        for(int j = 0; j < SIZE; j++)
        {
            if (arrMaze[i][j] == *playerMarker)
            {
                pos.first = i;
                pos.second = j;
            }
            if (arrMaze[i][j] == *endMarker)
            {
                endPos.first = i;
                endPos.second = j;
            }
            else
            {
                i++;
                j++;
            }
        }
    }
    
    //Place end location into stack
    EndLocation.push(endPos);
    
    
    //Place player location into stack
    playerLocation.push(pos);
    
    //Check to see if N, W, S, E are open
    pair1 = pos.first;
    pair2 = pos.second;
    
    while(playerLocation != EndLocation)
    {
        
        //Check North (- coloumn from Location)
        if(arrMaze[pair1][pair2 - 1] != *wallMarker)
        {
            //If last stack element = current move its already been done
            if (playerLocation.top() != playerLocationMoves.top())
            {
                do
                {
                    arrMaze[pair1][pair2--];
                    if (arrMaze[pair1][pair2] == *wallMarker)
                    {
                        pair1 = pos.first;
                        pair2 = pos.second;
                        playerLocation.push(pos);
                        playerLocationMoves.push(pos);
                    }
                }
                while(arrMaze[pair1][pair2] != *wallMarker);
            }
        }
        
        //Check West (- Row from Location)
        if(arrMaze[pair1 - 1][pair2] != *wallMarker)
        {
            do
            {
                arrMaze[pair1--][pair2];
                if (arrMaze[pair1][pair2] == *wallMarker)
                {
                    pair1 = pos.first;
                    pair2 = pos.second;
                    playerLocation.push(pos);
                    playerLocationMoves.push(pos);
                }
            }
            while(arrMaze[pair1][pair2] != *wallMarker);
        }
        
        //Check South (+ Coloumn from Location)
        if(arrMaze[pair1][pair2 + 1] != *wallMarker)
        {
            do
            {
                arrMaze[pair1][pair2++];
                if (arrMaze[pair1][pair2] == *wallMarker)
                {
                    pair1 = pos.first;
                    pair2 = pos.second;
                    playerLocation.push(pos);
                    playerLocationMoves.push(pos);
                }
            }
            while(arrMaze[pair1][pair2] != *wallMarker);
        }
        
        //Check East (+ Row from Location)
        if(arrMaze[pair1 + 1][pair2] != *wallMarker)
        {
            do
            {
                arrMaze[pair1++][pair2];
                if (arrMaze[pair1][pair2] == *wallMarker)
                {
                    pair1 = pos.first;
                    pair2 = pos.second;
                    playerLocation.push(pos);
                    playerLocationMoves.push(pos);
                }
            }
            while(arrMaze[pair1][pair2] != *wallMarker);
        }
    }
        
    
    
    
    return 0;
}
Last edited on
xismn (961)
Instead of an array of characters to represent your maze, you could have an array of Field objects. For example:

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
 
int main() {

	class Field {
	public :
		Field(char _symbol = ' ') : symbol(_symbol), already_visited(false) {}

		char symbol;
		bool already_visited;

	};

	const int maze_width = 5;
	const int maze_height = 5;
	Field fields[maze_width][maze_height] = {
		'#', '#', '#', '#', '#',
		'#', ' ', ' ', ' ', '#',
		'#', ' ', ' ', ' ', '#',
		'#', ' ', ' ', ' ', '#',
		'#', '#', '#', '#', '#',
	};

	int x = 1;
	int y = 1;

	fields[x][y].already_visited = true;

	return 0;
}


This would allow you to check whether a field has already been visited.
Last edited on
kingkush (282)
The maze was given to me by my teacher so i think he wants to keep it a char array.
However will it operate exactly the same as a char array?

On line 89 & 90 is where im trying to see if the move has already been made but I think that is the incorrect implementation.

Thanks for your advice!
cire (8284)
The maze was given to me by my teacher so i think he wants to keep it a char array.

An alternative would be to use a parallel array to track the "visited" state of a position.
closed account (48T7M4Gy)
It also depends what is meant by 'path'. If two paths crossover and if that is acceptable then a pre-visited space is not sufficient. Maybe a path is a couple of consecutive locations but even that can be insufficient depending on the rules and configuration of the maze. Both are complex problems to solve thoroughly unless you are experienced or interested in the standard text "Algorithms" by Sedgewick et al or his online courses and materials.

Separately, a single (2D) array can have multiple attributes - vacant, visited, boundary etc - as the value of each cell.
kingkush (282)
I was thinking i could use the stack for this. If i hit a dead end i go back to my last coordinate pair and try a different way. I can then "pop" the last coordinate pair into an array and check to see if its tried any dead ends. If that makes sense.
cire (8284)
I was thinking i could use the stack for this.

A stack is a last-in, last-out data structure which typically doesn't allow inspection of the non-top elements which means it isn't a good candidate for searching through all elements to ensure you aren't visiting a position already visited in the current path.

You would use the stack to make sure you're not generating the same path twice, not for making sure you don't cross the same position twice in a single path.
kingkush (282)
I would copy the contents of the stack into an array which i can search or is that not possible?
cire (8284)
It is certainly possible to roll your own stack that you can search. However, it won't be as efficient or intuitive as a parallel array.
kingkush (282)
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
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
 
#include <stack>
#include <iostream>
#include <vector>

using namespace std;

int main()
{
const char *playerMarker = "S"; //What player is marked as on board
const char *wallMarker = "X"; //What the walls are marked as on board
const char *endMarker = "E"; //What the end is marked as on the board
    
//Vector for player moves
vector<pair<int, int>> playerMovesVect;
    
// pair and stack for player location
std::pair <int, int> pos;
std::stack<std::pair <int, int> > playerLocation;
    
//pair and stack for end location
std::pair <int, int> endPos;
std::stack<std::pair <int, int> > EndLocation;
    
    
const int SIZE = (15 * 15);
    
//Variables to hold pair numbers
int pair1;
int pair2;
    
//Row * Coloumn
char arrMaze [SIZE][SIZE] =
{
        //   0    1    2    3    4    5   6    7    8   9    0    1   2    3    4
    /*0*/ {'X', 'X', 'X', 'X', 'X', 'X','X', 'X', 'X','X', 'X', 'X','X', 'X', 'X'},
    /*1*/ {'X', 'S', 'X', 'X', 'X', 'X','X', 'X', 'X',' ', 'X', 'X','X', 'X', 'X'},
    /*2*/ {'X', ' ', ' ', ' ', ' ', 'X','X', 'X', 'X',' ', 'X', ' ','X', 'X', 'X'},
    /*3*/ {'X', 'X', ' ', 'X', 'X', 'X','X', 'X', 'X',' ', 'X', ' ','X', 'X', 'X'},
    /*4*/ {'X', ' ', ' ', 'X', 'X', 'X','X', 'X', ' ',' ', ' ', ' ','X', 'X', 'X'},
    /*5*/ {'X', ' ', 'X', 'X', 'X', 'X','X', ' ', ' ','X', 'X', 'X','X', 'X', 'X'},
    /*6*/ {'X', ' ', 'X', ' ', 'X', 'X','X', ' ', ' ',' ', 'X', 'X','X', 'X', 'X'},
    /*7*/ {'X', ' ', 'X', ' ', 'X', 'X','X', ' ', 'X',' ', 'X', 'X','X', 'X', 'X'},
    /*8*/ {'X', ' ', ' ', ' ', 'X', 'X','X', ' ', 'X',' ', 'X', ' ',' ', ' ', 'X'},
    /*9*/ {'X', 'X', ' ', ' ', 'X', 'X','X', ' ', 'X',' ', 'X', ' ','X', ' ', 'X'},
    /*0*/ {'X', 'X', ' ', ' ', ' ', ' ',' ', ' ', 'X',' ', 'X', ' ','X', ' ', 'X'},
    /*1*/ {'X', 'X', ' ', 'X', 'X', 'X','X', 'X', 'X',' ', 'X', ' ','X', ' ', 'X'},
    /*2*/ {'X', 'X', ' ', 'X', 'X', 'X','X', 'X', 'X',' ', ' ', ' ','X', ' ', 'X'},
    /*3*/ {'X', 'X', ' ', 'X', 'X', 'X','X', 'X', 'X','X', 'X', ' ','X', 'E', 'X'},
    /*4*/ {'X', 'X', 'X', 'X', 'X', 'X','X', 'X', 'X','X', 'X', 'X','X', 'X', 'X'}};
    
    for(int i = 0; i < SIZE; i++)
    {
        for(int j = 0; j < SIZE; j++)
        {
            if (arrMaze[i][j] == *playerMarker)
            {
                pos.first = i;
                pos.second = j;
            }
            if (arrMaze[i][j] == *endMarker)
            {
                endPos.first = i;
                endPos.second = j;
            }
            else
            {
                i++;
                j++;
            }
        }
    }
    
    //Place end location into stack
    //EndLocation.push(endPos);
    
    
    //Place player location into stack
    //playerLocation.push(pos);
    
    //Check to see if N, W, S, E are open
    pair1 = pos.first;
    pair2 = pos.second;
    
    while(playerLocation != EndLocation)
    {
        //Check North (- [up] coloumn from Location)
        if(arrMaze[pair1][pair2 - 1] != *wallMarker)
        {
            //Check to see if move has been made
            for(int i = 0; i < playerMovesVect.size(); i++)
            {
                if (playerLocation.top() == playerMovesVect[i])
                {
                    //Remove Direction from stack
                    playerLocation.pop();
                    //Make last pair in stack variable
                    std::pair <int, int> currentLocation = playerLocation.top();
                    //Make last stack move current location again
                    arrMaze[currentLocation.first][currentLocation.second];
                    break;
                }
            }
        
            do
            {
                arrMaze[pair1][pair2--];
                if (arrMaze[pair1][pair2] == *wallMarker)
                {
                    pair1 = pos.first;
                    pair2 = pos.second;
                    playerLocation.push(pos);
                    playerMovesVect.push_back(pos);
                    arrMaze[pair1][pair2] = *playerMarker;
                }
            }
            while(arrMaze[pair1][pair2] != *wallMarker);
    
        }
        //Check West (- [left] Row from Location)
        if(arrMaze[pair1 - 1][pair2] != *wallMarker)
        {
            for(int i = 0; i < playerMovesVect.size(); i++)
            {
                if (playerLocation.top() == playerMovesVect[i])
                {
                    //Remove Direction from stack
                    playerLocation.pop();
                    //Make last pair in stack variable
                    std::pair <int, int> currentLocation = playerLocation.top();
                    //Make last stack move current location again
                    arrMaze[currentLocation.first][currentLocation.second];
                    break;
                }
            }
            do
            {
                arrMaze[pair1--][pair2];
                if (arrMaze[pair1][pair2] == *wallMarker)
                {
                    pair1 = pos.first;
                    pair2 = pos.second;
                    playerLocation.push(pos);
                    playerMovesVect.push_back(pos);
                    arrMaze[pair1][pair2] = *playerMarker;
                }
            }
            while(arrMaze[pair1][pair2] != *wallMarker);
        }
        
        //Check South (+ Coloumn [down] from Location)
        if(arrMaze[pair1][pair2 + 1] != *wallMarker)
        {
            for(int i = 0; i < playerMovesVect.size(); i++)
            {
                if (playerLocation.top() == playerMovesVect[i])
                {
                    //Remove Direction from stack
                    playerLocation.pop();
                    //Make last pair in stack variable
                    std::pair <int, int> currentLocation = playerLocation.top();
                    //Make last stack move current location again
                    arrMaze[currentLocation.first][currentLocation.second];
                    break;
                }
            }
            do
            {
                arrMaze[pair1][pair2++];
                if (arrMaze[pair1][pair2] == *wallMarker)
                {
                    pair1 = pos.first;
                    pair2 = pos.second;
                    playerLocation.push(pos);
                    playerMovesVect.push_back(pos);
                    arrMaze[pair1][pair2] = *playerMarker;
                }
            }
            while(arrMaze[pair1][pair2] != *wallMarker);
        }
        
        //Check East (+ [right] Row from Location)
        if(arrMaze[pair1 + 1][pair2] != *wallMarker)
        {
            for(int i = 0; i < playerMovesVect.size(); i++)
            {
                if (playerLocation.top() == playerMovesVect[i])
                {
                    //Remove Direction from stack
                    playerLocation.pop();
                    //Make last pair in stack variable
                    std::pair <int, int> currentLocation = playerLocation.top();
                    //Make last stack move current location again
                    arrMaze[currentLocation.first][currentLocation.second];
                    break;
                }
            }
            do
            {
                arrMaze[pair1++][pair2];
                if (arrMaze[pair1][pair2] == *wallMarker)
                {
                    pair1 = pos.first;
                    pair2 = pos.second;
                    playerLocation.push(pos);
                    playerMovesVect.push_back(pos);
                    arrMaze[pair1][pair2] = *playerMarker;
                }
            }
            while(arrMaze[pair1][pair2] != *wallMarker);
        }
    }
    
    //Print board
    for(int i=0; i<15; i++)    //This loops on the rows.
    {
        for(int j=0; j<15; j++) //This loops on the columns
        {
            cout << arrMaze[i][j]  << "  ";
        }
        cout << endl;
    }
        
    
    
    
    return 0;
}
kingkush (282)
The program will only be running through the maze provided and one with no exit so the solution doesn't need to cover every possible outcome. I also implemented the check using an vector of pairs and comparing it the the top of the stack on lines 96-107. Does that work?

And also my program compiles but it does not change the playerMarker and i cant figure out why.
Last edited on
kingkush (282)
So I think it has something to do with my while loop. 

1
2
3
4
5
 
std::pair <int, int> PC = playerLocation.top();
    std::pair <int, int> EL = EndLocation.top();
    
    std::cout<< PC.first << ", " << PC.second <<endl;
    std::cout<< EL.first << ", " << EL.second <<endl;


Both number set came as 0,0 so the while statement was immediately true and never executed my question is why?

Here is my code for finding the playerLocation and endLocation
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
 
const char *playerMarker = "S"; //What player is marked as on board
const char *wallMarker = "X"; //What the walls are marked as on board
const char *endMarker = "E"; //What the end is marked as on the board
    
//Vector for player moves
vector<pair<int, int>> playerMovesVect;
    
// pair and stack for player location
std::pair <int, int> pos;
std::stack<std::pair <int, int> > playerLocation;
    
//pair and stack for end location
std::pair <int, int> endPos;
std::stack<std::pair <int, int> > EndLocation;
    
    
const int SIZE = (15 * 15);
    
//Variables to hold pair numbers
int pair1;
int pair2;
    
//Row * Coloumn
char arrMaze [SIZE][SIZE] =
{
        //   0    1    2    3    4    5   6    7    8   9    0    1   2    3    4
    /*0*/ {'X', 'X', 'X', 'X', 'X', 'X','X', 'X', 'X','X', 'X', 'X','X', 'X', 'X'},
    /*1*/ {'X', 'S', 'X', 'X', 'X', 'X','X', 'X', 'X',' ', 'X', 'X','X', 'X', 'X'},
    /*2*/ {'X', ' ', ' ', ' ', ' ', 'X','X', 'X', 'X',' ', 'X', ' ','X', 'X', 'X'},
    /*3*/ {'X', 'X', ' ', 'X', 'X', 'X','X', 'X', 'X',' ', 'X', ' ','X', 'X', 'X'},
    /*4*/ {'X', ' ', ' ', 'X', 'X', 'X','X', 'X', ' ',' ', ' ', ' ','X', 'X', 'X'},
    /*5*/ {'X', ' ', 'X', 'X', 'X', 'X','X', ' ', ' ','X', 'X', 'X','X', 'X', 'X'},
    /*6*/ {'X', ' ', 'X', ' ', 'X', 'X','X', ' ', ' ',' ', 'X', 'X','X', 'X', 'X'},
    /*7*/ {'X', ' ', 'X', ' ', 'X', 'X','X', ' ', 'X',' ', 'X', 'X','X', 'X', 'X'},
    /*8*/ {'X', ' ', ' ', ' ', 'X', 'X','X', ' ', 'X',' ', 'X', ' ',' ', ' ', 'X'},
    /*9*/ {'X', 'X', ' ', ' ', 'X', 'X','X', ' ', 'X',' ', 'X', ' ','X', ' ', 'X'},
    /*0*/ {'X', 'X', ' ', ' ', ' ', ' ',' ', ' ', 'X',' ', 'X', ' ','X', ' ', 'X'},
    /*1*/ {'X', 'X', ' ', 'X', 'X', 'X','X', 'X', 'X',' ', 'X', ' ','X', ' ', 'X'},
    /*2*/ {'X', 'X', ' ', 'X', 'X', 'X','X', 'X', 'X',' ', ' ', ' ','X', ' ', 'X'},
    /*3*/ {'X', 'X', ' ', 'X', 'X', 'X','X', 'X', 'X','X', 'X', ' ','X', 'E', 'X'},
    /*4*/ {'X', 'X', 'X', 'X', 'X', 'X','X', 'X', 'X','X', 'X', 'X','X', 'X', 'X'}};
    
    for(int i = 0; i < SIZE; i++)
    {
        for(int j = 0; j < SIZE; j++)
        {
            //Find the playerMarker
            if (arrMaze[i][j] == *playerMarker)
            {
                pos.first = i;
                pos.second = j;
            }
            //find exitMarker
            else if (arrMaze[i][j] == *endMarker)
            {
                endPos.first = i;
                endPos.second = j;
            }
            else
            {
                i++;
                j++;
            }
        }
    }
    
    //Place end location into stack
    EndLocation.push(endPos);
    
    //Place player location into stack
    playerLocation.push(pos);
SakurasouBusters (732)
You have to develop an algorithm to help the player (S) find the exit (E). Is it correct?
closed account (48T7M4Gy)
Possibly more out of interest than anything else. But it does show how to analyse and stack the data very efficiently.

http://algs4.cs.princeton.edu/lectures/15UnionFind-2x2.pdf
Topic archived. No new replies allowed.