Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I have this AStar class, and at the movement it is INCREDIBLY slow. It takes waaay longer than I expected it too, and I'm not quite sure why. I added the generation part at the very beginning to speed it up somewhat, and all though it helped my game takes like 15 seconds to load.

If this isn't the right place to ask how to speed it up, just let me know. I'm not sure if this is too "debug my code" esq.

Thanks everyone! - tips

public class AStar {
    private final Tank tank;

    private Map<String, Node> nodes;

    public AStar(Tank tank) {
        this.tank = tank;

        this.nodes = new HashMap<String, Node>();
    }

    public void generate() {
        //long now = System.currentTimeMillis();
        for (int i = 0; i < TanksWorld.MAX_X; i++) {
            for (int j = 0; j < TanksWorld.MAX_Y; j++) {
                Node node = new Node(i, j);
                nodes.put(node.hash(), node);
            }
        }
        //System.out.println("Generate took " + (System.currentTimeMillis() - now));
    }

    public void reset() {
       // long now = System.currentTimeMillis();
        for (Node node : nodes.values()) {
            node.reset();
        }
        //System.out.println("Reset took: " + (System.currentTimeMillis() - now));
    }

    public Path pathTo(int xFinish, int yFinish) {
        int xStart = tank.getFloorX();
        int yStart = tank.getFloorY();

        if (xStart == xFinish && yStart == yFinish) {
            return new Path(true);
        }

        Node startNode = get(xStart, yStart);
        Node goalNode = get(xFinish, yFinish);

        PriorityQueue<Node> queue = new PriorityQueue<Node>();
        queue.add(startNode);

        Path bestPath = null;

        while (queue.size() != 0) {
            Node current = queue.poll();
            int xCurrent = current.getX();
            int yCurrent = current.getY();
            if (current.visited) {
                continue;
            }
            if (current.equals(goalNode)) {
                bestPath = reconstruct(current);
                break;
            }
            addNeighbors(current);
            current.visited = true;

            for (Node node : current.getNeighbors()) {
                if (node == null) {
                    continue;
                }
                if (node.visited) {
                    continue;
                }
                int xNode = node.getX();
                int yNode = node.getY();
                double distance = current.pathDistance + TanksGame.distance(xCurrent, yCurrent, xNode, yNode); // TODO distance
                if (node.parent != null && distance >= node.pathDistance) {
                    continue;
                }
                node.pathDistance = distance;
                node.heuristicDistance = TanksGame.distance(xNode, yNode, xFinish, yFinish) + distance;
                if (node.parent == null) {
                    node.priority = node.heuristicDistance;
                    queue.add(node);
                } else {
                    node.priority = node.heuristicDistance;
                }
                node.parent = current;
            }
        }

        return bestPath == null ? new Path(false) : bestPath;

    }

    private void addNeighbors(Node node) {
        int startX = node.getX();
        int startY = node.getY();

        // up
        node.addNeighbor(get(startX + Tank.MVMT_SPEED, startY));
        // down
        node.addNeighbor(get(startX, startY - Tank.MVMT_SPEED));
        // left
        node.addNeighbor(get(startX - Tank.MVMT_SPEED, startY));
        // right
        node.addNeighbor(get(startX + Tank.MVMT_SPEED, startY));
        // up left
        node.addNeighbor(get(startX - Tank.MVMT_SPEED, startY + Tank.MVMT_SPEED));
        // up right
        node.addNeighbor(get(startX + Tank.MVMT_SPEED, startY + Tank.MVMT_SPEED));
        // down left
        node.addNeighbor(get(startX - Tank.MVMT_SPEED, startY - Tank.MVMT_SPEED));
        // down right
        node.addNeighbor(get(startX + Tank.MVMT_SPEED, startY - Tank.MVMT_SPEED));
    }

    private Path reconstruct(Node goalNode) {
        Path path = new Path(true);
        Node node = goalNode;
        while (node != null) {
            path.addToFront(node);
            node = node.parent;
        }
        return path;
    }

    private Node get(int x, int y) {
        if (x < 0) {
            return null;
        }
        if (y < 0) {
            return null;
        }
        if (x > TanksWorld.MAX_X) {
            return null;
        }
        if (y > TanksWorld.MAX_Y) {
            return null;
        }
        String hash = Node.hash(x, y);
        return nodes.get(hash);
    }

    public class Path {
        private boolean finished;
        private List<Node> path;
        private int index;

        public Path(boolean finished) {
            this.finished = finished;
            this.index = 0;
            this.path = new ArrayList<Node>();
        }

        public boolean isFinished() {
            return finished;
        }

        public void addToFront(Node node) {
            path.add(0, node);
        }

        public Node get() {
            return path.get(index);
        }

        public void next() {
            index++;
        }

        public int getSize() {
            return path.size();
        }

        public boolean isDone() {
            return index >= getSize();
        }
    }

    public static class Node implements Comparable<Node> {
        private final int x;
        private final int y;

        private List<Node> neighbors;

        // TODO getters and setters
        public boolean visited = false;
        public double pathDistance = 0;
        public double heuristicDistance = Double.MAX_VALUE;
        public Node parent = null;
        public double priority = 0;

        public Node(int x, int y) {
            this.x = x;
            this.y = y;
            this.neighbors = new ArrayList<Node>();
        }

        public void reset() {
            parent = null;
            priority = 0;
            heuristicDistance = Double.MAX_VALUE;
            pathDistance = 0;
            visited = false;
        }

        public List<Node> getNeighbors() {
            return neighbors;
        }

        public void addNeighbor(Node node) {
            neighbors.add(node);
        }

        public int getX() {
            return x;
        }

        public int getY() {
            return y;
        }

        public int compare(Node one, Node two) {
            if (one.priority == two.priority) {
                return 0;
            }
            return one.priority > two.priority ? 1 : -1;
        }

        public int compareTo(Node two) {
            return compare(this, two);
        }

        public static String hash(int x, int y) {
            return "x_" + x + "_y_" + y + "_";
        }

        public String hash() {
            return "x_" + x + "_y_" + y + "_";
        }
    }
}
share|improve this question

closed as too localized by Byte56, John McDonald, msell, Patrick Hughes, Sean Middleditch Jun 23 '13 at 3:59

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

6  
Hey Tips, yeah, it's pretty much "debug my code". I suggest you get yourself a profiler. The profiler will show you exactly which parts of your code are taking the longest. It could be not in your pathfinding code, but how you're using the pathfinding code (i.e. finding lots and lots of paths). I know Netbeans has one built in that's pretty nice, give it a try. –  Byte56 Jun 22 '13 at 4:15
    
The following journal article provides a concise but detailed descriptions of optimizations of Djikstra's algorithm. Note that a* is one of these. Bidirectional Djikstra is another, and you can use both in tandem. algo2.iti.kit.edu/documents/routeplanning/geisberger_dipl.pdf –  Matthew James Davis Jun 22 '13 at 4:25
    
Also, check for any casts between integer types and float types in your deeply-nested loops. Integer arithmetic is faster than floating point in general, but converting back and forth is a real performance killer. –  Pieter Geerkens Jun 22 '13 at 17:15
    
There are several ways to improve a good but primitive A* algorithm. I suggest reading into hierarchical A*, quad tree's and binary heaps. Basically you want to iterate to the least possible amount of nodes when you require a new path. Hierarchical path-finding splits the map up in larger chunks where quad tree's and binary heaps help you directly with iterating through the least amount of nodes. –  Menno Gouw Aug 23 '13 at 17:41

1 Answer 1

up vote 3 down vote accepted

For one, your node priority should be based on the total estimated distance from start to end: current.pathDistance + node.heuristicDistance. You want to pick the nodes that have best likely outcome.

For two, the priorityQueue documentation reads The head of this queue is the least element, which means that your compare will want to return smaller values for more desirable choices, a subtraction should suffice: one.priority - two.priority

Before these changes, your algorithm was selecting nodes that were furthest from the destination to calculate next, which would result in flood-filling the entire world before settling on a result. That could take a while, especially if you re-calculate the "shortest" distance to every node from every adjacent node.

share|improve this answer
    
Even though it may look like I'm picking holes, I'd like to note that your code was very clean and easy to read. Well done. –  John McDonald Jun 22 '13 at 5:39
    
No, that's fine. Thank you very much, I'll try all of these and see how it works! –  Tips48 Jun 22 '13 at 22:14
    
Can you clarify what you meant on the second paragraph? That first part helped a lot. –  Tips48 Jun 23 '13 at 4:51
    
I believe the code under the Node.compare is returning the worse node as a better option (the opposite of what you want). If one is smaller than two, it should return -1, else return 1. –  John McDonald Jun 23 '13 at 17:05

Not the answer you're looking for? Browse other questions tagged or ask your own question.