如何硬编码合法动作以进行快速查找？

Question

我已经创建了一个游戏板 (5x5)，现在我想尽快决定何时移动是合法的。例如在 (0,0) 的棋子想去 (1,1)，这是合法的吗？首先，我试图通过计算找出答案，但这似乎很麻烦。我想根据棋盘上的位置对可能的移动进行硬编码，然后遍历所有可能的移动以查看它们是否与棋子的目的地匹配。我很难把它写在纸上。这就是我想要的：

//game piece is at 0,0 now, decide if 1,1 is legal
Point destination = new Point(1,1);     
destination.findIn(legalMoves[0][0]);

我面临的第一个问题是我不知道如何将可能的着法列表放入数组中，例如索引 [0][0]。这一定是相当明显的，但我坚持了一段时间。我想创建一个数组，其中有一个 Point 对象列表。所以在半代码中：legalMoves[0][0] = {Point(1,1),Point(0,1),Point(1,0)} 我不确定这是否有效，但它在逻辑上比 [[1,1],[0,1],[1,0]] 更有意义，但我不赞成这样做。

我遇到的第二个问题是，与其在每次游戏开始时使用实例变量 legalMoves 创建对象，不如从磁盘读取它。我认为这样应该更快？可序列化 class 是正确的选择吗？

我的第三个小问题是，对于 25 个位置，合法移动是不平衡的。有些人有 8 种可能的合法着法，其他人有 3 种。也许这根本不是问题。

Answer 1

The first problem I face is that I don't know how to put a list of possible moves in an array at for example index [0][0]

由于棋盘是 2D 的，合法的步数通常可以超过 1，因此您最终会得到 3D 数据结构：

Point legalMoves[][][] = new legalMoves[5][5][];
legalMoves[0][0] = new Point[] {Point(1,1),Point(0,1),Point(1,0)};

instead of creating the object at every start of the game with an instance variable legalMoves, I would rather have it read from disk. I think that it should be quicker this way? Is the serializable class the way to go?

如果不分析就无法回答这个问题。我无法想象为 5x5 棋盘计算任何类型的合法移动会在计算上如此密集以证明任何类型的额外 I/O 操作是合理的。

for the 25 positions the legal moves are unbalanced. Some have 8 possible legal moves, others have 3. Maybe this is not a problem at all.

这可以用上面描述的 3D "jagged array" 很好地处理，所以这根本不是问题。

Answer 2

您正在寻找可以为您提供给定点候选的结构，即 Point -> List<Point>。

通常，我会选择 Map<Point, List<Point>>。

您可以在程序启动时静态初始化此结构，也可以在需要时动态初始化。例如，我在这里使用 2 个辅助数组，其中包含一个点的可能翻译，这些将产生该点的 neighbors。

// (-1  1) (0  1) (1  1)
// (-1  0) (----) (1  0)
// (-1 -1) (0 -1) (1 -1)
// from (1 0) anti-clockwise:
static int[] xOffset = {1,1,0,-1,-1,-1,0,1};
static int[] yOffset = {0,1,1,1,0,-1,-1,-1};

以下 Map 包含 Point 的实际邻居，具有计算、存储和 return 这些邻居的功能。您可以选择一次初始化所有邻居，但鉴于数量较少，我认为这不是性能方面的问题。

static Map<Point, List<Point>> neighbours = new HashMap<>();

static List<Point> getNeighbours(Point a) {
    List<Point> nb = neighbours.get(a);
    if (nb == null) {
        nb = new ArrayList<>(xOffset.length); // size the list
        for (int i=0; i < xOffset.length; i++) {
            int x = a.getX() + xOffset[i];
            int y = a.getY() + yOffset[i];
            if (x>=0 && y>=0 && x < 5 && y < 5) {
                nb.add(new Point(x, y));
            }
        }
        neighbours.put(a, nb);
    }
    return nb;
}

现在检查合法移动就是在邻居中找到点：

static boolean isLegalMove(Point from, Point to) {
    boolean legal = false;
    for (Point p : getNeighbours(from)) {
        if (p.equals(to)) {
            legal = true;
            break;
        }
    }
    return legal;
}

注意：class Point 必须定义 equals() 和 hashCode() 才能使地图按预期运行。

如何硬编码合法动作以进行快速查找？

How to hard-code legal moves for fast lookup?

java

arrays

lookup