2D Игра: Быстрый (установленный) способ найти x самые близкие объекты для другого объекта - огромная сумма объектов, очень динамичных
Если у Вас есть время, затем смотрят на способ, которым I18N сделан в платформа Jifty - хотя первоначально довольно сбивающий с толку это очень изящно и применимо.
Они перегружаются _ так, чтобы можно было использовать _("text to translate") где угодно в коде. Эти строки затем переводятся с помощью Локаль:: Maketext как нормальный.
то, Что делает это действительно мощным, - то, что они задерживают перевод, пока строка не необходима с помощью Скаляр:: Задержите так, чтобы можно было начать добавлять строки в любое время, даже перед знанием, в какой язык они будут переведены. Например, в файлах конфигурации и т.д. Это действительно делает I18N легкий работать с.
3 ответа
Весь смысл выбора хорошей пространственной иерархии состоит в том, чтобы иметь возможность быстро выбирать только те объекты, которые нуждаются в проверке. (Как только вы обнаружите это небольшое подмножество, квадратный корень, вероятно, больше не повредит)
Меня также интересует, какой метод является лучшим / наиболее оптимальным для двумерной пространственной индексации высокодинамичных объектов .
Quadtree / kd-tree кажутся хорошими, но они не слишком хороши для динамической вставки. KD-деревья могут стать несбалансированными.
Просто случайная мысль, если ваши объекты являются точками, можно попробовать структуру с двойной сортировкой вставкой (по X и Y) в сочетании с бинарным поиском ..?
Самый простой подход - использовать сетку. У этого есть несколько преимуществ:
- простой
- быстрый
- легкий добавление и удаление объектов
- легкое изменение сетки на более мелкие детали, если вы все еще выполняете слишком много проверок расстояния
Также убедитесь, что вы не делаете квадратный корень для каждой проверки расстояния. Поскольку вы сравниваете только расстояния, вы также можете сравнить квадрат расстояния.
Для обнаружения широкофазных столкновений подойдет пространственный индекс , такой как дерево квадратов (поскольку оно 2D) или сетка. Я уже ссылался на учебник по Metanet Software раньше; он описывает схему на основе сетки. Конечно, в вашей игре даже нет необходимости так широко использовать сетки. Просто сохраните каждого актера в скрытой сетке и столкните его с объектами в той же и соседних ячейках.