Причина, по которой вы не видите очевидного прироста производительности от Quadtree, заключается в характере вашего моделирования. В настоящее время разделение по умолчанию заставляет большое количество boids сходиться в одну и ту же позицию.
Множество объектов в одном и том же положении сведет на нет возможное ускорение из-за пространственного разделения. Если все объекты находятся в одинаковом или близком положении, боиды в области вынуждены проверять все другие боиды в этой области.
Вы можете продемонстрировать себе, что ваш Quadtree работает, просмотрев или профилировав свое приложение с его настройками по умолчанию. Теперь включите разделение до максимума. Вы увидите визуально или с помощью профилирования, что по мере того, как боиды распределяются более равномерно, FPS значительно увеличивается. Это связано с тем, что Quadtree теперь может предотвращать вычисления благодаря своему пространственному разделению.
С низким разделением по умолчанию: ![С низким разделением](https://i.stack.imgur.com/ gtLTq.png)
С максимальным разделением: ![С максимальным разделением](https://i.stack.imgur.com/0bnzK .png)
Вы можете увидеть, как производительность увеличилась на втором изображении. Также обратите внимание, что предположение другого комментатора о том, что все время занимает построение Quadtree (insert
), неверно.
Хотя в некоторых приложениях вы можете обновлять Quadtree по мере перемещения объектов, поскольку в этой симуляции каждая составляющая перемещается в каждом кадре, реконструкция Quadtree с нуля меньше работы, а затем удаление каждого объекта и повторная вставка его в новое положение.
Совет пропустить квадратный корень и просто использовать квадрат расстояния хорош, так как это даст вам немного больше производительности.
person
ldlework
schedule
02.05.2021