java A*（星型）算法|有墙时如何返回？

Question

我目前正在尝试实现A*（A星）算法。当我没有墙的时候，当它只需要沿着墙走的时候，我已经让它工作了。我现在的问题是，当我把起点放在墙里面时，我的算法是无限计算的，因为我认为它不会倒转。你们能帮帮我吗

以下是节点类的代码：

int[][] mMap; // if there is a wall => 1

int[][] mAStarField;
ArrayList<AStarNode> mAStarPath;

public class AStarNode implements Comparable<AStarNode>{ 
  public int x; 
  public int y; 
  public float c;
  public AStarNode p; 
  public AStarNode(int x, int y, float c, AStarNode p) { 
    this.x = x; //X pos
    this.y = y; //Y pos
    this.c = c; //Cost to get to the node
    this.p = p; //Parent of the node
  }
  //override the compareTo method 
  public int compareTo(AStarNode node) 
  { 
    if (c == node.c) 
      return 0; 
    else if (c > node.c) 
      return 1; 
    else
      return -1; 
    } 
  
  
} 

public class Node { 
  public int x; 
  public int y; 
  public int z; 
  public int w; 
  public Node(int x, int y, int z, int w) { 
    this.x = x; 
    this.y = y;
    this.z = z; 
    this.w = w;
  }
}

这是我的A*算法的代码：

//Pathfinding with A*
//return path length
int updateAStar() {


  //Needed for drawing:
  //Array containing the distance to the start node (filled with max int at start)
  mAStarField = new int[mMap.length][mMap[0].length];
  //List containing the found path
  mAStarPath = new ArrayList<AStarNode>();

  for (int j = 0; j < mMap.length; j++) {
    for (int k = 0; k < mMap[0].length; k++) {
      mAStarField[j][k]=Integer.MAX_VALUE;
    }
  }

//AStarNode(x,y,c,w)
  //x X pos
  //y Y pos
  //c Cost to get to the node
  //p Parent of the node

  //List can be sorted expensive but simple by c value with
  //Collections.sort(openList); 
  ArrayList<AStarNode> openList = new  ArrayList<AStarNode>();
  ArrayList<AStarNode> closedList = new  ArrayList<AStarNode>();

  int dist = abs(mStartNode[0]-mEndNode[0])+abs(mStartNode[1]-mEndNode[1]);

  //If there is any target, that isn't on my field, add start node to list
  if (dist>0 && mMap[mStartNode[0]][mStartNode[1]] != 1 && mMap[mEndNode[0]][mEndNode[1]]!=1) {
    openList.add(new AStarNode(mStartNode[0], mStartNode[1], 0, null));
    mAStarField[mStartNode[0]][mStartNode[1]] = 0;
  }
  
// my code begins here (only everything from here on can be edited!)

  while(!openList.isEmpty())
  {
    Collections.sort(openList);
    AStarNode current = openList.get(0);
    
    if(current.x == mEndNode[0] && current.y == mEndNode[1])
    {
      return 1;
    }
    
    openList.remove(0);
    closedList.add(current);
    
    ArrayList<AStarNode> neighbors = new  ArrayList<AStarNode>();
    neighbors.add(new AStarNode(current.x - 1, current.y, current.c + 1, current));
    neighbors.add(new AStarNode(current.x + 1, current.y, current.c + 1, current));
    neighbors.add(new AStarNode(current.x, current.y - 1, current.c + 1, current));
    neighbors.add(new AStarNode(current.x, current.y + 1, current.c + 1, current));
    
    for(AStarNode n : neighbors)
    {
      if(n.x >= 0 && n.y >= 0 && n.x < mMap.length && n.y < mMap.length && mMap[n.x][n.y] != 1){
      
      float cost = estimateDistanceEnd(n.x, n.y);
      n.c = cost;
      
      if(closedList.contains(n) && cost >= n.c) continue;
      
      if(!openList.contains(n) || cost < n.c)
      {
        n.p = current;
        
        if(!openList.contains(n)){
          mAStarField[n.x][n.y] = (int) n.c;
          openList.add(n);
          Collections.sort(openList);
        }
      }
      }
    }
    
  }
  return -1;
}

int estimateDistanceEnd(int x, int y){
   return abs(x-mEndNode[0])+abs(y-mEndNode[1]); 
}

int estimateDistanceStart(AStarNode a){
   return abs(a.x-mStartNode[0])+abs(a.y-mStartNode[1]); 
}

int estimateDistance(AStarNode a, AStarNode b){
   return abs(a.x-b.x)+abs(a.y-b.y); 
}

A picture of my current path solving result

重要提示：我只能在我标记的区域内更改代码

谢谢大家!

Answer 1

我无法运行代码，但我对问题的根源有一点了解。看，A*算法在寻找最佳路径时不会“后退”。它解决了寻路问题，通过计算成本较低的方法来到达它所评估的每个节点的末端。它首先计算最简单的路线，然后如果它不起作用，它会扩大它的选择，直到它，呃，找到一条路，或者没有选择

封闭列表的原理，避免对一个节点进行两次求值。正如您所猜测的，这里的问题是，在寻路算法的每次迭代中，您都在为邻居创建新节点，从而使封闭列表更难正确使用

像自定义类这样的复杂对象可以通过3种方式进行比较：要么是相同的对象（它引用相同的指针（它是相同的实例，它在计算机内存中的相同位置）），要么不管它的指针指向什么，值都是相同的，或者您可以定义一个规则来比较它们。这些方法是：通过引用进行比较、通过值进行比较和运算符重载——虽然最后一种方法在java中不可能实现，但您可以编写一个方法来实现同样的目的

在执行closedList.contains(n)时，您是通过引用进行比较的（这是此类操作的默认值）。由于所有节点都是动态创建的，即使它们的坐标相同，它们在内存中的地址也不同，这就是为什么永远不会满足此条件的原因

假设你不能弄乱导师的代码，你仍然可以解决这个问题。你第一次几乎就做对了！事实上，有很多方法可以解决这个问题，由于我错过了一些上下文，我建议的方法将非常简单：您将编写一个从列表中获取特定节点的方法（就像我所说的运算符重载，但只需付出最小的努力），从这一点开始，我们将通过引用工作

首先，创建一个所有AStarNode的主列表（如果您还没有主列表，那么使用该主列表）：

// my code begins here (only everything from here on can be edited!)
ArrayList<AStarNode> nodesList = new  ArrayList<AStarNode>();
for (int j = 0; j < mapWidth; j++) {
  for (int k = 0; k < mapHeight; k++) {
    nodesList.add(new AStarNode(j, k)); // I gimmicked the constructor for my own confort, you'll have to tweak this line so it fits in your code
  }
}

然后，编写一个方法，根据给定的xy坐标从数组返回节点：

AStarNode GetAStarNodeByPosition(int x, int y, ArrayList<AStarNode> list) {
  for (AStarNode m : list) {
    if (m.x == x && m.y == y) {
      return m;
    }
  }

  return null;
}

现在，您可以使用它们通过引用来比较所有节点。因此，现在，您将始终通过引用从主列表中获取新节点，而不是一直实例化新节点：

ArrayList<AStarNode> neighbors = new  ArrayList<AStarNode>();
neighbors.add(GetAStarNodeByPosition(current.x - 1, current.y, nodesList));
neighbors.add(GetAStarNodeByPosition(current.x + 1, current.y, nodesList));
neighbors.add(GetAStarNodeByPosition(current.x, current.y - 1, nodesList));
neighbors.add(GetAStarNodeByPosition(current.x, current.y + 1, nodesList));

另外，不要忘记修复这一行：

//openList.add(new AStarNode(mStartNode[0], mStartNode[1], 0, null));
openList.add(GetAStarNodeByPosition(mStartNode[0], mStartNode[1], nodesList));

最后，如果你知道你的数组中可能有一些null，那么一定要记得测试它。在这种情况下，如果离迷宫的边界太近，GetAStarNodeByPosition方法可以返回一个null。您可以修改添加到邻居列表的方式，使其中没有null，也可以在此行中检查null：

if(n != null && n.x >= 0 && n.y >= 0 && n.x < mMap.length && n.y < mMap.length && mMap[n.x][n.y] != 1){

老实说，我完全不会在数组中包含null，如果以后进一步修改代码，会更安全

现在，所有节点都将相互关联，您将能够克服障碍，这需要您的算法以比直线更聪明的方式进行搜索

玩得开心