quadtree

Podczas nauki algorytmiki jednym z pierwszych algorytmów, które poznajemy, jest wyszukiwanie binarne pokazujące jak sprytnie szukać danych w posortowanej liście. Później poznajemy algorytmy wyszukiwania w grafach, z czego naturalnie przechodzi się do wyszukiwania ścieżek. Jednak tym razem spójrzmy na jeszcze inny rodzaj wyszukiwania, który może być przydatny przykładowo przy programowaniu gier. A jest to wyszukiwanie obiektów w przestrzeni. W artykule przedstawiam przykładowe podejścia do tego problemu, ograniczając się do przestrzeni dwuwymiarowej.