国际象棋游戏性能优化困境：更新攻击tiles后效率未提升

我正在开发一款国际象棋游戏，近期为优化走法生成效率，修改了攻击格（attackedTiles）和牵制（pins）的更新逻辑：原本每次生成走法时都会计算敌方的攻击格，现在改为在Board对象初始化时一次性计算该信息，之后每次移动时按需更新相关方格。

但测试后发现效率和之前持平，既没变慢也没变快，对此我感到困惑。性能分析器结果显示，瓶颈出在update函数本身，而非它调用的子函数。

当前实现的核心代码与数据结构 #

private HashMap<Integer, List<List<List<Integer>>>> attackedTiles;
private HashMap<Integer, List<List<Integer>>> pins;

private void updateAttackedTilesAndPins(int oldIndex, int newIndex) {
    int[] colors = new int[]{Piece.WHITE, Piece.BLACK};
    int pieceIndex = Piece.index(tile[newIndex]);

    for (int color : colors) {
        List<List<List<Integer>>> attackedTilesColor = attackedTiles.get(color);

        for (int i = 0; i < attackedTilesColor.size(); i++) {
            // 无需处理移动的棋子，之后会重新计算它的攻击格
            if (i == pieceIndex) {
                continue;
            }

            // 更新所有能看到移动棋子的视线
            for (List<Integer> lineOfSight : attackedTilesColor.get(i)) {
                if (lineOfSight.contains(oldIndex) || lineOfSight.contains(newIndex)) {
                    updateLineOfSight(lineOfSight);
                }
            }
        }
    }

    // 计算移动后棋子的攻击格
    attackedTiles.get(turn).set(pieceIndex, calculateAttackedTiles(newIndex));

    pins.get(turn).clear();

    // 检查是否存在牵制情况
    List<Integer> piecePositionsTurn = piecePositions.get(turn);
    for (int piecePosition : piecePositionsTurn) {
        if (piecePosition == -1) {
            continue;
        }

        List<Integer> pinLine = calculatePinLine(piecePosition);
        if (!pinLine.isEmpty()) {
            pins.get(turn).add(pinLine);
        }
    }
}

attackedTiles结构示例 #

每个内层列表代表棋子某一方向的视线：

Attacked tiles white:
[[48, 41]]
[[58, 49], [58, 51]]
[[59, 50], [59, 51], [59, 52], [59, 58], [59, 60]]
[[60, 51], [60, 52], [60, 53], [60, 59], [60, 61]]
[[61, 52], [61, 54]]
[[62, 45], [62, 47], [62, 52]]
[[63, 55], [63, 62]]
Attacked tiles black:
[[0, 1], [0, 8]]
[[1, 11], [1, 16], [1, 18]]
[[2, 9], [2, 11]]
[[3, 2], [3, 4], [3, 10], [3, 11], [3, 12]]
[[4, 3], [4, 5], [4, 11], [4, 12], [4, 13]]
[[5, 12], [5, 14]]
[[6, 12], [6, 21], [6, 23]]

疑问点 #

• 当前的更新方法是否存在设计缺陷？
• 是否存在缓存局部性使用不当的问题？
• attackedTiles的三层列表结构不仅不够优雅，是否也导致遍历效率低下？
• 是否需要更高效的棋子可视性判断方法，来精简遍历的列表范围？

内容的提问来源于stack exchange，提问作者Popo