Jak znaleźć komórki siatki 2D omiatanej przez ruchomy okrąg?

Tworzę grę opartą na siatce 2D, z niektórymi komórkami możliwymi do przejścia, a niektóre nie. Obiekty dynamiczne mogą się poruszać w sposób ciągły, niezależnie od siatki, ale muszą zderzać się z nieprzejezdnymi komórkami.

Napisałem algorytm do śledzenia promienia na siatce, który daje mi wszystkie komórki, które się przecinają. Rzeczywisty obiekt nie ma jednak wielkości punktowej; Obecnie reprezentuję je jako kręgi. Ale nie mogę znaleźć skutecznego algorytmu do śledzenia poruszającego się koła. Oto zdjęcie tego, czego potrzebuję:

Liczby pokazują, w jakiej kolejności koło zderza się z komórkami siatki. Czy ktoś zna algorytm znajdowania takich kolizji? Najlepiej w C #.

Aktualizacja Krąg może być większy niż pojedyncza komórka siatki.

Myślę, że twój rysunek jest trochę mylący, ponieważ wybierasz rysowanie pociągnięć od punktu na okręgu stycznego do twojego kierunku ruchu. Widzę, że zderzenia z krawędziami siatki zdarzają się, gdy TOP i LEWE punkty twojego okręgu dotykają krawędzi.

Niech C będzie twoim środkiem ir promieniem, więc P ' = C + ( r , 0) i P " = C + (0, r).

Jeśli D jest wektorem kierunku (versor), masz dwie linie:

R '= D · t + P' ,

R "= D · t + P"

Po prostu musisz znaleźć przecięcie tych linii z liniami równania:

y = i y = i, które są krawędziami twojej siatki!

Rozwiązanie jest łatwe, ponieważ musisz po prostu wziąć pod uwagę składową x lub y R 'i R ". Znajdziesz wartość t s dla każdego wstawienia, a punkty dla tych ts , po prostu posortuj te punkty według t, a ty są skończone.

Wierzę, że możesz łatwo powiedzieć, która komórka jest trafiona, jeśli znasz punkt przecięcia.

Działa to, jeśli r <1 (szerokość i wysokość komórki).

Działa to również w innych przypadkach, po prostu biorąc pod uwagę P i P " . Wybieramy GÓRA i LEWO ze względu na kierunek, DOLNĄ i PRAWĄ należy brać pod uwagę w przeciwnym kierunku, rozumiesz dlaczego.

Teraz spójrz na ten obraz:

Okrąg jest większy niż pojedyncza komórka i przypuszczamy, że zmierza w tym samym kierunku, co rysunek. P1 to pierwszy punkt, który się dotknie, P2 to drugi, P3 jest bezużyteczny, ponieważ znajduje się w dolnej połowie. Musisz tylko rzucić promienie z P1 i P2, jak widzieliśmy wcześniej, i zrobić to samo dla linii pionowych.

Ogólnie rzecz biorąc, będziesz mieć inne punkty początkowe oraz TOP i LEWE, z których strzelasz promieniami, im większy jest twój okrąg, tym więcej promieni rzucasz.

Szczerze mówiąc, można uniknąć strzelania do wszystkich promieni z uwzględnieniem geometrii, ale może to utrudnić zrozumienie.

Jeśli chcesz użyć algorytmu kolizji promieni, możesz wybrać osiem punktów na każdym kole (w przyrostach co 45 stopni, wyrównanych z kwadratową siatką) i użyć kolizji promieni między odpowiednimi punktami (tj. Od góry jednego kółko na górę drugiego). Połączenie wszystkich tych zderzeń promieni stanowi cały zestaw przecinających się komórek.

Prawdopodobnie można by to nieco poprawić - na przykład używając odcinka linii od środka jednego koła do środka drugiego, ale przedłużonego po obu stronach o promień koła, a także równoległych odcinków linii na po obu stronach na końcach kręgów.

Nie twierdzę, że jest to idealna analogia, ale możesz pomyśleć o algorytmie liniowym Bresenhama . Pomocna może być modyfikacja tego algorytmu lub jednego z jego rozszerzeń, zwłaszcza jeśli połączymy go z innymi postami i komentarzami. Zazwyczaj ten algorytm nie dotyczy zamawiania, ale wydaje mi się, że można go dodać dość trywialnie.