   Is this the most efficient way to implement A* in java for Dalvik VM?
  Code will follow, but for now this is my current A* implementation to find a path in a 2D world where the player can only move up, down, left and right and never diagonal.  The target platform is Android so it needs to be extremely fast in the Dalvik VM.Right now, 40 iterations runs in 8-9ms on my emulator.  That seems really slow to me.  I've already gone through and done lots of optimizations on this code and I'm getting to the point where I'm not sure if there are better ways to do this.  My target performance is 200 iterations in 8-9ms.  Anyone?(This is old code - see the most recent post for the current code)import java.util.ArrayList;import java.util.Collections;public class AStar {/** The set of map that have been searched through */private ArrayList<AITile> closed = new ArrayList<AITile>();/** The set of map that we do not yet consider fully searched */private ArrayList<AITile> open = new ArrayList<AITile>();/** The return path */private ArrayList<AITile> path = new ArrayList<AITile>();/** The map being searched */private AITile[][] map;/** The maximum depth of search we're willing to accept before giving up */private int maxSearchDistance;private int maxIterations;private int mapWidth;private int mapHeight;/** * Create a path finder  *  * @param heuristic The heuristic used to determine the search order of the map * @param map The map to be searched * @param maxSearchDistance The maximum depth we'll search before giving up */public AStar(AITile[][] map, int mapWidth, int mapHeight, int maxSearchDistance, int maxIterations) {this.map = map;this.mapWidth = mapWidth;this.mapHeight = mapHeight;this.maxSearchDistance = maxSearchDistance;this.maxIterations = maxIterations;}/** * @see PathFinder#findPath(Mover, int, int, int, int) */public ArrayList<AITile> findPath(int sx, int sy, int tx, int ty) {// easy first check, if the destination is blocked, we can't get thereAITile[][] map = this.map;ArrayList<AITile> closed = this.closed;ArrayList<AITile> open = this.open;int maxSearchDistance = this.maxSearchDistance;int maxIterations = this.maxIterations;if (map[tx][ty].state == AITile.CLOSED) {return null;}// initial state for A*. The closed group is empty. Only the starting// tile is in the open list and it'e're already theremap[sx][sy].cost = 0;map[sx][sy].depth = 0;closed.clear();open.clear();open.add(map[sx][sy]);map[tx][ty].parent = null;// while we haven'n't exceeded our max search depthint maxDepth = 0;// reusable declarations for this loop and nested loopsAITile current;int x, y;int xp, yp;float nextStepCost;AITile neighbor;float hc;boolean added;int iterations = 0;while ((iterations < maxIterations) && (maxDepth < maxSearchDistance) && (open.size() != 0)) {iterations++;// pull out the first AITile in our open list, this is determined to // be the most likely to be the next step based on our heuristiccurrent = open.get(0);//System.out.println("A-Star examining tile [" + current.x + "," + current.y + "]");if (current == map[tx][ty]) {break;}open.remove(current);closed.add(current);// search through all the neighbors of the current AITile evaluating// them as next stepsfor (x = -1; x < 2; x++) {for (y = -1; y < 2; y++) {// not a neighbor, its the current tileif ((x == 0) && (y == 0)) {continue;}// if we're not allowing diagonal movement then only// one of x or y can be setif ((x != 0) && (y != 0)) {continue;}// determine the location of the neighbor and evaluate itxp = x + current.x;yp = y + current.y;if (isValidLocation(map, sx, sy, xp, yp)) {// the cost to get to this AITile is cost the current plus the movement// cost to reach this AITile. Note that the heuristic value is only used// in the sorted open listnextStepCost = current.cost;neighbor = map[xp][yp];map[xp][yp].visited = true;// if the new cost we've determined for this AITile is lower than // it has been previously makes sure the AITile hasn'e've// determined that there might have been a better path to get to// this AITile so it needs to be re-evaluatedif (nextStepCost < neighbor.cost) {if (open.contains(neighbor)) {open.remove(neighbor);}if (closed.contains(neighbor)) {closed.remove(neighbor);}}// if the AITile hasn't already been processed and discarded the// reset it's cost to our current cost and add it as a next possible// step (i.e. to the open list)if (!open.contains(neighbor) && !(closed.contains(neighbor))) {neighbor.cost = nextStepCost;neighbor.heuristic = getHeuristicCost(xp, yp, tx, ty);maxDepth = Math.max(maxDepth, neighbor.setParent(current));//System.out.println("neighbor [" + neighbour.x + "," + neighbour.y + "] now has parent [" + current.x + "," + current.y + "]");//Add to open in order of heuristic + costhc = nextStepCost + neighbor.heuristic;added = false;for (int i = 0; i < open.size(); i++) {AITile tile = open.get(i);if (hc < tile.cost + tile.heuristic) {open.add(i, neighbor);added = true;break;}}if (!added) {open.add(neighbor);}}}}}}// since we'e've run out of search // there was no path. Just return nullif (map[tx][ty].parent == null) {return null;}// At this point we've definitely found a path so we can uses the parent// references of the map to find out way from the target location back// to the start recording the map on the way.// thats it, we have our path path.clear();AITile target = map[tx][ty];while (target.x != sx || target.y != sy) {path.add(target);target = target.parent;}Collections.reverse(path);return path;}/** * Check if a given location is valid for the supplied mover *  * @param mover The mover that would hold a given location * @param sx The starting x coordinate * @param sy The starting y coordinate * @param x The x coordinate of the location to check * @param y The y coordinate of the location to check * @return True if the location is valid for the given mover */protected boolean isValidLocation(AITile[][] map, int sx, int sy, int x, int y) {if ((x < 0) || (y < 0) || (x >= mapWidth) || (y >= mapHeight)) {return false;}if (((sx != x) || (sy != y))) {return (map[x][y].state != AITile.CLOSED);}return true;}/** * Get the heuristic cost for the given location. This determines in which  * order the locations are processed. *  * @param mover The entity that is being moved * @param x The x coordinate of the tile whose cost is being determined * @param y The y coordiante of the tile whose cost is being determined * @param tx The x coordinate of the target location * @param ty The y coordinate of the target location * @return The heuristic cost assigned to the tile */public float getHeuristicCost(int x, int y, int tx, int ty) {float dx = tx - x;float dy = ty - y;float result = (float) (Math.sqrt((dx*dx)+(dy*dy)) * 1.02f);// stupid euclidean distance.  try manhattan instead with 1/50th tiebreaker//float result = (Math.abs(x - tx) + Math.abs(y - ty)) * 1.02f;return result;}}public class AITile {public static final int OPEN = 0;public static final int CLOSED = 1;public static final int SELF = 2;public static final int TARGET = 3;public static final int INVALID = 4;public int state = OPEN;public int topLeftX;public int topLeftY;public int width;public int height;public int x;public int y;// A* Stuffpublic float cost;/** The parent of this node, how we reached it in the search */public AITile parent;/** The heuristic cost of this node */public float heuristic;/** The search depth of this node */public int depth;public boolean visited;public void resetAStar() {x = 0;y = 0;cost = 0f;parent = null;heuristic = 0f;depth = 0;visited = false;}public int setParent(AITile parent) {depth = parent.depth + 1;this.parent = parent;return depth;}}[Edited by - rbgrn on May 15, 2009 1:40:07 PM]
  I got rid of the open/closed lists, switching instead to a doubly-linked list for open and just booleans on the nodes for closed.  This made a tremendous difference, I believe performance has increased 2-4 times but I have nothing empirical to show that.  I just know that with the game running with no A-Star iteration limit, the longest search I'm seeing is 16ms.  If I can double the speed once more, I'll have it down to 8ms which will fit my worst-case CPU budget.Here's the next iteration of code that uses a linked list for the open queue:(this is still not current.  see the newest posted code.)import java.util.ArrayList;import java.util.Collections;public class AStar {/** The return path */private ArrayList<AITile> path = new ArrayList<AITile>();/** The map being searched */private AITile[][] map;/** The maximum depth of search we're willing to accept before giving up */private int maxSearchDistance;private int maxIterations;private int mapWidth;private int mapHeight;/** * Create a path finder *  * @param heuristic *  The heuristic used to determine the search order of the map * @param map *  The map to be searched * @param maxSearchDistance *  The maximum depth we'll search before giving up */public AStar(AITile[][] map, int mapWidth, int mapHeight, int maxSearchDistance, int maxIterations) {this.map = map;this.mapWidth = mapWidth;this.mapHeight = mapHeight;this.maxSearchDistance = maxSearchDistance;this.maxIterations = maxIterations;}/** * @see PathFinder#findPath(Mover, int, int, int, int) */public ArrayList<AITile> findPath(int sx, int sy, int tx, int ty) {// easy first check, if the destination is blocked, we can't get thereAITile[][] map = this.map;int maxSearchDistance = this.maxSearchDistance;int maxIterations = this.maxIterations;int mapWidth = this.mapWidth;int mapHeight = this.mapHeight;if (map[tx][ty].state == AITile.CLOSED) {return null;}// initial state for A*. The closed group is empty. Only the starting// tile is in the open list and it'e're already theremap[sx][sy].cost = 0;map[sx][sy].depth = 0;// this is where the open list startsAITile firstOpen = map[sx][sy];firstOpen.isAstarOpen = true;map[tx][ty].pathParent = null;// while we haven'n't exceeded our max search depthint maxDepth = 0;// reusable declarations for this loop and nested loopsAITile current;int x, y;int xp, yp;float nextStepCost;AITile neighbor;float hc;int iterations = 0;while ((iterations < maxIterations) && (maxDepth < maxSearchDistance) && (firstOpen != null)) {iterations++;// pull out the first AITile in our open list, this is determined to// be the most likely to be the next step based on our heuristiccurrent = firstOpen;// System.out.println("A-Star examining tile [" + current.x + "," + current.y + "]");if (current == map[tx][ty]) {break;}current.isAstarOpen = false;// This may assign firstOpen to null.firstOpen = current.openNext;if (firstOpen != null) {firstOpen.openPrev = null;}current.isAstarClosed = true;// search through all the neighbors of the current AITile evaluating// them as next stepsfor (x = -1; x < 2; x++) {for (y = -1; y < 2; y++) {// not a neighbor, its the current tileif ((x == 0) && (y == 0)) {continue;}// if we're not allowing diagonal movement then only// one of x or y can be setif ((x != 0) && (y != 0)) {continue;}// determine the location of the neighbor and evaluate itxp = x + current.x;yp = y + current.y;if (isValidLocation(map, sx, sy, xp, yp, mapWidth, mapHeight)) {// the cost to get to this AITile is cost the current plus the movement// cost to reach this AITile. Note that the heuristic value is only used// in the sorted open listnextStepCost = current.cost;neighbor = map[xp][yp];map[xp][yp].visited = true;// if the new cost we've determined for this AITile is lower than// it has been previously makes sure the AITile hasn't// determined that there might have been a better path to get to// this AITile so it needs to be re-evaluatedif (nextStepCost < neighbor.cost) {// remove from open listneighbor.isAstarOpen = false;if (neighbor.openPrev != null) {neighbor.openPrev.openNext = neighbor.openNext;}neighbor.openNext = null;// it's neither open nor closed.neighbor.isAstarClosed = false;}// if the AITile hasn't already been processed and discarded the// reset it's cost to our current cost and add it as a next possible// step (i.e. to the open list)if (!neighbor.isAstarClosed && !neighbor.isAstarOpen) {neighbor.cost = nextStepCost;neighbor.heuristic = getHeuristicCost(xp, yp, tx, ty);maxDepth = Math.max(maxDepth, neighbor.setParent(current));// System.out.println("neighbor [" + neighbour.x + "," + neighbour.y + "] now has parent ["// + current.x + "," + current.y + "]");// Add to open in order of heuristic + costhc = nextStepCost + neighbor.heuristic;// we're opening it, so let's just mark it now.neighbor.isAstarOpen = true;if (firstOpen == null) {firstOpen = neighbor;} else {AITile tile = firstOpen;while (true) {// find the spot to insert it, either at the beginning, middle or end.if (hc < tile.cost + tile.heuristic) {// insert this node before tileneighbor.openNext = tile;neighbor.openPrev = tile.openPrev;if (tile.openPrev == null) {// head of list.firstOpen = neighbor;} else {tile.openPrev.openNext = neighbor;}tile.openPrev = neighbor;break;}if (tile.openNext == null) {// hc was bigger than all current values - it goes on the end.tile.openNext = neighbor;neighbor.openPrev = tile;break;}tile = tile.openNext;}}}}}}}// since we'e've run out of search// there was no path. Just return nullif (map[tx][ty].pathParent == null) {return null;}// At this point we've definitely found a path so we can uses the parent// references of the map to find out way from the target location back// to the start recording the map on the way.// thats it, we have our pathpath.clear();AITile target = map[tx][ty];while (target.x != sx || target.y != sy) {path.add(target);target = target.pathParent;}Collections.reverse(path);return path;}/** * Check if a given location is valid for the supplied mover *  * @param mover *  The mover that would hold a given location * @param sx *  The starting x coordinate * @param sy *  The starting y coordinate * @param x *  The x coordinate of the location to check * @param y *  The y coordinate of the location to check * @return True if the location is valid for the given mover */protected boolean isValidLocation(AITile[][] map, int sx, int sy, int x, int y, int mapWidth, int mapHeight) {if ((x < 0) || (y < 0) || (x >= mapWidth) || (y >= mapHeight)) {return false;}if (((sx != x) || (sy != y))) {return (map[x][y].state != AITile.CLOSED);}return true;}/** * Get the heuristic cost for the given location. This determines in which order the locations are processed. *  * @param mover *  The entity that is being moved * @param x *  The x coordinate of the tile whose cost is being determined * @param y *  The y coordiante of the tile whose cost is being determined * @param tx *  The x coordinate of the target location * @param ty *  The y coordinate of the target location * @return The heuristic cost assigned to the tile */public float getHeuristicCost(int x, int y, int tx, int ty) {float dx = tx - x;float dy = ty - y;float result = (float) (Math.sqrt((dx * dx) + (dy * dy)) * 1.02f);// stupid euclidean distance. try manhattan instead with 1/50th tiebreaker// float result = (Math.abs(x - tx) + Math.abs(y - ty)) * 1.02f;return result;}}public class AITile {public static final int OPEN = 0;public static final int CLOSED = 1;public static final int SELF = 2;public static final int TARGET = 3;public static final int INVALID = 4;public int state = OPEN;public int topLeftX;public int topLeftY;public int width;public int height;public int x;public int y;// A* Stuffpublic float cost;/** The parent of this node, how we reached it in the search */public AITile pathParent;/** The heuristic cost of this node */public float heuristic;/** The search depth of this node */public int depth;public boolean visited;public boolean isAstarClosed;public boolean isAstarOpen;public AITile openNext;public AITile openPrev;public void resetAStar() {x = 0;y = 0;cost = 0f;pathParent = null;heuristic = 0f;depth = 0;visited = false;isAstarClosed = false;isAstarOpen = false;openNext = null;openPrev = null;}public int setParent(AITile parent) {depth = parent.depth + 1;this.pathParent = parent;return depth;}} [Edited by - rbgrn on May 15, 2009 1:27:55 PM];  A few comments:1) Please use source tags2) Please profile your code and show us the slowest parts.  We will go from there.   ;  You're using insertion sort to maintain your open list in sorted order. Don't. There's a reason priority queues exist and are always used for A*.   ;  Are emulators a valid measurement of performance? I couldn't imagine that they would be, but I have zero experience in the matter.   ;Quote:Original post by SneftelYou're using insertion sort to maintain your open list in sorted order. Don't. There's a reason priority queues exist and are always used for A*.I switched to the linked list after reading these tips on efficiency in this algorithm - http://www.gamasutra.com/features/20010314/pinter_01.htmThe Dalvik VM kind of sucks with array copies I'm finding.  Just switching to the LL gained a 2-4 fold in performance.;Quote:Original post by EzbezAre emulators a valid measurement of performance? I couldn't imagine that they would be, but I have zero experience in the matter.Yes!  The devkit emulator is very comparable to the real device.  The actual device may be slightly faster or slower in some scenarios but overall they got the ARM emulation down to where it's very reliable as a baseline.   ;Quote:Original post by rbgrnQuote:Original post by SneftelYou're using insertion sort to maintain your open list in sorted order. Don't. There's a reason priority queues exist and are always used for A*.I switched to the linked list after reading these tips on efficiency in this algorithm - http://www.gamasutra.com/features/20010314/pinter_01.htmThe Dalvik VM kind of sucks with array copies I'm finding.  Just switching to the LL gained a 2-4 fold in performance.Were you using a heap for your OPEN list previously?  How was it implemented?  It is asymptotically fastest, and the constants really don't need to be bad at all.   ;Quote:Original post by EmergentQuote:Original post by rbgrnQuote:Original post by SneftelYou're using insertion sort to maintain your open list in sorted order. Don't. There's a reason priority queues exist and are always used for A*.I switched to the linked list after reading these tips on efficiency in this algorithm - http://www.gamasutra.com/features/20010314/pinter_01.htmThe Dalvik VM kind of sucks with array copies I'm finding.  Just switching to the LL gained a 2-4 fold in performance.Were you using a heap for your OPEN list previously?  How was it implemented?  It is asymptotically fastest, and the constants really don't need to be bad at all.The first post has my original code and the second post has my current, much faster code.I was using an ArrayList which is a managed array.  The performance hits were from inserting in the middle of it and checking for the existence of an element in it.  My new code is much faster for both of those operations.;  Yes, but by simply using a binary heap, you can avoid middle-insertion altogether. For that matter, by using an extra field in the tile class, you can also make checking for an item in the open-list O(1) too. Fix your algorithms first, then fix your implementation.   