controllers/algorithms/spatial_hash.py - master - Vibek/First_Game

controllers/algorithms/spatial_hash.py
140 строк6 KB
Vibek
Оптимизация, иснхронизация хитбоксов
21 июн 2026, 17:09
21 июн 2026, 17:09bbdda9b
"""
Алгоритм 3: SpatialHashGrid — пространственное разбиение для broad-phase коллизий.
"""
from __future__ import annotations

import math
from typing import Any

import pygame
from pygame.math import Vector2


class SpatialHashGrid:
    """
    Пространственная хеш-таблица для оптимизации коллизий.

    Архитектурное правило:
    - НЕ знает про Player, Enemy, Projectile (MVC compliant)
    - Читает геометрию через duck typing (OBB, hitbox, rect)
    - Не изменяет состояние объектов
    """

    def __init__(self, cols: int, rows: int, screen_w: int, screen_h: int) -> None:
        if cols <= 0 or rows <= 0:
            raise ValueError("cols и rows должны быть > 0")
        if screen_w <= 0 or screen_h <= 0:
            raise ValueError("screen_w и screen_h должны быть > 0")

        self._cols = cols
        self._rows = rows
        self._screen_w = screen_w
        self._screen_h = screen_h
        self.cell_w = screen_w // cols
        self.cell_h = screen_h // rows
        self._cells: dict[tuple[int, int], list[Any]] = {}

    def clear(self) -> None:
        """Полная очистка сетки перед новым кадром."""
        self._cells.clear()

    def insert(self, entity: Any) -> None:
        """Добавляет сущность во все ячейки, пересекаемые её AABB."""
        bounds = self._resolve_bounds(entity)
        for cx, cy in self._iter_cell_coords(bounds):
            self._cells.setdefault((cx, cy), []).append(entity)

    def query_nearby(self, entity: Any, margin: int = 0) -> list[Any]:
        """
        Возвращает сущности в ячейках вокруг AABB entity с дополнительным margin.
        Может включать саму entity — фильтровать на стороне вызывающего кода.
        """
        bounds = self._resolve_bounds(entity)
        if margin > 0:
            bounds = bounds.inflate(margin * 2, margin * 2)
        return self._collect_from_bounds(bounds)

    def query_rect(self, rect: pygame.Rect) -> list[Any]:
        """Возвращает сущности в ячейках, пересекающих заданный прямоугольник."""
        return self._collect_from_bounds(rect)

    @staticmethod
    def bounds_from_points(points: list[Vector2]) -> pygame.Rect:
        """Строит axis-aligned bbox для набора точек (например, конуса атаки)."""
        if not points:
            return pygame.Rect(0, 0, 0, 0)
        xs = [p.x for p in points]
        ys = [p.y for p in points]
        left = min(xs)
        top = min(ys)
        right = max(xs)
        bottom = max(ys)
        width = max(1, int(math.ceil(right - left)))
        height = max(1, int(math.ceil(bottom - top)))
        return pygame.Rect(int(math.floor(left)), int(math.floor(top)), width, height)

    @staticmethod
    def _resolve_bounds(entity: Any) -> pygame.Rect:
        get_corners = getattr(entity, "get_obb_corners", None)
        if callable(get_corners):
            corners = get_corners()
            if len(corners) >= 3:
                return SpatialHashGrid.bounds_from_points(corners)

        outward_radius = getattr(entity, "outward_hit_radius", None)
        if outward_radius is not None and outward_radius > 0:
            center = getattr(entity, "hitbox_center", None)
            if center is not None:
                r = int(math.ceil(outward_radius))
                return pygame.Rect(int(center.x - r), int(center.y - r), r * 2, r * 2)

        hitbox = getattr(entity, "hitbox", None)
        pos = getattr(entity, "pos", None)
        if hitbox is not None and pos is not None:
            left = pos.x + hitbox.offset_x
            top = pos.y + hitbox.offset_y
            return pygame.Rect(
                int(left),
                int(top),
                int(hitbox.width),
                int(hitbox.height),
            )

        return entity.rect

    def _cell_range(self, rect: pygame.Rect) -> tuple[int, int, int, int]:
        if rect.width <= 0 or rect.height <= 0:
            cx = max(0, min(self._cols - 1, rect.left // self.cell_w))
            cy = max(0, min(self._rows - 1, rect.top // self.cell_h))
            return cx, cx, cy, cy

        cx_min = rect.left // self.cell_w
        cx_max = (rect.right - 1) // self.cell_w
        cy_min = rect.top // self.cell_h
        cy_max = (rect.bottom - 1) // self.cell_h

        cx_min = max(0, min(self._cols - 1, cx_min))
        cx_max = max(0, min(self._cols - 1, cx_max))
        cy_min = max(0, min(self._rows - 1, cy_min))
        cy_max = max(0, min(self._rows - 1, cy_max))
        return cx_min, cx_max, cy_min, cy_max

    def _iter_cell_coords(self, rect: pygame.Rect) -> list[tuple[int, int]]:
        cx_min, cx_max, cy_min, cy_max = self._cell_range(rect)
        coords: list[tuple[int, int]] = []
        for cx in range(cx_min, cx_max + 1):
            for cy in range(cy_min, cy_max + 1):
                coords.append((cx, cy))
        return coords

    def _collect_from_bounds(self, rect: pygame.Rect) -> list[Any]:
        seen: set[int] = set()
        result: list[Any] = []
        for cx, cy in self._iter_cell_coords(rect):
            for entity in self._cells.get((cx, cy), ()):
                entity_id = id(entity)
                if entity_id in seen:
                    continue
                seen.add(entity_id)
                result.append(entity)
        return result