经过数小时的尝试后尝试实施 A* 算法 我想我会请人审查我的代码

Question

我一直在尝试在塔防类游戏中实现 A* 算法，经过几个小时的尝试，我想我会要求对我的逻辑缺陷有一些了解。 我一直在尝试通过 http://web.mit.edu/eranki/www/tutorials/search/ & 创建它 但是，在尝试为 AStarNode 生成 successors/neighbors 时出现无限问题（我认为）- 第一次实现 A* 并且仍在学习。

private ArrayList<AStarNode> aStaring(Object o, AStarNode start, AStarNode goal) {
    ArrayList<AStarNode> closed = new ArrayList();
    ArrayList<AStarNode> open = new ArrayList();

    start.g = 0;
    start.h = estimateDistance(start, goal);
    start.f = 0;

    open.add(start);

    while(!open.isEmpty()){
        AStarNode q = null;

        for(AStarNode asn : open){
            if(q == null || asn.f < q.f){
                q = asn;
            }
        }

        open.remove(q);
        closed.add(q);
        for(AStarNode succesor : q.generateSuccesors()){
            if(closed.contains(succesor)){
                System.out.println("Closed contained succesor");
                //TODO Check if walkable 
            }else{
                if(!open.contains(succesor)){
                    succesor.g = q.g+1;
                    succesor.h = estimateDistance(succesor, goal);
                    succesor.f = succesor.g + succesor.h;
                    succesor.parent = q;
                    open.add(succesor);
                }else{
                    float nextG = q.g + succesor.cost;
                    if(nextG < succesor.g){
                        open.remove(succesor);
                        closed.add(succesor);
                    }
                }
                if(succesor.x == goal.x && succesor.y == goal.y){ //path found
                    System.out.println("hurray");
                    return reconstructPath(succesor);
                }
            }
        }
    }
    return null;
}
public class AStarNode {

private MapDimension md = new MapDimension();
public AStarNode parent;
public int x,y;
public int f,g,h;
public int cost = 1;

public AStarNode(int x, int y){
    this.x = x;
    this.y = y;
}

//Looking up 4 neighbors and adding to node;
public ArrayList<AStarNode> generateSuccesors(){
    ArrayList<AStarNode> neighbors = new ArrayList<>();
    if(x+1 < md.getWidth()){
        AStarNode temp = new AStarNode(x+1,y);
        temp.parent = this;
        neighbors.add(temp);
    }
    if(x-1 > 0){
        AStarNode temp = new AStarNode(x-1,y);
        temp.parent = this;
        neighbors.add(temp);
    }
    if(y+1 < md.getHeight()){
        AStarNode temp = new AStarNode(x,y+1);
        temp.parent = this;
        neighbors.add(temp);
    }
    if(y-1 > 0){
        AStarNode temp = new AStarNode(x,y-1);
        temp.parent = this;
        neighbors.add(temp);
    }
    return neighbors;
}
}

地图：

public static final int[][] MAP = {
    {1, 1, 1, 1, 2, 2},
    {1, 1, 1, 0, 0, 2},
    {2, 0, 1, 0, 0, 0},
    {2, 0, 1, 0, 1, 1},
    {2, 2, 1, 1, 1, 1},
    {2, 2, 0, 0, 0, 1},
    {2, 1, 1, 1, 1, 1},
    {0, 1, 0, 0, 2, 2},
    {2, 1, 0, 2, 2, 2},
    {0, 1, 0, 0, 2, 2},
};

任何指向正确方向的指针都会很棒:]

Answer 1

每次你运行 generateSuccessors，你都会创建 4 个（或更少）AStarNode 对象的新实例。这本身不是问题，但是AStarNode没有定义hashCode和equals。所以坐标相同的两个节点不被认为是相等的，所以 closed.contains(successor) 永远不会 return 为真。

在 AStarNode 上实施 hashCode 和 equals（或让您的 IDE 为您完成）。像这样简单的东西：

public int hashCode(){
   return x*y;
}

public boolean equals(Object o){
  if (o instanceof AStarNode){
    return x==((AStarNode)o).x && y==((AStarNode)o).y;
  }
  return false;
}