我一直在尝试开发一个算法,根据以下参数显示在正方形棋盘上可以移动到哪些格子:
- 您每次移动角色时,可以将其移动速度内的任何格子。 - 每个水平/垂直移动值为1格。 - 每个对角线值为1.5格(向下舍入-因此第一个对角线值为1,第二个对角线值为2,然后再回到1等)。 - 您无法将角色移动到其他角色占据的格子上,因此必须绕过它们。
注意:我当前没有检查瓷砖是否被占用,我希望一步一步来,第一步是获得角色可以移动到哪些瓷砖的正确结果。
我有一个尺寸为棋盘大小的三维数组。第三个维度有两个层,第一个初始化为全部为99,除了您要移动的角色(原点),该角色设置为0。该维度包含从每个瓷砖到原点的距离。 另一层包含到达该瓷砖所需的对角线数。
基本上,我有一个递归函数,检查每个相邻的瓷砖以获取到达原点的最短距离,并将当前瓷砖设置为该最低距离号码+1(如果是第二个对角线,则为+2)。它从原点递归地向外移动,使用已经填充的瓷砖来生成可以移动到的所有潜在瓷砖的地图。
左上和右下象限可以正常工作,但右上和左下象限不能,这真的让我感到困惑。您能否帮助我提出一个新算法或修复此算法?
- 您每次移动角色时,可以将其移动速度内的任何格子。 - 每个水平/垂直移动值为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;
}
}`
这是在15x15的网格上,从7,7开始以4的移动速度打印出来的结果(仅用于测试目的,边界为15)。
(为了更容易阅读,顶部网格中的99已被替换为“ ”)
左上和右下象限可以正常工作,但右上和左下象限不能,这真的让我感到困惑。您能否帮助我提出一个新算法或修复此算法?