BYOW个人记录

codex辅助，差不多一天半搞完了，统计说是10h，不知道准不准

从开始写 BYOW 到最后收尾，感觉这个项目比前面的 proj 更像是在真正做一个小型游戏系统。最后实现出来的版本大致包括：根据 seed 确定性生成随机世界，房间之间用 MST 保证连通，再额外加一些边让地图不那么像树；玩家可以通过 WASD 移动，:Q 保存，L 读取，R 回放，M 返回菜单；HUD 会显示鼠标所在 tile 的描述和当前收集进度；地图里有多个 light source，玩家走到灯上就会吃掉它，目标是吃完所有灯。

比较满意的是后期把结构拆开了：Engine 主要负责菜单、输入、渲染循环和 save/load；WorldGenerator 专门负责地图生成；GameState 负责玩家位置、移动、灯光、视野和历史输入。这样比一开始全部堆在 Engine 里舒服很多。灯光系统用了两份世界：一份是真实逻辑地图 world，一份是经过光照计算后的 lightedWorld。有限视野默认开启，用的是玩家周围的菱形范围；灯光则根据光源距离和墙体遮挡决定地板显示成哪一档蓝色亮度。

我的个人实现：CS61B proj3 BYOW

Bresenham 直线算法

我在灯光里需要判断：一个地板格能不能被某个光源照到。如果光源和目标 tile 中间有墙，那么这束光就应该被挡住；如果没有墙，就根据距离给这个 tile 一个亮度等级。

这个判断用的是 Bresenham 直线算法。它原本是用来在像素格子上画直线的，但在这里可以拿来枚举“从光源到目标格子这条直线经过了哪些 tile”。

核心想法：

从 (x0, y0) 到 (x1, y1) 画一条尽量接近真实直线的格子路径。
沿着这条路径检查每个 tile。
如果中途遇到 WALL，说明没有 line of sight。
否则说明光源能照到目标 tile。

代码形态大概是：

private boolean hasLineOfSight(int x0, int y0, int x1, int y1) {
    int dx = Math.abs(x1 - x0);
    int dy = Math.abs(y1 - y0);
    int sx = x0 < x1 ? 1 : -1;
    int sy = y0 < y1 ? 1 : -1;
    int err = dx - dy;

    int x = x0;
    int y = y0;

    while (!(x == x1 && y == y1)) {
        if (!(x == x0 && y == y0) && world[x][y] == Tileset.WALL) {
            return false;
        }

        int e2 = 2 * err;

        if (e2 > -dy) {
            err -= dy;
            x += sx;
        }

        if (e2 < dx) {
            err += dx;
            y += sy;
        }
    }

    return true;
}

其中 err 可以理解成“当前格子路径和真实直线之间的误差”。每一步根据误差决定接下来应该往 x 方向走、往 y 方向走，还是两个方向都走。乘 2 的 e2 是为了避免处理半格误差时出现小数。这个算法的本质是：在整数网格里，每一步都选最接近真实直线的下一个格子。

我这里的灯光没有用 BFS 扩散，因为 BFS 会让光沿着走廊拐弯；而我想要的是墙能挡光，光不应该自动绕过转角。所以更适合用 line of sight。

灯光亮度用的是 square / Chebyshev distance：

1	int distance = Math.max(Math.abs(x - light.x), Math.abs(y - light.y));

这样光圈是一层一层的方形，比较接近最后项目里的视觉效果。

Bitmask BFS

这个算法没有直接放进最后功能里，但它适合解决一个问题：如果给定一张地图，要求玩家吃完所有 lights 的最少操作数，应该怎么算？

这个问题可以看成最短路，但普通 BFS 只记录玩家位置 (x, y) 不够，因为同一个位置下，“已经吃过哪些灯”也会影响后续选择。

所以状态应该是：

1	(x, y, mask)

其中 mask 是一个 bitmask，用二进制记录已经吃过哪些灯。比如有 4 个灯：

0000 - 一个灯都没吃
0001 - 吃了第 0 个灯
0101 - 吃了第 0 和第 2 个灯
1111 - 所有灯都吃完

BFS 的目标就是第一次到达：

1	mask == (1 << lightsCount) - 1

因为每次移动的代价都是 1，所以 BFS 第一次到达目标状态时，步数就是最少操作数。

伪代码：

Queue<State> queue = new ArrayDeque<>();
boolean[][][] visited = new boolean[WIDTH][HEIGHT][1 << lightsCount];

queue.add(new State(startX, startY, startMask, 0));
visited[startX][startY][startMask] = true;

while (!queue.isEmpty()) {
    State cur = queue.remove();

    if (cur.mask == fullMask) {
        return cur.steps;
    }

    for (direction : directions) {
        int nx = cur.x + dx;
        int ny = cur.y + dy;

        if (!canWalk(nx, ny)) {
            continue;
        }

        int nextMask = cur.mask;
        if (lightIndex[nx][ny] != -1) {
            nextMask |= 1 << lightIndex[nx][ny];
        }

        if (!visited[nx][ny][nextMask]) {
            visited[nx][ny][nextMask] = true;
            queue.add(new State(nx, ny, nextMask, cur.steps + 1));
        }
    }
}

这里 visited 必须是三维的：

1	visited[x][y][mask]

因为同一个位置但吃灯状态不同，不能视作同一个状态。比如都在 (10, 5)，一个状态只吃了 1 个灯，另一个状态已经吃了 5 个灯，它们后续意义完全不同。如果只用 visited[x][y]，就会错误剪枝。

复杂度是：

1	O(WIDTH * HEIGHT * 2^k)

其中 k 是灯的数量。灯数量少的时候这个方法很直接；灯很多时，2^k 会变得很大，可以考虑先算两两最短路，再做 TSP 风格的 bitmask DP。