Двумерная ускоряющая структура - PullRequest
0 голосов
/ 01 июня 2018

Я пишу небольшую игру, в которой много (порядка 1000-10000) машин едут вокруг вас и должны плавно увернуться друг от друга.Их положение может быть представлено их 2D XY-координатами.

Каждый кадр, каждый автомобиль должен гарантировать, что он не сталкивается с другим, который наивно реализован будет алгоритмом O (N ^ 2).Какую структуру 2D-ускорения лучше всего использовать, чтобы сделать ее более эффективной?

Чтобы добавить больше контекста:

  • Поскольку автомобили могут перемещаться куда угодно, структура должна постоянно отслеживать все автомобили.Таким образом, его нужно быстро обновить (например, не O (N) для каждого автомобиля).
  • Каждый автомобиль движется на каждом кадре
  • Автомобили не могутударил любую другую машину.У них, очевидно, есть знания о своих размерах, их текущем направлении и скорости.Их размер равен ноль-ноль (потому что вы знаете, что это автомобиль), и ему нужны эти данные при проверке столкновений.
  • Я рассмотрел обычную сетку с сет-структурой, которая работает,но каждая машина все еще должна проверять свою собственную камеру и всех своих (8) соседей, поэтому я думаю, что есть еще лучшие способы.

Ответы [ 2 ]

0 голосов
/ 03 июня 2018

Вы можете использовать что-то вроде quadtree .Квадродерево - это двумерная схема индексации с временем обновления (вставки / удаления) O (log n).

Самая простая возможность - хранить прямоугольники (ограничивающие оси прямоугольники) для каждого автомобиля.Затем, каждый раз перед тем, как заново вставить автомобиль в его новую позицию, вы выполняете запрос окна (запрос прямоугольника) в новой позиции, чтобы увидеть, перекрывается ли он с любой другой машиной.Если у вас есть исходный код дерева, вы даже можете реализовать комбинированную операцию updateAnCheck (), которая обнаруживает коллизии и обновления за один вызов.(Я предполагаю, что структура обновляется достаточно часто, так что старые и новые позиции перекрываются, так что столкновения более или менее надежно обнаруживаются, другие мудрые машины могут «телепортироваться» друг через друга, если они достаточно быстры).

Сложность:

  • Обновление: O (log n) на автомобиль
  • Запрос: O (log n) на автомобиль
  • Пространство: О O (log n) наcar

Общая вычислительная сложность: обнаружение всех коллизий для n car: O (n * 2 * log n) = O (n log n) Общая сложность пространства: около O (n * log n)

Существует множество реализаций с открытым исходным кодом для квадродеревьев, если вы используете Java, вы можете проверить mine .

0 голосов
/ 01 июня 2018

Итак, вы должны проверить, есть ли столкновение.Для того, чтобы произошло столкновение, если я понимаю ваш пример, после того, как автомобили движутся, в одном и том же месте должны быть две машины.

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

После того, как мы это сделаем, вам нужно будет только проверить, содержит ли набор следующую позицию автомобиля, чтобы узнать, будет ли столкновение или нет, и в консультации HashSet, которая является O (1).Примените это к количеству автомобилей (n), и вы будете управлять коллизиями в O (n).

Пример для дальнейшего уточнения:

Выэта матрица позиций с автомобилями на «О» и пустыми пространствами на «Х».Это означает, что у вас будет машина на позиции 1, а другая - на позиции 8, если вы пронумеруете свои позиции из верхнего левого угла.

O X X
X X X
X O X

Это будет означать, что у вас есть набор целых чисел с позициями 1 и8 на это.Теперь, пример для перемещения одного из автомобилей:

Автомобиль в положении 1 перемещается в положение 2: Вы проверяете, находится ли положение 2 в наборе [O (1)].Это не так.Вы удаляете позицию 1 из набора [O (1)] и добавляете позицию 2 к набору [O (1)], потому что теперь в позиции 1 нет машины, а в позиции 2.

Повторите для каждого автомобиля (n) => O (1) * O (n) = O (n).

...