java A* star for game development












0














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.



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

}








share







New contributor




Sark is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

























    0














    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.



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

    }








    share







    New contributor




    Sark is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
    Check out our Code of Conduct.























      0












      0








      0







      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.



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

      }








      share







      New contributor




      Sark is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.











      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.



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

      }






      java game a-star





      share







      New contributor




      Sark is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.










      share







      New contributor




      Sark is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.








      share



      share






      New contributor




      Sark is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.









      asked 2 mins ago









      Sark

      1




      1




      New contributor




      Sark is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.





      New contributor





      Sark is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.






      Sark is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.



























          active

          oldest

          votes











          Your Answer





          StackExchange.ifUsing("editor", function () {
          return StackExchange.using("mathjaxEditing", function () {
          StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
          StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
          });
          });
          }, "mathjax-editing");

          StackExchange.ifUsing("editor", function () {
          StackExchange.using("externalEditor", function () {
          StackExchange.using("snippets", function () {
          StackExchange.snippets.init();
          });
          });
          }, "code-snippets");

          StackExchange.ready(function() {
          var channelOptions = {
          tags: "".split(" "),
          id: "196"
          };
          initTagRenderer("".split(" "), "".split(" "), channelOptions);

          StackExchange.using("externalEditor", function() {
          // Have to fire editor after snippets, if snippets enabled
          if (StackExchange.settings.snippets.snippetsEnabled) {
          StackExchange.using("snippets", function() {
          createEditor();
          });
          }
          else {
          createEditor();
          }
          });

          function createEditor() {
          StackExchange.prepareEditor({
          heartbeatType: 'answer',
          autoActivateHeartbeat: false,
          convertImagesToLinks: false,
          noModals: true,
          showLowRepImageUploadWarning: true,
          reputationToPostImages: null,
          bindNavPrevention: true,
          postfix: "",
          imageUploader: {
          brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
          contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
          allowUrls: true
          },
          onDemand: true,
          discardSelector: ".discard-answer"
          ,immediatelyShowMarkdownHelp:true
          });


          }
          });






          Sark is a new contributor. Be nice, and check out our Code of Conduct.










          draft saved

          draft discarded


















          StackExchange.ready(
          function () {
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f210156%2fjava-a-star-for-game-development%23new-answer', 'question_page');
          }
          );

          Post as a guest















          Required, but never shown






























          active

          oldest

          votes













          active

          oldest

          votes









          active

          oldest

          votes






          active

          oldest

          votes








          Sark is a new contributor. Be nice, and check out our Code of Conduct.










          draft saved

          draft discarded


















          Sark is a new contributor. Be nice, and check out our Code of Conduct.













          Sark is a new contributor. Be nice, and check out our Code of Conduct.












          Sark is a new contributor. Be nice, and check out our Code of Conduct.
















          Thanks for contributing an answer to Code Review Stack Exchange!


          • Please be sure to answer the question. Provide details and share your research!

          But avoid



          • Asking for help, clarification, or responding to other answers.

          • Making statements based on opinion; back them up with references or personal experience.


          Use MathJax to format equations. MathJax reference.


          To learn more, see our tips on writing great answers.





          Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


          Please pay close attention to the following guidance:


          • Please be sure to answer the question. Provide details and share your research!

          But avoid



          • Asking for help, clarification, or responding to other answers.

          • Making statements based on opinion; back them up with references or personal experience.


          To learn more, see our tips on writing great answers.




          draft saved


          draft discarded














          StackExchange.ready(
          function () {
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f210156%2fjava-a-star-for-game-development%23new-answer', 'question_page');
          }
          );

          Post as a guest















          Required, but never shown





















































          Required, but never shown














          Required, but never shown












          Required, but never shown







          Required, but never shown

































          Required, but never shown














          Required, but never shown












          Required, but never shown







          Required, but never shown







          Popular posts from this blog

          Ellipse (mathématiques)

          Quarter-circle Tiles

          Mont Emei