# A Star Pathfinding algorithm optimization

• May 16th, 2011, 12:08 PM
randomcracker
A Star Pathfinding algorithm optimization
Hi anyone have any idea of how I can optimize my implementation of the A* pathfinding algorithm? Here is my code, it's made for Android but I'm guessing most of it is normal Java.
Pathfinder class.
Code Java:

```  import java.util.ArrayList;     import com.levitas.Util;   public class Pathfinder { public static ArrayList<Node> Open = new ArrayList<Node>(); public static ArrayList<Node> Closed = new ArrayList<Node>(); public static ArrayList<Node> Final = new ArrayList<Node>(); static boolean hasFoundPath; static Map nodez; static final Vec2 Start = new Vec2(), End = new Vec2(); static Node checknext = null; static int checknextI = 0; static Node finalNode; static boolean done = true;     public static Vec2[] findPath(Map map, Node start, Vec2 end) { done=false; hasFoundPath=false; checknextI = 0; checknext = finalNode = null; Start.inherits(start); End.inherits(end); nodez = map; Open.clear(); Closed.clear(); Final.clear(); Open.add(start); while(true) { //Loop for finding node with lowest F. for(int i=0; i<Open.size(); i++) { if(hasFoundPath) break; if(checknext==null) {checknext = Open.get(i); checknextI=i; continue;} if(Open.get(i).getF()<checknext.getF()) {checknext = Open.get(i); checknextI=i;} } if(hasFoundPath) break; Closed.add(Open.get(checknextI)); Open.remove(checknextI); Closed.get(Closed.size()-1).spawn(); if(hasFoundPath) break; } return finalNode.getFinalPath(); } public static int GetF(int x, int y, int G) { return G+((Util.pos(End.x-x)+Util.pos(End.y-y))*10); }   }```

Node class.
Code Java:

```  class Node extends Vec2 { Node parent; int G, H; public Node(int x, int y, int G, Node parent) { this.parent = parent; set(x, y); this.G = G; //ADD 10/14 ON THIS!!!!!!!!!!!!!!!!!! H = (Util.pos(Pathfinder.End.x-x)+Util.pos(Pathfinder.End.y-y))*10; } public Node() { this.G = 0; this.parent = null; } public void inherit(Vec2 v) { this.x = v.x; this.y = v.y; } public int getF() { return G+H; } public Node(Vec2 v) { this(v.x, v.y, 0, null); } public void spawn() { if(Pathfinder.End.x==x && Pathfinder.End.y==y){Pathfinder.finalNode = this; Pathfinder.hasFoundPath=true; return;} addz(x-1, y, G+10); addz(x-1, y-1, G+14); addz(x, y-1, G+10); addz(x+1, y-1, G+14); addz(x+1, y, G+10); addz(x+1, y+1, G+14); addz(x, y+1, G+10); addz(x-1, y+1, G+14); } private void addz(int x, int y, int G) { if((Pathfinder.nodez.get(x, y))==null || Pathfinder.hasFoundPath) return;   for(int i=0; i<Pathfinder.Closed.size(); i++) if(Pathfinder.Closed.get(i).x==x && Pathfinder.Closed.get(i).y==y) return;   for(int i=0; i<Pathfinder.Open.size(); i++) if(Pathfinder.Open.get(i).x==x && Pathfinder.Open.get(i).y==y && Pathfinder.Open.get(i).G < G) return; else if(Pathfinder.Open.get(i).x==x && Pathfinder.Open.get(i).y==y) Pathfinder.Open.remove(i);   if(Pathfinder.nodez.get(x, y).canUse()) Pathfinder.Open.add(new Node(x, y, G, this)); } public Vec2[] getFinalPath() { Node tmp = Pathfinder.finalNode; Vec2[] returned; while(true) { Pathfinder.Final.add(tmp); tmp = tmp.parent; if(tmp == null) break; } returned = new Vec2[Pathfinder.Final.size()+1]; returned[0] = Pathfinder.Start; for(int i=Pathfinder.Final.size()-1;i>-1;i--) returned[Pathfinder.Final.size()-i] = Pathfinder.Final.get(i);   returned[returned.length-1] = Pathfinder.End; Pathfinder.done = true; return returned; } }```
The Vec2 class consists of two simple coordinate points. The Map object contains an array of instances of a class that contains attributes for the two dimensional tilebased world. The only idea I have of an optimization is to use an individual two dimensional array for each attribute instead but I'm unsure of if that would help at all. Please post any thoughts on the subject. Also I appologise for any unclearities and incorrect english.
• May 16th, 2011, 12:26 PM
KevinWorkman
Re: A Star Pathfinding algorithm optimization
If you want help, I'd suggest providing an SSCCE that demonstrates the problem. For example, are you experiencing performance issues? Are they all the time? Do you know which part of the code is bogging it down?
• May 16th, 2011, 01:08 PM
copeg
Re: A Star Pathfinding algorithm optimization
What makes you believe it needs optimization? If you have something which suggests it is not optimal, I'd recommend profiling the code, printing out the times it takes for certain tasks to complete - quite often the result is not what you expected, so you can spend time optimizing the true bottleneck rather than spending time optimizing something that saves you a few milliseconds here or there.
• May 16th, 2011, 01:38 PM
randomcracker
Re: A Star Pathfinding algorithm optimization
Thanks for the fast replies, I appreciate it. I'm working on a Windows Port(Shouldn't take long). I believe it needs optimization on the grounds that it runs slowly on my Android device while every example implementation of the algorithm I've tested have run incredibly smooth taking only a few milliseconds to fully complete. On my device a path of 20 squares can take 2 seconds to calculate. I have tested rts games on the device and they all have Pathfinding algorithms that finishes in under half a second. I'll get back to you with a SSCCE.
• May 18th, 2011, 11:11 PM
helloworld922
Re: A Star Pathfinding algorithm optimization
Try taking a look at A* Pathfinding for Beginners. Section 6 has some tips on how to get a faster implementation of the algorithm.