# A* Pathfinding for a Game

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

while(!openSet.isEmpty()){

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

MapMain currentNode = openSet.poll();
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)){
}

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

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;
while(!nodeCurrent.equals(nodeStart)){
nodeCurrent = nodeCurrent.getPathParent();
}

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

}

• 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. Dec 22, 2018 at 11:39
• 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.
– Sark
Dec 22, 2018 at 17:26

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.

• 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... Dec 22, 2018 at 9:32
• 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!
– Sark
Dec 22, 2018 at 17:31
• 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. Dec 22, 2018 at 17:58
• 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.
– Sark
Dec 22, 2018 at 18:06
• 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.
– Sark
Dec 24, 2018 at 6:35