I'm trying to code the A* algorithm using a self implemented PQ and Vector. It has verticies as junctions and edges as roads. I was able to correctly code the dijkstra algorithm however I needed to improve the performance.
Currently my algorithm breaks throwing a null pointer exception as commented in the code. I've been researching the algorithm for the past 5+ hours whilst trying to implement it. I don't fully understand the method of comparing paths as well as I did for the dijkstra implementation.
Here is my current code:
private Vertex dijkstra (int start, int end)
{
Vertex current;
while (!(pqOpen.IsEmpty()))
{
current = pqOpen.GetNextItem();
else
{
for (int i = 0; i < current.neighbors.GetNoOfItems(); i++)
{
if (hold != null && hold.neighbors.GetItem(i).fromid != hold.city)
{
int x = 1;
if (hold2 == null || hold.getTentativeDistance() < hold2.getTentativeDistance())
{
hold2.from = hold; //throws null pointer here
hold2.setTentativeDistance(hold.getTentativeDistance());
hold2.setF(hold2.getTentativeDistance() + heuristic(hold2, endLoc));
System.out.println(hold2.from.city);
}
}
}
}
return null;
}
private double heuristic(Vertex goal, Vertex next)
{
return Math.sqrt(Math.pow((goal.x - next.x), 2) + Math.pow((goal.y - next.y), 2));
}
I've got a feeling that I've totally misunderstood the pseudo code about half way down the algorithm but as of yet I haven't found a representation that I can wrap my head around - so could someone possibly take a look at my code and point out where and what I'm doing wrong?
Here is a link to the website I used for reference: http://wiki.gamegardens.com/Path_Finding_Tutorial#Pseudo-code_A.2A
I also tried the wikipedia one, but their methods confused me even more: http://en.wikipedia.org/wiki/A*_search_algorithm
Currently it does loop round a few times and stores some nodes, however they are incorrect.
I've reverted my code and attempted it a different way. I'm now using these pseudo-code examples to understand the algorithm. http://web.mit.edu/eranki/www/tutorials/search/ and http://www.redblobgames.com/pathfinding/a-star/introduction.html
On the first one, I think my code is correct until line 13 on the pseudo code. From that point I get confused about the term he uses 'position'.
The if statement that I commented out, is from my dijkstra algorithm. However I think the if statements in the pseudo code I meantioned earlier should be something similar to what the IF statements are.
Could anyone possibly help me understand line 13 in the pseudocode in relation to my code?
I did not read all the code, but this part is obviously bad :)
if (hold2 == null)
{
hold2.from = hold; //throws null pointer here
}
See? If the hold2 is null, you are trying to asign value to field from of hold2 which is null in this case, therefore it throws an exception.