I wrote a pathfinding algorithm for android. It seems to be running very slowly and I can not figure out why. I have asked a similar question before, but I didn't get the answers I was looking for (And I have changed code since then). Here is my path finding class :
public class Pathfinding {
private static Node[][] grid;
private static NodeComparator nodeComparator;
static{
nodeComparator = new NodeComparator();
}
public static class NodeComparator implements Comparator<Node> {
@Override
public int compare(Node node1, Node node2) {
if(node1.F > node2.F){
return 1;
}
else if(node1.F < node2.F){
return -1;
}
else{
return 0;
}
}
}
public static Array<Node> findPath(Node start, Node finish, Node[][] _grid) {
Array<Node> path = new Array<Node>();
Array<Node> openList = new Array<Node>();
Array<Node> closedList = new Array<Node>();
grid = _grid;
if(start == null){
return path;
}
if(finish == null){
return path;
}
Node currentNode = start;
currentNode.G = 0;
currentNode.H = getHeuristic(currentNode, finish);
currentNode.parent = null;
openList.add(currentNode);
System.out.println("PATHFINDING STARTED ||| startPos : " + start.position + " finishPos : " + finish.position);
while (openList.size > 0) {
//Sorts open nodes lowest F value to heighest
openList.sort(nodeComparator);
currentNode = openList.first();
//If path is found, return
if (currentNode == finish) {
System.out.println("PATH FOUND...RETURNING -gat5");
return constructPath(currentNode);
}
openList.removeValue(currentNode, true);
closedList.add(currentNode);
int counter = 0;
for (Node neighbor : getNeighbors(currentNode)) {
if (!closedList.contains(neighbor, true)) { //If neighbor not in closed list
if(neighbor != null) { //If neighbor not wall
if(counter == 4){
counter++;
}
int movementCost = checkMovementCost(counter);
if (openList.contains(neighbor, true)) {
if (currentNode.G + movementCost < neighbor.G) {
neighbor.parent = currentNode;
}
} else {
openList.add(neighbor);
neighbor.parent = currentNode;
neighbor.H = getHeuristic(currentNode, finish);
neighbor.G = neighbor.parent.G + movementCost;
}
counter++;
}
}
}
System.out.println(counter);
}
System.out.println("NO FINAL");
System.out.println("NO PATH FOUND RETURNING...");
path.add(start);
return path;
}
private static int checkMovementCost(int neighbor) {
int movementCost = 0;
switch (neighbor) {
//Diagonal
case 0:
case 2:
case 6:
case 8:
movementCost = 16;
break;
//Not Diagonal
case 1:
case 3:
case 5:
case 7:
movementCost = 10;
break;
}
return movementCost;
}
public static Array<Node> constructPath(Node finish) {
Array<Node> pathNodes = new Array<Node>();
Node currentNode = finish;
pathNodes.add(currentNode);
while (currentNode.parent != null) {
currentNode = currentNode.parent;
pathNodes.add(currentNode);
}
return pathNodes;
}
private static float getHeuristic(Node start, Node finish){
int H = 0;
H += Math.abs(start.position.x - finish.position.x);
H += Math.abs(start.position.y - finish.position.y);
return H;
}
private static Array<Node> getNeighbors(Node node){
Array<Node> neighbors = new Array<Node>();
int x = (int)node.position.x;
int y = (int)node.position.y;
if(x - 1 > 0 && x - 1 < grid.length && y + 1 < grid.length && y + 1 > 0){
neighbors.add(grid[x - 1][y + 1]);
}
else{
neighbors.add(null);
}
if(x > 0 && x < grid.length && y + 1 < grid.length && y + 1 > 0){
neighbors.add(grid[x][y + 1]);
}
else{
neighbors.add(null);
}
if(x + 1 > 0 && x + 1 < grid.length && y + 1 < grid.length && y + 1 > 0){
neighbors.add(grid[x + 1][y + 1]);
}
else{
neighbors.add(null);
}
if(x - 1 > 0 && x - 1 < grid.length && y < grid.length && y > 0){
neighbors.add(grid[x - 1][y]);
}
else{
neighbors.add(null);
}
if(x > 0 && x < grid.length && y < grid.length && y > 0){
neighbors.add(grid[x][y]);
}
else{
neighbors.add(null);
}
if(x + 1 > 0 && x + 1 < grid.length && y < grid.length && y > 0){
neighbors.add(grid[x + 1][y]);
}
else{
neighbors.add(null);
}
if(x - 1 > 0 && x - 1 < grid.length && y - 1 < grid.length && y - 1> 0){
neighbors.add(grid[x - 1][y - 1]);
}
else{
neighbors.add(null);
}
if(x > 0 && x < grid.length && y - 1 < grid.length && y - 1 > 0){
neighbors.add(grid[x][y - 1]);
}
else{
neighbors.add(null);
}
if(x + 1 > 0 && x + 1 < grid.length && y - 1 < grid.length && y - 1 > 0){
neighbors.add(grid[x + 1][y - 1]);
}
else{
neighbors.add(null);
}
return neighbors;
}
}
Thank you so much for your help!
**Some more information : ** When I run this algorithm only once, it works fine. But once I run it 3+ times, it starts lose framerate fast. My grid I am using is 200x200.
If your evaluation of the paths is as simple as you are pointing out, probably the slowness of the algorithm has something do do with the ordering that you do in each iteration of the algorithm.
//Sorts open nodes lowest F value to heighest
openList.sort(nodeComparator);
Just using PriorityQueue to order the nodes to be expanded by the algorithm results in a much more efficient implementation. If you want, take a look to the implementation details of the A* algorithm implemented in the library hipster4j. This works in Android, too.
Hope my answer helps.