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

Question

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

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

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

Answer 1

Я не думаю, что это особенно неэффективно для реализации вашего предложения: проверьте, не переместился ли объект за пределы своего квадродерева, и если да, то удалите и повторно добавьте его. Любой объект, который перемещается от одного кадра к следующему, должен будет иметь некоторое обнаружение столкновения, конечно? И операции с квадродеревом выполняются только в том случае, если он перемещает квадродерево, и затраченное там время ЦП, вероятно, затмевается тем, что ЦП делает более точное «Касается ли объект А объект В?» вычисления. Так что я не знаю, что вы можете сделать лучше.

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

Answer 2

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

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