1

I am currently working on my first game for android, and my first time creating an a* path finding algorithm. It is a 2d game. I have created one enemy containing this algorithm (ie. It is being ran once every frame) and it slows down performance from 60fps to 1-2 fps. Obviously something is horribly wrong, I have tried looking online for solutions but have yet to find an answer. Here are my pathfinding classes:

package com.frog8fly.nunca;

import com.badlogic.gdx.utils.Array;

import java.util.Comparator;

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;

    Node currentNode = start;
    currentNode.parent = null;
    currentNode.G = 0;
    currentNode.H = getHeuristic(currentNode, finish);
    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("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);
        System.out.println("Anotha");
    }

    pathNodes.reverse();

    return pathNodes;
}

private static float getHeuristic(Node start, Node finish){
    int H = 0;

    System.out.println(start.position);
    System.out.println(finish.position);

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

    for(Node nodee : neighbors){
        if(node.position != null){

        }
    }

    return neighbors;

}

}

And my Node class:

package com.frog8fly.nunca;

import com.badlogic.gdx.math.Vector2;

public class Node{

    public Node parent;
    public Vector2 position;

    public float G, H, F;

    public Node(Vector2 position){
        this.position = position;
        this.position.x = (int)Math.floor(this.position.x);
        this.position.y = (int)Math.floor(this.position.y);
    }
}
5
  • A* is slow by nature. You have to profile your code to determine where the CPU time is spent, and optimize it (usually, this is not a question of writing but a question of design). It's often the case with games. - The for(Node nodee : neighbors) loop doesn't compile, BTW. Commented Mar 21, 2016 at 22:46
  • Thanks for replying, what kind of optimizations would you recommend? As far as I can see, since I am only running this algorithm once a frame, would it really make that big of a difference? Commented Mar 22, 2016 at 2:43
  • It depends on where your CPU time is spent. It may consist in changing the List implementation you ar using, or in switch lists to arrays, or event reducing the size of the applicable graph should it be possible to determine the area that is concerned for sure without alering the behaviour of the algorithm. Finally, it may consist in doing a dual A* (from the current location AND from the targel location, stopping when they meet) instead of a single one. Once a frame doesn't tell me much: how big and complex is your graph? Commented Mar 22, 2016 at 6:58
  • @Shlublu My graph is 100 x 100. Commented Mar 22, 2016 at 12:46
  • 1
    OK, not that big but thoroughly connected. @AustinD is right though, a similar question was already asked and the answer it received applies here. Commented Mar 22, 2016 at 13:35

1 Answer 1

0

You're heuristic function is wrong. I believe you want:

H += Math.abs(start.position.x - finish.position.x);
H += Math.abs(start.position.y - finish.position.y);

Having an incorrect heuristic could definitely slow down A* search to a crawl since it basically reduces it to breadth first search.

Sign up to request clarification or add additional context in comments.

4 Comments

Thanks for the reply! Fixed the heuristic, but still going slow as ever :\
@Wyatt And the movement cost is zero for directions 4 and 5. It would be safer/easier/maybe cheaper to do something like return (neighbor == 0 || (neighbour & 1 == 0)) ? 16: 10; I suspect 10 and 16 are inverted though, if 0 stands for north.
@Shlublu 4 isn't used because it is center. 5 should has a movement cost of 10, shouldn't it? 0 is topleft, 1 is top center, 2 is topright, 3 is middle right, so on... 4 is the center square like I said so it's not checked.
@Wyatt OK, forget what I said. I misunderstood the movements map!

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.