Astar optimalization (A*) [closed]

So I have written own implementation of AStar (A*) algorithm to find paths around my 2d tile based map. My problem is that if I call it each frame (I need to do it) and I'm searching path from corner of map to corner, my game runs at c.a. 7 fps. How can I can optimize it here is the code:

package com.kubasienki.survive.pathfinding;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

import com.kubasienki.survive.cave.Dungeon;
import com.kubasienki.survive.cave.Map;

public class PathFinder {

public ArrayList<Node> open = new ArrayList<Node>();
public ArrayList<Node> closed = new ArrayList<Node>();
ArrayList<Node> path = new ArrayList<Node>();

public void print(ArrayList<Node> array) {

for (int i = 0; i < array.size(); i++) {
System.out.println("S " + array.get(i).x + "\t" + array.get(i).y
+ "\t" + i + "\\" + array.size());
}
}

public int findNode(Node node, ArrayList<Node> array) {
// //////System.out.println("####################"+array.toString());
for (int i = 0; i < array.size(); i++) {
// //////System.out.println("S " + array.get(i).x + "\t" +
// array.get(i).y
// + "\t" + i);
if (node.x == array.get(i).x && node.y == array.get(i).y) {
return i;
}
}
return -1;
}

void chceckNeighbour(Node nodee, Dungeon map, int endX, int endY) {

// ////System.out.println("CHECKED: " + nodee.x + "\t" + nodee.y +
// " closed: "
// + findNode(nodee, closed) + " open: " + findNode(nodee, open));
// print(open);
int iterator = findNode(nodee, closed);
if (!closed.isEmpty() && iterator != -1
&& nodee.cost < closed.get(iterator).cost) {
// ////System.out.println("FOUND IN CLOSED");
closed.get(iterator).parentX = nodee.x;
closed.get(iterator).parentY = nodee.y;
closed.get(iterator).cost = nodee.cost;
closed.get(iterator).costH = nodee.cost + Math.abs(nodee.x - endX)
+ Math.abs(nodee.y - endY);
}
iterator = findNode(nodee, open);
if (!open.isEmpty() && iterator != -1
&& nodee.cost < open.get(iterator).cost) {
// ////System.out.println("FOUND IN OPEN");
open.get(iterator).parentX = nodee.x;
open.get(iterator).parentY = nodee.y;
open.get(iterator).cost = nodee.cost;
open.get(iterator).costH = nodee.cost + Math.abs(nodee.x - endX)
+ Math.abs(nodee.y - endY);
} else if (findNode(nodee, open) == -1 && findNode(nodee, closed) == -1) {
// ////System.out.println("ADDING NEW: " + nodee.x + "\t" +
// nodee.y);
open.get(open.size() - 1).cost = nodee.cost;
open.get(open.size() - 1).costH = nodee.costH;
open.get(open.size() - 1).x = nodee.x;
open.get(open.size() - 1).y = nodee.y;
open.get(open.size() - 1).parentX = nodee.parentX;
open.get(open.size() - 1).parentY = nodee.parentY;

// //////System.out.print("''''''''''''''''''''" + findNode(nodee,
// open));

/*
* for(Node nodez : open){
* //////System.out.print(nodez.x+"\t"+nodez.y+"|"); }
*/
}
}

public void checkNeighbours(Node node, Dungeon map, int endX, int endY) {
Node gen = new Node();
// print(open);
if (node.x != 0) {
gen.x = (node.x - 1);
gen.y = node.y;
if (Dungeon.dungeon.get(gen.x).get(gen.y)) {
gen.cost = node.cost + 500;
} else {
gen.cost = node.cost + 1;
}
gen.costH = node.cost + Math.abs(gen.x - endX)
+ Math.abs(gen.y - endY);
gen.parentX = node.x;
gen.parentY = node.y;
// ////System.out.println("x-1");
chceckNeighbour(gen, map, endX, endY);
}
if (node.y != 0) {
gen.x = node.x;
gen.y = (node.y - 1);
if (Dungeon.dungeon.get(gen.x).get(gen.y)) {
gen.cost = node.cost + 500;
} else {
gen.cost = node.cost + 1;
}
gen.costH = gen.cost + Math.abs(gen.x - endX)
+ Math.abs(gen.y - endY);
gen.parentX = node.x;
gen.parentY = node.y;
// ////System.out.println("y-1");
chceckNeighbour(gen, map, endX, endY);
}
if (node.x < Dungeon.dungeon.size() - 1) {
gen.x = (node.x + 1);
gen.y = node.y;
if (Dungeon.dungeon.get(gen.x).get(gen.y)) {
gen.cost = node.cost + 500;
} else {
gen.cost = node.cost + 1;
}
gen.costH = gen.cost + Math.abs(gen.x - endX)
+ Math.abs(gen.y - endY);
gen.parentX = node.x;
gen.parentY = node.y;
// ////System.out.println("x+1");
chceckNeighbour(gen, map, endX, endY);
}
if (node.y < Dungeon.dungeon.get(0).size() - 1) {
gen.x = node.x;
gen.y = (node.y + 1);
if (Dungeon.dungeon.get(gen.x).get(gen.y)) {
gen.cost = node.cost + 500;
} else {
gen.cost = node.cost + 1;
}
gen.costH = gen.cost + Math.abs(gen.x - endX)
+ Math.abs(gen.y - endY);
gen.parentX = node.x;
gen.parentY = node.y;
// ////System.out.println("y+1");
chceckNeighbour(gen, map, endX, endY);
// //////System.out.println("REMOVE");
}
}

public ArrayList<Node> find(Dungeon map, int startX, int startY, int endX,
int endY) {
// ////System.out.println("SEARCHING START");

boolean goal = false;
open.clear();
closed.clear();
path.clear();
Node temp = new Node();
temp.x = startX;
temp.y = startY;
temp.cost = 0;
temp.costH = Math.abs(startX - endX) + Math.abs(startY - endY);
temp.parentX = -1;
temp.parentY = -1;
// print(open);

while (!goal) {

// //////System.out.println(closed.size());

// SORTING
// //////System.out.println(open.size());
// print(open);
// //////System.out.println();
Collections.sort(open, new Comparator<Node>() {

@Override
public int compare(Node o1, Node o2) {
return o1.costH - o2.costH;

}
});
// /SORTING END
// for(Node nodez : open){
// //////System.out.print(nodez.x+"\t"+nodez.y+"|");
// }
if (open.isEmpty()) {
// //////System.out.println("EMPTY");
} else {

if (open.get(0).x == endX && open.get(0).y == endY) {
goal = true;
} else {
// ////System.out.println("#################" +
// open.get(0).x
// + "\t" + open.get(0).y + "#################");
temp = open.get(0);
open.remove(0);
// //////System.out.println("REMOVE:\t" + temp.x + "\t" +
// temp.y);
// //////System.out.println(temp.x + "\t" + temp.y + "\t" +
// (temp.cost));
checkNeighbours(temp, map, endX, endY);

}
}

}
// ////System.out.println("SEARCHING END");
boolean start = false;
Node back = new Node();
back = open.get(0);

while (!start) {
// System.out.println("x: " + back.x + " y: " + back.y + "");
// System.out.println("NEW PATH PART");
path.get(path.size() - 1).x = back.x;
path.get(path.size() - 1).y = back.y;
// System.out.println("x: " + path.get(path.size()-1).x + " y: " +
// path.get(path.size()-1).y + "");
back.x = back.parentX;
back.y = back.parentY;
back = closed.get(findNode(back, closed));
int i = findNode(back, closed);
if (closed.get(i).parentX == -1) {
start = true;
}
}
// System.out.println("RETURNING PATH");
// print(path);
return path;
}

}


• IMHO this is a good question. Obviously, the task is to optimize "all that code", no matter what the closing squad says. You could use profiling to find the critical part, however, looking at the whole makes more sense. Some tips: 1. On a small device not everything gets optimized as well as in a server VM, so using local variables for things like open.size() - 1 may help. 2. In case your lists get large, using a HashMap can speed up findNode a lot. 3. As you move through the dungeon, the optimal path changes slowly and you might be able to reuse some old value. Commented May 4, 2014 at 17:45