a* pathFinding，实现不能正常工作？有什么建议吗？

Question

嗨，我正在用曼哈顿的距离来实现一个路径查找器，似乎可以用它来包围我的头脑:这是搜索的代码，

 public LinkedList<MapNode> search(MapNode startNode, MapNode goalNode) {

    LinkedList<MapNode> closedList = new LinkedList<MapNode>();
    LinkedList<MapNode> openList = new LinkedList<MapNode>();

    openList.add(startNode);

    startNode.setPathParent(null);

    while (!openList.isEmpty()) {
        MapNode node = (MapNode) openList.removeFirst();

        if (node == goalNode) 
            return constructPath(goalNode);

        else {
            closedList.add(node);

            // add neighbors to the open list
            Iterator<MapNode> i = getNeighbours(node, goalNode).iterator();

            while (i.hasNext()) {
                MapNode neighborNode = (MapNode) i.next();

                if (!closedList.contains(neighborNode) && !openList.contains(neighborNode)) {
                        neighborNode.setPathParent(node);
                        openList.add(neighborNode);

                }
            }
        }
    }
    // no path found
    return null;
}

下面是我的getneighbours()方法：

public LinkedList<MapNode> getNeighbours(MapNode node, MapNode goalNode) {

    Position positionCheck = new Position(0, 0);

    for (int x = -1; x < 2; x++){

        int newX = node.getPosition().getPositionX() + x;
        if(newX<0 || newX >= Map.DIMENSION){continue;}

        for (int y = -1; y < 2; y++){

            int newY = node.getPosition().getPositionY() + y;
            if(newY<0 || newY >= Map.DIMENSION){continue;}

            positionCheck.setPositionX(newX);
            positionCheck.setPositionY(newY);

            if(!node.getPosition().equals(positionCheck)){
                calculateCost(map.elementAt(positionCheck), goalNode);

                neighbours.add(map.elementAt(positionCheck));
            }
        }

    }   

    return neighbours;
}

它可以工作，但不幸的是它没有使用曼哈顿原则，其输出如下：

 Shortest Delivery Point is: 6 miles! - 8,7 // using manhattan distance
 S = Start, D=Destination, "."= path taken.


 [3,4] ->
 [4,3] ->
 [5,4] ->
 [6,5] ->
 [ D ] ->

 [0,0]  [0,1]  [0,2]  [0,3]  [0,4]  [0,5]  [0,6]  [0,7] 
 [1,0]  [1,1]  [1,2]  [1,3]  [1,4]  [1,5]  [1,6]  [1,7] 
 [2,0]  [2,1]  [2,2]  [2,3]  [2,4]  [ S ]  [2,6]  [2,7] 
 [3,0]  [3,1]  [3,2]  [3,3]  [ . ]  [3,5]  [3,6]  [3,7] 
 [4,0]  [4,1]  [4,2]  [ . ]  [4,4]  [4,5]  [4,6]  [4,7] 
 [5,0]  [5,1]  [5,2]  [5,3]  [ . ]  [5,5]  [5,6]  [5,7] 
 [6,0]  [6,1]  [6,2]  [6,3]  [6,4]  [ . ]  [6,6]  [6,7] 
 [7,0]  [7,1]  [7,2]  [7,3]  [7,4]  [7,5]  [ D ]  [7,7] 

我只是想知道是否有人能发现我做不到的事，这是我第一次弄乱寻路，所以我有点不舒服。谢谢你的帮助..。

Answer 1

从打开列表中取出的节点必须是F成本最小的节点。这使得使用链接列表是一个错误的选择--要么必须彻底搜索它才能提取节点，要么必须彻底搜索它才能插入节点。但是，不管选择与否，这样的选择是不正确的，因为你两者都不做。

另外，如果邻居已经在开放列表中，那么如果新的路径更好的话，您必须比较G分数，并重新使用它。

对闭集使用链接列表也是一个错误的选择，您只需要在其上添加“添加”和“包含”，而包含对于链接列表则是很糟糕的。不过，这并不影响正确性。