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