java - 星算法不起作用

Question

我根据维基百科页面上的伪代码实现了这个算法link to page对于 A*，但它没有找到任何路径。当我使用它时，我永远不会达到当前节点等于目标的地步。我认为这可能与我的启发式或我初始化 f 和 g 分数的方式有关，但我似乎无法弄清楚。

我使用的 map 大小为 1920 x 1080，像元大小为 30。

private ArrayList<Vector2> aStar(Vector2 start, Vector2 goal) {
    HashSet<Vector2> closedSet = new HashSet<Vector2>();
    ArrayList<Vector2> openSet = new ArrayList<Vector2>();
    openSet.add(start);
    HashMap<Vector2,Vector2> cameFrom = new HashMap<Vector2, Vector2>();
    HashMap<Vector2,Float> gScore = new HashMap<Vector2, Float>();
    HashMap<Vector2,Float> fScore = new HashMap<Vector2, Float>();
    ArrayList<Vector2> neighbors = new ArrayList<Vector2>();
    neighbors.add(new Vector2(0,30));
    neighbors.add(new Vector2(0,-30));
    neighbors.add(new Vector2(30,0));
    neighbors.add(new Vector2(-30,0));
    for(int i = 0; i < 1920; i +=30){
        for(int j = 0; j < 1080; j +=30){
            gScore.put(new Vector2(i,j),Float.MAX_VALUE);
            fScore.put(new Vector2(i,j),Float.MAX_VALUE);
        }
    }
    gScore.put(start,0f);
    fScore.put(start,heuristic(start,goal));

    while(!openSet.isEmpty()){
        int low = 0;
        for(int i = 0; i < openSet.size(); i++){
            if(fScore.get(openSet.get(i))<fScore.get(openSet.get(low))){
                low = i;
            }
        }
        Vector2 current = openSet.get(low);
        if(current.equals(goal)){
            System.out.println("YES!");
            return null;
        }
        openSet.remove(current);
        closedSet.add(current);
        for(Vector2 neighbor:neighbors){
            Vector2 tst = new Vector2(neighbor.x + current.x,neighbor.y + current.y);
            if(tst.x > -30 && tst.x <1920 && tst.y > -30 && tst.y < 1080){
                neighbor.add(current);
                if(closedSet.contains(neighbor)){
                    continue;
                }
                if(!openSet.contains(neighbor)){
                    openSet.add(neighbor);
                }

                float tentative_gScore = gScore.get(current) + heuristic(current,neighbor);
                if(tentative_gScore >= gScore.get(neighbor)){
                    continue;
                }

                cameFrom.put(neighbor,current);
                gScore.put(neighbor,tentative_gScore);
                fScore.put(neighbor,gScore.get(neighbor)+heuristic(neighbor,goal));
            }
        }

    }

    return null;
}

private float heuristic(Vector2 begin, Vector2 end) {
    return  (Math.abs(begin.x - end.x) + Math.abs(begin.y - end.y)) ;
}

Answer 1

neighbor.add(current); 行改变了邻居。不仅如此，您还存储了那个邻居，这意味着该对象引用将被保留，并可能在未来的代码中进一步扭曲。

另一个问题是你的启发式。您使用的是曼哈顿距离，这意味着有大量路径都具有相同的距离(只要您从不离开目标节点，每条路径的距离都相同)。尝试允许对角邻居，并使用欧几里得距离而不是曼哈顿距离。