A Star Implementation in Java

Question

So I'm currently having trouble with the finishing touches of my A* Pathfinding, I have all of my necessary helper functions to do so, and I've actually implemented this algorithm in both Javascript and ActionScript, however I am tripping over using Lists in Java.

It comes up with no errors, but I need to get the finishing touches in so I can test to make sure it is functioning properly.

What I need to do is sort the openList so I can retrieve the lowest cost Node, this is where I need the help.

Here is what I have:

public class Pathfinding
{
    List<Node> closedList = new ArrayList<Node>();
    List<Node> openList = new ArrayList<Node>();

public Node calculateShortestDistance(List<Integer> tiles, Node start, Node goal, List<Integer> passableTiles)
{

    Node currentNode = new Node(start.row, start.col, start.gCost, start.fCost, null);

    while(!catchMeIfYouCan(currentNode, goal))
    {
        int row = currentNode.row;
        int col = currentNode.col + 1;

        addChild(row, col, tiles, passableTiles, currentNode, goal, openList, closedList);

        //left child
        col -= 2;
        addChild(row, col, tiles, passableTiles, currentNode, goal, openList, closedList);

        //top child
        col++;
        row--;
        addChild(row, col, tiles, passableTiles, currentNode, goal, openList, closedList);

        //bottom child
        row += 2;
        addChild(row, col, tiles, passableTiles, currentNode, goal, openList, closedList);

        //bottom right
        col++;
        addChild(row, col, tiles, passableTiles, currentNode, goal, openList, closedList);

        //bottom left
        col -= 2;
        addChild(row, col, tiles, passableTiles, currentNode, goal, openList, closedList);

        //top left
        row -= 2;
        addChild(row, col, tiles, passableTiles, currentNode, goal, openList, closedList);

        //top right
        col += 2;
        addChild(row, col, tiles, passableTiles, currentNode, goal, openList, closedList);

        //Put currentNode in the closedList
        closedList.add(currentNode);
        //Sort the openList

        //Assign currentNode to the last element in the List

    }
    return currentNode;
}

Answer 1

Sorting the list is pretty easy. First, you need to make Node Comparable:

class Node implements Comparable<Node>

Then you need to write:

public boolean compareTo(Node other)

That should be an equality test.

Then, you can easily use Collections.sort():

Collections.sort(openList);