I am building an application that is using A Star to calculate a route between two rooms. However I have run into an NullPointrException when I test the algorithm. This is my Vertex class:
Vertex.java
package testalgo;
import java.util.ArrayList;
public class Vertex {
/**
* @param args
*/
int vertexNumber;
int x;
int y;
public Vertex(int vertNum, int x,int y){
vertexNumber = vertNum;
this.x = x;
this.y = y;
}
public int getVertexNum(){
return vertexNumber;
}
public int getX(){
return x;
}
public int getY(){
return y;
}
public double distanceTo(Vertex other){
return Math.sqrt( Math.pow( x -other.x, 2) + Math.pow( y- other.y,2) );
}
}
This my Graph class:
Graph.java
package testalgo;
import java.io.File;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
public class Graph
{
static ArrayList<Vertex> vertices = new ArrayList<Vertex>();
static HashMap<Integer, LinkedList<Integer>> adj =new HashMap<Integer, LinkedList<Integer>>();
static Vertex v;
static Scanner sc;
public Graph(ArrayList<Vertex> verts ){
}
public static void addVertextToVertices(Vertex v1){
vertices.add(v1);
}
public static void addVertex(int vertexNumber)
{
adj.put(vertexNumber, new LinkedList<Integer>());
}
public static void addEgde(int vertexIndex, int vertexIndex2) {
adj.get(vertexIndex).add(vertexIndex2);
}
public static List<Integer> getNeighbors(int v) {
return adj.get(v);
}
}
And this is my AStar class
AStar.java
package testalgo;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
public class AStar {
static Vertex v;
static Graph g;
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Vertex a = new Vertex(1, 796, 629);
Vertex b = new Vertex (2, 1424, 479);
Vertex c = new Vertex (3, 1484,480 );
Vertex d = new Vertex (4,922, 386);
Vertex e = new Vertex (5, 919, 311);
Vertex f = new Vertex (6, 563, 286);
Vertex g1 = new Vertex (7,507, 283);
g.addVertextToVertices(a);
g.addVertextToVertices(b);
g.addVertextToVertices(c);
g.addVertextToVertices(d);
g.addVertextToVertices(e);
g.addVertextToVertices(f);
g.addVertextToVertices(g1);
g.addVertex(g.vertices.indexOf(a));
g.addVertex(g.vertices.indexOf(b));
g.addVertex(g.vertices.indexOf(c));
g.addVertex(g.vertices.indexOf(d));
g.addVertex(g.vertices.indexOf(e));
g.addVertex(g.vertices.indexOf(f));
g.addVertex(g.vertices.indexOf(g1));
g.addEgde(g.vertices.indexOf(a),g.vertices.indexOf(b));
g.addEgde(g.vertices.indexOf(b),g.vertices.indexOf(a));
g.addEgde(g.vertices.indexOf(a),g.vertices.indexOf(e));
g.addEgde(g.vertices.indexOf(e),g.vertices.indexOf(a));
g.addEgde(g.vertices.indexOf(b),g.vertices.indexOf(g1));
g.addEgde(g.vertices.indexOf(g1),g.vertices.indexOf(b));
g.addEgde(g.vertices.indexOf(c),g.vertices.indexOf(g1));
g.addEgde(g.vertices.indexOf(g1),g.vertices.indexOf(c));
g.addEgde(g.vertices.indexOf(c),g.vertices.indexOf(d));
g.addEgde(g.vertices.indexOf(d),g.vertices.indexOf(c));
g.addEgde(g.vertices.indexOf(d),g.vertices.indexOf(e));
g.addEgde(g.vertices.indexOf(e),g.vertices.indexOf(d));
g.addEgde(g.vertices.indexOf(e),g.vertices.indexOf(f));
g.addEgde(g.vertices.indexOf(f),g.vertices.indexOf(e));
g.addEgde(g.vertices.indexOf(f),g.vertices.indexOf(g1));
g.addEgde(g.vertices.indexOf(g1),g.vertices.indexOf(f));
System.out.println(g.getNeighbors(g.vertices.indexOf(a)));
System.out.println(g.getNeighbors(g.vertices.indexOf(b)));
System.out.println(g.getNeighbors(g.vertices.indexOf(c)));
System.out.println(g.getNeighbors(g.vertices.indexOf(d)));
System.out.println(g.getNeighbors(g.vertices.indexOf(e)));
System.out.println(g.getNeighbors(g.vertices.indexOf(f)));
System.out.println(g.getNeighbors(g.vertices.indexOf(g1)));
findPath(a, e);// This is line 90
}
public static List<Node> findPath(Vertex start, Vertex goal){
List<Node> open = new ArrayList<Node>();
List<Node> closed = new ArrayList<Node>();
Node start_Node = new Node (start,null, 0.0, v.distanceTo(goal)); // This is line 99
open.add(start_Node);
while(open != null){
Collections.sort(open, sortNodes);
Node current = open.get(0);
if(current.v == goal){
List<Node> path = new ArrayList<Node>();
while(current.parent != null){
path.add(current);
current = current.parent;
}
open.clear();
closed.clear();
return path;
}
open.remove(current);
closed.add(current);
List<Integer> neighbours =g.getNeighbors(g.vertices.indexOf(current.v));
for (int i=0; i<neighbours.size(); i++){
Vertex currentV = g.vertices.get(neighbours.get(i));
double g = current.g + current.v.distanceTo(currentV);
double h = currentV.distanceTo(goal);
Node succesor = new Node (currentV,current, g, h);
//succesor.setParent(current);
if(hasVertex(closed, succesor.v) && g >= succesor.g){
continue;
}
if(!hasVertex(open, succesor.v) || g < succesor.g){
open.add(succesor);
}
open.remove(succesor);
closed.remove(succesor);
succesor.parent= current;
double f= succesor.g + succesor.h;
open.add(succesor);
}
}
closed.clear();
return null;
}
private static boolean hasVertex(List<Node> list, Vertex vertex ){
for(Node n: list){
if(n.v.equals(vertex))
return true;
}
return false;
}
private double calculateH(Node current){
return Math.sqrt( Math.pow(current.v.getX(), 2) + Math.pow( current.v.getY(),2) );
}
private static Comparator<Node> sortNodes = new Comparator<Node>(){
public int compare(Node n0, Node n1) {
if(n1.f < n0.f)
return +1;
if(n1.f < n0.f)
return -1;
return 0;
}
};
}
This is the error I'm getting
Exception in thread "main" java.lang.NullPointerException
at testalgo.AStar.findPath(AStar.java:99)
at testalgo.AStar.main(AStar.java:90)
Thank you for all your help!
