Kdtree C ++ удалить и вставить низкую Perfomance

Question

В моей игре я использую libkdtree ++.Мой подход на каждом ходу NPC или игрока, стереть его из дерева и вставить новую позицию.Примерно так:

void Map::updateEntityPos(Entity& e)
{
    map_lock.lock();
    map_duplet.set_data(e.getLastPos(), &e);
    entity_tree->erase_exact(map_duplet);
    entity_tree->optimise();
    map_duplet.set_data(e.getPos(), &e);
    entity_tree->insert(map_duplet);
    entity_tree->optimise();
    map_lock.unlock();
}

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

Answer 1

Вставка или удаление из коллекции каждый раз, когда что-то движется, является верным способом сузить производительность вашей программы в одно мгновение.

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