Оптимизация: пространственный хэш и квадродерево

В разработке игр на Phaser обработка большого количества объектов на сцене может стать узким местом производительности. Прямое сравнение коллизий между всеми объектами приводит к квадратичной сложности (O(n^2)), что при сотнях или тысячах спрайтов сильно тормозит. Для решения этой проблемы используются структуры данных, оптимизирующие поиск и проверку взаимодействий: пространственный хэш и квадродерево.

Пространственный хэш (Spatial Hash)

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

Преимущества:

Легкость реализации.
Константное время добавления и удаления объектов из сетки.
Эффективен для объектов равномерного распределения.

Недостатки:

Неэффективен при сильно различающихся размерах объектов.
Фиксированный размер ячеек может потребовать балансировки.

Пример реализации на Phaser с использованием Jav * aScript:

class SpatialHash {
    constructor(cellSize) {
        this.cellSize = cellSize;
        this.buckets = new Map();
    }

    _hash(x, y) {
        const col = Math.floor(x / this.cellSize);
        const row = Math.floor(y / this.cellSize);
        return `${col},${row}`;
    }

    ins ert(object) {
        const hash = this._hash(object.x, object.y);
        if (!this.buckets.has(hash)) this.buckets.se t(hash, []);
        this.buckets.get(hash).push(object);
    }

    query(object) {
        const neighbors = [];
        const col = Math.floor(object.x / this.cellSize);
        const row = Math.floor(object.y / this.cellSize);

        for (let dx = -1; dx <= 1; dx++) {
            for (let dy = -1; dy <= 1; dy++) {
                const hash = `${col + dx},${row + dy}`;
                if (this.buckets.has(hash)) {
                    neighbors.push(...this.buckets.get(hash));
                }
            }
        }
        return neighbors;
    }

    clear() {
        this.buckets.clear();
    }
}

Использование: Каждый кадр объекты обновляются в хэше через insert, затем при проверке коллизий вызывается query для конкретного объекта, сокращая количество проверок с (n) до небольшого числа соседних объектов.

Квадродерево (Quadtree)

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

Преимущества:

Эффективно для сцен с большим разбросом объектов.
Поддерживает динамическое изменение плотности объектов.
Позволяет уменьшить сложность проверки до (O(n n)).

Недостатки:

Более сложная реализация по сравнению с хэшом.
Пересортировка объектов при изменении положения может быть затратной при частых обновлениях.

Пример реализации в Phaser:

class Quadtree {
    constructor(boundary, capacity) {
        this.boundary = boundary; // { x, y, width, height }
        this.capacity = capacity;
        this.objects = [];
        this.divided = false;
    }

    subdivide() {
        const { x, y, width, height } = this.boundary;
        const w = width / 2;
        const h = height / 2;
        this.northeast = new Quadtree({x: x + w, y: y, width: w, height: h}, this.capacity);
        this.northwest = new Quadtree({x: x, y: y, width: w, height: h}, this.capacity);
        this.southeast = new Quadtree({x: x + w, y: y + h, width: w, height: h}, this.capacity);
        this.southwest = new Quadtree({x: x, y: y + h, width: w, height: h}, this.capacity);
        this.divided = true;
    }

    insert(object) {
        if (!this._contains(this.boundary, object)) return false;
        if (this.objects.length < this.capacity) {
            this.objects.push(object);
            return true;
        }
        if (!this.divided) this.subdivide();
        return (
            this.northeast.insert(object) ||
            this.northwest.insert(object) ||
            this.southeast.insert(object) ||
            this.southwest.insert(object)
        );
    }

    query(range, found = []) {
        if (!this._intersects(this.boundary, range)) return found;
        for (const obj of this.objects) {
            if (this._contains(range, obj)) found.push(obj);
        }
        if (this.divided) {
            this.northwest.query(range, found);
            this.northeast.query(range, found);
            this.southwest.query(range, found);
            this.southeast.query(range, found);
        }
        return found;
    }

    _contains(rect, obj) {
        return (
            obj.x >= rect.x &&
            obj.x < rect.x + rect.width &&
            obj.y >= rect.y &&
            obj.y < rect.y + rect.height
        );
    }

    _intersects(a, b) {
        return !(
            b.x > a.x + a.width ||
            b.x + b.width < a.x ||
            b.y > a.y + a.height ||
            b.y + b.height < a.y
        );
    }
}

Применение: Квадродерево идеально подходит для платформеров, стрелялок и стратегий, где объекты распределены неравномерно, а некоторые зоны сцены остаются пустыми. Использование query ограничивает поиск коллизий только теми объектами, которые реально могут столкнуться.

Сравнение пространственного хэша и квадродерева

Характеристика	Пространственный хэш	Квадродерево
Сложность реализации	Простая	Сложная
Подходит для	Равномерно распределённых объектов	Неравномерно распределённых объектов
Добавление/удаление	Очень быстро	Быстро, но требует пересортировки при делении
Память	Прямолинейная	Рекурсивная структура
Эффективность поиска	Хорошо для плотных равномерных сцен	Отлично для разреженных и динамических сцен

Оптимизация: пространственный хэш и квадродерево

Пространственный хэш (Spatial Hash)

Квадродерево (Quadtree)

Сравнение пространственного хэша и квадродерева

Рекомендации по использованию в Phaser