Обнаружение столкновений коробок — фундаментальная концепция компьютерной графики и разработки игр. Он включает в себя определение того, перекрываются или сталкиваются ли два или более прямоугольных блока друг с другом. В этой статье мы рассмотрим различные методы реализации обнаружения столкновений блоков, а также приведем примеры кода, которые помогут вам понять и освоить этот важный метод.

Метод 1: обнаружение столкновений в граничной рамке с выравниванием по оси (AABB)
Метод обнаружения столкновений AABB — один из самых простых и наиболее широко используемых алгоритмов. Предполагается, что поля выровнены по осям x, y и z. Чтобы проверить наличие столкновения между двумя AABB, вы сравниваете диапазоны их координат вдоль каждой оси.

Пример кода:

def check_aabb_collision(box1, box2):
    if (box1.min_x <= box2.max_x and box1.max_x >= box2.min_x) and \
       (box1.min_y <= box2.max_y and box1.max_y >= box2.min_y) and \
       (box1.min_z <= box2.max_z and box1.max_z >= box2.min_z):
        return True
    else:
        return False

Метод 2: обнаружение столкновений по теореме о разделяющихся осях (SAT)
Метод обнаружения столкновений SAT более универсален и может обрабатывать повернутые блоки. Он проверяет столкновение, проецируя блоки на набор разделяющих осей и проверяя перекрытие вдоль каждой оси.

Пример кода:

def check_sat_collision(box1, box2):
    for axis in box1.axes + box2.axes:
        if not is_overlap(box1.project(axis), box2.project(axis)):
            return False
    return True
def is_overlap(projection1, projection2):
    return projection1.max >= projection2.min and projection2.max >= projection1.min

Метод 3: Обнаружение столкновений квадродерева
Обнаружение столкновений квадродерева подходит для сценариев, в которых имеется большое количество блоков и вы хотите оптимизировать процесс обнаружения столкновений. Он предполагает рекурсивное разделение пространства на квадранты и хранение ящиков в соответствующем квадранте. Проверки на столкновение выполняются только в соответствующих квадрантах.

Пример кода:

class QuadtreeNode:
    def __init__(self, boundary):
        self.boundary = boundary
        self.boxes = []
        self.children = [None, None, None, None]
    def insert(self, box):
        if not self.boundary.contains(box):
            return False
        if len(self.boxes) < MAX_BOXES_PER_NODE:
            self.boxes.append(box)
            return True
        if self.children[0] is None:
            self.subdivide()
        for child in self.children:
            if child.insert(box):
                return True
        return False
    def subdivide(self):
        # Create four children nodes and divide the boundary
        # Assign appropriate boxes to each child node
    def query(self, box):
        # Return a list of potential collisions from the quadtree
def check_quadtree_collision(quadtree, box):
    potential_collisions = quadtree.query(box)
    for collision_box in potential_collisions:
        if check_aabb_collision(collision_box, box):
            return True
    return False

Обнаружение столкновений коробок — важнейший аспект разработки игр и компьютерной графики. В этой статье мы рассмотрели три распространенных метода: обнаружение столкновений AABB, обнаружение столкновений SAT и обнаружение столкновений квадродерева. Каждый метод имеет свои преимущества и подходит для разных сценариев. Поняв и внедрив эти методы, вы сможете эффективно справляться с обнаружением столкновений блоков в своих проектах.