2D-игра: быстрый (устный) способ найти x ближайших сущностей для другого объекта - огромное количество сущностей, очень динамичных

Я работаю над 2D-игрой с огромным количеством динамических объектов. Ради удовольствия, давайте назовем их солдатами, и предположим, что из них 50000 (которые я просто случайно придумал, это может быть намного больше или намного меньше :)).2D-игра: быстрый (устный) способ найти x ближайших сущностей для другого объекта - огромное количество сущностей, очень динамичных

Все эти солдаты перемещают каждый кадр в соответствии с правилами - думайте о боях/флокеровании/рулевом управлении. Для каждого солдата, чтобы обновить его движение, мне нужны солдаты X, которые ближе всего к той, которую я обрабатываю.

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

источник

2009-08-13 Anonymous

не забудьте закрыть вопрос, выбрав наиболее полезный ответ. – Toad

Вот [хороший алгоритм] (http://wapedia.mobi/en/Flocking_ (поведение)), аналогично предложению reinier. –

[этот блог] (http://blogs.msdn.com/devdev/) имеет [хорошую запись одного решения] (http://blogs.msdn.com/devdev/archive/2007/06/07/k -nearest-neighbour-spaces-search.aspx) (а также ряд других хороших артикулов) – BCS

Самый простой способ - использовать сетку. Она имеет ряд преимуществ:

простые
быстро
легко добавлять и удалять объекты
легко изменить сетку на более тонкие детали, если вы все еще делаете слишком много проверок расстояния

Кроме того, убедитесь, что вы не выполняете squareroot для каждой проверки расстояния. Поскольку вы только сравниваете расстояния, вы также можете сравнить квадрат расстояния.

источник

2009-08-13 12:49:30 Toad

+1 для квадратного совета, всегда приятно напомнить ему – Gnoupi

+1 для площади, многие люди не понимают насколько экспансивна функция действительно, и как просто ее избежать;) –

Для широкополосного обнаружения столкновений, spatial index, как квад-дерево (так как это 2D) или сетка. Я связался с Metanet Software's tutorial; он описывает схему на основе сетки. Конечно, вашей игре даже не нужно использовать сетки так широко. Просто сохраните каждого актера в скрытой сетке и столкните его с объектами в одной и соседних ячейках.

источник

2009-08-13 12:50:18

quadtree - не лучший, так как для каждого движущегося объекта вам нужно удалить его из дерева и снова вставить его. Потенциально дорогостоящая операция. Или вам нужно снова восстановить дерево в каждом кадре. – Toad

@reinier: Я думаю, вы проведете некоторое тестирование, чтобы выяснить, как часто вам нужно обновлять quadtree. Вы всегда можете замедлить эту скорость и увеличить радиус объектов для проверки конфликтов. По общему признанию, быстро движущиеся объекты могут вылететь из увеличенного радиуса в любом случае, но это были проблемы, в первую очередь. –

тот же аргумент касается сетки; ^) – Toad

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

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

Quadtree/kd-tree кажется приятным, но они не слишком хороши с динамическими вставками. KD-деревья могут стать неуравновешенными.

Просто случайная мысль, если ваши сущности - это точки, которые сортируются по двойной структуре (по X и Y) в сочетании с бинарным поиском, может быть что-то попробовать ..?

источник

2009-08-13 13:50:03 Led

, если это не нужно, зачем использовать его? – Toad

2D-игра: быстрый (устный) способ найти x ближайших сущностей для другого объекта - огромное количество сущностей, очень динамичных

ответ

Смежные вопросы