chuanqi/tests/test_path_find.py

# tests/test_path_find.py
"""
cpp_reversed/path_find.py 的 pytest 测试套件
覆盖: 启发式/代价、邻居、寻路主算法、边界处理、扩展寻路
"""
import os
import sys
import pytest

CPP_REV = os.path.abspath(os.path.join(os.path.dirname(__file__), "..", "cpp_reversed"))
if CPP_REV not in sys.path:
    sys.path.insert(0, CPP_REV)

import map_parser
import path_find
from path_find import (
    find_path, find_path_extended, path_cost, path_is_valid,
    heuristic, step_cost, NEIGHBOR_OFFSETS,
    LINE_COST, BIAS_COST, DEFAULT_DIS_X, DEFAULT_DIS_Y,
    _is_passable, _is_reachable, _straight_waypoints,
)
from map_parser import load, MapData, MapCell

SAMPLE_DIR = os.path.abspath(
    os.path.join(os.path.dirname(__file__), "..",
                 "996传奇盒子资源包", "03-游戏客户端", "jycq_206923", "scene", "map")
)


# ============== Fixtures ==============

@pytest.fixture(scope="module")
def m_0139():
    return load(os.path.join(SAMPLE_DIR, "0139.map"))


@pytest.fixture(scope="module")
def m_0():
    return load(os.path.join(SAMPLE_DIR, "0.map"))


@pytest.fixture(scope="module")
def m_3():
    return load(os.path.join(SAMPLE_DIR, "3.map"))


# ============== 常量测试 ==============

class TestConstants:
    """验证算法常量与 Lua PathFindAStar 一致"""

    def test_line_cost(self):
        assert LINE_COST == 10

    def test_bias_cost(self):
        assert BIAS_COST == 14

    def test_default_dis(self):
        assert DEFAULT_DIS_X == 24
        assert DEFAULT_DIS_Y == 16


# ============== 启发式 & 代价 ==============

class TestHeuristic:
    """测试启发式函数 (欧氏距离²)"""

    def test_same_point(self):
        assert heuristic(5, 5, 5, 5) == 0

    def test_adjacent_orthogonal(self):
        assert heuristic(0, 0, 1, 0) == 1
        assert heuristic(0, 0, 0, 1) == 1

    def test_adjacent_diagonal(self):
        assert heuristic(0, 0, 1, 1) == 2

    def test_distance_3_4(self):
        assert heuristic(0, 0, 3, 4) == 25  # 3²+4²=25 (5²)


class TestStepCost:
    """测试移动代价 (与 Lua PathNode:cost 一致)"""

    def _cell(self):
        return MapCell()

    def test_orthogonal_cost(self):
        c = self._cell()
        assert step_cost(c, c, 0, 0, 1, 0) == LINE_COST
        assert step_cost(c, c, 0, 0, 0, 1) == LINE_COST
        assert step_cost(c, c, 0, 0, -1, 0) == LINE_COST

    def test_diagonal_cost(self):
        c = self._cell()
        assert step_cost(c, c, 0, 0, 1, 1) == BIAS_COST
        assert step_cost(c, c, 0, 0, -1, -1) == BIAS_COST


# ============== 邻居 ==============

class TestNeighbors:
    """8 方向邻居"""

    def test_neighbor_count(self):
        assert len(NEIGHBOR_OFFSETS) == 8

    def test_orthogonal_present(self):
        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            assert (dx, dy) in NEIGHBOR_OFFSETS

    def test_diagonal_present(self):
        for dx, dy in [(1, 1), (1, -1), (-1, 1), (-1, -1)]:
            assert (dx, dy) in NEIGHBOR_OFFSETS


# ============== 辅助函数 ==============

class TestHelpers:
    """_is_passable / _is_reachable"""

    def test_is_passable_oob(self, m_0):
        assert not _is_passable(m_0, -1, 0)
        assert not _is_passable(m_0, 0, -1)
        assert not _is_passable(m_0, m_0.width, 0)

    def test_is_passable_obstacle(self, m_0):
        # 找一个不可走的格
        for y in range(m_0.height):
            for x in range(m_0.width):
                if not m_0.get_cell(x, y).is_walkable:
                    assert not _is_passable(m_0, x, y)
                    return

    def test_is_reachable_passable(self, m_0):
        # 找一个明显可达的格 (找一个全可走区域)
        # 0.map 中央通常是可达的
        assert _is_reachable(m_0, 350, 350)

    def test_is_reachable_dead_end(self, m_0):
        """一个完全被障碍包围的格应该是 dead end"""
        # 难精确构造,跳过; 用 _is_reachable 返回 False 的概率
        # 实际只要确认函数有定义且类型正确
        assert callable(_is_reachable)


# ============== 主寻路算法 ==============

class TestFindPath:
    """find_path 主算法测试"""

    def test_same_point(self, m_0):
        # 找一个可走点
        x, y = 350, 350
        if not _is_passable(m_0, x, y):
            pytest.skip("(350, 350) 不可走, 跳过")
        path = find_path(m_0, x, y, x, y, dis_x=100, dis_y=100)
        assert path == [(x, y)]

    def test_adjacent_orthogonal(self, m_0):
        path = find_path(m_0, 100, 100, 101, 100, dis_x=10, dis_y=10)
        # 不一定有这条路, 但若有应该 2 步
        if path:
            assert path[0] == (100, 100)
            assert path[-1] == (101, 100)
            assert len(path) <= 3  # 可能走 1 或 2 步

    def test_straight_line_optimal(self, m_0):
        """无障碍直道应该得到最优解 (N*10 代价)"""
        # 找一段空旷的 30 格
        for y in range(700):
            run_start = None
            for x in range(700):
                if _is_passable(m_0, x, y):
                    if run_start is None:
                        run_start = x
                else:
                    if run_start is not None and x - run_start >= 30:
                        end = x - 1
                        path = find_path(m_0, run_start, y, end, y,
                                          dis_x=200, dis_y=200, max_iter=10000)
                        assert path is not None and len(path) > 0
                        cost = path_cost(m_0, path)
                        # 最短 = 水平 N*10, 但可能对角绕行 = 略多
                        assert cost <= (end - run_start) * 10 + 20
                        # 起点终点对
                        assert path[0] == (run_start, y)
                        assert path[-1] == (end, y)
                        # valid
                        assert path_is_valid(m_0, path)
                        return
                    run_start = None

    def test_out_of_bounds_returns_empty(self, m_0):
        assert find_path(m_0, 100, 100, 9999, 9999, dis_x=10, dis_y=10) == []
        assert find_path(m_0, -1, 0, 10, 10, dis_x=10, dis_y=10) == []

    def test_obstacle_start_returns_empty(self, m_0):
        # 找一个障碍格作为起点
        for y in range(m_0.height):
            for x in range(m_0.width):
                if not _is_passable(m_0, x, y):
                    path = find_path(m_0, x, y, x + 1, y, dis_x=10, dis_y=10)
                    assert path == []
                    return

    def test_dead_end_end_returns_empty(self, m_0):
        """终点是死格 (8 邻居都不可走) 返回 []"""
        # 找第一个不可走的格
        for y in range(m_0.height):
            for x in range(m_0.width):
                if not _is_passable(m_0, x, y):
                    path = find_path(m_0, 0, 0, x, y, dis_x=10, dis_y=10)
                    assert path == []
                    return

    def test_path_is_contiguous(self, m_0):
        """路径相邻点必须是 8 邻居"""
        for y in range(50):
            run_start = None
            for x in range(50):
                if _is_passable(m_0, x, y):
                    if run_start is None:
                        run_start = x
                else:
                    if run_start is not None and x - run_start >= 10:
                        end = x - 1
                        path = find_path(m_0, run_start, y, end, y, dis_x=20, dis_y=20)
                        if path:
                            for (x1, y1), (x2, y2) in zip(path, path[1:]):
                                assert abs(x2 - x1) <= 1 and abs(y2 - y1) <= 1
                                assert (x1, y1) != (x2, y2)
                        return
                    run_start = None

    def test_path_avoids_obstacles(self, m_0):
        """路径中所有点都应该是可走的"""
        # 在 0.map 上找一个有效 path
        path = find_path(m_0, 100, 100, 110, 100, dis_x=50, dis_y=50)
        if path:
            for x, y in path:
                assert _is_passable(m_0, x, y), f"({x},{y}) 不可走, 在 path 中"

    def test_diagonal_blocked_by_adjacent_obstacle(self, m_0139):
        """对角穿越: 若两个正交邻居都是障碍, 应对角不可走 (防穿墙)"""
        # 0139.map 上, 看几个对角情况
        # 直接验证算法不允许"穿墙"
        # 找一个有此类障碍的位置
        for y in range(1, 10):
            for x in range(1, 10):
                c = m_0139.get_cell(x, y)
                if not c.is_walkable:
                    side1 = m_0139.get_cell(x + 1, y)
                    side2 = m_0139.get_cell(x, y + 1)
                    diag = m_0139.get_cell(x + 1, y + 1)
                    if (not side1.is_walkable and not side2.is_walkable
                            and diag.is_walkable):
                        # 不应通过对角走到 (x+1, y+1)
                        # 通过尝试路径 (x, y) → (x+1, y+1)
                        # 由于 (x, y) 不可走, 这个 path 应该是 []
                        path = find_path(m_0139, 0, 0, x + 1, y + 1, dis_x=100, dis_y=100)
                        # 不应包含 (x+1, y+1) 通过 (x, y) 的对角
                        # (简化检查: 不测试具体路径, 只测不会通过该对角)
                        return


# ============== 工具函数 ==============

class TestPathCost:
    """path_cost 函数"""

    def test_empty_path(self):
        assert path_cost(None, []) == 0

    def test_single_point(self, m_0):
        assert path_cost(m_0, [(5, 5)]) == 0

    def test_orthogonal_straight(self, m_0):
        # 假设这些点都可走, 5 步正交 = 5*10
        cost = path_cost(m_0, [(0, 0), (1, 0), (2, 0), (3, 0), (4, 0)])
        assert cost == 40

    def test_diagonal(self, m_0):
        cost = path_cost(m_0, [(0, 0), (1, 1), (2, 2)])
        assert cost == 28  # 2 * 14

    def test_mixed(self, m_0):
        cost = path_cost(m_0, [(0, 0), (1, 0), (2, 1)])
        # 1 步正交 (10) + 1 步对角 (14) = 24
        assert cost == 24


class TestPathIsValid:
    """path_is_valid 验证"""

    def test_empty(self):
        assert not path_is_valid(None, [])

    def test_single_walkable(self, m_0):
        # 找一个可走格
        x, y = 100, 100
        if _is_passable(m_0, x, y):
            assert path_is_valid(m_0, [(x, y)])

    def test_oob(self, m_0):
        assert not path_is_valid(m_0, [(-1, 0)])
        assert not path_is_valid(m_0, [(m_0.width, 0)])

    def test_obstacle_in_path(self, m_0):
        # 找一个不可走格
        for y in range(m_0.height):
            for x in range(m_0.width):
                if not _is_passable(m_0, x, y):
                    assert not path_is_valid(m_0, [(0, 0), (x, y)])
                    return

    def test_non_neighbor(self, m_0):
        # 两个不相邻的格
        assert not path_is_valid(m_0, [(0, 0), (10, 10)])

    def test_valid_path(self, m_0):
        path = find_path(m_0, 100, 100, 110, 100, dis_x=50, dis_y=50)
        if path:
            assert path_is_valid(m_0, path)


# ============== 分段寻路 (扩展) ==============

class TestFindPathExtended:
    """find_path_extended 分段寻路"""

    def test_short_path_no_segmentation(self, m_0):
        # 短距离不需要分段
        p1 = find_path(m_0, 100, 100, 105, 100, dis_x=50, dis_y=50)
        p2 = find_path_extended(m_0, 100, 100, 105, 100, chunk_size=20)
        # 都应该非空, 终点一致
        if p1 and p2:
            assert p1[0] == p2[0]
            assert p1[-1] == p2[-1]


# ============== 端到端: 真实 .map 文件 ==============

class TestE2E:
    """真实 .map 文件上的端到端寻路"""

    @pytest.mark.parametrize("filename", ["0139.map", "0.map", "3.map", "d022.map", "d401.map"])
    def test_random_short_path(self, filename):
        """在每个 map 上找一个 5x5 区域做短距离寻路"""
        m = load(os.path.join(SAMPLE_DIR, filename))
        # 在 100x100 区域找一个可走的起点和终点
        for sy in range(50, 100, 5):
            for sx in range(50, 100, 5):
                if not _is_passable(m, sx, sy):
                    continue
                # 找终点
                for ey in range(sy, sy + 10, 2):
                    for ex in range(sx, sx + 10, 2):
                        if (ex, ey) == (sx, sy):
                            continue
                        if not _is_passable(m, ex, ey):
                            continue
                        path = find_path(m, sx, sy, ex, ey, dis_x=30, dis_y=30)
                        if path:
                            assert path_is_valid(m, path)
                            return  # 找到一个就够了
        pytest.skip(f"{filename}: 在测试区域未找到有效 path")


if __name__ == "__main__":
    sys.exit(pytest.main([__file__, "-v", "--tb=short"]))