-
Notifications
You must be signed in to change notification settings - Fork 0
/
MazeSolver-2 (1).java
202 lines (151 loc) · 5.51 KB
/
MazeSolver-2 (1).java
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
//Samit Basnet
//algorithm to solve the maze
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Stack;
import java.util.ArrayList;
class MazeSolver
{
//Stack<GridLocation> moves=new Stack<GridLocation>();
GridLocation current;
//agenda to add the adjacent location
Agenda moves;
//arraylist to keep track to visited positions
ArrayList<GridLocation> visited=new ArrayList<GridLocation>();
//arraylist to keep track of added position and what it was added by
ArrayList<GridLocation> added=new ArrayList<GridLocation>();
ArrayList<GridLocation> addedby=new ArrayList<GridLocation>();
//arraylist to keep track of path to the goal
ArrayList<GridLocation> path=new ArrayList<GridLocation>(); //from goal to start(backwards)
ArrayList<GridLocation> sortedpath=new ArrayList<GridLocation>();
int row;
int col;
public MazeSolver(Agenda plan)
{
moves=plan; //stackagenda follows the given agenda
}
public ArrayList solveMaze(Maze maze, MazeGUI graphics) //important method that solves the maze
{
MazeGUI gui=graphics;
moves.clear(); //empties the stack
int row=maze.getNumRows();
int col=maze.getNumCols();
GridLocation start=maze.getStartLocation(); //start of maze
GridLocation goal=maze.getGoalLocation(); //goal of maze
moves.addLocation(start); //add the start location to stackagenda
//add start location to arraylist holding positions
visited.add(start);
added.add(start);
addedby.add(start);
current=start; //GridLocation current is start
while(!current.equals(goal)) //loop runs until current element is not the goal
{
//removes start from stackagenda as it won't be a valid move
if ( current.equals(start)){
moves.clear();
}
int currentrow=current.getRow(); //get the current row
int currentcol=current.getColumn(); //get the current column
//gives the location in the North
if(maze.isValidLoc((currentrow-1),currentcol)) //checks if the new location is valid
{
GridLocation loca=new GridLocation(currentrow-1,currentcol); //makes the GridLocation out of new column and row
GridLocation location=maze.getMazeLocation(loca); //gets the location equivalent in the maze world
if(maze.getSquare(location)!='#'&& visited.contains(location)!=true) //doesnt add if it is a wall or a visited location
{
moves.addLocation(location); //adds the current location to moves stackagenda
gui.addLocToAgenda(location);
addedby.add(current); //adds the location that this new location was added by
added.add(location); //adds the new location
}
}
//gives the location in the South
if(maze.isValidLoc((currentrow+1),currentcol))
{
GridLocation loca=new GridLocation(currentrow+1,currentcol);
GridLocation location=maze.getMazeLocation(loca);
if(maze.getSquare(location)!='#'&&visited.contains(location)!=true)
{
moves.addLocation(location);
gui.addLocToAgenda(location);
addedby.add(current);
added.add(location);
}
}
//gives the location in the East
if(maze.isValidLoc(currentrow,currentcol+1))
{
GridLocation loca=new GridLocation(currentrow,currentcol+1);
GridLocation location=maze.getMazeLocation(loca);
if(maze.getSquare(location)!='#'&&visited.contains(location)!=true)
{
moves.addLocation(location);
gui.addLocToAgenda(location);
addedby.add(current);
added.add(location);
}
}
//gives the location in the West
if(maze.isValidLoc(currentrow,currentcol-1))
{
GridLocation loca=new GridLocation(currentrow,currentcol-1);
GridLocation location=maze.getMazeLocation(loca);
if(maze.getSquare(location)!='#'&&visited.contains(location)!=true)
{
moves.addLocation(location);
gui.addLocToAgenda(location);
addedby.add(current);
added.add(location);
}
}
//gets a new current from the stackagenda moves of newly added valid moves
if(moves.isEmpty())
{
return path;
}
current=moves.getLocation();
gui.pause(1);
gui.visitLoc(current);
visited.add(current); //adds this new location to visited arraylist
} //End of while loop
//to track the path from goal to start
GridLocation cur=goal; //give the goal location to cur
path.add(goal); //add the goal to path as it is from where we are starting to track back
while (!cur.equals(start)) //tracks back until it reaches start location
{
int idx=added.indexOf(cur); //gets index of current location
path.add(addedby.get(idx)); //gets and adds the location cur was added by from addedby arraylist
cur=addedby.get(idx); //change the cur to the addedby location
}
for(int j=path.size()-1; j>=0;j--) //sorts the path from start to goal
{
sortedpath.add(path.get(j));
gui.addLocToPath(path.get(j));
}
return sortedpath; //returns the sorted path
}
public static void main(String[] args) throws FileNotFoundException
{
Maze maze1=new Maze(args[0]); //give a new maze via user input
String type = args[1];
Agenda agenda = null;
if(type.equals("s"))
{
StackAgenda moves=new StackAgenda();
agenda =moves;
}
else if(type.equals("q"))
{
QueueAgenda moves=new QueueAgenda();
agenda=moves;
}
else if(!type.equals("s")&&!type.equals("q"))
{
System.out.println("Error! Please enter a valid entry.");
System.exit(0);
}
MazeSolver solver = new MazeSolver (agenda);
MazeGUI mazeGraphics = new MazeGUI(maze1);
System.out.println(solver.solveMaze(maze1, mazeGraphics));
}
}