src/utils/pathfinding.py - master - i_918/Vault_Escape

src/utils/pathfinding.py
70 строк3 KB
Ilya
исправление pylance ошибок
24 май 2026, 18:32
24 май 2026, 18:323ad3bad
import heapq
from typing import Dict, List, Optional, Tuple


class Pathfinding:

    @staticmethod
    def find_path(
        game_map: List[List[int]], start: Tuple[int, int], end: Tuple[int, int]
    ) -> Optional[List[Tuple[int, int]]]:
        width = len(game_map)
        height = len(game_map[0]) if width > 0 else 0
        open_set: List[Tuple[float, Tuple[int, int]]] = [
            (Pathfinding.heuristic(start, end), start)
        ]
        came_from: Dict[Tuple[int, int], Tuple[int, int]] = {}
        g_score: Dict[Tuple[int, int], int] = {start: 0}
        f_score: Dict[Tuple[int, int], float] = {
            start: Pathfinding.heuristic(start, end)
        }
        open_set_hash: set[Tuple[int, int]] = {start}
        while open_set:
            current = heapq.heappop(open_set)[1]
            open_set_hash.discard(current)
            if current == end:
                return Pathfinding.reconstruct_path(came_from, current)
            for neighbor in Pathfinding.get_neighbors(current, game_map, width, height):
                tentative_g_score = g_score[current] + 1
                if neighbor not in g_score or tentative_g_score < g_score[neighbor]:
                    came_from[neighbor] = current
                    g_score[neighbor] = tentative_g_score
                    f_score[neighbor] = float(
                        tentative_g_score
                    ) + Pathfinding.heuristic(neighbor, end)
                    if neighbor not in open_set_hash:
                        heapq.heappush(open_set, (f_score[neighbor], neighbor))
                        open_set_hash.add(neighbor)
        return None

    @staticmethod
    def heuristic(a: Tuple[int, int], b: Tuple[int, int]) -> float:
        return float(abs(a[0] - b[0]) + abs(a[1] - b[1]))

    @staticmethod
    def get_neighbors(
        pos: Tuple[int, int], game_map: List[List[int]], width: int, height: int
    ) -> List[Tuple[int, int]]:
        x, y = pos
        neighbors: List[Tuple[int, int]] = []
        directions = [(0, -1), (0, 1), (-1, 0), (1, 0)]
        for dx, dy in directions:
            new_x, new_y = (x + dx, y + dy)
            if (
                0 <= new_x < width
                and 0 <= new_y < height
                and (game_map[new_x][new_y] != 0)
            ):
                neighbors.append((new_x, new_y))
        return neighbors

    @staticmethod
    def reconstruct_path(
        came_from: Dict[Tuple[int, int], Tuple[int, int]], current: Tuple[int, int]
    ) -> List[Tuple[int, int]]:
        path = [current]
        while current in came_from:
            current = came_from[current]
            path.append(current)
        path.reverse()
        return path