如何在不实际增加数组大小的情况下在数学上具有数组边界？

Question

所以我有一个由 64 个方块组成的一维数组表示的游戏板，我想知道一块棋子何时试图逃离边界。

例如：假设国际象棋中的国王在 X 上：

0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 X 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

用一个方向向量很容易计算出被攻击的方格：

-9, -8, -7,
-1,      1,
 7,  8,  9

0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 1 1 1 0 0
0 0 0 1 X 1 0 0
0 0 0 1 1 1 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

另外，如果他在棋盘的上边缘或下边缘：我只是添加一个 if 来检查 square + directionvector[i] > 63 或方形 + directionvector[i] < 0

所以：

0 0 0 1 X 1 0 0
0 0 0 1 1 1 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

当它位于侧边时，问题就来了：

0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 1
1 0 0 0 0 0 1 X
1 0 0 0 0 0 1 1
1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

这是将发生的事情，它会“跳”到上面看到的错误位置。

你知道有什么方法可以检查这个吗？谢谢

Answer 1

您可以从单元格索引中获取行号 i / 8（floored），并使用它来检查是否向右或向左一步传递到另一行。

例如在这里，在一个四列的棋盘上，从位置 7 向“右”走，我们到达位置 8。它们的行号是 7 / 4 = 1 和 8 / 4 = 2，所以我们换到另一行。

....
...7
8...
....

但是对角线移动更难做到，因为您希望它们改变行。最后，这几乎只是将电路板变成二维数组，步长偏移为二维值，您可以在其中以明显的方式检查溢出。

IMO，原则上你所要求的对于一维板来说是不可能的。将板定义为一维向量（类似地，将偏移量定义为一维偏移量），则板内没有边缘，也没有任何东西可以逃逸。而不是这个：

.ab.
....
...c
d...

你真的只有这个：

.ab........cd...

很明显，c 和 d 彼此相邻，就像 a 和 b 一样。

Answer 2

在你的程序开始时，你可以预先计算出每个棋子和每个方格的合法移动并将它们存储在某个地方。

假设您的方格编号为 0 到 63，那么 KING_MOVES[i] 将存储国王在方格 i 上的合法移动（其中 i 的范围为 0 到 63） .例如，KING_MOVES[0] = { 1, 8, 9 } 和 KING_MOVES[31] = { 22, 23, 30, 38, 39 }。同样，对于角落里的马，KNIGHT_MOVES[0] = { 10, 17 }.

  0  1  2  3  4  5  6  7
  8  9 10 11 12 13 14 15
 16 17 18 19 20 21 22 23
 24 25 26 27 28 29 30 31
 32 33 34 35 36 37 38 39
 40 41 42 43 44 45 46 47
 48 49 50 51 52 53 54 55
 56 57 58 59 60 61 62 63

每个方格的合法步数不同（国王在中心有 8 步，但在角落只有 3 步）。您可以单独存储合法移动的数量（例如 NUM_KING_MOVES[31] = 5），或者您可以用特殊值终止每个列表，例如 -1 或 64。

要预先计算这些列表，您可以将每个一维数字转换为一对（行、列）坐标，并通过边界检查天真地生成移动。对于第 31 格上的国王，您将 31 转换为（第 3 行，第 7 列）。当向右移动时，你最终到达（第 3 行，第 8 列），这是非法的，因此你放弃此移动。当移动到左上角时，您最终到达（第 2 行，第 6 列），这是合法的，因此您将其转换回一维表示：2 * 8 + 6 = 22。您将此移动附加到 KING_MOVES[31]等等。

这为您提供了两全其美的方法：更快、更短的移动生成代码，并且不会因填充而在每块棋盘上浪费内存。缺点是需要几千字节的额外内存。

如果您要走这条路，您还可以查看 bitboards 以获得更快的移动生成。

如何在不实际增加数组大小的情况下在数学上具有数组边界？

how to mathematically have array border without actually increasing the array size?

arrays

chess

vector