2
\$\begingroup\$

I'm working on a game and I have developed A* path finding for certain enemies. But I think I have some optimization issues. If I put the player in an area that cannot be reached and put 3 or 4 enemies around him they are forced to use A* until there are no options left. This causes a dramatic slowdown.

There are several limiting factors that limit the area that can be searched. If the node is out of the attack range of the enemy, if the node falls out of the viewable screen, if the node fall out of the current "area", then the node will be ignored. So in this case with the current enemy and it's range we should be checking about an 18x18 grid. Things to consider, I'm using the map tiles themselves as the nodes, I'm using a priority queue for the open set, although I'm forced to remove an object from it if I have to update the parent or update the G value and re add it to preserve the proper order, and I'm using a hash set for the closed list.

Not sure if I shouldn't be using the actual map as the nodes. Since the map tiles can be checked over and over I'm also forced to set the G value to maximum the first time I come across it for the current instance of the A* so that the calculated value will always be smaller.

This path finding occurs once every cycle of the game. The code is ready for diagonal movement but so far I'm only taking advantage of horizontal and vertical movement. I've also tried running it with other sections of code commented out to see if something else might be causing the slowdown, but it's definitely the A*.

I ran some tests and saw that the closed set had about 280 elements in it, and the open set had around 250 when it finished checking everything, not sure if those numbers make sense. I would think one of those should be a lot smaller considering the limitations. I'm probably doing a lot wrong here so any tips on how to make this code more efficient would be greatly appreciated.

This is a top down 2d game like original Zelda. The map consists of tiles each with their own attributes. The A* path finding algorithm tries to find a path from a starting tile to an end tile using only vertical or horizontal movements. Hope that makes it more clear about what the game is like and how it functions.

Here is the class I use for A*

    package enemiesClass;

    import java.awt.Point;
    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.Comparator;
    import java.util.HashSet;
    import java.util.PriorityQueue;
    import java.util.Queue;
    import java.util.Set;

    import Engine.Animator;
    import Engine.MapMain;

    public class Astar {

    private MapMain nodeStart;//starting tile 
    private MapMain nodeEnd;//ending tile
    private Enemies enemy;
    private boolean diag;//can move diagonally
    private boolean isPath;//true if there is a path and flase if there is not
    private ArrayList<MapMain> pathToEnd = new ArrayList<MapMain>();
    private int sightDistance;// = enemy.sightAttackRange*Animator.scale;//the maximum distance the enemy can see while attacking
    private Point heroCent = Animator.getBoard().findCenter(Animator.getBoard().getHero().getRect());//center of hero rect

    public Astar(MapMain nodeStart, MapMain nodeEnd, Enemies enemy, boolean diag){
        this.nodeStart = nodeStart;
        this.nodeEnd = nodeEnd;
        this.enemy = enemy;
        this.diag = diag;
        sightDistance = enemy.sightAttackRange*Animator.scale;//the maximum distance the enemy can see while attacking
        isPath = findPath();
    }


    private boolean findPath(){
        Set<MapMain> closedSet = new HashSet<MapMain>();
        Queue<MapMain> openSet = new PriorityQueue<MapMain>(11, nodeComparator);
        nodeStart.setPathG(0);
        nodeStart.setPathH(getDistance(nodeStart, nodeEnd));
        nodeStart.setPathF(nodeStart.getPathH()+nodeStart.getPathF());
        openSet.add(nodeStart);

        while(!openSet.isEmpty()){

            //MapMain[] maps = findNeighbors(openSet.peek());

            MapMain currentNode = openSet.poll();
            closedSet.add(currentNode);
            if (currentNode.equals(nodeEnd)){
                makePathToEnd();
                return true;
            }
            //look through each neighbor 
            for(MapMain map: findNeighbors(currentNode)){
                Point mapCent = Animator.getBoard().findMapTileCenter(map);//center point of map tile
                //Line2D line = new Line2D.Double(mapCent, Animator.getBoard().findCenter(Animator.getBoard().getHero().getRect()));

                if(closedSet.contains(map)){
                    continue;//if this map tile was already added to closedSet
                }

                if(Animator.getBoard().isRectInTile(map)){
                    continue;//if any tile in this map space has a rect in it
                }

                if(mapCent.x > enemy.mapAreaBR.getX()+Animator.scale || mapCent.x < enemy.mapAreaTL.getX() ||
                        mapCent.y > enemy.mapAreaBR.getY()+Animator.scale || mapCent.y < enemy.mapAreaTL.getY()){
                    continue;//if map tile is leaving the area the enemy is in
                }

                if(mapCent.x > Animator.screenW+Animator.scale || mapCent.x < -Animator.scale ||
                        mapCent.y > Animator.screenH+Animator.scale || mapCent.y < 0){
                    continue;//if map tile is outside of viewable screen
                }

                if(!checkRange(mapCent)){
                    continue;//hero is out of range from the center of this tile
                }

                if(!openSet.contains(map)){
                    map.setPathG(Integer.MAX_VALUE);//if this tile has not been added set the G to max value 
                    map.setPathH(getDistance(map, nodeEnd));//find cost to to end node
                }

                //find cost to neighbor
                int tempG = currentNode.getPathG()+getDistance(currentNode, map);

                //if the new G cost to the neighbor is less then the old G cost to the neighbor
                if(tempG < map.getPathG()){
                    if(openSet.contains(map)){//if this tile is already in open set
                        openSet.remove(map);//remove it to make changes so the order is preserved 
                    }
                    map.setPathG(tempG);//apply new G cost
                    map.setPathF(map.getPathH()+map.getPathG());//calculate new F cost
                    map.setPathParent(currentNode);//add current node as parent
                    openSet.add(map);//add map to open set
                }
            }
        }

        return false;

    }

    //find neighbor nodes
    private MapMain[] findNeighbors(MapMain node){
        int neighborCount = 4;
        if(diag) neighborCount = 8;
        MapMain maps[] = new MapMain[neighborCount];

        int index = 0;

        for(MapMain map: Animator.getBoard().getMapMainArrayL1()){
            int mapx = map.getMapPoint().x;
            int mapy = map.getMapPoint().y;
            int nodex = node.getMapPoint().x;
            int nodey = node.getMapPoint().y;

            //create loop for checking all neighbor nodes
            for(int ix = -1; ix < 2; ix++){
                for(int iy = -1; iy < 2; iy++){
                    if(ix == 0 && iy == 0) continue;//skip if it's the middle tile which is the current node

                    if(mapx == nodex+ix && mapy == nodey+iy){
                        if(ix == 0 || iy == 0){//if horizontal or vertical node always add neighbor
                            maps[index] = map;
                            index++;
                        }else if(diag){//if diagonal node only add when diag is true
                            maps[index] = map;
                            index++;
                        }
                    }
                }
            }
        }

        return maps;
    }

    private void makePathToEnd(){
        MapMain nodeCurrent = nodeEnd;
        pathToEnd.add(nodeCurrent);
        while(!nodeCurrent.equals(nodeStart)){
            nodeCurrent = nodeCurrent.getPathParent();
            pathToEnd.add(nodeCurrent);
        }

        Collections.reverse(pathToEnd);
    }

    //checks to see if the hero is in range from given spot
    private boolean checkRange(Point point){
        if(heroCent.y > point.y-(sightDistance) && heroCent.y < point.y+(sightDistance) &&
                heroCent.x > point.x-(sightDistance) && heroCent.x < point.x+(sightDistance)){
            return true;
        }
        return false;
    }

    //get distance from one map tile to another
    private int getDistance(MapMain map1, MapMain map2){
        int distX = Math.abs(map1.getMapPoint().x-map2.getMapPoint().x);
        int distY = Math.abs(map1.getMapPoint().y-map2.getMapPoint().y);

        if(distX > distY)return 14*distY+10*(distX-distY);
        return 14*distX+10*(distY-distX);
    }

    //comparator for priority queue
    private Comparator<MapMain> nodeComparator = new Comparator<MapMain>(){

        @Override
        public int compare(MapMain a1, MapMain a2) {

            return a1.getPathF() - a2.getPathF();

        }
    };

    public boolean isPath() {
        return isPath;
    }

    public ArrayList<MapMain> getPathToEnd() {
        return pathToEnd;
    }   
}

And here is the section of code that calls it

//do attack style 2 checks 
private void doAttackStyle2(){

    if(checkHeroAcross() || attacking){
        setAttackDraw();
        bullet3attack();
        return;
    }


    if(!findAttackSpot2()){
        stopAttack();
        return;
    }


    attackPoint = heroPoint;
    Astar astar = new Astar(findClosestTile(),Animator.getBoard().getMapFromPoint(attackPoint),this,false);
    if(astar.isPath()){
        if(attackPause < 29){
            attackAlert();
            return;
        }
        speed = attackSpeed;
        faceHero();
        dy=0;
        dx=0;
        moving = true;

        astarPath = astar.getPathToEnd();
        byte tileLoc = findRectLocationInMapTile(astarPath.get(0), Animator.getBoard().getRectCorners(rect));
        byte nextLoc = 0;//next location to move to
        if(astarPath.size() > 1){
            nextLoc = getAttackNextTile();
            moveAttackPath(tileLoc,nextLoc);
        }else{
            moveAttackPathFinal();
        }
    }else{
        stopAttack();
    }

}
\$\endgroup\$
  • 3
    \$\begingroup\$ Not quite enough for a full review, but: Why are you running full A* on every tick of your game? Usually you wouldn't need to do that. Most A* results will be at least useful for a few ticks or even seconds. \$\endgroup\$ – Vogel612 Dec 22 '18 at 11:39
  • \$\begingroup\$ Thanks! I was wondering if that was necessary. Never used A* before so I wasn't sure how it needs to work. I'll reduce the useage of it and see how it turns out. \$\endgroup\$ – Sark Dec 22 '18 at 17:26
5
\$\begingroup\$

Calling PriorityQueue.contains is O(n) in the size of the priority queue and this ruins your performance.

For example here:

if(!openSet.contains(map)){
    map.setPathG(Integer.MAX_VALUE);//if this tile has not been added set the G to max value 
    map.setPathH(getDistance(map, nodeEnd));//find cost to to end node
}

It is ok to have duplicates in the open set just check if the current node is in the closed set when you pull it out of the open set before continuing with it. Or if you don't like that, you can have a parallel open set to the open priority queue.

\$\endgroup\$
  • \$\begingroup\$ Or use a priority queue with O(1) contains!. That's for C# though - unfortunately I'm not aware of one for Java, but it is open source... \$\endgroup\$ – BlueRaja - Danny Pflughoeft Dec 22 '18 at 9:32
  • \$\begingroup\$ One of the reasons I need to check if it's not in open set yet is because I'm using the actual map tiles as the nodes. It's very likely the tile has been used in the past and already has a G value set. The G value has to be reset so it can be compared. But this may be a flawed method. I'll look into creating separate nodes so this won't be needed. Once I see the performance increase I'll check this answer. Thanks for the tip! \$\endgroup\$ – Sark Dec 22 '18 at 17:31
  • 1
    \$\begingroup\$ Storing ephemeral data pertaining to the path finding in the actual map tiles is a Bad Idea TM, for one you are preventing yourself from paralleling the A* search for the different agents for example. Also it's just the wrong place for this data. \$\endgroup\$ – Emily L. Dec 22 '18 at 17:58
  • \$\begingroup\$ I was always worried about doing that. That's why I pointed it out. The game runs in a single thread so it wouldn't run parallel, but still it's bad practice. And I totally now see how I ruined the purpose of the priority queue by forcing the game to run through the entire queue each time. I'm pretty sure when I eliminate it I'll see a performance boost. Just didn't realize what I was doing at the time. \$\endgroup\$ – Sark Dec 22 '18 at 18:06
  • \$\begingroup\$ I've hit a wall. The priority queue comparable value can change during the coarse of the algorithm. Any attempt to remove an element and restructure the queue results in 0(n). I'm not sure what you mean by don't worry about duplicates? In order to check contains I have to compare objects, if openSet just got new objects added each time it would always add new objects to closed set. Maybe I misunderstood what you were trying to say? I know there are other heaps that can do 0(1) removal, but they don't come in stock java it doesn't look. \$\endgroup\$ – Sark Dec 24 '18 at 6:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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