О чем этот пример
При разработке игр часто возникает задача быстрого поиска объектов в заданной области экрана. Например, для определения столкновений, отрисовки только видимых спрайтов или поиска целей для ИИ. Перебор всех объектов на сцене может быть крайне неэффективным. В этой статье мы разберем, как использовать структуру данных R-Tree в Phaser для мгновенного поиска объектов в прямоугольной области. Этот подход позволяет оптимизировать производительность вашей игры, особенно когда на сцене находится сотни или тысячи активных элементов.
Версия Phaser: код и демо в этой статье рассчитаны на Phaser 3.90.0.
Живой запуск
Ниже встроен рабочий билд примера. Оригинальный источник: GitHub.
Исходный код
class Example extends Phaser.Scene
{
boxY = 0;
boxX = 0;
result;
preload ()
{
this.load.setBaseURL('https://raw.githubusercontent.com/phaserjs/examples/master/public/');
this.load.image('phaser', 'assets/sprites/diamond.png');
}
create ()
{
const tree = Phaser.Structs.RTree();
const w = this.sys.textures.getFrame('phaser').width;
const h = this.sys.textures.getFrame('phaser').height;
for (let i = 0; i < 512; i++)
{
const x = Phaser.Math.Between(0, 800);
const y = Phaser.Math.Between(0, 600);
const sprite = this.add.image(x, y, 'phaser').setOrigin(0);
tree.insert({
left: x,
top: y,
right: x + w,
bottom: y + h,
sprite: sprite,
w: w,
h: h
});
}
this.result = tree.search({
minX: 0,
minY: 0,
maxX: 256,
maxY: 256
});
this.input.on('pointermove', pointer =>
{
this.boxX = pointer.x;
this.boxY = pointer.y;
this.result = tree.search({
minX: this.boxX,
minY: this.boxY,
maxX: this.boxX + 256,
maxY: this.boxY + 256
});
});
this.events.on('render', this.render, this);
}
render ()
{
const ctx = this.sys.game.context;
ctx.strokeStyle = 'rgba(255,255,255,1)';
ctx.lineWidth = 2;
ctx.strokeRect(this.boxX, this.boxY, 256, 256);
ctx.fillStyle = 'rgba(255,0,0,0.5)';
this.result.forEach(s =>
{
ctx.fillRect(s.left, s.top, s.w, s.h);
});
}
}
const config = {
type: Phaser.CANVAS,
parent: 'phaser-example',
width: 800,
height: 600,
scene: Example
};
const game = new Phaser.Game(config);
Что такое R-Tree и зачем он нужен
R-Tree — это древовидная структура данных, предназначенная для эффективного хранения и поиска пространственных объектов по их границам (bounding boxes). В отличие от простого перебора всех объектов (сложность O(n)), R-Tree выполняет поиск за логарифмическое время в среднем случае.
В игровом движке Phaser реализация R-Tree доступна через модуль Phaser.Structs.RTree. Он идеально подходит для сценариев, где вам нужно быстро найти все спрайты, попадающие в область просмотра камеры, зону действия спеллa или потенциальные цели для столкновений.
Основные методы, которые мы будем использовать:
- insert() — для добавления объекта с его границами в дерево.
- search() — для поиска всех объектов, чьи границы пересекаются с заданным прямоугольником.
Создание R-Tree и наполнение объектами
В примере мы создаем сцену и наполняем ее 512 случайно расположенными спрайтами. Каждый спрайт добавляется не только на экран, но и в R-Tree с описанием его ограничивающего прямоугольника.
Ключевой момент: данные, которые мы сохраняем в дереве, — это обычный JavaScript-объект. В нем хранятся координаты прямоугольника (left, top, right, bottom), ссылка на сам спрайт и его размеры. Это позволяет после быстрого поиска по дереву сразу получить доступ к игровому объекту (спрайту).
const tree = Phaser.Structs.RTree();
const w = this.sys.textures.getFrame('phaser').width;
const h = this.sys.textures.getFrame('phaser').height;
for (let i = 0; i < 512; i++)
{
const x = Phaser.Math.Between(0, 800);
const y = Phaser.Math.Between(0, 600);
const sprite = this.add.image(x, y, 'phaser').setOrigin(0);
tree.insert({
left: x,
top: y,
right: x + w,
bottom: y + h,
sprite: sprite,
w: w,
h: h
});
}Поиск объектов в динамической области
После заполнения дерева мы выполняем первоначальный поиск в статической области (левый верхний квадрат 256x256). Однако настоящая мощь R-Tree раскрывается при динамических запросах.
В примере поиск привязан к движению указателя мыши. При каждом перемещении курсора вызывается tree.search() для прямоугольной области размером 256x256, центр которой — текущие координаты мыши. Метод search() принимает объект с полями minX, minY, maxX, maxY и возвращает массив всех объектов из дерева, чьи прямоугольники пересекаются с заданной областью.
this.input.on('pointermove', pointer =>
{
this.boxX = pointer.x;
this.boxY = pointer.y;
this.result = tree.search({
minX: this.boxX,
minY: this.boxY,
maxX: this.boxX + 256,
maxY: this.boxY + 256
});
});Результат поиска сохраняется в свойстве this.result для последующей отрисовки в методе render().
Визуализация результата через событие render
Phaser предоставляет специальное событие render, которое вызывается после отрисовки всего игрового кадра. Это идеальное место для поверхностной отрисовки поверх игрового мира, например, для дебаг-информации или, как в нашем случае, для визуализации зоны поиска и найденных объектов.
В обработчике render() мы получаем доступ к CanvasRenderingContext2D через this.sys.game.context и рисуем два типа элементов:
1. Белый контур (strokeRect) — это динамическая область поиска, следующая за курсором.
2. Красные полупрозрачные прямоугольники (fillRect) поверх каждого спрайта, который был найден в результате последнего поиска по R-Tree.
render ()
{
const ctx = this.sys.game.context;
// Отрисовка области поиска
ctx.strokeStyle = 'rgba(255,255,255,1)';
ctx.lineWidth = 2;
ctx.strokeRect(this.boxX, this.boxY, 256, 256);
// Отрисовка найденных объектов
ctx.fillStyle = 'rgba(255,0,0,0.5)';
this.result.forEach(s =>
{
ctx.fillRect(s.left, s.top, s.w, s.h);
});
}Это наглядно демонстрирует, как движущаяся область 'захватывает' разные спрайты, и дерево мгновенно выдает новый результат.
Что попробовать дальше
Использование R-Tree в Phaser — это мощный метод оптимизации для игр с большим количеством объектов на сцене. Вместо дорогостоящего перебора вы получаете быстрый поиск по области. Вы можете экспериментировать, применяя этот подход для: - Кастомизации зоны видимости камеры (culling). - Предварительного отбора кандидатов для точной проверки физических столкновений. - Создания систем выделения объектов (как в стратегиях) или поиска ближайших целей. Попробуйте интегрировать R-Tree в свою игру и замерьте прирост производительности в сценариях с тысячами активных спрайтов.