CODEWITHSUNDEEP
javaalgorithma-star
Sameeha Rahman
Sameeha Rahman

Reputation: 11

A-star algorithm java implementation explained

I recently had course work on a Java implementation of the A star algorithm, where the input data is in the form of a 20 * 20 grid.

According to the A star algorithm pseudocode, the node with lowest final cost in the open list is chosen as the current node to travel to.

Before actually implementing the algorithm in Java, I went through many different implementations in other languages, like ruby, python and c++.

One thing common in the implementation in other languages is that it sticks to the algorithms method of going to the node with the lowest final cost as the new current node when traversing the path.

I used a priority queue to implement the open list for this algorithm, adding the comparator below, which gives higher priority to the node with lower final cost

PriorityQueue<GridPiece> unvisitedNodes = new PriorityQueue<>(10,
            (gridPie1, gridPie2) -> ((GridPiece) gridPie1).getFinalCost() > 
((GridPiece) gridPie2).getFinalCost()? -1
                    : ((GridPiece) gridPie1).getFinalCost() < ((GridPiece) 
gridPie2).getFinalCost() ? 1 : 0);

But when I run the algorithm, I get the longest path possible. The legend for both images are, the path is orange, source is pink and destination is purple.

image of incorrect path

When I looked into Java implementations for this algorithm for a gridbased input, if a priority queue is used, they always give higher priority to the nodes with higher final cost. I tried this method by changing the comparator to this

PriorityQueue<GridPiece> unvisitedNodes = new PriorityQueue<>(10,
            (gridPie1, gridPie2) -> ((GridPiece) gridPie1).getFinalCost() < 
((GridPiece) gridPie2).getFinalCost()? -1
                    : ((GridPiece) gridPie1).getFinalCost() > ((GridPiece) 
gridPie2).getFinalCost() ? 1 : 0);

I then get a better path;

image of correct path

My simple request is a short explanation to why the algorithm doesn't behave as expected when the implementation exactly sticks to the pseudo code and why the priority of the nodes need to be switched (higher final cost is traveled to first) for the algorithm to work in a java implementation?

The full code for the project can be found here.

Upvotes: 0

Views: 2492

Answers (1)

sprinter
sprinter

Reputation: 27946

The head of a priority queue is the least element with respect to the given ordering. Your comparator returns -1 when the first element's cost is greater than the second element's cost. In other words, you are putting the highest cost element first. That's why the head of your queue has the grid pie with the largest cost.

In your second implementation, the comparator returns -1 when the first element's cost is less than the second element's cost, which is what you want.

If you are just sorting by cost (presumably an int?) then you can just do:

new PriorityQueue<GridPiece>(Comparator.comparingInt(GridPiece::getFinalCost));

There's rarely a reason to specify the initial capacity. For a small grid like yours just use the default capacity to keep things simple.

Upvotes: 1

Related Questions