Dodałbym to jako komentarz w odpowiedzi na odpowiedź @ Natana Reeda, z wyjątkiem tego, że jest zbyt duży, aby być komentarzem, i być może w każdym razie zasługuje na osobną odpowiedź.
Robiliśmy dokładnie to, co zaproponowano w jego odpowiedzi, i faktycznie mieliśmy komentarz w źródle prowadzącym do tej strony. W przeważającej części działało to bardzo dobrze, z tym wyjątkiem, że raz na dwa lub trzy miesiące losowo traciliśmy serwer, który przestał odpowiadać z powodu ogromnego czasu trwania zapytań.
Przyczyna problemu zwróciła moją uwagę podczas sprawdzania wydajności, aby dowiedzieć się, co było przyczyną tego problemu. Jest to prawdopodobnie tylko problem, jeśli pozwalasz na nakładanie się obiektów. W naszej grze tak się dzieje, aw najgorszym przypadku może to czasami doprowadzić do gwałtownego wzrostu wydajności.
Mieliśmy jedną skrzynkę, w której około 100 obiektów, wszystkie z ograniczającymi dyskami, było skupionych w bardzo bliskiej odległości. Doprowadziło to do problemu bardzo głębokiego skoku w drzewie, ponieważ doszliśmy do punktu, w którym obiekty były większe niż obszar objęty przez quadtree węzły, więc każdy nowy obiekt pojawiał się w wielu węzłach, co prowadzi do masywnego podziału drzewo, dzięki czemu problem wymyka się spod kontroli.
Wynika to z tego, że jeśli pozwalasz na nakładanie się obszarów obiektów, uważnie obserwuj rzeczy, jeśli otrzymujesz ciasne skupiska obiektów, aby mieć pewność, że twoje drzewo nie będzie zbyt głębokie.
Rozwiązaniem, które obecnie badam, jest przechowywanie obiektów jako punktów, a następnie podczas wyszukiwania zwiększyć granice prostokąta wyszukiwania o maksymalny promień przechowywany w drzewie. To powinno dla nas zadziałać, ponieważ drzewo jest wyszukiwaniem pierwszego przejścia, a następnie przeprowadzamy sprawdzanie zasięgu w oparciu o prawdziwe koło, a także kilka innych kryteriów, aby dodatkowe fałszywe alarmy zostały odfiltrowane.
Rzeczywisty przebieg może się różnić.