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 g = new SimpleGraph(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

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------

My code so far :

import java.util.*;

import java.io.*;

import org.jgrapht.*;

import org.jgrapht.graph.*;

import org.jgrapht.alg.*;

public class mazesolver

{

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

{

UndirectedGraph g = new SimpleGraph(DefaultEdge.class);

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

Scanner infile = new Scanner(file);

int y = 0;

String ThisLine = null,PrevLine;

while (infile.hasNext())

{

PrevLine = ThisLine;

ThisLine = infile.nextLine();

System.out.println(ThisLine);

for (int x=0; x

{

if (ThisLine.charAt(x) == ' ') //add vertex if space

{

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

//add edge if space is to the left

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

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

//add edge if space is above (use PrevLine)

if(y>0 && PrevLine.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());

}

}}