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

每次有東西移動時插入或從集合中移除是一種可靠的方法，可以在瞬間瓶頸執行程序。

將你的世界分割成一個網格，並且在任何一個點上保留一個關於哪些字符是網格特定平方的參考。當你想找出靠近另一個實體的實體時，你可以圍繞實體中心定義一個圓，檢查哪個方塊與這個圓重疊，只檢查那些位於這四個方塊內的實體，以確定哪個實體位於圓內。