Wolf Marian Wolf Marian - 1 month ago 9
Java Question

NullPointerException on PriorityQueue A* algorithm

I try to implement A* algorithm. I don't know why but I get this error:

enter image description here

My graph and heuristic is this:

enter image description here

I wrote the values of heuristics when the nodes are created. And the value of edged, when an edge is created.

Here is the code:

package com.astar.algorithm;

import java.util.PriorityQueue;
import java.util.HashSet;
import java.util.Set;

import java.util.List;
import java.util.Comparator;
import java.util.ArrayList;
import java.util.Collections;

public class AStar {



public static void main(String[] args){


Node s = new Node("S", 12);
Node a = new Node("A", 5);
Node b = new Node("B", 5);
Node c = new Node("C", 5);
Node d = new Node("D", 2);
Node e = new Node("E", 2);
Node f = new Node("F", 1);
Node h = new Node("H", 1);
Node g = new Node("G", 0);

s.adjacencies = new Edge[]{
new Edge(b, 8),
new Edge(a, 10)
};

b.adjacencies = new Edge[]{
new Edge(d, 8),
new Edge(g, 16)
};

d.adjacencies = new Edge[]{
new Edge(g, 3),
new Edge(h, 1)
};

h.adjacencies = new Edge[]{
new Edge(f, 1)
};

a.adjacencies = new Edge[]{
new Edge(g, 10),
new Edge(c, 2)
};

c.adjacencies = new Edge[]{
new Edge(e, 3)
};

e.adjacencies = new Edge[]{
new Edge(g, 2)
};

AstarSearch(s, g);

List<Node> path = printPath(g);

System.out.println("Path: " + path);


}

public static List<Node> printPath(Node target){
List<Node> path = new ArrayList<Node>();

for(Node node = target; node!=null; node = node.parent){
path.add(node);
}

Collections.reverse(path);

return path;
}

public static void AstarSearch(Node source, Node goal){

Set<Node> explored = new HashSet<Node>();

PriorityQueue<Node> queue = new PriorityQueue<Node>(8, new Comparator<Node>(){
//override compare method
public int compare(Node i, Node j){
if(i.f_scores > j.f_scores){
return 1;
}

else if (i.f_scores < j.f_scores){
return -1;
}

else{
return 0;
}
}

}
);

//cost from start
source.g_scores = 0;

queue.add(source);

boolean found = false;

while((!queue.isEmpty())&&(!found)){

//the node in having the lowest f_score value
Node current = queue.poll();

explored.add(current);

//goal found
if(current.value.equals(goal.value)){
found = true;
}

//check every child of current node
for(Edge o : current.adjacencies){
Node child = o.target;
double cost = o.cost;
double temp_g_scores = current.g_scores + cost;
double temp_f_scores = temp_g_scores + child.h_scores;


/*if child node has been evaluated and
the newer f_score is higher, skip*/

if((explored.contains(child)) && (temp_f_scores >= child.f_scores)) {
continue;
}

/*else if child node is not in queue or
newer f_score is lower*/

else if((!queue.contains(child)) || (temp_f_scores < child.f_scores)){

child.parent = current;
child.g_scores = temp_g_scores;
child.f_scores = temp_f_scores;

if(queue.contains(child)){
queue.remove(child);
}

queue.add(child);

}

}

}

}

}

class Node{

public final String value;
public double g_scores;
public final double h_scores;
public double f_scores = 0;
public Edge[] adjacencies;
public Node parent;

public Node(String val, double hVal){
value = val;
h_scores = hVal;
}

public String toString(){
return value;
}

}

class Edge{
public final double cost;
public final Node target;

public Edge(Node targetNode, double costVal){
target = targetNode;
cost = costVal;
}
}

Answer

Your program fails at node G when it adds a Node to the queue without setting adjacencies to any values.

The following piece of code tries to add child without assigned adjacencies:

queue.add(child);

The quick fix would be to change Node class and initialize adjacencies with an empty array like this:

public Edge[] adjacencies = new Edge[]{};

So the Node class would look like:

class Node{
        public final String value;
        public double g_scores;
        public final double h_scores;
        public double f_scores = 0;
        public Edge[] adjacencies = new Edge[]{};
        public Node parent;

        public Node(String val, double hVal){
                value = val;
                h_scores = hVal;
        }

        public String toString(){
                return value;
        }    
}

The better solution would be replace array with ArrayList.