A*寻路问题Processing(Java)

Question

我对编程还很陌生，虽然按照一堆教程我最终得到了这段代码来处理我正在尝试制作的小游戏的寻路。

If 适用于小而直的路径但不适用于复杂的路线（它冻结并且 closedSet.size() 在仅 54 * 46 的网格中变得大于 70000）。

请注意 wall 是否为真取决于碰撞方块的高度，因此它可能来自一个点为真但来自另一个点为假。是这个问题吗？

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

如有任何建议或微小的更改，我们也将不胜感激。

Answer 1

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

您的代码确实实现了一些逻辑

“如果节点已关闭，则不再处理它”，并且
"如果节点已经在open set中，比较G分数"

但在这两种情况下它都不起作用，因为 Spot 没有实现 equals，因此 contains 正在比较引用相等性，它总是错误的。因此，实施 Spot.equals。具体来说，让它只比较 x 和 y，因为 f/g/h/parent 对于被认为相等的节点允许不同。

即使有效，在 ArrayList 和 PriorityQueue 上使用 contains 对性能来说也不是很好。对于封闭列表，很容易使用HashSet（当然，也可以实现Spot.hashCode，某种程度上只依赖于x和y）。对于 open 列表，摆脱 slow contains 是更多的工作。您可以使用的一个技巧是手动维护一个二进制堆，另外还有一个 HashMap 将 x,y 对映射到相应节点所在的堆中的索引。手动维护堆的原因是每当节点在队列中移动时必须更新HashMap，而普通的PriorityQueue没有这样的功能。

从性能的角度来看，寻找继任者的工作方式也让我担心，但我看不到细节。

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?

没关系，A* 可以容忍一个点可以从一侧到达但不能从另一侧到达。它本身无法考虑的是，到达某个点的方向是否会影响该节点具有哪些后继节点，但这不会发生在这里。

A*寻路问题Processing(Java)

A* Pathfinding problems Processing(Java)

java

processing

a-star