java - 如何对合法 Action 进行硬编码以进行快速查找？

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 创建对象。我想这样应该会更快吧？可序列化类是正确的选择吗？

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

Answer 1

您正在寻找一个结构，该结构将为您提供给定点的候选点，即 Point -> List<Point> .

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

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

// (-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 的实际邻居使用计算、存储和返回这些邻居的函数。您可以选择一次性初始化所有邻居，但考虑到数字很小，我不认为这会造成性能问题。

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;
}

注:类Point必须定义equals()和hashCode()使 map 按预期运行。