问题：

用基于平铺的移动计算所有可能的endpoint的算法

通和裕

2023-03-14

注意：我目前不检查是否一个瓷砖被占用，我想采取这一步一次，第一步是得到正确的结果，哪些瓷砖的角色可以去。

我有一个板大小的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;
    }
}`

左上和右下象限工作正常，但右上和左下没有，这真的难倒我了。你能帮我想出一个新算法或者修正这个算法吗？

共有1个答案

丁鸿信

2023-03-14

您可以通过存储步骤数乘以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)的平铺。然后，我们将重复地从队列中提取一个平铺，检查它的邻居中的哪个值大于当前平铺的值加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  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)

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

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

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,-1)(1,0)(1,1)(0,1)(-1,1)(-1,0)，对于每个（dx,dy）检查:
坐标(x+dx，y+dy)是否在网格内，
以及tile(x+dx，y+dy)是否是障碍，
以及平铺(x+dx，y+dy)是否为空或其值大于当前平铺加2或3。
如果所有三个条件都是，则将(x+dx，y+dy)的值替换为当前平铺的值加2或3。
如果tile(x+dx,y+dy)的新值小于最大距离减1，则将tile(x+dx,y+dy)添加到队列中。

类似资料：

计算移动平均数MySQL？

问题内容：美好的一天，我正在使用以下代码来计算9天移动平均线。但这是行不通的，因为它会在调用限制之前先计算所有返回的字段。换句话说，它将计算该日期之前或等于该日期的所有关闭时间，而不仅仅是最后9个。因此，我需要从返回的选择中计算出SUM，而不是直接计算出来。 IE浏览器从SELECT中选择SUM … 现在我将如何去做，这是非常昂贵的还是有更好的方法？问题答案：使用类似内查询返回的所
高效的“滚动/移动哈希”计算（如移动平均）

我正在尝试优化一个程序，该程序需要在数据流的每个位置（字节）为数据流中的恒定大小窗口计算哈希。在比可用RAM大得多的磁盘文件中查找重复时需要它。目前我为每个窗口计算单独的md5哈希，但它花费了很多时间（窗口大小为几千字节，因此每个数据字节被处理几千次）。我想知道是否有一种方法可以在恒定（与窗口大小无关）时间内计算每个后续哈希（例如移动平均中1个元素的加减）？哈希函数可以是任何东西，只要它不提供长哈
使用Python编写平铺地板的算法

我正试着做作业，但做不到。我研究了很多相关的话题，但找不到答案，所以需要帮助。我们的老师想要这个；制定一个计划，用4×4英寸大小的黑白相间的瓷砖铺一个矩形浴室地板。地板尺寸（以英寸为单位）是4的倍数确定输入和输出。输入是地板尺寸（长×宽），以英寸为单位。输出是瓷砖地板。 Step2）将问题分解为更小的任务。自然的子任务是铺设一排瓷砖。如果可以解决这个问题，那么可以通过从一面墙开始，将一行
基于2D平铺的碰撞检测

我计划一个独立游戏项目已经有一段时间了。我会为你总结一下，这样我就可以直接回答这个问题。它是通过Visual Studio完全使用最新版本的XNA完成的。希望将其放在360和PC上，但目前我只是在真正寻找面向PC的解决方案。这是一个2D侧向滚动射击游戏（想想大都会风格，甚至是Terraria）。它最终将包括一个游戏中的地图编辑器，地图是基于图块的（16x16）。会有向上和向下滚动。我希望在开发
PySpark：计算指数移动平均线

公式链接:https://sciencing.com/calculate-exponential-moving-averages-8221813.html
Java 计算给定 int 数组的所有可能组合

我正在尝试构造一个程序，该程序将获取一个int（｛1，2，3｝）数组和一个长度值，并计算该数组的所有可能组合。例如: 这将输出：但是当我尝试在 for 循环中调用可能的梳子时，我不断收到堆栈溢出错误 }

用基于平铺的移动计算所有可能的endpoint的算法

共有1个答案

相关问答

相关文章

相关阅读

相关工具

相关文档