To answer your second question concerning what data structure to use for the open list:
I've implemented A* using a simple TreeSet which assumes the 'nodes' implement Comparable. Works fine, TreeSet is relatively fast, and provides a getFirst() method.
The only issue is that by default it ignores duplicate entries, i.e. nodes that have the same score. So you need to code the compareTo() method so that nodes with the same score are not 'equivalent', i.e.
class Node implements Comparable< Node >
{
private int score;
public int compareTo( Node node )
{
if( node.score == this.score )
{
return -1; // pretend nodes are not equivalent to allow duplicate entries in the open list
}
else
{
return this.score - node.score;
}
}
…
}
Weelll. I had another look at the algorithm. I thought i could eliminate the the CLOSED list from the algorithm, so that parent nodes could be garbage collected. But i can't really since:
if n' is on the CLOSED list and the existing one is as good or better then discard n' and continue
So the idea of copying stuff downward will only work if…
- CLOSED is not a list but a HashMap, whose key is a unique code for each "equivalent" state and value the Cost
Anyway my problem with the Data structure for the lists is not the duplicates, yet, but the:
if n' is on the OPEN list and the existing one is as good or better then discard n' and continue
line implies that we can get the information that the "existing one" is as good or better that the current value.
That information is the cost, and the cost is encapsulated into the state itself, so the normal reaction is to get the object,
and get the cost off it. How ever all Abstract Set classes only have the method:
boolean remove(Object o) and no get()
I guess a solution is to copy the the cost to the hashmap uncondicionaly like this:
public final AStarState solve (AStarState initialState)
{
CLOSED.put(initialState.getCode(), initialState.getCost());
OPEN.offer(initialState);
while(!OPEN.isEmpty()){
AStarState currentState = (AStarState) OPEN.poll();//Take the most prioritary
if(currentState.isFinalState()){
return currentState;
}
else{
for(AStarState child : currentState.getChildren()){//Prune replicates here (including already scheduled loops)
//if node_successor is on the OPEN list but the existing one is as good or better then discard this successor and continue
//if node_successor is on the CLOSED list but the existing one is as good or better then discard this successor and continue
if(CLOSED.get(child.getCode()) >= child.getCost()){
continue;
}
else{
CLOSED.put(currentState.getCode(), currentState.getCost());
OPEN.remove(child);
OPEN.offer(child);//merry go round
}
}
//the currentState instance goes out of scope and is garbage collected,
//if the child didn't save its parent. The child has two options, to save the parent
//or to copy the information it needs
}
}
return null; //WE HAVE FAILED! I'm going to be here another year!
}
And the child keeps a reference to the parent or copies the values consoant implementation.
Right?
I'm not sure if this matters, but that comparator isn't really valid, because it doesn't have a<b equivalent to b>a. It will only make a difference if TreeSet depends on a valid ordering, not sure whether it does. How you get round that, I'm not sure, if nothing else you can give each node a long index when you make it, but that seems like a waste of memory 
You might also want to implement hashcodes and equals() to match up with the comparator, and add the special case that a node should be equal to itself in that comparison.
FAO: i30817
If I'm following you, your issue is with updating closed nodes when a better path has been found yes?
In the standard A* implementation there are three data-structures:
- the open set (TreeSet)
- the closed set (any Collection)
- and something that maps between the 'world' and the set of nodes (whether open or closed)
The latter is important in that it's the means of identifying any existing nodes that are adjacent to the current node. This is case-dependant - in the implementation I developed for a large terrain RPG game it's a grid (i.e. a 2D array) that allows me to lookup an existing node at a given co-ordinate if one exists and modify it's score and parent node as appropriate.
Therefore there is no need to 'get' a node from the closed list.
FAO: shingoki
Not sure what you mean by
a<b equivalent to b>a? Or are you talking about the case of a node being compared to itself? (shouldn't happen in my implementation so I could alter the compareTo() method to assert this).
The order of the elements in a TreeSet is determined by the natural ordering of the elements (if no specific comparator is supplied), e.g. alphabetic for strings, or is defined by the explicit Comparator provided by implementing Comparable. If you look at the JavaDoc for Comparable it recommends that a class that implements Comparable is also consistent with the equals / hashCode contract, and a class that doesn't support this is violating the Set interface. But as A* (or at least my implementations of it) never need to explicitly compare nodes for equality but rely on the fact that TreeSet uses the comapreTo() method I don't bother implementing equals and hashCode - in fact I very rarely do.
I am in fact thinking that using a genetic algorithm would give more acceptable results more quickly. I'm just going to try to complete the heuristic given, and if it chokes on a simple 3 processor 600 nodes problem, i'm going to try g.a. Only 12 days until delivery though.
Yup you don't need to implement equals and hash unless you use them of course I was indeed referring to the recommendation that they be consistent, I normally try to implement them so that I don't forget about it and trip up later.
The a<b, b>a thing is just that if you have an ordering, and you get a.compareTo(b) = -1, you should get b.compareTo(a) = 1. That is, if a really is "bigger than" b, you would expect b to be "smaller than" a, they can't both be bigger than the other. I think that has a fancy name, I can't remember it though I don't know whether TreeSet relies on this, but it seems like it might do. If you end up with two equal scoring nodes, TreeSet should logically try to put them both first, if they are both greater than the other In actual fact that might end up resolving itself, maybe the second one inserted will put itself first, and it will all work.
Yeah I see your point and an operation that behaves like that is called transitive.
It does seem to work but you've got me worried now, I'll have to beef up my unit-tests next time I get round to working on it!
If I can just worry one person each day, I feel I have a purpose 
Implementing compareTo or equals wrong, or forgetting to implement it at all can be a really hard to detect error.
So yes, you can be proud to scare people with this XD
several months on - any wise tips to share ?
pondering on doing some a* and offering it as a jme demo - after all, as much help can be offered to new commers the better for the community
i've implemented an A* algorithm in java myself, but i'm not sure what kind of performance to expect. What is a good test to do, and what kind of numbers should i see?