Hi guys, I’m here to get help but to share something too.
I’ve done an implementation of the A* algorithm and the graphics part too, it works but it need to be optimized.
In the src folder u will find 2 packages, in astar/Astar.java there is the algorithm, but to implement the opened list i had to use a LinkedList, i couldn’t make it work with the TreeSet, maybe i was doing something weird with the Comparator.
The second thing i would like to resolve, once i press esc the window quit but the app keeps running, i noticed it because i’m on a Mac and the icon app is there until i force quit.
The code isn’t so clean but considering that you only need to open the Astar class and maybe the Square one, i would really like that someone can check it to give some tips.
The code: A_star.zip
Edit: If someone want to test the app, once you launch it, you can use the right click to make the tiles walkable/unwalkable and the left click to tell the “player” to go there.
Ok i cleaned up a bit and resolved the part where it keeps running after che quit command, i had to stop the ScheduledThreadPoolExecutor that i used to fine the path. Someone can tell me how can i get it working with a better data structure than the LinkedList? I refer to the opened list. It’s not i didn’t tried to do it, you can even see the comparator i used in the TreeSet, and i spent about two days to repair some bugs to let it run without strange behaviours. I wanted to share it too, so beginners trying to implement this thing will have a start point (it’s only a square finding a way on a grid, but I implemented a version that find a new road when the path it found isn’t valid, so i consider it a good start point 
).
[java]
//imports
public class Astar {
private static Square getFirst(LinkedList<Square> openedSet) {
Square x = openedSet.get(0);
int min = x.getfScore();
for(Square s: openedSet)
if(s.getfScore() < min){
min = s.getfScore();
x=s;
}
return x;
}
/*
private static class SquareFScoreComparator implements Comparator<Square> {
public int compare(Square t, Square t1) {
int ris = t.getfScore() - t1.getfScore();
if(ris != 0)
return ris;
else if(t.x == t1.x && t.y == t1.y)
return 0;
// i should return a value based on a second heuristic, but i don’t need so much precision.
else return -1;
}
}
*
/
public static List<Square> Astar(Square start, Square goal) {
/ start initialize /
HashSet<Square> closedSet = new HashSet<Square>();
LinkedList<Square> openedSet = new LinkedList<Square>();
openedSet.add(start);
HashMap<Square, Square> cameFrom = new HashMap<Square, Square>();
start.setgScore(0);
start.sethScore(heuristicCostEstimate(start, goal));
start.setfScore(start.gethScore());
/ end initialize */
while (!openedSet.isEmpty()) {
Square x = getFirst(openedSet);
if (x == goal) {
List<Square> reconstructPath = reconstructPath(cameFrom, x);
reconstructPath.remove(0);
return reconstructPath;
}
openedSet.remove(x);
closedSet.add(x);
for (Square y : x.takeAdjacents()) {
if (!y.isWalkable() || closedSet.contains(y)) {
continue;
}
int tentativeGScore = x.getgScore() + 1;
boolean tentativeIsBetter;
boolean notContained = false;
if (!openedSet.contains(y)) {
notContained = true;
tentativeIsBetter = true;
} else if (tentativeGScore < y.getgScore()) {
tentativeIsBetter = true;
} else {
tentativeIsBetter = false;
}
if (tentativeIsBetter) {
cameFrom.put(y, x);
y.setgScore(tentativeGScore);
y.sethScore(heuristicCostEstimate(y, goal));
y.setfScore(y.getgScore() + y.gethScore());
if(notContained)
openedSet.add(y);
}
}
}
return null;
}
private static int heuristicCostEstimate(Square start, Square goal) {
return Math.abs(start.getX() - goal.getX()) + Math.abs(start.getY() - goal.getY());
}
private static List<Square> reconstructPath(HashMap<Square, Square> map, Square currentNode){
if(map.get(currentNode) != null){
List<Square> p = reconstructPath(map, map.get(currentNode));
p.add(currentNode);
return p;
}
else{
List<Square> p = new LinkedList<Square>();
p.add(currentNode);
return p;
}
}
}
[/java]
Some time ago, i made DynamicPriorityQueue. An interface describing priority queue in which its possible to change priority of already inserted element. And then I implemented it using a heap.
Key idea of this is, when you insert element, you get back object that contains index (or something like it) of inserted element and which gets updated when queue is reordered.
When used as normal DynamicQueue, it performs around 2 times slower than java.util.DynamicQueue, which I consider acceptable (if added functionalyty is usefull).
You should be able to use it in your A*.
Using this, I made tile based A* with euclidean heuristics and with heuristic based on pathfinding through downsampled tile map (using minimum of costs of tiles in supertile).
The second heuristic led to quite big improvement unless fooled by thin walls (which are invisible in downsampled map).
Unfortunately, javadoc i wrote is quite minimal and in Czech, and I because of current problems with plugins in JMP, swing wersion of pathfinding application does not compile (I had to reinstall JMP and installing GUIbuilder plugin fails, and my swing app depends on it (or better to say on bean-binding).
But, here it is anayway
If someone want to actualy use it, contact me and I’ll add license (something like LGPL or other permisive license)
I ended up using the java.util.PriorityQueue, maybe the TreeSet was having problem with the Squares having the same F score. I have to thank Alpedar however, I didn’t think to use a Queue, I was stuck with the Set. I replaced the file in the link, who wants can use it freely.
Some time ago I tried several Collections to find out whats the most efficient. I ended up not using anything from the standard java collections, since none of them were fast enough.
I used org.apache.commons.collections.buffer.PriorityBuffer
http://commons.apache.org/collections/api-release/org/apache/commons/collections/buffer/PriorityBuffer.html
… which is basically a BinaryHeap. The only problem here was, that you can only remove the first Object, but not resort if F is changing. So I subclassed it the following way:
[java]
class BinaryHeap extends PriorityBuffer {
BinaryHeap(Comparator comp) {
super(comp);
}
void resort(Node p) {
int i = 0;
for (; i <= this.size; ++i) {
if (p == elements) {
break;
}
}
percolateUpMinHeap(i);
}
}
[/java]
That did the job for me, and its really fast. Otherwise you could implement your own BinaryHeap that fits to your needs.
BTW your reconstructPath method could run into problems when the stack gets to big. I wouldn’t use recursion here. If you like recursion don’t use Java, use Scala http://www.scala-lang.org/ 
I thought to use this thing with little movements, but you got a point with the recursion, i will fix it to make it more flexible. Recursion is slowly too… I will do some test with the structure i’m using, the BinaryHeap, and if i don’t get too lazy with something implemented by me I saw a bunch of people using his own structure to optimize the algorithm. Thanks for the tips, they’re always welcome