Thread: 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.

 
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.

 
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.

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.