Kdtree c++擦除和插入低性能

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个正方形内的实体，以确定哪个在圆内。