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.

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.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; } }