Gfrktyl

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

    }



}

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.