Блог

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

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

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

Я не думаю, что особенно неэффективно реализовать ваше предложение: проверьте, не переместился ли объект за пределы своего квадратичного дерева, и если да, то удалите и повторно добавьте его. Для любого объекта, который перемещается из одного кадра в следующий, необходимо, чтобы на нем выполнялось какое-либо обнаружение столкновений, не так ли? И операции с quadtree выполняются только в том случае, если они перемещают quadtrees, и время процессора, затрачиваемое на это, вероятно, затмевается временем процессора, выполняющим более точные вычисления «Касается ли объект A объекта B?». Так что я не знаю, что вы можете сделать лучше.

На ваш 2-й вопрос: я не знаю, как другие люди реализуют quadtrees, но я разрешаю объектам занимать более одного квадратичного дерева именно по той причине, которую вы указали на своей диаграмме (когда объект пересекает границу). Таким образом, объект имеет «текущий список квадратиков» вместо «текущего квадрата».

Удаление / повторное добавление может быть оптимизировано путем перемещения вверх по дереву квадратиков вместо полного удаления элемента из дерева и последующего повторного добавления, т. Е. Перехода к «родительскому» квадратику, а затем добавления его «родительским» — если он не вписывается в «родительский», перейдитек «дедушке и бабушке» и т. Д.

Что касается вашей второй проблемы, вам понадобится некоторая гибкость — если все 3 находятся на ребре, вы не можете их опустить — но это должно быть (простите за каламбур) крайним случаем.