我一直在尝试开发一种算法，根据这些参数显示您可以在正方形板上移动到哪个平铺：
-你可以在棋盘上移动你的角色，每转一圈，移动到他们移动速度范围内的任何棋盘上。
-每个水平/垂直移动值1个平铺。
-每个对角线值为1.5（向下舍入-因此第一个对角线值为1，第二个对角线值为2，然后返回到1，等等）。
-不能将角色移动到具有其他角色的平铺上，因此必须绕行。
注意：我目前不检查是否有平铺被占用，我想一步一步地执行此操作，第一步是获得角色可以转到哪个平铺的正确结果。
我有一个董事会大小的三维阵列。第三个维度有两个层，第一个被初始化为所有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
这是以4的移动速度打印时的结果，从15x15网格上的7、7开始（仅用于测试目的，edgeofboard=15）
（顶部网格上的99s替换为“”，以便于阅读）
顶部网格是三维空间的第一层，即到达该平铺所需的平铺数量。
底部网格是到达该平铺所需的对角线数。
左上角和右下角象限工作正常，但右上角和左下角不正常，这让我很难受。你能帮我想出一个新的算法还是修正这个算法？
最佳答案
通过存储步骤数乘以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)
当我们从队列中获取tile（5,3）时，它的值为2，因此它的邻居（4,3）将获得值4；但是，该tile已经具有较小的值3，因此我们保留较小的值，并且不将tile添加到队列中。在处理完这个瓷砖的所有邻居之后，我们得到：
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）添加到队列中。
关于c# - 基于平铺运动计算所有可能终点的算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/57845587/