Develop a program that can read in a maze from a text file and solve it using th

Question

Develop a program that can read in a maze from a text file and solve it using the JGraphT library.  Extra credit: Display an animated graphical solution to the maze.


1. Use this web site to generate a maze and save it to a text file:  http://www.delorie.com/game-room/mazes/genmaze.cgi

2. Created an undirected graph:  UndirectedGraph<String, DefaultEdge> g = new SimpleGraph<String, DefaultEdge>(DefaultEdge.class);

3. Read the text file and convert it to an undirected graph using the JGraphT library. Begin by reading a line, and adding every character as a vertex:
while (infile.hasNext())
{
     PreviousLine = ThisLine;
     ThisLine = infile.nextLine();

     // step through each character of ThisLine in a for loop
     // if the character is a space, add it as a vertex:   g.addVertex(x+":"+y);
     //    Add edge if the character to the left is a space: g.addEdge((x-1)+":"+y,x+":"+y);
     //    Add edge if the character above is a space: g.addEdge(x+":"+(y-1),x+":"+y);

     y++;
}
     
4. Print the vertex set and edge set:    g.vertexSet()   g.edgeSet()

5. Use DijkstraShortestPath algorithm to solve the maze:
DijkstraShortestPath Path = new DijkstraShortestPath(g, BeginVertex, EndVertex);

6. Print the Path and Length:    Path.getPath()    Path.getPathLength()

Example Output

Maze
line 0: *************
line 1:             *
line 2: * ******* *
line 3: * *     * *  
line 4: * * * ****
line 5: *     *
line 6: *************

Vertex Set
[0:1, 1:1, 2:1, 3:1, 4:1, 5:1, 6:1, 7:1, 8:1, 9:1, 10:1, 11:1, 1:2, 2:2, 10:2, 11:2, 1:3, 2:3, 4:3, 5:3, 6:3, 7:3, 8:3, 10:3, 11:3, 1:4, 2:4, 4:4, 5:4, 7:4, 8:4, 1:5, 2:5, 3:5, 4:5, 5:5, 7:5, 8:5, 9:5, 10:5, 11:5, 12:5]

Edge Set
[(0:1 : 1:1), (1:1 : 2:1), (2:1 : 3:1), (3:1 : 4:1), (4:1 : 5:1), (5:1 : 6:1), (6:1 : 7:1), (7:1 : 8:1), (8:1 : 9:1), (9:1 : 10:1), (10:1 : 11:1), (1:1 : 1:2), (1:2 : 2:2), (2:1 : 2:2), (10:1 : 10:2), (10:2 : 11:2), (11:1 : 11:2), (1:2 : 1:3), (1:3 : 2:3), (2:2 : 2:3), (4:3 : 5:3), (5:3 : 6:3), (6:3 : 7:3), (7:3 : 8:3), (10:2 : 10:3), (10:3 : 11:3), (11:2 : 11:3), (1:3 : 1:4), (1:4 : 2:4), (2:3 : 2:4), (4:3 : 4:4), (4:4 : 5:4), (5:3 : 5:4), (7:3 : 7:4), (7:4 : 8:4), (8:3 : 8:4), (1:4 : 1:5), (1:5 : 2:5), (2:4 : 2:5), (2:5 : 3:5), (3:5 : 4:5), (4:4 : 4:5), (4:5 : 5:5), (5:4 : 5:5), (7:4 : 7:5), (7:5 : 8:5), (8:4 : 8:5), (8:5 : 9:5), (9:5 : 10:5), (10:5 : 11:5), (11:5 : 12:5)]

Solution Path
[(0:1 : 1:1), (1:1 : 1:2), (1:2 : 1:3), (1:3 : 1:4), (1:4 : 1:5), (1:5 : 2:5), (2:5 : 3:5), (3:5 : 4:5), (4:4 : 4:5), (4:3 : 4:4), (4:3 : 5:3), (5:3 : 6:3), (6:3 : 7:3), (7:3 : 8:3), (8:3 : 8:4), (8:4 : 8:5), (8:5 : 9:5), (9:5 : 10:5), (10:5 : 11:5), (11:5 : 12:5)]

Length of Solution Path = 20.0
CODE SO FAR!!!!!

import java.util.*;

import java.io.*;

import org.jgrapht.*;

import org.jgrapht.graph.*;

import org.jgrapht.alg.*;

public class mazerunner

{

public static void main (String[] args) throws IOException

{

UndirectedGraph<String, DefaultEdge> g = new SimpleGraph<String, DefaultEdge>(DefaultEdge.class);

File file = new File("maze1.txt");

Scanner infile = new Scanner(file);

String Line;

int y = 0;

while (infile.hasNextLine())

{

Line = infile.nextLine();

System.out.println(Line);

for (int x=0; x<Line.length(); x++)

{

g.addVertex(x+":"+y);

if (x > 0 && Line.charAt(x-1)== ' ')

g.addEdge((x-1)+":"+y, x+":"+y);

}

y++;

}

System.out.println("Number of Vertices = " + g.vertexSet().size());

System.out.println("Vertex set = " + g.vertexSet());

}

}

Explanation / Answer

import java.util.*;
import java.io.*;
import org.jgrapht.*;
import org.jgrapht.graph.*;
import org.jgrapht.alg.*;

public class mazerunner{

public static void main (String[] args) throws IOException{

UndirectedGraph<String, DefaultEdge> g = new SimpleGraph<String, DefaultEdge>(DefaultEdge.class);
File file = new File("maze1.txt");
Scanner infile = new Scanner(file);
String previousline,Line;
int y = 0;
while (infile.hasNextLine()){
previousline = Line;
Line = infile.nextLine();
System.out.println(Line);
for (int x=0; x<Line.length(); x++){
if(Line.charAt(x)==' ')
g.addVertex(x+":"+y);
if (x > 0 && Line.charAt(x-1)== ' ')
g.addEdge((x-1)+":"+y, x+":"+y);
if(y>0 && previousline.charAt(x)==' ')
g.addEdge((x)+":"+y-1,x+":"+y);
}
y++;
}
System.out.println("Number of Vertices = " + g.vertexSet().size());
System.out.println("Vertex set = " + g.vertexSet());

DijkstraShortestPath Path = new DijkstraShortestPath(g, BeginVertex, EndVertex);
System.out.println(Path.getPath());
System.out.println(Path.getPathLength());

}

}

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.