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#, но не смотрел их, а текст хороший.
  • +13

Комментарии (22)

0
слышал про эту тему мельком, в статейке чтото совсем ничего не понял =)
0
Читай код, там все понятно. А статейка считай комментарий.
0
Из похожего
gskinner.com/blog/archives/2005/02/source_code_gri.html
An optimized AS3 version — gskinner.com/blog/archives/2008/01/proximitymanage.html
0
Пасиб! но во-первых — тормозит. Во-вторых — лучше использовать сетку. И отталкиваться от самого большого объекта в игре. Неможет жебыть чтобы объект был больше там пол экрана например?) с сеткой удобнее, потому как можно её дорисовывать, тем самым растягивая наш игровой мирдо сколькоугодного размера:) сам читал о сетке недавно.) Это тоже интересно хотя мало чего понятно)
+1
Тормозит отрисовка. dl.dropbox.com/u/11399208/QuadTree2.swf

Сетка в принципе тормознее для объектов больше ячейки грида.
Как вариант делать два грида — для больших и маленьких. Но это извращенство уже.

Это тоже можно растягивать, просто я не делал. Пока.

Насчет непонятно — попробую вечерком написать подробно, как работает.
0
А вообще объекты разные бывают. Например может быть триггер события на пол-уровня вообще, почему нет. Если не долго проверить, то не надо себя ограничивать.
0
Спасибо. Не знаю использовать ли, но в плане самобучения однозначно полезняк!
0
От себя добавлю что QuadTree в основном используют для оптимизации столкновений/отрисовки статики. Для динамики всё же шустрее ведет себя сетка. А по поводу того как натягивать сетку и по каким параметрам вообще её делать — на глаз. Все равно будет некое константное значение размера ячейки, под конкретную игру и для конкретных объектов. Делать сенсор в пол игрового мира — я бы такую идею забанил на этапе проектирования :D

romamik просьба описать скорость/технологию работы квад три с динамическими объектами, которые периодически при изменениях положения выписывают себя из листьев дерева и потом дописывают.

Ну и в целом по статье — нужно расписать механизм парсинга дерева на основе данных игровых объектов подробно, т.е. почему делим первый квад, конкретное условие деления, и конкретное условие записи линка на игровой объект в лист дерева. С нуля въехать в любые деревья — очень сложно. А раз ты въехал то объяснить другим думаю будет просто. Раз уж статью написал)) К тому же раз ты только въехал — объяснить себе еще раз зачем что нужно будет полезной практикой, может быть перепишешь код заново после этого. Ну и про динамику вопрос повис.
0
Я переписал текст, надеюсь он теперь что-то объясняет.
0
Вот. Теперь красиво. Плюсанул.

Теперь нужно разобраться с динамическими объектами. Вариант с «пореже двигать объект» отпадает. Для небольшой оптимизации в листьях можно заводить кеш под линки. Жрёт память, но динамику снижает.

Рендерер тоже я так понял завязан на квад? Тоже интересно узнать сколько рекурсий требуется чтобы забрать все объекты на рендер. В сетке всё просто — взял крайние точки AABB, получил начальный/конечный индекс сетки — прошёлся один раз, забрал все объекты.

Так то деревья интереснее, математика в действии)) Пугает только рекурсия во флеше. Вобщем даёшь продолжение темы!
+1
С динамическими объектами не все так плохо. Во второй демке всего 1000 объектов, каждый степ движется примерно 100 остальные стоят, FPS — около 70. Если движутся все 1000, то около 40, а если ни одного, то 80.
Ну для меня как раз соотношение 1000 всего на 100 движущихся вполне устраивает.

Хотя в реальном движке с рендером и всеми делами уже ФПС выше 40-50 не поднимается хоть убейся, даже без квад-три вообще :-). А там еще логики никакой толком нет.
+1
я еще встречал использование QuadTree во фликселе. может кому интересно будет тамошний класс посмотреть
+2
Еще есть всема любимий

lab.polygonal.de/2007/09/09/quadtree-demonstration/
0
классный блог, нашёл что то про хеш и инстансинг почитать на ночь.

I’m not sure if the quad tree is faster than a regular grid, but I’ll compare both versions soon.

А вот это меня огорчило. Где правда? Что быстрее?
0
Только сорцов-то не дает…
А так хорош. Хотя вот этот конкретный пост мне не понравился — не понятно ничего толком :-)
0
Тут дело в том что там есть либа, которую долгое время много флешеров исползовали :) от polygonal, lab.polygonal.de/as3ds/

так что все исходники должни бить там.
0
По моему там нет… Но не буду врать, не искал подробно.
0
Квад трии хорош для 3д, для 2д имхо быстрее будет просто регулярная сетка с размерами ячеек 100x100 пикселей.
0
Хотя конечно это зависит от подвижности объектов и их размера…
0
А так же их количества и размеров карты :-)
0
была бы еще прорисовка разделена от самой реализации алгоритма — было бы вообще замечательно..)
0
А зачем вообще прорисовка? Она только для дебага самого этого дерева…
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.