Moving game objects along an A* Path

Question

I am having a game with a lot of GameBodyObjects and some of them are moving, some of them are not. When I calculate A* for the moving objects it gets really slow when all the objects are present. If there is just a Player then the A* is fast.

Here is my Game update loop:

public Game update(float dt) {
    if(isStarted()) {
        duration += dt;

        ArrayList<GameBodyObject> objects = getAllGameBodyObjects();

        if(!astar.isInitialized()) {
            astar.initialize(GameLogicConstants.ASTAR_GRID_SIZE);
            astar.getGrid().recalculateObstacles(objects);
        }

        for (Player p : players) {
            p.update(dt, objects, astar);
        }

        for (BootCamp bootCamp : bootCamps) {
            bootCamp.update(dt, objects, astar);
        }

        for(WaveManager wave : waves) {
            wave.update(dt, objects, astar);
        }
        //checkCollisions();

        astar.getGrid().recalculateObstacles(objects);

        gameCycles++;
    }
    return this;
}

The recalculateObstacles function is really fast, and I don't think it's the bottleneck.

For every GameBodyObject, I have a method moveTowardsPoint which gets an A* every tick in the game and perform the A* algorithm task and moves along the path found.

Here is my A* implementation:

public Path process(GameBodyObject me, Point target, ArrayList<GameBodyObject> others) throws Exception {

    if(grid == null) {
        throw new Exception("You have to initialize AStar first.");
    }

    grid.unsetObstacleForObject(me);

    Spot start = grid.getSpotAtPosition(me.getPosition().getX(), me.getPosition().getY());
    Spot end = grid.getSpotAtPosition(target.getX(), target.getY());

    end = grid.moveSpotSoThatItDoesntCollide(end, me.getRadius());

    List<Spot> openSet = new ArrayList<Spot>(grid.getMaxSize());
    List<Spot> closedSet = new ArrayList<>();
    List<Spot> path = new ArrayList<>();

    openSet.add(start);

    boolean hasHit = false;

    while(openSet.size() > 0) {

        int winner = 0;
        for(int i = 1; i < openSet.size(); i++) {
            if(openSet.get(i).getF() < openSet.get(winner).getF()) {
                winner = i;
            }
        }

        Spot current = openSet.get(winner);


        if(current == null) {
            return new Path(hasHit, false, new ArrayList<>());
        }

        if(current.equals(end)) {
            // We are done, reconstruct the path...
            Spot temp = current;
            path.add(temp);
            while(temp.getPrevious() != null) {
                Spot previous = temp.getPrevious();
                temp.setPrevious(null);
                path.add(previous);
                temp = previous;
            }

            grid.resetObstacles();
            Collections.reverse(path);
            return new Path(hasHit, true, path);
        }

        openSet.remove(current);
        closedSet.add(current);

        List<Spot> neighbors = current.getNeighbors();

        for(Spot neighbor : neighbors) {
            if(!closedSet.contains(neighbor)) {
                if(!grid.isCollidingWithObstacle(neighbor, me.getRadius())) {
                    double tempG = current.getG() + 1;
                    if (openSet.contains(neighbor)) {
                        if (tempG < neighbor.getG()) {
                            neighbor.setG(tempG);
                        }
                    } else {
                        neighbor.setG(tempG);
                        openSet.add(neighbor);
                    }

                    neighbor.setH(heuristic(neighbor, end));
                    neighbor.setF(neighbor.getG() + neighbor.getH());
                    neighbor.setPrevious(current);
                } else {
                    hasHit = true;
                }
            }
        }

    }

    grid.resetObstacles();
    return new Path(hasHit, false, new ArrayList<>());
}

public double heuristic(Spot spot, Spot end) {
    double dx = spot.getAbsoluteX() - end.getAbsoluteX();
    double dy = spot.getAbsoluteY() - end.getAbsoluteY();
    return Math.sqrt(dx * dx + dy * dy);
    //return Math.abs(dx) + Math.abs(dy);
}

For more context, the Grid.java: https://gist.github.com/Durisvk/4de2d7e2e0a229a6cfd4bb9cc7203996

and lastly the GameBodyObject.java: https://gist.github.com/Durisvk/209f25c781af4aa53a4011f522b5c2d9

EDIT

Super, Thank you guys, I didn't await that kind of discussion. I thought to myself that my work 4 days were wasted and I won't use the A* at the end. But I hope I will optimize it as much as I can.

There were some questions about the game I am making. It's a Dota 2 for browsers, but the problem is on server when I am calculating this A* so there is no delay in drawing on client.

Answer 1

You can improve the performance by using appropriate data structures.

1. You can obtain the closest node using a PriorityQueue.

2. You can use a Set (for instance, a HashSet) to keep track of open and closed nodes. It's not just about performance. It makes your intent more clear. If something is a set, use a Set for it, not a List.

This way, the time complexity will decrease to O(E log V), where E is the number of edges and V is the number of nodes in the grid (it can be even better in practice if finds the "right" path to the end quickly).

Answer 2

Pathfinding is a complex topic and there's a lot of information about it in the web. I highly recommend to invest some time into reading about it.

If you have a high number of objects chasing a low number of targets or only the nearest of many tragets, then you might be better off with Heatmap Pathfinding. It has a high base cost for generating the heat map depending on map size, but no additional cost for the number of pathfinders. And if only the nearest of multiple targets is chased, then a single heatmap can be used for all targets. If every object chases the nearest hostile object, then you could have thousands of objects using just two heatmaps, one for each side (or three, with neutral camp creeps). The linked website uses values of 0 for the targets, but you can also use higher numbers to indicate lower priority targets. Heatmaps for immobile targets need only be calculated once per match, or every time an immovable gets destroyed if you use one heatmap for all of them at once.

No matter which algorithm you use, there are many ways of optimizing pathfinding. For a DotA-like game I suggest the following:

• Use AI ticks with a fixed length to get framerate independant behaviour and limit CPU usage, start with 1-10 ticks per second. Reduce ticks until the delay becomes notable (or increase until AI behaviour is acceptable). Do aggro range/line of sight checks and recalculate paths to moving targets once per tick at most. For (non-attacking) players limit path recalculations to once per move order (e.g. right-click), unless they run into an obstacle.
• Once a path is calculated, store it and only recalculate it if either the target moves or the object runs into an obstacle.
• If an object chases a distant moving target, reduce recalculations of the path to once every 2-10 ticks, for example. The further away the target is the less recalculation should be done to keep the CPU load somewhat constant. Also, frequent recalculations should be less important on greater distances.
• Lane creeps follow the same paths most of the time. Create a chain of checkpoints (hardcoded as part of the map, but only visible to the AI) along each lane and have the creeps just calculate a path to the next checkpoint until targets with a higher priority come in range. Make sure that they target the following checkpoint shortly before reaching the current one, or they will waste time trying to reach that exact spot and maybe even block each other.
• If lane creeps were distracted from their usual route, but lose their target, they must go back to the pregenerated path along their respective lane. If you just look for the nearest checkpoint it might happen, that the creeps walk in the wrong direction at first. That's not a big problem, but it can be easily fixed by simply chosing the checkpoint that comes after the nearest one.
• Make creeps go back to their lane or camp before they waste too much time on pathfinding.
• Ideally you can avoid pathfinding over long distances (almost) completely. If you use heatmaps, limit their size to a certain radius or number of calculation steps. With A* limit distance to target (along the path, not linear distance). If you can't avoid it, you should consider using more tricks.
• The usual way of handling long distance pathfinding is using a grid of checkpoints all over the map with each checkpoint representing a node in an undirected, weighted graph (might be overkill, depending on map size). The distances between neighbouring nodes/checkpoints are precalculated and stored. On static maps these can be baked into the map file (or a seperate file used alongside the map file). This is typical for RTS games and shooters, btw. To find a path to a distant target first find both the closest checkpoint and the checkpoint closest to the target. Then use the pregenerated graph to find the shortest chain of checkpoints between them. Use your regular (short distance) algorithm to path to the nearest checkpoint and follow the chain. After reaching the last checkpoint path to the actual target. Again, this might waste time, so simply skip the first and the last checkpoint in the chain. Do a range check for the target (once per tick or less) to find whether it is still closest to the same checkpoint as before. Recalculate the path if, and only if, the target is now closer to a different checkpoint. As soon as the pathfinding object comes close to its target do more frequent recalculations. This way you never have to calculate a short range path longer than twice the distance between checkpoints, and this only in extreme cases. The distance between checkpoints should be kept small enough to avoid long small scale pathfinding calculations, but long enough to keep the total number of checkpoints on a level that allows fast enough large scale pathfinding. Organize the checkpoints into a quadtree to make finding the nearest one easier.
• Another trick is to use the terrain to seperate the map into multiple areas with mostly impassable boundaries that can only be entered through a few choke points (like the steep banks of the river in DotA 2). To reach a target in a different area you have to have to go through such a choke point, which limits the number of possible paths to check.

Answer 3

recalculateObstacles is really fast function, and I don't think it's the bottleneck.

Did you profile this? Humans are notoriously bad at guessing what the bottlenecks are. That's what profiling tools are for.

for every GameBodyObject I have a method moveTowardsPoint which gets an A* every tick in the game and preform the A* task and moves along the path found.

This is most likely your problem. You should should only perform A* when absolutely necessary, not every tick for every object(!!!).

Depending on the game, you may need to run the path-finder once a second, or you may be able to cache the result once and never run it again. You may need to run it once per object, or you may be able to share results between objects. We don't know enough about your game to make those decisions.

List<Spot> openSet = new ArrayList<Spot>(grid.getMaxSize());
List<Spot> closedSet = new ArrayList<>();

As mentioned elsewhere, you'll see significant speedups in your pathfinding if you use the correct data-structures.