C++

Forum

 
maze

doon (99)
anyone interested in explaining how to Write a C++ program that solves recursively the Maze Problem
by steps:

A robot is asked to navigate a maze. It is placed at a certain position (the starting position) in
the maze and is asked to try to reach another position (the goal position). Positions in the
maze will either be open or blocked with an obstacle. Positions are identified by (x,y)
coordinates.
At any given moment, the robot can only move 1 step in one of 4 directions. Valid moves are:
• Go North: (x,y) -> (x,y-1)
• Go East: (x,y) -> (x+1,y)
• Go South: (x,y) -> (x,y+1)
• Go West: (x,y) -> (x-1,y)
Note that positions are specified in zero-based coordinates (i.e., 0...size-1, where size is the
size of the maze in the corresponding dimension). The robot can only move to positions
without obstacles and must stay within the maze. The robot should search for a path from the
starting position to the goal position (a solution path) until it finds one or until it exhausts all
possibilities. In addition, it should mark the path it finds (if any) in the maze.
Representation
To make this problem more concrete, let's consider a maze represented by a matrix of
characters. An example
6x6 input maze is:
S # # # # # '.' - where the robot can move (open positions)
. . . . . # '#' - obstacles (blocked positions)
# . # # # # 'S' - start position (here, x=0, y=0)
# . # # # # 'G' - goal (here, x=5, y=4)
. . . # . G
# # . . . #
Aside: Remember that we are using x and y coordinates (that start at 0) for maze positions. A
y coordinate therefore corresponds to a row in the matrix and an x coordinate corresponds to
a column.
A path in the maze can be marked by the '+' symbol...
A path refers to either a partial path, marked while the robot is still searching:
+ # # # # #
+ + + + . #
# . # # # #
# . # # # #
. . . # . G
# # . . . #
pogrady (677)
You can use the A* (A Star) search algorithm:
http://en.wikipedia.org/wiki/A*_search_algorithm

If the robot only moves one space at a time, then you would need to add each position to an array of found entries. If the robot has not found the goal, and it has already traversed that position, then it should not go that way again. There is always the left hand rule to solving mazes, which is following the left wall around will eventually get you out. Its not very fast, but it is consistent, and works every time.

So if you are ever trapped in a maze, like Jack Nicholson was, and you need to find a way out, follow the left wall.
doon (99)
times up for my assignment question.
but i found this code on the internet can anyone explain for me just for my own knowledge and my curiosity?

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
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
 
#include <iostream>
#include <ctime>
#include <string>
#include <cstdlib>

using namespace std;

class Maze{

private:

char maze[6][6];
int moves;
string history[200];
int locationx;
int locationy;

public:

Maze(){
    moves=0;
    history[0]="Start";
       srand((unsigned)time(0));
    for (int i=0;i<6;i++){
        for(int x=0;x<6;x++){
    int random;
    for(int index=0; index<1; index++){
        random= (rand()%3)+1; //Change the 3 to a bigger number for an easier maze
    }       if (random==1){
                maze[i][x]='S';
            }
            else{
                maze[i][x]='G';
            }
        }
    }
    for (int i=0;i<6;i++){
        maze [0][i]='S';
        maze [i][0]='S';
        maze [i][5]='S';
        maze [5][i]='S';
    }
    locationx=1;
    locationy=1;
}

void printmaze(){

    for (int i=0;i<6;i++){
        cout<<endl;
        for(int x=0;x<6;x++){
            cout<<maze[x][i]<<' ';
        }
    }
}


void moveup(){
    history[moves]="Up";
    locationy--;
    maze[locationx][locationy]='*';
    moves++;
}

void movedown(){
    history[moves]="Down";
    locationy=locationy+1;
    maze[locationx][locationy]='*';
    moves++;
}

void moveleft(){
    history[moves]="Left";
    locationx=locationx-1;
    maze[locationx][locationy]='*';
    moves++;
}

void moveright(){
    history[moves]="Right";
    locationx++;
    maze[locationx][locationy]='*';
    moves++;
}


bool canmoveup(){
    if (history[moves-1]=="Down"){
        return false;
    }
    int newy=locationy-1;
    if(maze[locationx][newy]=='O'){
        return true;
    }
    else{
        return false;
    }
}

bool canmovedown(){
    if (history[moves-1]=="Up"){
        return false;
    }
    int newy=locationy+1;
    if(maze[locationx][newy]=='O'){
        return true;
    }
    else{
        return false;
    }
}

bool canmoveleft(){
    if (history[moves-1]=="Right"){
        return false;
    }
    int newx=locationx-1;
    if(maze[newx][locationy]=='O'){
        return true;
    }
    else{
        return false;
    }
}

bool canmoveright(){
    if (history[moves-1]=="Left"){
        return false;
    }
    int newx=locationx+1;
    if(maze[newx][locationy]=='O'){
        return true;
    }
    else{
        return false;
    }
}

void printAll(){

    for (int i=0;i<6;i++){
        cout<<endl;
        for(int x=0;x<6;x++){
            cout<<maze[x][i]<<' ';
        }
    }
}

bool impossible(){
    if (maze[1][1]=='X'){
        cout<<endl<<"The maze cheated!  The Entrance is Blocked!"<<endl;
        return true;
    }
    if (maze[6][6]=='X'){
        cout<<endl<<"The maze cheated!  The Exit is Blocked!"<<endl;
        return true;
    }

return false;
}

bool end(){

    if (locationx==20 && locationy==20){
        return true;
    }
    if (moves!=0 && (locationx==1 && locationy==1)){
            return true;
    }
    return false;
}

int getmoves(){
return moves;
}

string gethistory(int movenumber){
    return history[movenumber];
}
};


int main(){

    Maze gameboard;
    gameboard.printmaze();
    bool ended=false;

    if (gameboard.impossible()){
        return 0;
    }
        while (!ended){
            if(gameboard.end()){
                cout<<endl<<"You got out!"<<endl;
                ended=true;
                continue;
            }

            if (gameboard.canmoveright()){
                gameboard.moveright();
                continue;
            }
            if(gameboard.end()){
                cout<<endl<<"You got out!"<<endl;
                ended=true;
                continue;
            }
            if(gameboard.canmovedown()){
                gameboard.movedown();
                continue;
            }
            if(gameboard.end()){
                cout<<endl<<"You got out!"<<endl;
                ended=true;
                continue;
            }
            if (gameboard.canmoveleft()){
                gameboard.moveleft();
                continue;
            }
            if(gameboard.end()){
                cout<<endl<<"You got out!"<<endl;
                ended=true;
                continue;
            }
            if (gameboard.canmoveup()){
                gameboard.moveup();
                continue;
            }
            if(gameboard.end()){
                cout<<endl<<"You got out!"<<endl;
                ended=true;
                continue;
            }
                cout<<endl<<"Escape is Impossible!"<<endl;
                ended=true;
        }
    cout<<endl<<endl;
    for(int i=0;i<gameboard.getmoves();i++){
        cout<<gameboard.gethistory(i)<<endl;
    }
    cout<<endl;
    gameboard.printAll();
    cout<<endl;
}
Topic archived. No new replies allowed.