A* 寻路 - 停止通过瓷砖对角线移动

Question

我正在尝试了解 A* 搜索算法，我得到了一个正在穿过迷宫的正方形，但该正方形将穿过两个角接触的方块。这是一个例子：

Image - Click here

有没有办法阻止算法将其添加到路径中

public List<Node> findPath(Vector2i start, Vector2i goal){

    List<Node> openList = new ArrayList<Node>();
    List<Node> closeList = new ArrayList<Node>();

    Node current = new Node(start, null, 0, getDistance(start, goal));
    openList.add(current);
    while(openList.size() > 0){
        Collections.sort(openList, nodeSorter);
        current = openList.get(0);
        if(current.tile.equals(goal)){
            List<Node> path = new ArrayList<Node>();
            while(current.parent != null){
                path.add(current);
                current = current.parent;
            }
            openList.clear();
            closeList.clear();
            return path;
        }
        openList.remove(current);
        closeList.add(current);
        for(int i = 0; i < 9; i++){
            if(i == 4) continue;
            int x = current.tile.getX();
            int y = current.tile.getY();
            int xi = (i % 3) - 1;
            int yi = (i / 3) - 1;
            Tile at = getTile(x + xi, y + yi);
            if(at == null || at == Tile.voidTile) continue;
            if(at.isSolid()) continue;

            Vector2i a = new Vector2i(x + xi, y + yi);
            double gCost = current.gCost + getDistance(current.tile, a);
            double hCost = getDistance(a, goal);
            Node node = new Node(a, current, gCost, hCost);
            if(vecInList(closeList, a) && gCost >= current.gCost) continue;
            if(!vecInList(openList, a) || gCost < node.gCost) openList.add(node);
        }
    }
    closeList.clear();
    return null;
}

Answer 1

小题外话：如果你不想把这样的tile添加到open list，那么它们一定不能被认为是neighbors。所以你应该回答创建寻路算法的基本问题 - 在我的图中哪些节点被认为是邻居。

在你的情况下，你的 current tile 不是 diagonal tile if 他们的邻居两个共同邻居都不合格。例如，对于图块 {+1, +1}，这些邻居将是 {0, +1} 和 {+1, 0}。等等。那么，让我们检查一下：

// code here...
if(at.isSolid()) continue;

if (Math.abs(xi * yi) == 1) {
  // this is true if we're checking diagonal tile
  if ( !isPassable(getTile(x + xi, y)) && !isPassable(getTile(x, y + yi))  {
    // Both common neigbors are not passable
    // So we won't add this tile as neighbor
    continue;
  }
}

方法是可以通过的：

private boolean isPassable(Tile tile) {
  return tile != Tile.voidTile && !tile.isSolid();
}

如果你处理对角线瓷砖，那么公共邻居总是存在的，所以你不应该检查它们是否为空。

A* 寻路 - 停止通过瓷砖对角线移动

A* Pathfinding - Stop moving diagonal through tiles

java

path-finding

2d-games