Пытаясь реализовать алгоритм A* после нескольких часов попыток, я подумал, что попросил бы кого-нибудь просмотреть мой код

Question

Я пытался реализовать алгоритм A* в игре в стиле Tower Defense, и после нескольких часов попыток я подумал, что хотел бы получить представление о моих логических недостатках. Я пытался создать его с помощью http://web.mit.edu/eranki/www/tutorials/search/ & /questions/28192655/nevozmozhno-realizovat-zvezdu-v-java/28192673#28192673 Но при попытке генерации возникает бесконечная проблема преемники / соседи по узлу AStarNode(я думаю) - впервые внедряем 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 и равно. Таким образом, два узла с одинаковыми координатами не считаются равными, поэтому closed.contains(successor) НИКОГДА не вернет истину.

Реализуйте hashCode и equals на AStarNode (или попросите вашу 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;
}