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

每次有东西移动时插入或从集合中移除是一种可靠的方法，可以在瞬间瓶颈执行程序。

将你的世界分割成一个网格，并且在任何一个点上保留一个关于哪些字符是网格特定平方的参考。当你想找出靠近另一个实体的实体时，你可以围绕实体中心定义一个圆，检查哪个方块与这个圆重叠，只检查那些位于这四个方块内的实体，以确定哪个实体位于圆内。