Search code examples
javaprocessinga-star

A* Pathfinding problems Processing(Java)

I'm quite new to programming though following a bunch of tutorials I've ended up with this code to deal with the pathfinding of a small game I'm trying to make.

If works for small and straight paths but not for complex routes (it freezes and closedSet.size() gets larger than 70000 in a grid that is only 54 * 46).

Note that wall is true depending on the height of the colliding tiles, so it may be true coming from a point but false coming from another. Is that the problem?

import java.util.*;

int heuristic(int x,int y,int x_,int y_){
  int dstX = abs(x - x_);
  int dstY = abs(y - y_);
  if(dstX > dstY){
    return 14*dstY + 10*(dstX - dstY);
  }else{
    return 14*dstX + 10*(dstY - dstX);
  }
}

boolean wall(int x, int y, int x_, int y_){
  Tile tileS = getTile(x, y);
  Tile tileCurr = getTile(x_, y_);
  if(abs(tileS.altitude - tileCurr.altitude) > 1 || tileS.altitude  < 1){
    return true;
  }else{
    return false;
  }
}

ArrayList<PVector> findPath(int startx, int starty, int endx, int endy){
  
  Queue<Spot> openSet = new PriorityQueue<Spot>(fComparator);
  ArrayList<Spot> closedSet = new ArrayList<Spot>();
  
  Spot start = new Spot(startx, starty);
  Spot end = new Spot(endx, endy);
  Spot current = start;
  
  openSet.add(start);
  
  while(!openSet.isEmpty()){
    
    current = openSet.poll();
    closedSet.add(current);
    
    println(closedSet.size());
    
    if (current.x == end.x && current.y == end.y) {
      break;
    }
    
    ArrayList<Spot> successors = new ArrayList<Spot>();
    
    for(int i = 0; i < collidingTiles.size(); i++){
      JSONObject difference = collidingTiles.getJSONObject(i);
      /*JSONArray such as
      [{x: -1, y: -1},{x: 0, y: -1},...](not including {x:0, y:0})
     */

      int x_ = difference.getInt("x");
      int y_ = difference.getInt("y");
      int x = x_ + current.x;
      int y = y_ + current.y;
      
      if(x >= 0 && x <= map.columns && y >= 0 && y <= map.rows){
        Spot s = new Spot(x, y);
        successors.add(s);
      }
    }
    
    for(Spot s: successors){
      if (!closedSet.contains(s) && !wall(s.x, s.y, current.x, current.y)) {
        int tempG = current.g  + heuristic(s.x, s.y, current.x, current.y);
        
        if(tempG < s.g || !openSet.contains(s)){
          s.g = tempG;
          s.h = heuristic(s.x, s.y, end.x, end.y);
          s.f = s.g + s.h;
          s.parent = current;
          if (!openSet.contains(s)) {
            openSet.add(s);
          }
        }
      }
    }
    successors.clear();
  }
  
  ArrayList<PVector> path = new ArrayList<PVector>();
  Spot temp = current;
  PVector tile = new PVector(temp.x + 0.5, temp.y + 0.5);
  path.add(tile);
  while (temp.parent != null) {
    tile = new PVector(temp.parent.x + 0.5, temp.parent.y + 0.5);
    path.add(0, tile);
    temp = temp.parent;
  }
  return path;
}

class Spot{
  int x, y;
  int f, g, h = 0;
  Spot parent;
  
  Spot(int x_, int y_){
    x = x_;
    y = y_;
  }
  
}

Comparator<Spot> fComparator = new Comparator<Spot>() {
  @Override
  int compare(Spot s1, Spot s2) {
    return s1.f - s2.f;
  }
};

Any recommendations or minor changes are also appreciated.

Solution

  • closedSet.size() gets larger than 70000 in a grid that is only 54 * 46

    Your code does implement some logic that says

    1. "if a node is closed, don't process it again", and
    2. "if the node is already in the open set, compare G scores"

    But in both cases it does not work, because Spot does not implement equals, and therefore contains is comparing for reference equality and it will always be false. So, implement Spot.equals. Specifically, make it compare only x and y, because f/g/h/parent are allowed to be different for nodes that are considered equal for this purpose.

    Even when it works, using contains on an ArrayList and a PriorityQueue is not so good for performance. For the closed list, it is easy to use a HashSet (of course, also implement Spot.hashCode, in some way that depends only on x and y). For the open list, getting rid of slow contains is more work. One trick you can use is manually maintaining a binary heap, and additionally have a HashMap which maps an x,y pair to the index in the heap where the corresponding node is located. The reason for manually maintaining a heap is that the HashMap must be updated whenever nodes are moved in the queue, and the normal PriorityQueue does not have such functionality.

    The way that finding successors works also worries me from a performance perspective, but I cannot see the details.

    Note that wall is true depending on the height of the colliding tiles, so it may be true coming from a point but false coming from another. Is that the problem?

    That's fine, A* can tolerate a spot being reachable from one side but not an other. What it cannot natively take into account is if the direction a spot was reached from affects which successors that node has, but that does not happen here.