Java a* algorithm implementation issue

Question

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.

Edit:

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?

Read dijkstra at first place, the difference of a* from dijkstra is just an additional heuristic weight for the priority queue. I would say a* is an optimization for dijkstra. — AlexTheo
– AlexTheo, Commented Mar 25, 2015 at 20:24
In Java, method names should start with a lower case letter. Perhaps you would like to change your method names as described here. oracle.com/technetwork/java/codeconventions-135099.html — Chan
– Chan, Commented Mar 25, 2015 at 22:07
Which part of the algorithm do you start to lose your confidence in understanding what is happening? If you are looking for a more verbose explanation, you could give this a try. web.mit.edu/eranki/www/tutorials/search — Taekahn
– Taekahn, Commented Mar 25, 2015 at 22:14
@Taekahn I'm currently looking at this pseudo-code: web.mit.edu/eranki/www/tutorials/search and it's on line 13 that I'm starting to get confused. I don't understand what it means by the 'a node with the same position as successor is in the OPEN list' by position what does it mean? PQ position? I'll edit the first post as I've reverted my code and tackled it a different way — Craig
– Craig, Commented Mar 26, 2015 at 15:40
@Taekahn I just realised that you linked me to the same page I was looking at! Sorry about that - I already had that link open last night before you had commented - decided to try and implement it this morning! — Craig
– Craig, Commented Mar 26, 2015 at 15:48

libik · Accepted Answer · 2015-03-25 20:23:53Z

2

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.

answered Mar 25, 2015 at 20:23

libik

23.1k10 gold badges52 silver badges94 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Java a* algorithm implementation issue

Edit:

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

Edit:

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related