2D пространственное разделение альтернатив пространственным хешам и квадродеревам

11

Я пытался реализовать алгоритм пространственного разделения в моей игре, но и пространственные хеши, и квадродерево - это не то, что я ищу.

Размер моего уровня не должен иметь ограничения (только пределы Int32). Мне нужен алгоритм пространственного разделения, который не нуждается в «ширине уровня» и «высоте уровня».

У меня много движущихся физических объектов. Мне нужно, чтобы алгоритм был достаточно быстрым, чтобы поддерживать более 500 объектов.

Любая альтернатива?

c# collision-detection physics tree Витторио Ромео
источник

Ответы:

13

Динамическое Дерево

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

Когда Эрин обновил алгоритм до более широкого, он пошел с btDbvt Натанаэля Прессона. Это широкая фаза, используемая физикой пули. Эрин модифицировал и оптимизировал алгоритм для 2d.

Вы можете прочитать обзор сверхвысокого уровня в руководстве по Box2D (§4.11 или выполнить поиск по Dynamic Tree).

Вот исключение из документации в коде (что очень хорошо, учитывая, что оно не является частью общедоступного API).

Динамическое широкофазное дерево AABB, вдохновленное btDbvt Натанаэля Прессона. Динамическое дерево упорядочивает данные в двоичном дереве для ускорения запросов, таких как объемные запросы и приведение лучей. Листья являются прокси с AABB. В дереве мы расширяем прокси-AABB с помощью b2_fatAABBFactor, чтобы прокси-AABB был больше, чем объект клиента. Это позволяет клиентскому объекту перемещаться небольшими суммами без запуска обновления дерева.

Узлы объединяются и перемещаются, поэтому мы используем индексы узлов, а не указатели.

Мое понимание алгоритма Динамического Дерева таково. Динамическое дерево - это нечто среднее между классическим двоичным деревом avl и квадродеревом. Конечный эффект - это квадродерево, которое разделяет каждый узел пополам, и линия разделения не фиксируется (две половины не имеют одинакового размера, как дерево квадов). AVL приходит, потому что квадри с динамическими разбиениями может выродиться по существу в список (O (n) скорость поиска). AVL используется для балансировки поддеревьев, чтобы обеспечить скорость поиска O lg (N).

Лучше всего код MIT, так что не стесняйтесь копировать / получить / бесстыдно украсть / и т.д.

deft_code
источник
Выглядит ... сложно! Я посмотрю на это, хотя. Кто-то предложил мне использовать технику «очистки и сокращения» или «сортировки и очистки», но я не смог ничего найти в реализации C # или .NET. Я нашел пример на С ++, но он сбивает с толку и не работает (я все равно пытался его реализовать). Как вы думаете, SAP будет легче реализовать? Есть ли реализация .NET?
Витторио Ромео
8

Это очень похоже на аналогичный вопрос, заданный здесь на Gamedev, но, учитывая, что вы заинтересованы в производительности, а не в хранении файлов, возможно, мой ответ будет для вас более полезным . Я приведу большую часть этого здесь для полноты, но оригинальный ответ обеспечивает немного больше глубины, если вы хотите изучить это.

Я столкнулся с подобной проблемой и решил создать свою собственную структуру для обработки данных. Он свободно основан на квадродереве, но обладает бесконечной (по крайней мере такой же большой, как Int) расширяемостью во всех направлениях. Он был разработан для обработки данных, основанных на сетке, которые расширялись из центральной точки, так же, как сейчас делает Minecraft. Это экономит место в памяти и очень быстро.

Мой код можно найти здесь . Код завершен, протестирован (модульные и нагрузочные тесты) и довольно оптимизирован. Однако внутренняя работа еще не слишком хорошо документирована, но все общедоступные методы таковы, что ее следует использовать. Если кто-то решит попробовать, не стесняйтесь обращаться ко мне с вопросами или комментариями.

dlras2
источник
1

При работе с относительно небольшим числом (<несколько тысяч) небольших объектов (большинство объектов недостаточно велики, чтобы потенциально сталкиваться с множеством других объектов), я обнаружил, что работает простой упорядоченный по оси X список выровненных по оси ограничительных рамок (AABB) довольно хорошо. Я просто помещаю объекты в список, затем каждый кадр после перемещения объектов, быстро сортирую список по значению x, а затем делаю один проход по списку, проверяя близость AABB. Для каждого объекта я проверяю его по объектам, находящимся перед ним в списке, пока не достигну конца списка или объекта, который находится вне диапазона x; то есть значение x его левого края является> значением x правого края тестируемого объекта. Он в основном динамически делит пространство на иногда перекрывающиеся кусочки размером AABB-x-width. Это'

Shavais
источник
0

Может быть, алгоритм R-дерева - это то, что вы ищете.

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

бездельничать
источник
Я попробовал реализацию C #, и производительность была слишком плохой, когда «удалялись и добавлялись объекты на их новой позиции».
Витторио Ромео