使用基于 Tile 的移动计算所有可能终点的算法

Question

我一直在尝试开发一种算法，根据这些参数显示您可以在方形板上移动到哪些方块：

-你将你的角色在棋盘上每转一圈移动到他们移动速度范围内的任何板块。

-每个 horizontal/vertical 移动值 1 个板块。

-每条对角线值 1.5（向下舍入 - 因此第一个对角线值 1，第二个对角线值 2，然后返回 1，依此类推）。

-你不能将一个角色移动到上面有另一个角色的方块上，所以你必须四处走动。

注意：我目前不检查某个方格是否被占用，我想一次执行此步骤，第一步是获得角色可以去哪些方格的正确结果。

我有一个棋盘大小的 3d 数组。第三个维度有两层，第一个被初始化为所有 99，除了你正在移动的角色（原点），它被设置为 0。这个维度包含每个瓦片到原点的距离。另一层包含到达该图块所需的对角线数。

基本上我有一个递归函数，它检查每个相邻的图块到原点的最短距离，并将当前图块设置为该最小距离数字 +1（如果它是第二个对角线，则为 +2）。它递归地从原点移出，使用它已经填充的图块生成它可以移动到的所有潜在图块的地图。

`

const int edgeOfBoard = 15;
static int[,,] movementCount = new int[edgeOfBoard, edgeOfBoard, 2]; //movement speed/diagonals tracking matrix

static void Main()
{
    int movementSpeed = 4;  //number of tiles character can move
    int x = 7;              //x starting position
    int y = 7;              //y starting position

    for(int i = 0; i < edgeOfBoard; i++)    //fill movementCount with 99
    {
        for(int j = 0; j < edgeOfBoard; j++)
        {
            movementCount[i, j, 0] = 99;
        }
    }

    movementCount[x, y, 0] = 0; //set origin (character's location) as 0 movements from itself

    pathfinder(movementSpeed, x, y, 0); //run pathfinder algorithm
    print();    //print result
}

private static void print() //print result
{
    for(int y = 0; y < edgeOfBoard; y++)    //print movement to get to a given tile
    {
        for(int x = 0; x < edgeOfBoard; x++)
        {
            if(movementCount[x, y, 0] == 99) //replace 99s with " " to make it easier to read
            {
                Console.Write("| ");
            }else
            {
                Console.Write("|" + movementCount[x, y, 0]);
            }
        } 
        Console.WriteLine("|");
    }

    Console.WriteLine();


    for(int y = 0; y < edgeOfBoard; y++)    //print diagonals needed to get to a given tile
    {
        for(int x = 0; x < edgeOfBoard; x++)
        {
            if(movementCount[x, y, 1] == 0) 
            {
                Console.Write("| ");
            }else
            {
                Console.Write("|" + movementCount[x, y, 1]);
            }
        } 
        Console.WriteLine("|");
    }
}

internal static void pathfinder(int movementSpeed, int x, int y, int depth)
{
    if (depth <= movementSpeed) //cuts off when limit is reached
    {

        for (int Y = -1; Y <= 1; Y++)   //checks all adjacent tiles
        {
            for (int X = -1; X <= 1; X++)
            {
                //Console.WriteLine("y = " + y + ", Y = " + Y + ", x = " + x + ", X = " + X + ", mvC[] = " + movementCount[x + X, y + Y, 0]);

                //Checks if current adjacent tile subject is in bounds and is not the origin of the search
                if (y + Y >= 0 && y + Y <= edgeOfBoard && x + X >= 0 && x + X <= edgeOfBoard && !(Y == 0 && X == 0) && (movementCount[x + X, y + Y, 0] == 99)) 
                {
                    int[] lowestAdjacent = findLowestAdjacent(x + X, y + Y); //find the lowest adjacent tile
                    if (lowestAdjacent[0] + 1 <= movementSpeed) //if it is within the movement speed, add it to the matrix
                    {
                        movementCount[x + X, y + Y, 0] = lowestAdjacent[0] + 1; //update movement speed for subject tile
                        movementCount[x + X, y + Y, 1] = lowestAdjacent[1];     //update number of diagonals needed for subject tile
                        //print();
                    }
                }

            }
        }

        for (int Y = -1; Y <= 1; Y++)   //mmove into already checked tiles to recursively check their adjacent tiles
        {
            for (int X = -1; X <= 1; X++)
            {
                if (y + Y >= 0 && y + Y <= 15 && x + X >= 0 && x + X <= 15 && !(Y == 0 && X == 0) && (movementCount[x + X, y + Y, 0] != 99) && (movementCount[x + X, y + Y, 0] < movementSpeed))
                {
                    pathfinder(movementSpeed, x + X, y + Y, depth + 1);
                }
            }
        }
    }
}

private static int[] findLowestAdjacent(int x, int y) //finds lowest number of movements to get to subject tile (x, y)
{
    int[] lowestRtrn = { 99, 0 }; //movement, diagonals
    int lowest = 99;

    for (int Y = -1; Y <= 1; Y++)   //checks each adjacent tile
    {
        for (int X = -1; X <= 1; X++)
        {
            if (y + Y >= 0 && y + Y <= edgeOfBoard && x + X >= 0 && x + X <= edgeOfBoard) //ensures it is within bounds
            {
                int diag = isDiagonalMovement(x, y, x + X, y + Y) ? diagonalMovementIncrease(movementCount[x + X, y + Y, 1] + 1) : 0;   //checks whether or not it should be diagonally increased
                if ((movementCount[x + X, y + Y, 0] + diag) < lowest)   //adds to result if lower than current
                {
                    lowest = movementCount[x + X, y + Y, 0] + diag;
                    lowestRtrn[1] = movementCount[x + X, y + Y, 1] + (isDiagonalMovement(x, y, x + X, y + Y) ? 1 : 0);
                }
            }
        }
    }

    lowestRtrn[0] = lowest;
    return lowestRtrn;  
}   

private static int diagonalMovementIncrease(int diagonalMovements)  //checks if diagonal is second diagonal (+2 instead of +1)
{
    return diagonalMovements % 2 == 0 ? 1 : 0;
}

private static bool isDiagonalMovement(int x, int y, int X, int Y) //checks if (x, y) is diagonal from (X, Y)
{
    if (
        (x + 1 == X && y + 1 == Y) ||
        (x - 1 == X && y + 1 == Y) ||
        (x + 1 == X && y - 1 == Y) ||
        (x - 1 == X && y - 1 == Y)
        )
    {
        return true;
    }
    else
    {
        return false;
    }
}`

Code Result

这是在 15x15 网格上从 7、7 开始以移动速度 4 打印时的结果（仅用于测试目的，edgeOfBoard = 15）（99s 替换为顶部网格中的“”以使其更易于阅读）

顶部网格是三维的第一层 - 到达该图块所需的图块数量。底部网格是到达该图块所需的对角线数。

左上和右下象限正常，但右上和左下象限却不行，这真难倒我。你能帮我想出一个新算法或解决这个问题吗？

Answer 1

可以将对角线步数乘以2存储为1.5步的业务简化。所以水平或垂直步数变为2，对角线步数变为3，最大距离x变为2*x+1。这意味着我们不必存储额外的网格，其中包含有多少对角线已用于到达任何图块。

让我们从这个网格开始，其中值为 99 表示它未被访问且为空：

99 99 99 99 99 99 99 99 99 99
99 99 99 99 99 99 99 99 99 99
99 99 99 99 99 99 99 99 99 99
99 99 99 99 99 99 99 99 99 99
99 99 99 99 99  0 99 99 99 99
99 99 99 99 99 99 99 99 99 99
99 99 99 99 99 99 99 99 99 99
99 99 99 99 99 99 99 99 99 99
99 99 99 99 99 99 99 99 99 99
99 99 99 99 99 99 99 99 99 99

我们从初始位置开始，即坐标为 (5,4) 的图块，在堆栈（这比使用递归简单得多）或队列（在这种情况下比堆栈更有效） .然后，我们将重复从队列中取出一个图块，检查它的哪个邻居的值大于当前图块的值加二（如果是对角线邻居，则为三），如果是，则替换邻居的值并添加平铺到队列中。处理完第一个图块的所有邻居后，我们会遇到这种情况：

99 99 99 99 99 99 99 99 99 99
99 99 99 99 99 99 99 99 99 99
99 99 99 99 99 99 99 99 99 99
99 99 99 99  3  2  3 99 99 99
99 99 99 99  2  0  2 99 99 99
99 99 99 99  3  2  3 99 99 99
99 99 99 99 99 99 99 99 99 99
99 99 99 99 99 99 99 99 99 99
99 99 99 99 99 99 99 99 99 99
99 99 99 99 99 99 99 99 99 99

队列中的这些图块：

(5,3), (6,3), (6,4), (6,5), (5,5), (4,5), (4,4), (4,3)

当我们从队列中取出瓦片 (5,3) 时，它的值为 2，因此它的邻居 (4,3) 将获得值 4；但是，该图块已经具有较小的值 3，因此我们保留该较小的值，并且不将该图块添加到队列中。处理完该图块的所有邻居后，我们得到：

99 99 99 99 99 99 99 99 99 99
99 99 99 99 99 99 99 99 99 99
99 99 99 99  5  4  5 99 99 99
99 99 99 99  3  2  3 99 99 99
99 99 99 99  2  0  2 99 99 99
99 99 99 99  3  2  3 99 99 99
99 99 99 99 99 99 99 99 99 99
99 99 99 99 99 99 99 99 99 99
99 99 99 99 99 99 99 99 99 99
99 99 99 99 99 99 99 99 99 99

如果可以达到的最大距离是，例如9（通过执行 2*4+1 从 4 转换而来），我们继续从队列中取出图块并处理它们的邻居，直到不再有新图块的值等于或小于 9，并且队列为空。最终结果是：

99 99 99 99  9  8  9 99 99 99
99 99  9  8  7  6  7  8  9 99
99 99  8  6  5  4  5  6  8 99
99  9  7  5  3  2  3  5  7  9
99  8  6  4  2  0  2  4  6  8
99  9  7  5  3  2  3  5  7  9
99 99  8  6  5  4  5  6  8 99
99 99  9  8  7  6  7  8  9 99
99 99 99 99  9  8  9 99 99 99
99 99 99 99 99 99 99 99 99 99

要将距离从 +2/+3 逻辑转换为 +1/+1.5 逻辑，请将网格中的值除以 2，例如9 变成 4。

您可以使用相同的二维网格来同时考虑障碍物。你可以例如用 99 标记空方块，用 -1 标记障碍物。初始网格：

99 99 99 99 99 99 99 99 99 99
99 99 99 99 99 99 99 99 99 99
99 99 99 99 99 99 99 99 99 99
99 99 99 99 -1 99 99 -1 99 99
99 99 99 99 99  0 99 -1 99 99
99 99 99 99 99 99 99 -1 99 99
99 99 99 99 99 -1 99 99 99 99
99 99 99 99 99 99 99 99 99 99
99 99 99 99 99 99 99 99 99 99
99 99 99 99 99 99 99 99 99 99

然后会导致：

99 99 99 99  9  8  9 99 99 99
99 99 99  8  7  6  7  8 99 99
99 99  8  7  5  4  5  7  9 99
99  9  7  5 -1  2  3 -1 99 99
99  8  6  4  2  0  2 -1 99 99
99  9  7  5  3  2  3 -1 99 99
99 99  8  6  5 -1  5  7  9 99
99 99  9  8  7  8  7  8 99 99
99 99 99 99  9 99  9 99 99 99
99 99 99 99 99 99 99 99 99 99

代码主要部分的详细信息将是：

从队列中取出一张牌。
迭代它的邻居：(-1,-1) (0,-1) (1,-1) (1,0) (1,1) (0,1) (-1,1) (-1,0) 和每个 (dx,dy) 检查：
坐标(x+dx,y+dy)是否在网格内，
瓦片(x+dx,y+dy)是否不是障碍物，
以及图块 (x+dx, y+dy) 是否为空或具有比当前图块大 2 或 3 的值。
如果对所有三个条件都是肯定的，则将 (x+dx,y+dy) 的值替换为当前图块的值加上 2 或 3。
如果瓦片(x+dx, y+dy) 的新值小于最大距离减1，则将瓦片(x+dx, y+dy) 添加到队列中。

使用基于 Tile 的移动计算所有可能终点的算法

Algorithm to Calculate all possible end points with Tile-based movement

c#

algorithm

recursion

grid

path-finding