
QuadTree для самых маленьких
Текст полностью переписан, чтобы стать лучше :-)
Я сделал свою реализацию quadtree и желаю поделиться ей с народом. Оказалось, что это простая штука, которую несложно сделать.
Демка: Посмотреть.
Исходники (на AS3): скачать.
(Обновлено 28/01/2011 — поправлены баги, улучшена демка)
Зачем вообще это нужно?
Quadtree — это структура данных позволяющая ответить на вопросы: какие из кучи прямоугольных объектов пересекаются с заданным прямоугольником, и какие из кучи прямоугольных объектов пересекаются между собой.
На эти вопросы можно ответить и без quadtree, но скорее всего это выйдет дольше:
1. Если просто перебирать все объекты — это выйдет очень долго. Хотя часто этот подход срабатывает :-)
2. Если сделать сетку, и поместить ссылку на каждый объект в те ячейки, которые он пересекает, то во-первых вы быстро выясните, что это не так легко и быстро, если объект больше ячейки сетки, а во-вторых вы например будете напрасно перебирать клетки сетки, в которых ничего нет, а для тех, в которых окажется много объектов, вы будете очень долго искать пересечения. Это очень популярная техника, подкупающая простотой идеи, и действительно простая и эффективная, в случае если объекты меньше размера ячейки сетки и равномерно распределены в пространстве.
Как это работает?
Quadtree концептуально немного сложнее сетки, но в реализации даже проще, чем сетка, учитывающая, что объекты могут быть больше размера ячейки.
Основной идеей Quadtree является последовательное разделение участков пространства на четыре части. Т.е. берем квадрат, делим его на четыре квадрата поменьше, каждый получившийся — еще на четыре, и так далее. Получается квадратное дерево, потому так и называется.
Основным объектом нашего Quadtree является как раз такой квадрат, или узел дерева. Он содержит список тех объектов, которые находятся непосредственно в нем, а также ссылки на четыре дочерних квадрата поменьше.
Чтобы поместить прямоугольник в Quadtree мы находим среди всех наших квадратов такой, который
а) содержит наш прямоугольник целиком (это основное и обязательное требование)
б) содержит как можно меньше других прямоугольников
Каждый объект добавляется только в один узел дерева, т.е. если он содержится в каком-то квадрате, то он уже не добавляется в родителя этого квадрата, хотя физически (на плоскости) он и в нем содержится тоже.
Алгоритм добавления очень простой:
1) Начинаем с самого большого квадрата.
2) Если в дочерних квадратах пусто, и в самом квадрате пусто, то добавляем в этот текущий квадрат
3) Если объект не вписывается целиком ни в один из дочерних квадратов, то также добавляем объект в текущий квадрат
4) Если объект все же вписывается целиком в один из дочерних квадратов, то переходим к пункту (2), но уже с этим квадратом
Возможно имеет смысл ввести ограничение на минимальный размер квадрата (и соответственно глубину дерева) — но реально этот параметр сам собой ограничится размерами объектов и плотностью их распределения в пространстве.
Что если объект не содержится в самом большом квадрате? Три варианта:
1) Выдать ошибку.
2) Сделать квадрат побольше, добавив имеющийся самый большой в него в качестве дочернего.
3) Сделать как я :-) Смотри демку и исходники. Я на этот вопрос забил, но при реализации он решился сам собой, хоть и неэффективно для объектов вне квадрата.
Как использовать полученное дерево после добавления всех объектов?
Чтобы найти пересекающиеся с заданным прямоугольником объекты делаем так:
1) Начинаем с самого большого квадрата.
2) Проверяем все объекты из списка текущего квадрата на пересечение с прямоугольником.
3) Проверяем все четыре дочерних квадрата на пересечение с прямоугольником и для пересекающихся переходим к пункту 2
Чтобы найти все пересекающие многоугольники думаем сами, т.к. я пока не делал и врать не буду, но это не сильно сложно сделать: просто иерархически все перебрать, проверив на пересечение только потенциально пересекающиеся объекты.
Что делать если объект передвинулся?
Я не нашел ничего лучше, чем вынуть его из Quadtree и засунуть обратно. Скорее всего это можно оптимизировать, хотя бы проверив что он остается в том же квадрате и не трогать его тогда, но на практике в моем случае такая оптимизация ничего не дала. Наверное можно что-то еще придумать. Могу порекомендовать поменьше объекты двигать :-)
Еще посмотреть:
github.com/AdamAtomic/flixel/blob/master/org/flixel/FlxQuadTree.as — Исходник из фликселя (ссылка дана Eugene)
www.kyleschouviller.com/wsuxna/quadtree-source-included/ — на английском, но с картинками. Еще там есть исходники на C#, но не смотрел их, а текст хороший.
Я сделал свою реализацию quadtree и желаю поделиться ей с народом. Оказалось, что это простая штука, которую несложно сделать.
Демка: Посмотреть.
Исходники (на AS3): скачать.
(Обновлено 28/01/2011 — поправлены баги, улучшена демка)
Зачем вообще это нужно?
Quadtree — это структура данных позволяющая ответить на вопросы: какие из кучи прямоугольных объектов пересекаются с заданным прямоугольником, и какие из кучи прямоугольных объектов пересекаются между собой.
На эти вопросы можно ответить и без quadtree, но скорее всего это выйдет дольше:
1. Если просто перебирать все объекты — это выйдет очень долго. Хотя часто этот подход срабатывает :-)
2. Если сделать сетку, и поместить ссылку на каждый объект в те ячейки, которые он пересекает, то во-первых вы быстро выясните, что это не так легко и быстро, если объект больше ячейки сетки, а во-вторых вы например будете напрасно перебирать клетки сетки, в которых ничего нет, а для тех, в которых окажется много объектов, вы будете очень долго искать пересечения. Это очень популярная техника, подкупающая простотой идеи, и действительно простая и эффективная, в случае если объекты меньше размера ячейки сетки и равномерно распределены в пространстве.
Как это работает?
Quadtree концептуально немного сложнее сетки, но в реализации даже проще, чем сетка, учитывающая, что объекты могут быть больше размера ячейки.
Основной идеей Quadtree является последовательное разделение участков пространства на четыре части. Т.е. берем квадрат, делим его на четыре квадрата поменьше, каждый получившийся — еще на четыре, и так далее. Получается квадратное дерево, потому так и называется.
Основным объектом нашего Quadtree является как раз такой квадрат, или узел дерева. Он содержит список тех объектов, которые находятся непосредственно в нем, а также ссылки на четыре дочерних квадрата поменьше.
Чтобы поместить прямоугольник в Quadtree мы находим среди всех наших квадратов такой, который
а) содержит наш прямоугольник целиком (это основное и обязательное требование)
б) содержит как можно меньше других прямоугольников
Каждый объект добавляется только в один узел дерева, т.е. если он содержится в каком-то квадрате, то он уже не добавляется в родителя этого квадрата, хотя физически (на плоскости) он и в нем содержится тоже.
Алгоритм добавления очень простой:
1) Начинаем с самого большого квадрата.
2) Если в дочерних квадратах пусто, и в самом квадрате пусто, то добавляем в этот текущий квадрат
3) Если объект не вписывается целиком ни в один из дочерних квадратов, то также добавляем объект в текущий квадрат
4) Если объект все же вписывается целиком в один из дочерних квадратов, то переходим к пункту (2), но уже с этим квадратом
Возможно имеет смысл ввести ограничение на минимальный размер квадрата (и соответственно глубину дерева) — но реально этот параметр сам собой ограничится размерами объектов и плотностью их распределения в пространстве.
Что если объект не содержится в самом большом квадрате? Три варианта:
1) Выдать ошибку.
2) Сделать квадрат побольше, добавив имеющийся самый большой в него в качестве дочернего.
3) Сделать как я :-) Смотри демку и исходники. Я на этот вопрос забил, но при реализации он решился сам собой, хоть и неэффективно для объектов вне квадрата.
Как использовать полученное дерево после добавления всех объектов?
Чтобы найти пересекающиеся с заданным прямоугольником объекты делаем так:
1) Начинаем с самого большого квадрата.
2) Проверяем все объекты из списка текущего квадрата на пересечение с прямоугольником.
3) Проверяем все четыре дочерних квадрата на пересечение с прямоугольником и для пересекающихся переходим к пункту 2
Чтобы найти все пересекающие многоугольники думаем сами, т.к. я пока не делал и врать не буду, но это не сильно сложно сделать: просто иерархически все перебрать, проверив на пересечение только потенциально пересекающиеся объекты.
Что делать если объект передвинулся?
Я не нашел ничего лучше, чем вынуть его из Quadtree и засунуть обратно. Скорее всего это можно оптимизировать, хотя бы проверив что он остается в том же квадрате и не трогать его тогда, но на практике в моем случае такая оптимизация ничего не дала. Наверное можно что-то еще придумать. Могу порекомендовать поменьше объекты двигать :-)
Еще посмотреть:
github.com/AdamAtomic/flixel/blob/master/org/flixel/FlxQuadTree.as — Исходник из фликселя (ссылка дана Eugene)
www.kyleschouviller.com/wsuxna/quadtree-source-included/ — на английском, но с картинками. Еще там есть исходники на C#, но не смотрел их, а текст хороший.
- +13
- romamik
Комментарии (22)
gskinner.com/blog/archives/2005/02/source_code_gri.html
An optimized AS3 version — gskinner.com/blog/archives/2008/01/proximitymanage.html
Сетка в принципе тормознее для объектов больше ячейки грида.
Как вариант делать два грида — для больших и маленьких. Но это извращенство уже.
Это тоже можно растягивать, просто я не делал. Пока.
Насчет непонятно — попробую вечерком написать подробно, как работает.
romamik просьба описать скорость/технологию работы квад три с динамическими объектами, которые периодически при изменениях положения выписывают себя из листьев дерева и потом дописывают.
Ну и в целом по статье — нужно расписать механизм парсинга дерева на основе данных игровых объектов подробно, т.е. почему делим первый квад, конкретное условие деления, и конкретное условие записи линка на игровой объект в лист дерева. С нуля въехать в любые деревья — очень сложно. А раз ты въехал то объяснить другим думаю будет просто. Раз уж статью написал)) К тому же раз ты только въехал — объяснить себе еще раз зачем что нужно будет полезной практикой, может быть перепишешь код заново после этого. Ну и про динамику вопрос повис.
Теперь нужно разобраться с динамическими объектами. Вариант с «пореже двигать объект» отпадает. Для небольшой оптимизации в листьях можно заводить кеш под линки. Жрёт память, но динамику снижает.
Рендерер тоже я так понял завязан на квад? Тоже интересно узнать сколько рекурсий требуется чтобы забрать все объекты на рендер. В сетке всё просто — взял крайние точки AABB, получил начальный/конечный индекс сетки — прошёлся один раз, забрал все объекты.
Так то деревья интереснее, математика в действии)) Пугает только рекурсия во флеше. Вобщем даёшь продолжение темы!
Ну для меня как раз соотношение 1000 всего на 100 движущихся вполне устраивает.
Хотя в реальном движке с рендером и всеми делами уже ФПС выше 40-50 не поднимается хоть убейся, даже без квад-три вообще :-). А там еще логики никакой толком нет.
lab.polygonal.de/2007/09/09/quadtree-demonstration/
А вот это меня огорчило. Где правда? Что быстрее?
А так хорош. Хотя вот этот конкретный пост мне не понравился — не понятно ничего толком :-)
так что все исходники должни бить там.