In my code below, I have 2 versions of the same maze - 1 hardcoded, and one with a more dynamic approach - Reading from an file, and converting it. However, I’m have issues with the last part, when I try to compute the shortest path.
TestDijkstra4.java
package maze_drawing;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.io.UnsupportedEncodingException;
import java.util.PriorityQueue;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
class Vertex implements Comparable<Vertex>
{
public final String name;
public static String faceDirection;
public Edge[] adjacencies;
public double minDistance = Double.POSITIVE_INFINITY;
public Vertex previous;
public Vertex(String argName) {
name = argName;
}
public String toString() {
return name;
}
public int compareTo(Vertex other)
{
return Double.compare(minDistance, other.minDistance);
}
}
class Edge
{
public final Vertex target;
public final String direction;
public Edge(Vertex argTarget, String argDirection){
target = argTarget;
direction = argDirection;
}
}
public class TestDijkstra4
{
public static void computePaths(Vertex source, String faceDirection)
{
source.minDistance = 0;
double turningweight = 0;
// robotDirection = faceDirection;
PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>();
vertexQueue.add(source);
while (!vertexQueue.isEmpty()) {
Vertex u = vertexQueue.poll();
// Visit each edge exiting u
for (Edge e : u.adjacencies)
{
Vertex v = e.target;
double distanceThroughU = u.minDistance + 10;
if (distanceThroughU < v.minDistance) {
vertexQueue.remove(v);
v.minDistance = distanceThroughU ;
v.previous = u;
vertexQueue.add(v);
}
}
}
}
public static List<Vertex> getShortestPathTo(Vertex target)
{
List<Vertex> path = new ArrayList<Vertex>();
for (Vertex vertex = target; vertex != null; vertex = vertex.previous)
path.add(vertex);
Collections.reverse(path);
return path;
}
public static void main(String args[]) throws FileNotFoundException, UnsupportedEncodingException
{
int startX = 0;
int startY = 0;
int endX = 3;
int endY = 3;
String facing = "N";
String start = ""+startX+""+startY;
String end = ""+endX+""+endY;
Vertex v00 = new Vertex("00");
Vertex v10 = new Vertex("10");
Vertex v20 = new Vertex("20");
Vertex v30 = new Vertex("30");
Vertex v40 = new Vertex("40");
Vertex v50 = new Vertex("50");
Vertex v60 = new Vertex("60");
Vertex v01 = new Vertex("01");
Vertex v11 = new Vertex("11");
Vertex v21 = new Vertex("21");
Vertex v31 = new Vertex("31");
Vertex v41 = new Vertex("41");
Vertex v51 = new Vertex("51");
Vertex v61 = new Vertex("61");
Vertex v02 = new Vertex("02");
Vertex v12 = new Vertex("12");
Vertex v22 = new Vertex("22");
Vertex v32 = new Vertex("32");
Vertex v42 = new Vertex("42");
Vertex v52 = new Vertex("52");
Vertex v62 = new Vertex("62");
Vertex v03 = new Vertex("03");
Vertex v13 = new Vertex("13");
Vertex v23 = new Vertex("23");
Vertex v33 = new Vertex("33");
Vertex v43 = new Vertex("43");
Vertex v53 = new Vertex("53");
Vertex v63 = new Vertex("63");
Vertex v04 = new Vertex("04");
Vertex v14 = new Vertex("14");
Vertex v24 = new Vertex("24");
Vertex v34 = new Vertex("34");
Vertex v44 = new Vertex("44");
Vertex v54 = new Vertex("54");
Vertex v64 = new Vertex("64");
Vertex v05 = new Vertex("05");
Vertex v15 = new Vertex("15");
Vertex v25 = new Vertex("25");
Vertex v35 = new Vertex("35");
Vertex v45 = new Vertex("45");
Vertex v55 = new Vertex("55");
Vertex v65 = new Vertex("65");
Vertex v06 = new Vertex("06");
Vertex v16 = new Vertex("16");
Vertex v26 = new Vertex("26");
Vertex v36 = new Vertex("36");
Vertex v46 = new Vertex("46");
Vertex v56 = new Vertex("56");
Vertex v66 = new Vertex("66");
v00.adjacencies = new Edge[]{ new Edge(v10, "E"), new Edge(v01, "N") };
v10.adjacencies = new Edge[]{ new Edge(v00, "S"), new Edge(v20, "E") };
v20.adjacencies = new Edge[]{ new Edge(v10, "W"), new Edge(v21, "N"), new Edge(v30, "E") };
v30.adjacencies = new Edge[]{ new Edge(v20, "W"), new Edge(v31, "N"), new Edge(v40, "E") };
v40.adjacencies = new Edge[]{ new Edge(v30, "W"), new Edge(v50, "E") };
v50.adjacencies = new Edge[]{ new Edge(v40, "W"), new Edge(v51, "N") };
v60.adjacencies = new Edge[]{ new Edge(v61, "N") };
v01.adjacencies = new Edge[]{ new Edge(v02, "N"), new Edge(v00, "S") };
v11.adjacencies = new Edge[]{ new Edge(v12, "N") };
v21.adjacencies = new Edge[]{ new Edge(v31, "E"), new Edge(v20, "S") };
v31.adjacencies = new Edge[]{ new Edge(v21, "W"), new Edge(v30, "S") };
v41.adjacencies = new Edge[]{ new Edge(v51, "E"), new Edge(v42, "N") };
v51.adjacencies = new Edge[]{ new Edge(v50, "S"), new Edge(v41, "W") };
v61.adjacencies = new Edge[]{ new Edge(v60, "S"), new Edge(v62, "N") };
v02.adjacencies = new Edge[]{ new Edge(v01, "S"), new Edge(v03, "N") };
v12.adjacencies = new Edge[]{ new Edge(v11, "S"), new Edge(v13, "N"), new Edge(v22, "E") };
v22.adjacencies = new Edge[]{ new Edge(v12, "W"), new Edge(v32, "E") };
v32.adjacencies = new Edge[]{ new Edge(v22, "W"), new Edge(v42, "E") };
v42.adjacencies = new Edge[]{ new Edge(v32, "W"), new Edge(v41, "S"), new Edge(v43, "N") };
v52.adjacencies = new Edge[]{ new Edge(v62, "E") };
v62.adjacencies = new Edge[]{ new Edge(v52, "W"), new Edge(v61, "S"), new Edge(v63, "N") };
v03.adjacencies = new Edge[]{ new Edge(v13, "E"), new Edge(v02, "S"), new Edge(v04, "N") };
v13.adjacencies = new Edge[]{ new Edge(v03, "W"), new Edge(v23, "E"), new Edge(v12, "S") };
v23.adjacencies = new Edge[]{ new Edge(v13, "W"), new Edge(v33, "E") };
v33.adjacencies = new Edge[]{ new Edge(v34, "N"), new Edge(v23, "W") };
v43.adjacencies = new Edge[]{ new Edge(v42, "S"), new Edge(v44, "N"), new Edge(v53, "E") };
v53.adjacencies = new Edge[]{ new Edge(v43, "W") };
v63.adjacencies = new Edge[]{ new Edge(v62, "S"), new Edge(v64, "N") };
v04.adjacencies = new Edge[]{ new Edge(v05, "N"), new Edge(v03, "S") };
v14.adjacencies = new Edge[]{ new Edge(v15, "N"), new Edge(v24, "E") };
v24.adjacencies = new Edge[]{ new Edge(v14, "W"), new Edge(v25, "N") };
v34.adjacencies = new Edge[]{ new Edge(v33, "S"), new Edge(v35, "N") };
v44.adjacencies = new Edge[]{ new Edge(v45, "N"), new Edge(v43, "S") };
v54.adjacencies = new Edge[]{ new Edge(v64, "E") };
v64.adjacencies = new Edge[]{ new Edge(v54, "W"), new Edge(v65, "N"), new Edge(v63, "S") };
v05.adjacencies = new Edge[]{ new Edge(v06, "N"), new Edge(v04, "S") };
v15.adjacencies = new Edge[]{ new Edge(v14, "S") };
v25.adjacencies = new Edge[]{ new Edge(v26, "N"), new Edge(v24, "S") };
v35.adjacencies = new Edge[]{ new Edge(v36, "N"), new Edge(v34, "S") };
v45.adjacencies = new Edge[]{ new Edge(v55, "E"), new Edge(v44, "S") };
v55.adjacencies = new Edge[]{ new Edge(v45, "W") };
v65.adjacencies = new Edge[]{ new Edge(v64, "S"), new Edge(v66, "N") };
v06.adjacencies = new Edge[]{ new Edge(v16, "E"), new Edge(v05, "S") };
v16.adjacencies = new Edge[]{ new Edge(v06, "W"), new Edge(v26, "E") };
v26.adjacencies = new Edge[]{ new Edge(v16, "W"), new Edge(v25, "S") };
v36.adjacencies = new Edge[]{ new Edge(v35, "S"), new Edge(v46, "E") };
v46.adjacencies = new Edge[]{ new Edge(v36, "W"), new Edge(v56, "E") };
v56.adjacencies = new Edge[]{ new Edge(v46, "W"), new Edge(v66, "E") };
v66.adjacencies = new Edge[]{ new Edge(v56, "W"), new Edge(v65, "S") };
Vertex[] vertices = { v00, v10, v20, v30, v40, v50, v60, v01, v11, v21, v31, v41, v51, v61, v02, v12, v22, v32, v42, v52, v62, v03, v13, v23, v33, v43, v53, v63, v04, v14, v24, v34, v44, v54, v64, v05, v15, v25, v35, v45, v55, v65, v06, v16, v26, v36, v46, v56, v66 };
Vertex[] vertices2 = new Vertex[49];
System.out.println("Start");
HentMazeFil mazeFile = new HentMazeFil();
String lineCoords;
Vertex v[] = new Vertex[67];
String Rest[] = new String[67];
String wholeLine[] = new String[49];
//Assign v[]
for (int i = 0; i < 49; i++) {
lineCoords = mazeFile.nextLineCoords();
if (lineCoords != null) {
v[Integer.parseInt(lineCoords.substring(0, 2))] = new Vertex(lineCoords.substring(0, 2));
Rest[Integer.parseInt(lineCoords.substring(0, 2))] = new String(lineCoords.substring(2, 6));
wholeLine[i] = lineCoords;
}
else {
System.out.println("Line = Null"); // End of while loop.
break;
}
lineCoords = mazeFile.nextLineCoords(); // Skipping "extra lines" from Linux files.
}
String line;
//Adding edges
for (int i = 0; i < 49; i++) {
line = wholeLine[i];
v[Integer.parseInt(line.substring(0, 2))] = new Vertex(line.substring(0, 2));
//vertices2[i] = v[Integer.parseInt(line.substring(0, 2))]; //vertices2[0] = first line, vertices2[1] = second line etc.
Rest[Integer.parseInt(line.substring(0, 2))] = new String(line.substring(2, 6));
if (line.charAt(2) == '0') {
if (line.charAt(3) == '0') {
if (line.charAt(4) == '0') {
if (line.charAt(5) == '0') {
v[Integer.parseInt(line.substring(0, 2))].adjacencies = new Edge[] {new Edge (v[Integer.parseInt(line.substring(0, 2))+1], "N") ,new Edge (v[Integer.parseInt(line.substring(0, 2))+10], "E"), new Edge (v[Integer.parseInt(line.substring(0, 2))-1], "S"), new Edge (v[Integer.parseInt(line.substring(0, 2))-10], "W")};
}
else {
v[Integer.parseInt(line.substring(0, 2))].adjacencies = new Edge[] {new Edge (v[Integer.parseInt(line.substring(0, 2))+1], "N") ,new Edge (v[Integer.parseInt(line.substring(0, 2))+10], "E"), new Edge (v[Integer.parseInt(line.substring(0, 2))-1], "S")};
}
}
else if (line.charAt(5) == '0') {
v[Integer.parseInt(line.substring(0, 2))].adjacencies = new Edge[] {new Edge (v[Integer.parseInt(line.substring(0, 2))+1], "N") ,new Edge (v[Integer.parseInt(line.substring(0, 2))+10], "E"), new Edge (v[Integer.parseInt(line.substring(0, 2))-10], "W")};
}
else {
v[Integer.parseInt(line.substring(0, 2))].adjacencies = new Edge[] {new Edge (v[Integer.parseInt(line.substring(0, 2))+1], "N") ,new Edge (v[Integer.parseInt(line.substring(0, 2))+10], "E")};
}
}
else if (line.charAt(4) == '0') {
if (line.charAt(5) == '0') {
v[Integer.parseInt(line.substring(0, 2))].adjacencies = new Edge[] {new Edge (v[Integer.parseInt(line.substring(0, 2))+1], "N"), new Edge (v[Integer.parseInt(line.substring(0, 2))-1], "S"), new Edge (v[Integer.parseInt(line.substring(0, 2))-10], "W")};
}
else {
v[Integer.parseInt(line.substring(0, 2))].adjacencies = new Edge[] {new Edge (v[Integer.parseInt(line.substring(0, 2))+1], "N") , new Edge (v[Integer.parseInt(line.substring(0, 2))-1], "S")};
}
}
else if (line.charAt(5) == '0') {
v[Integer.parseInt(line.substring(0, 2))].adjacencies = new Edge[] {new Edge (v[Integer.parseInt(line.substring(0, 2))+1], "N") , new Edge (v[Integer.parseInt(line.substring(0, 2))-10], "W")};
}
else {
v[Integer.parseInt(line.substring(0, 2))].adjacencies = new Edge[] {new Edge (v[Integer.parseInt(line.substring(0, 2))+1], "N")};
}
}
else if (line.charAt(3) == '0') {
if (line.charAt(4) == '0') {
if (line.charAt(5) == '0') {
v[Integer.parseInt(line.substring(0, 2))].adjacencies = new Edge[] {new Edge (v[Integer.parseInt(line.substring(0, 2))+10], "E"), new Edge (v[Integer.parseInt(line.substring(0, 2))-1], "S"), new Edge (v[Integer.parseInt(line.substring(0, 2))-10], "W")};
}
else {
v[Integer.parseInt(line.substring(0, 2))].adjacencies = new Edge[] {new Edge (v[Integer.parseInt(line.substring(0, 2))+10], "E"), new Edge (v[Integer.parseInt(line.substring(0, 2))-1], "S")};
}
}
else if (line.charAt(5) == '0') {
v[Integer.parseInt(line.substring(0, 2))].adjacencies = new Edge[] {new Edge (v[Integer.parseInt(line.substring(0, 2))+10], "E"), new Edge (v[Integer.parseInt(line.substring(0, 2))-10], "W")};
}
else {
v[Integer.parseInt(line.substring(0, 2))].adjacencies = new Edge[] {new Edge (v[Integer.parseInt(line.substring(0, 2))+10], "E")};
}
}
else if(line.charAt(4) == '0') {
if (line.charAt(5) == '0') {
v[Integer.parseInt(line.substring(0, 2))].adjacencies = new Edge[] {new Edge (v[Integer.parseInt(line.substring(0, 2))-1], "S"), new Edge (v[Integer.parseInt(line.substring(0, 2))-10], "W")};
}
else {
v[Integer.parseInt(line.substring(0, 2))].adjacencies = new Edge[] {new Edge (v[Integer.parseInt(line.substring(0, 2))-1], "S")};
}
}
else if(line.charAt(5) == '0') {
v[Integer.parseInt(line.substring(0, 2))].adjacencies = new Edge[] {new Edge (v[Integer.parseInt(line.substring(0, 2))-10], "W")};
}
else {
System.out.println("No openings - File read '1111'");
}
vertices2[i] = v[Integer.parseInt(line.substring(0, 2))];
vertices2[i].adjacencies = v[Integer.parseInt(line.substring(0, 2))].adjacencies;
}//end of i loop
for (int i = 0; i < 49; i++) {
if (vertices[i].toString().equals(start)) {
computePaths(vertices[i], facing);
}
}
for (int i = 0; i < 49; i++) {
if (vertices[i].toString().equals(end)) {
System.out.println("Distance to " + vertices[i] + ": " + vertices[i].minDistance);
List<Vertex> path = getShortestPathTo(vertices[i]);
System.out.println("Path: " + path);
PrintWriter writer = new PrintWriter("traversalfile.txt", "UTF-8");
for (int j = 0; j < path.size()-1; j++) {
int directionValue = Integer.parseInt(path.get(j+1).toString())-Integer.parseInt(path.get(j).toString());
if (directionValue == 1) {
System.out.println("N");
writer.println("N");
}
else if (directionValue == 10) {
System.out.println("E");
writer.println("E");
}
else if (directionValue == -1) {
System.out.println("S");
writer.println("S");
}
else if (directionValue == -10) {
System.out.println("W");
writer.println("W");
}
else {
System.out.println("Something went wrong");
}
}
writer.close();
}
}
}
}
My problem is, when I try to use “vertices2” instead of “vertices” in the last part of the code.
It goes wrong in the “computepath” method.
I get:
“Exception in thread “main” java.lang.NullPointerException
at maze_drawing.TestDijkstra4.computePaths(TestDijkstra4.java:60)
at maze_drawing.TestDijkstra4.main(TestDijkstra4.java:307)
Java Result: 1”
I’ve been stuck here for a while, and I can’t seem to find a solution.
When I print vertices & vertices2, they seem almost identical - The only variation is the edge order, but they’re connected to a correct Vertex.
I’ve tried to use some print lines, to see exactly where it goes wrong - It seems to happen specifically in “vertexQueue.add(v);” - The 2. time I get there (= for the 2. edge). It doesn’t matter which start position i choose, I get the same error.
But there’s no problems, when I use “vertices”, it’s only when I use “vertices2”.
I’ve also tried to print all vertices2.adjacencies (in a for(edge e : vertices2[i].adjacencies) loop), which shows all the edges to a vertex.
Can you see what’s wrong?
Thanks in advance.
The 2 other connected files:
HentMazeFil.java:
package maze_drawing;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class HentMazeFil {
java.io.File file;
String lineCoords;
Scanner input;
public HentMazeFil() {
file = new java.io.File("newtestmap.map");
try {
input = new Scanner(file);
} catch (FileNotFoundException ex) {
System.out.println("File dont exist");
}
}
public String nextLineCoords() {
if (input.hasNext()) {
lineCoords = input.nextLine();
return lineCoords;
}
return null;
}
}
newtestmap.map:
000011
101010
200010
300010
401010
500110
600111
010101
110111
211001
311100
410011
511100
610101
020101
120001
221010
321010
420100
521011
620100
030001
131000
231010
330110
430001
531110
630101
040101
140011
240110
340101
440101
541011
640100
050101
151101
250101
350101
451001
551110
650101
061001
161010
261100
361001
461010
561010
661100