国际象棋游戏优化：尽管攻击图块更新，但性能低下

Question

我正在开发一款国际象棋游戏，最近对我的代码进行了更改，以通过更有效地更新攻击图块和引脚来优化移动生成。最初，我每次生成移动时都会计算敌方的攻击图块。但是，我修改了代码，在 Board 对象初始化期间计算一次此信息，然后在每次移动过程中根据需要更新相关方块。

这里是更新函数和相关数据结构：

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++) {
            //no point in looking at the moved piece, since we will recalculate the attacked tiles for it anyway
            if (i == pieceIndex) {
                continue;
            }

            //update every line of sight that could see the moved piece
            for (List<Integer> lineOfSight : attackedTilesColor.get(i)) {
                if (lineOfSight.contains(oldIndex) || lineOfSight.contains(newIndex)) {
                    updateLineOfSight(lineOfSight);
                }
            }
        }
    }

    //calculate the attacked tiles for the moved piece
    attackedTiles.get(turn).set(pieceIndex, calculateAttackedTiles(newIndex));

    pins.get(turn).clear();

    //check if any piece is pinning anything
    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);
        }
    }
}

我知道 AttackTiles 很难看，所以它可能看起来像这样，其中每个内部列表都是一个方向上的一块的视线：

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]]

我对这种方法很有信心，因为我觉得它应该比以前更快。经过一些测试后，我发现它同样快。不慢，也不快。我真的不太明白。

我确实运行了一个分析器，这些是结果

据我所知，是更新函数本身导致速度变慢，而不是子函数。我想知道我的方法是否有缺陷，或者我是否没有有效地利用缓存局部性。 AttackTiles 数据结构可能不是最优雅的，但它的迭代速度是否也很慢？我是否只需要一个更有效的版本来检查一个片段是否被另一个人看到，这样我就可以修剪该列表或其他东西而不必查看它？

Answer 1

我当然不完全确定效率的显着提高，但我认为你应该尝试这些操作，看看会发生什么。 我更改了您代码的两部分：

    //update every line of sight that could see the moved piece
    for (List<Integer> lineOfSight : attackedTilesColor.get(i)) {
        if (lineOfSight.contains(oldIndex) || lineOfSight.contains(newIndex)) {
            updateLineOfSight(lineOfSight);
        }
    }

    //check if any piece is pinning anything
    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);
        }
    }

并将其转化为

.stream()

:

//update every line of sight that could see the moved piece
attackedTilesColor.get(i).stream()
        .filter(lineOfSight -> lineOfSight.contains(oldIndex) || lineOfSight.contains(newIndex))
        .forEach(this::updateLineOfSight);

//check if any piece is pinning anything
piecePositions.get(turn).stream()
        .filter(piecePosition -> piecePosition != -1)
        .map(this::calculatePinLine)
        .filter(pinLine -> !pinLine.isEmpty())
        .forEach(pins.get(turn)::add);