[C++, Java] What are the requirements for implementing an A star algorithm?

[tom_mai78101]

I'm thinking of understanding the requirements for implementing an A star algorithm. It's like this bane of my programming talent, I need to overcome that, otherwise I'm not improving myself.
tag: A-star, Astar, astar, A*, algorithm
The best way to describe this question:

I know that for an A-star algorithm, I need to have an open set (with the starting node included, this set is for checking on nodes that are potential nodes to be added to the closed set) and an closed set (this set is for gathering potential nodes and find the shortest path that beelines from the start to the goal). Other than these two objects, I don't know what the rest of the objects are used for.

According to the Wikipedia article, there is supposed to be a Map object used. What does this Map object refer to in the code? What is the equivalent in C++? In Java?

And then there's this heuristic cost estimate. I do know that for every small area from the starting node to the finishing node, each node have a value set to it that calculates which nodes, when added to the closed set, will make the total heuristic score count be the lowest of them all, and the relevant nodes will be called as the shortest path. And that there are two heuristic scorekeepers. What are they?

Where do you start initializing the heuristic score just when the A star algorithm starts kicking in at the beginning?

My Chinese text Algorithm book just doesn't cut it without translating to English.

EDIT: Working Astar algorithm in Java

 

[Accname]

I made a little test program in Ruby once when I was a little kid going to school.
You can have a look, it displays the approximated costs and the open / close list very nicely with visual data.

My algorithm looked something like this:

def find_path(start_node, target_node)
    // open_nodes holds all nodes which have not been expanded yet
    open_nodes = [start_node]
    current_node = start_node
    final_node = start_node
 
    loop
        if open_nodes.empty?
            // end if no nodes can be expanded anymore == no path found
            throw NO_RESULT
        end
 
        if current_node.x == target_node.x && current_node.y == target_node.y
            // end if we reached the target node
            final_node = current_node
            break
        else
            // continue expanding the lists if we are still looking for the path
            expand_node(current_node, open_nodes, target_node)
            current_node = find_node_with_lowest_approx_value()
        end
    end
    return RESULT
end
 
def expand_node(current_node, open_nodes, target_node)
    // iterate through every adjacent node of the current node and add it to the open_nodes array
    for adj_node in current_node.adjacent_nodes
        // if the node is already closed it cannot be opened again
        // if the node has an exact value it has been expanded already
        next if adj_node.closed || adj_node.exact_value != 0
 
        // calculate the approximated distance to the end node
        approx_distance = Math.hypot(adj_node.x - target_node.x,   adj_node.y - target_node.y) * 2
 
        // the exact costs to reach this node
        exact_value = current_node.exact_value + adj_node.cost
 
        // the approximated costs from this node to the end node
        approx_value = approx_distance + exact_value
 
        adj_node.exact_value = exact_value
        adj_node.approx_value = approx_value
        adj_node.predecessor = current_node
        open_nodes.add(adj_node)
    end
    // after a node has been expanded it is closed
    open_nodes.delete(current_node)
    current_node.closed = true
end
 
 
class Node
  // the coordinates of this node
  attr_reader :x
  attr_reader :y
  
  // these attributes are used by the pathfinding algorithm
  // whether the node has been expanded or not
  attr_accessor :closed
  // Exact costs to reach this node
  attr_accessor :exact_value
  // Approximated costs to reach target node from this node
  attr_accessor :approx_value
  // The costs it takes to pass over this node
  attr_reader :cost
  // an array with all adjacent nodes
  attr_accessor :adjacent_nodes
  // the predecessor of this node in the currently calculated move_route
  attr_accessor :predecessor
  
end

Here is a small script which shows the pathfinding in action with visual aid.
Only runs on windows though since this is Ruby with RGSS as a windowing and graphics library.

 

[tom_mai78101]

Accname, your program stalled after I pressed the "Start" button. Am I doing it right?

Anyway, I looked at your code, got confused, looked back at the Wikipedia article, got way more confused, Googled around, found a site that explicitly tells you about the F(x), G(x), H(x), and the cost of all three of them.

The code below is in Java. I am wondering if I'm doing it right.

package main;
 
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
 
public class Atsr {
 
    public static class Node {
        ArrayList<Node> neighbors = new ArrayList<Node>();
        Node parent;
     
        /*
        *
        * Where I got this:              http://nakkaya.com/2010/06/01/path-finding-using-astar-in-clojure/
        *
        *    g(x) - cost of getting to that node from starting node.
        *  h(x) - cost of getting to the goal node from current node.
        *  f(x) - g(x)+h(x)
        *
        */
 
        int g_costFromStartToThisNode;
        int h_costFromThisNodeToGoal;
        int f_costOfGandH;
     
        int x;
        int y;
     
        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
     
        public ArrayList<Node> calculateAdjacentNodes() {
            ArrayList<Node> results = new ArrayList<Node>();
            results.clear();
            for (int yy = this.y - 1; yy < this.y + 1; yy++) {
                if (yy < 0 || yy > 480)
                    continue;
                for (int xx = this.x - 1; xx < this.x + 1; xx++) {
                    if (xx < 0 || xx > 640)
                        continue;
                    if (xx == this.x && yy == this.y)
                        continue;
                    results.add(new Node(xx, yy));
                }
            }
            return results;
        }
    }
 
    public static void main(String[] arg) {
     
        Node start = new Node(10, 10);
        Node goal = new Node(50, 100);
     
        boolean failed = false;
     
        ArrayList<Node> open = new ArrayList<Node>();
        ArrayList<Node> closed = new ArrayList<Node>();
        ArrayList<Node> path = new ArrayList<Node>();
     
        Node current = start;
        open.add(current);
 
        while (true) {
 
            Collections.sort(open, new Comparator<Node>() {
                @Override
                public int compare(Node a, Node b) {
                    if (a.f_costOfGandH < b.f_costOfGandH)
                        return -1;
                    if (a.f_costOfGandH > b.f_costOfGandH)
                        return 1;
                    return 0;
                }
            });
            current = open.remove(0);
            closed.add(current);
         
            ArrayList<Node> adjacentNodes = current.calculateAdjacentNodes();
            for (Node n : adjacentNodes) {
                if (closed.contains(n)) {
                    adjacentNodes.remove(n);
                }
            }
            for (Node n : adjacentNodes) {
                if (!open.contains(n)) {
                    n.g_costFromStartToThisNode = estimateDistance(start, n);
                    n.h_costFromThisNodeToGoal = estimateDistance(n, goal);
                    n.f_costOfGandH = n.g_costFromStartToThisNode + n.h_costFromThisNodeToGoal;
                    n.parent = current;
                    open.add(n);
                }
                if (open.contains(n)) {
                    if (n.g_costFromStartToThisNode > current.g_costFromStartToThisNode) {
                        n.parent = current;
                        n.g_costFromStartToThisNode = estimateDistance(start, current);
                        n.h_costFromThisNodeToGoal = estimateDistance(current, goal);
                        n.f_costOfGandH = n.g_costFromStartToThisNode + n.h_costFromThisNodeToGoal;
                        open.remove(n);
                        closed.add(n);
                    }
                }
            }
 
            //Until...
            if (closed.contains(goal)) {
                break;
            }
            if (open.size() <= 0) {
                System.out.println("No more paths to take.");
                failed = true;
                break;
            }
        }
     
        if (!failed) {
            while (current != start) {
                path.add(current);
                current = current.parent;
            }
        }
    }
 
    private static int estimateDistance(Node start, Node goal) {
        return Math.abs(start.x - goal.x) + Math.abs(start.y - goal.y);
    }
}

 

[Accname]

As the infor text at the beginning of the program tells you, the algorithm will update each time you hit the >enter< key.
If you keep it pressed it will update continuously.

My ruby implementation is somewhat optimized.
For example, you do not need any "closed" set. You only use it to keep track of which nodes have been closed and which havent. For that you do not need a data structure, you can simply keep track of this via a boolean variable inside you node class.