tests/test_bfs.py

"""tests/test_bfs.py —— BFS 寻路算法单元测试

覆盖范围
--------
TC-1  标准唯一通路
TC-2  起点与终点重合
TC-3  绝对无解（终点被墙封死）
TC-4  多条通路最优性（BFS 必须返回最短路）
TC-5  起点本身是墙（非法输入）
TC-6  性能基准：10×10 空旷地图 < 2ms
"""

from __future__ import annotations

import numpy as np

from maze_env.bfs import bfs


# ---------------------------------------------------------------------------
# TC-1  标准可行通路
# ---------------------------------------------------------------------------

def test_standard_path() -> None:
    """TC-1：唯一通路，验证 success / steps / path 首尾 / 路径长度一致性。

    地图::

         █ █ █ █ █
         █ · · · █
         █ █ █ · █
         █ █ █ · █
         █ █ █ █ █

    起点 (1,1) → 终点 (3,3)，唯一通路共 4 步。
    """
    grid = np.array([
        [1, 1, 1, 1, 1],
        [1, 0, 0, 0, 1],
        [1, 1, 1, 0, 1],
        [1, 1, 1, 0, 1],
        [1, 1, 1, 1, 1],
    ], dtype=np.int32)
    r = bfs(grid, start=(1, 1), end=(3, 3))

    assert r["success"] is True
    assert r["steps"] == 4
    assert r["path"][0]  == (1, 1)
    assert r["path"][-1] == (3, 3)
    assert len(r["path"]) == r["steps"] + 1
    assert isinstance(r["execution_time_ms"], float)


# ---------------------------------------------------------------------------
# TC-2  起点与终点重合
# ---------------------------------------------------------------------------

def test_same_start_end() -> None:
    """TC-2：起点与终点重合，steps=0，path=[start]。"""
    grid = np.array([
        [1, 1, 1],
        [1, 0, 1],
        [1, 1, 1],
    ], dtype=np.int32)
    r = bfs(grid, start=(1, 1), end=(1, 1))

    assert r["success"] is True
    assert r["steps"] == 0
    assert r["path"] == [(1, 1)]


# ---------------------------------------------------------------------------
# TC-3  绝对无解（终点被墙四面封死）
# ---------------------------------------------------------------------------

def test_no_path_enclosed() -> None:
    """TC-3：终点被墙封死，无任何通路，优雅返回 False。

    地图::

         · █ █ █ █
         █ █ █ █ █
         █ █ · █ █
         █ █ █ █ █
         █ █ █ █ █

    起点 (0,0) 孤立，终点 (2,2) 被墙完全包围，两者均无通路。
    """
    grid = np.array([
        [0, 1, 1, 1, 1],
        [1, 1, 1, 1, 1],
        [1, 1, 0, 1, 1],
        [1, 1, 1, 1, 1],
        [1, 1, 1, 1, 1],
    ], dtype=np.int32)
    r = bfs(grid, start=(0, 0), end=(2, 2))

    assert r["success"] is False
    assert r["steps"] == -1
    assert r["path"] == []


# ---------------------------------------------------------------------------
# TC-4  多条通路最优性
# ---------------------------------------------------------------------------

def test_multiple_paths_shortest() -> None:
    """TC-4：多条通路最优性验证 —— BFS 必须返回最短路，而非 DFS 的长路。

    设计说明
    --------
    6×6 开放网格（仅保留外围墙），起点 (1,1) 终点 (4,4)。
    同时存在多条通路；曼哈顿距离下界 = |4-1| + |4-1| = 6。

    断言 steps == 6 验证 BFS 返回最短路，而非 DFS / 随机游走可能返回的冗长路径。
    """
    grid = np.array([
        [1, 1, 1, 1, 1, 1],
        [1, 0, 0, 0, 0, 1],
        [1, 0, 0, 0, 0, 1],
        [1, 0, 0, 0, 0, 1],
        [1, 0, 0, 0, 0, 1],
        [1, 1, 1, 1, 1, 1],
    ], dtype=np.int32)
    r = bfs(grid, start=(1, 1), end=(4, 4))

    assert r["success"] is True
    # ── 最优性断言：BFS 必须返回最短路，非 DFS 可能返回的更长路径 ──────────
    assert r["steps"] == 6, (
        f"BFS 最优性失败：期望最短步数 6（曼哈顿距离），实际得到 {r['steps']}。"
        "若此断言失败，说明算法使用了 DFS 或其他非最短路策略。"
    )
    assert r["path"][0]  == (1, 1)
    assert r["path"][-1] == (4, 4)
    # 每步必须是四邻域移动（步距 == 1，不允许斜跨）
    for i in range(len(r["path"]) - 1):
        rr, rc = r["path"][i]
        nr, nc = r["path"][i + 1]
        assert abs(nr - rr) + abs(nc - rc) == 1, (
            f"路径第 {i}→{i+1} 步不是四邻域移动：{r['path'][i]}→{r['path'][i+1]}"
        )


# ---------------------------------------------------------------------------
# TC-5  起点本身是墙（非法输入）
# ---------------------------------------------------------------------------

def test_start_is_wall() -> None:
    """TC-5：起点本身是墙（非法输入），立即返回 success=False。"""
    grid = np.array([
        [1, 1, 1],
        [1, 0, 1],
        [1, 1, 1],
    ], dtype=np.int32)
    r = bfs(grid, start=(0, 0), end=(1, 1))   # (0,0) 是墙

    assert r["success"] is False
    assert r["steps"] == -1
    assert r["path"] == []


# ---------------------------------------------------------------------------
# TC-6  性能基准
# ---------------------------------------------------------------------------

def test_performance_10x10_empty() -> None:
    """TC-6：性能基准 —— 10×10 空旷地图单次 BFS 耗时必须 < 2ms。

    设计说明
    --------
    10×10 地图（外围墙 + 全内部可通行），起点 (1,1) 终点 (8,8)，
    最大可能节点数 = 8×8 = 64，BFS 应在亚毫秒级完成。

    若此断言失败，说明实现存在严重性能缺陷（如在循环内做 O(N) 查找），
    应检查 visited 是否使用 set（而非 list）。
    """
    grid = np.ones((10, 10), dtype=np.int32)
    grid[1:9, 1:9] = 0   # 内部 8×8 区域全部清空（可通行）

    result = bfs(grid, start=(1, 1), end=(8, 8))

    assert result["success"] is True, "10×10 空旷地图应能找到路径"
    assert result["steps"] == 14, (
        f"10×10 空旷地图最短步数期望 14（曼哈顿距离），实际 {result['steps']}"
    )
    # ── 性能断言：< 2ms ────────────────────────────────────────────────────
    assert result["execution_time_ms"] < 2.0, (
        f"BFS 性能不达标：10×10 地图耗时 {result['execution_time_ms']:.4f}ms，"
        f"阈值 2.0ms。请检查 visited 集合实现（应为 set，而非 list）。"
    )