Przeszukanie obszaru wokół punktu

Question

Zagadnienie: Jak najefektowniej przeszukać obszar w okół danego punktu, aby sprawdzić kolizje lub znaleźć wszystkie obiekty znajdujące się w pobliżu.

Przykład: Projekt gry 2D, kilka obiektów na mapie, gracz, kilka przedmiotów, kilka przeciwników czy inne. Potrzebuję sprawdzić czy nie występuje kolizja z przeciwnikami, oraz czy przedmioty są na tyle blisko gracza, aby mógł je podnieść. Mamy tablice, gdzie umieszczone są wszystkie obiekty.

Istnieje opcja przeszukania wszystkich elementów w tablicy i sprawdzanie dla każdego obiektu pozycji i porównanie jej z pozycją gracza.

Inną opcją jest utworzenie tablicy(dwuwymiarowej), gdzie indeksami będą współrzędne mapy, a obiekty przypisane zgodnie z ich miejscem na mapie. Z naszej głównej tablicy pobieramy współrzędne gracza i w drugiej tablicy sprawdzamy czy "sąsiadujące" indeksy posiadają obiekty, a jeżeli tak to wtedy możemy wykonać odpowiednie operacje na nich.

W pierwszym sposobie minusem jest fakt, iż przeszukujemy całą tablice, nawet jeżeli dany przedmiot czy wróg jest na drugim końcu mapy, a w drugim natomiast musimy poświęcić miejsce na drugą tablice, którą dodatkowe trzeba będzie uaktualniać za każdym przemieszczeniem się gracza czy wrogów (czy przedmiotów, nieistotne).

Zakładam, iż w przypadku jeżeli na mapie jest tylko kilka przedmiotów to pierwsza opcja jest lepsza. Ale co w przypadku jeżeli mamy różne obiekty rzędu 100, 1000, 1000000? Kiedy sposób 1 czy 2 jest lepszy? Może to nie ma znaczenia i lepiej zawsze stosować drugi? Może istnieją o wiele lepsze rozwiązania? Co lepiej jeżeli mapa jest, a co jak bardzo duża? Co jeżeli musimy przeszukać mały obszar w okół gracza, a co jeżeli duży? Co jeżeli obliczamy kolizje za pomocą promienia? Wyszukujemy obiektów w promieniu (załóżmy) 10 jednostek, a obiekt, z którym miałaby wystąpić kolizja znajduje się 11 jednostek dalej, ale jest tak duży promień, że koliduje z pierwszym obiektem?

Problemów i pytań pewnie jest więcej, nie ma sensu się rozdrabniać. Proszę o ogólne porady/opinie/doświadczenia, sposoby na rozwiązanie problemu, link do materiałów, które mogą okazać się przydatne, lub zagadnienia pod którym mogę szukać informacji

Answer 1

https://en.wikipedia.org/wiki/Quadtree

... i wydajniejsze przy dużej ilości obiektów

https://en.wikipedia.org/wiki/R-tree

A tak na marginesie, jeśli masz więcej takich pytań: https://www.amazon.com/2D-Game-Collision-Detection-introduction/dp/1479298123/ref=sr_1_2?ie=UTF8&qid=1506493858&sr=8-2&keywords=collision+detection

i klasyk ale dla 3D

https://www.amazon.com/Real-Time-Collision-Detection-Interactive-Technology/dp/1558607323/ref=sr_1_1?ie=UTF8&qid=1506493858&sr=8-1&keywords=collision+detection