How can i improve performance of the A-Star algorithm?

Question

I have implemented the A-Star algorithm and I am not getting the performance as expected, How can I improve the performance of the algorithm.

Below is the main function which is called in a while loop till the destination node is reached, This is a single direction AStar implementation.

public void step(boolean useQueueOnly) {
        count ++;
        m_fixedNodeId = m_nextNodeId;
        m_fixedCost = m_nextCost;
        int fromNodeId = m_current.getPrevNodeId();

        int arcId = m_network.getFirstArc(m_fixedNodeId);
        while (arcId != Integer.MIN_VALUE) {
            int nextNodeId = m_network.getBegNodeId(arcId);
            if (nextNodeId == m_fixedNodeId) {
                nextNodeId = m_network.getEndNodeId(arcId);
            }
            int arcCost;
            if (m_forwardDirection) {
                arcCost = m_network.getCost(arcId, m_fixedNodeId, fromNodeId);
            } else {
                arcCost = m_network.getCost(arcId, nextNodeId, fromNodeId);
            }

            arcCost = Math.max(MIN_COST_ALLOWED, arcCost);

            if (arcCost != Integer.MAX_VALUE) {
                int newNodeCost = (int) Math.min((long) m_fixedCost + arcCost,
                        Integer.MAX_VALUE);

                int nodePrevCost  = fromMap.get(nextNodeId) != null ? fromMap.get(nextNodeId).getCost() : Integer.MAX_VALUE;

                double approxCost = newNodeCost + m_approximator.approximate(nextNodeId);

                AStarEntry ase = new AStarEntry(nextNodeId, approxCost, arcId, m_current, m_fixedNodeId, newNodeCost);

                if ((nodePrevCost == Integer.MAX_VALUE) &&
                        (newNodeCost != Integer.MAX_VALUE)) {
                    //haven't yet reached this node.
                    if(fromMap.get(nextNodeId) == null){
                        fromMap.put(nextNodeId, ase);
                        m_priorityNodeQueue.add(ase);
                    }

                } else if (newNodeCost < nodePrevCost) {
                    //already reached this node.
                    m_priorityNodeQueue.remove(ase);

                }
            }
            arcId = m_network.getNextArc(m_fixedNodeId, arcId);
        }

        m_current = m_priorityNodeQueue.poll();
        m_nextNodeId = m_current.getNodeId();
        m_nextCost = m_current.getCost();

}

This is the class I am using in the priority queue.

class AStarEntry implements Cloneable, Comparable<AStarEntry>{

    public double m_weight;
    public int m_nodeId;
    public int m_arcId;
    public int m_prevNodeId;
    public int m_cost;

    public AStarEntry m_parent;

    public AStarEntry(int nodeId, double weight, int arcId, AStarEntry parent, int prevNodeId, int cost) {
        m_nodeId = nodeId;
        m_weight = weight;
        m_arcId = arcId;
        m_parent = parent;
        m_prevNodeId = prevNodeId;
        m_cost = cost;
    }

    @Override
    public int compareTo(AStarEntry o) {

        // assumption no NaN and no -0        
        return m_weight > o.m_weight ? +1 : m_weight < o.m_weight ? -1 : 0;
    }

    public double getWeight() {
        return m_weight;
    }

    public int getNodeId() {
        return m_nodeId;
    }

    public int getArcId() {
        return m_arcId;
    }

    public AStarEntry getParent() {
        return m_parent;
    }

    public int getPrevNodeId() {
        return m_prevNodeId;
    }

    public int getCost() {
        return m_cost;
    }

    @Override
    public String toString() {

        return m_nodeId + " (" + m_arcId + ") weight: " + m_weight;
    }
}

I am not able to figure out the reason for bad performance, please help me identify one.

Answer 1

You should check how many nodes are explored before you find the solution.

You can than try to improve your overestimation-function (heuristic) for the cost of the remaining path to reduce the number of explored nodes.

In general the performance of a A*-Algorithm mainly depends on the heuristic you use not really on the optimization of the code. So try to put as much domain knowledge into your heuristic as possible to reduce the number of explored nodes.