A* 寻路需要绕过拐角，而不是穿过它们

Question

我有一个问题，我希望寻路计算绕过 "wall" 的一个角，像这样：

* []|
[][]|
____|

但就目前而言，它会切开墙角。我不能完全消除对角线移动，我希望寻路允许在开放区域进行对角线移动。截至目前，我只能通过创建另一个 "wall there." 来说服它根本不占据角落。这是所需的代码：

public static void Ai() {
    open.add(grid[startX][startY]);

    Cell current;

    while (true) {
        current = open.poll();
        //If the cell is blocked, move on
        if (current == null)break;
        closed[current.x][current.y] = true;

        //If cell is where you want to end up, stop the loop
        if (current.equals(grid[endX][endY])) {
            return;
        }

        Cell t;
        if(current.x-1>=0){
            t = grid[current.x-1][current.y];
            checkAndUpdateCost(current, t, current.finalCost+V_H_COST); 

            if(current.y-1>=0){                      
                t = grid[current.x-1][current.y-1];
                if (checkAndReturnWall(grid[current.x-1][current.y]) || checkAndReturnWall(grid[current.x][current.y - 1])) {
                    checkAndUpdateCost(current, t, (current.finalCost + DIAGONAL_COST) * 500);
                }
                else checkAndUpdateCost(current, t, current.finalCost+DIAGONAL_COST); 
            }

            if(current.y+1<grid[0].length){
                t = grid[current.x-1][current.y+1];
                if (checkAndReturnWall(grid[current.x-1][current.y]) || checkAndReturnWall(grid[current.x][current.y + 1])) {
                    checkAndUpdateCost(current, t, (current.finalCost + DIAGONAL_COST) * 500);
                }
                else checkAndUpdateCost(current, t, current.finalCost+DIAGONAL_COST); 
            }
        } 

        if(current.y-1>=0){
            t = grid[current.x][current.y-1];
            checkAndUpdateCost(current, t, current.finalCost+V_H_COST); 
        }

        if(current.y+1<grid[0].length){
            t = grid[current.x][current.y+1];
            checkAndUpdateCost(current, t, current.finalCost+V_H_COST); 
        }

        if(current.x+1<grid.length){
            t = grid[current.x+1][current.y];
            checkAndUpdateCost(current, t, current.finalCost+V_H_COST); 

            if(current.y-1>=0){
                t = grid[current.x+1][current.y-1];
                if (checkAndReturnWall(grid[current.x+1][current.y]) || checkAndReturnWall(grid[current.x][current.y - 1])) {
                    checkAndUpdateCost(current, t, (current.finalCost + DIAGONAL_COST) * 500);
                }
                else checkAndUpdateCost(current, t, current.finalCost+DIAGONAL_COST); 
            }

            if(current.y+1<grid[0].length){
               t = grid[current.x+1][current.y+1];
                if (checkAndReturnWall(grid[current.x+1][current.y]) || checkAndReturnWall(grid[current.x][current.y + 1])) {
                    checkAndUpdateCost(current, t, (current.finalCost + DIAGONAL_COST) * 500);
                }
                else checkAndUpdateCost(current, t, current.finalCost+DIAGONAL_COST); 
            }  
        }
    }

墙壁作为单元格返回为 null，checkAndReturnWall returns 当所选单元格中存在墙壁时为真。

Answer 1

假设您的运动场是 square-grid，那么您可以将运动评估为 2 个运动（[=16= 上的一个运动，y-axis 上的一个运动), 然后将其作为一个来执行。详细说明：

您正在尝试移动 north-east。请原谅我的伪代码：

if(checkEastCell() != wall){
   moveNorthEast();
}
else if(checkNorthCell() != wall){
   moveNorthEast();
}
else{
   pathingFailure(); 
}

A* 寻路需要绕过拐角，而不是穿过它们

A* Pathfinding Needs to go around corner, not through them

java

a-star

path-finding