О чем этот пример
При разработке игр часто возникает задача быстрого поиска объектов в определённой области экрана. Например, для проверки столкновений курсора с объектами, поиска врагов в зоне видимости или определения объектов для атаки. Перебор всех игровых спрайтов при каждом движении мыши — операция ресурсоёмкая, особенно если объектов сотни. На помощь приходит структура данных R-Tree, реализованная в Phaser как `Phaser.Structs.RTree`. Эта статья покажет, как использовать R-Tree для эффективного поиска объектов в прямоугольной области, что значительно повысит производительность ваших игр при работе с большим количеством объектов на сцене.
Версия Phaser: код и демо в этой статье рассчитаны на Phaser 3.90.0.
Живой запуск
Ниже встроен рабочий билд примера. Оригинальный источник: GitHub.
Исходный код
class Example extends Phaser.Scene
{
preload ()
{
this.load.setBaseURL('https://raw.githubusercontent.com/phaserjs/examples/master/public/');
this.load.image('ship', 'assets/sprites/phaser-ship.png');
}
create ()
{
// Create an RTree
const tree = new Phaser.Structs.RTree();
for (let i = 0; i < 512; i++)
{
const ship = this.add.image(Phaser.Math.Between(0, 800), Phaser.Math.Between(0, 590), 'ship');
const bounds = ship.getBounds();
// Insert our entry into the RTree:
tree.insert({ left: bounds.left, right: bounds.right, top: bounds.top, bottom: bounds.bottom, sprite: ship });
}
const debug = this.add.graphics();
debug.lineStyle(1, 0x00ff00);
let results = [];
this.input.on('pointermove', pointer =>
{
// First clear the previous results
results.forEach(entry =>
{
entry.sprite.setTint(0xffffff);
});
debug.clear();
// Update the search area
const bbox = {
minX: pointer.x - 100,
minY: pointer.y - 100,
maxX: pointer.x + 100,
maxY: pointer.y + 100
};
// Search the RTree
results = tree.search(bbox);
// Set Tint on intersecting Sprites
results.forEach(entry =>
{
entry.sprite.setTint(0xff0000);
});
// Draw debug
debug.strokeRect(bbox.minX, bbox.minY, 200, 200);
}, this);
}
}
const config = {
type: Phaser.AUTO,
width: 800,
height: 600,
backgroundColor: '#2d2d2d',
parent: 'phaser-example',
scene: Example
};
const game = new Phaser.Game(config);
Что такое R-Tree и зачем он нужен?
R-Tree — это древовидная структура данных, индексирующая пространственные объекты по их ограничивающим прямоугольникам (bounding boxes). Вместо последовательного перебора всех объектов для нахождения тех, что пересекаются с заданной областью, RTree выполняет поиск за логарифмическое время.
В контексте Phaser это позволяет мгновенно находить все спрайты, попадающие в область курсора мыши, зону видимости камеры или область эффекта, без проверки каждого объекта на сцене.
Пример из статьи как раз демонстрирует эту задачу: он находит все спрайты кораблей в пределах квадрата 200x200 пикселей, следующего за курсором.
Создание RTree и наполнение данными
Первым делом создаётся экземпляр RTree. Затем для каждого игрового объекта вычисляется его ограничивающий прямоугольник и записывается в дерево вместе со ссылкой на сам объект.
const tree = new Phaser.Structs.RTree();В цикле создаются спрайты и для каждого из них получаются границы. Ключевой момент — вставка данных в RTree. Данные должны представлять собой объект с полями, описывающими прямоугольник (left, right, top, bottom), и любыми другими пользовательскими данными (в нашем случае — ссылкой на спрайт).
const ship = this.add.image(Phaser.Math.Between(0, 800), Phaser.Math.Between(0, 590), 'ship');
const bounds = ship.getBounds();
tree.insert({ left: bounds.left, right: bounds.right, top: bounds.top, bottom: bounds.bottom, sprite: ship });Метод getBounds() возвращает прямоугольник Phaser.Geom.Rectangle, описывающий габариты спрайта в мировых координатах.
Организация поиска по области
Поиск в RTree запускается в обработчике события движения указателя pointermove. Для этого необходимо определить область поиска — прямоугольник (bbox — bounding box).
const bbox = {
minX: pointer.x - 100,
minY: pointer.y - 100,
maxX: pointer.x + 100,
maxY: pointer.y + 100
};Обратите внимание, что RTree в Phaser ожидает на вход объект с полями minX, minY, maxX, maxY, а не left, right и т.д. Это важно для корректной работы.
Затем выполняется собственно поиск:
results = tree.search(bbox);Метод search() возвращает массив всех записей (тех самых объектов, которые мы вставляли через insert), чьи прямоугольники пересекаются с заданным bbox.
Визуализация и обработка результатов
После получения результатов их нужно обработать. В примере это делается в два этапа: 1. Сброс визуального выделения у всех объектов из предыдущего результата поиска. 2. Применение выделения (установка красного оттенка) к объектам из нового результата.
// Сброс предыдущего выделения
results.forEach(entry => {
entry.sprite.setTint(0xffffff);
});
// Применение нового выделения к найденным спрайтам
results.forEach(entry => {
entry.sprite.setTint(0xff0000);
});Для наглядности область поиска также отрисовывается на экране с помощью графического объекта debug.
debug.strokeRect(bbox.minX, bbox.minY, 200, 200);Важно не забывать очищать графику (debug.clear()) и сбрасывать выделение перед каждым новым поиском, чтобы визуализация соответствовала текущему кадру.
Что попробовать дальше
Использование Phaser.Structs.RTree — это мощный приём для оптимизации пространственных запросов в играх. Вы можете адаптировать этот подход не только для взаимодействия с курсором, но и для расчёта зоны видимости NPC, определения объектов в радиусе действия заклинания или оптимизации широкофазного обнаружения столкновений.
Попробуйте поэкспериментировать: измените размер области поиска в зависимости от скорости движения курсора, реализуйте выделение объектов по клику с помощью tree.search(), или создадите динамическое дерево, которое будет обновляться (tree.clear() + перевставка) для движущихся объектов.