Znalezienie kierunku podróży w świecie z zawiniętymi krawędziami

Muszę znaleźć najkrótszą odległość od jednego punktu w moim świecie 2D do innego punktu, w którym krawędzie są owinięte (jak asteroidy itp.). Wiem, jak znaleźć najkrótszą odległość, ale staram się znaleźć kierunek.

Najkrótszą odległość podaje:

int rows = MapY;
int cols = MapX;

int d1 = abs(S.Y - T.Y);
int d2 = abs(S.X - T.X);
int dr = min(d1, rows-d1);
int dc = min(d2, cols-d2);

double dist = sqrt((double)(dr*dr + dc*dc));

Przykład świata

                   :         
                   :  T    
                   :         
    :--------------:---------
    :              :
    :           S  :
    :              :
    :              :
    :  T           :
    :              :
    :--------------:

Na schemacie krawędzie pokazano za pomocą: i -. W prawym górnym rogu pokazałem też zawinięte powtórzenie świata. Chcę znaleźć kierunek w stopniach od S do T. Więc najkrótsza odległość to powtórzenie T. w prawym górnym rogu, ale jak obliczyć kierunek w kierunku od S do powtarzanego T w prawym górnym rogu?

Znam pozycje zarówno S, jak i T, ale przypuszczam, że muszę znaleźć pozycję powtarzanej T, ale tam więcej niż 1.

Układ współrzędnych światów zaczyna się od 0,0 w lewym górnym rogu i 0 stopni, aby kierunek mógł zacząć się na Zachodzie.

Wygląda na to, że nie powinno to być zbyt trudne, ale nie byłem w stanie znaleźć rozwiązania. Mam nadzieję, że ktoś może pomóc? Wszelkie strony będą mile widziane.

Będziesz musiał nieco ulepszyć algorytm, aby obliczyć kąt - obecnie rejestrujesz tylko bezwzględną różnicę pozycji, ale potrzebujesz różnicy względnej (tzn. Może być dodatnia lub ujemna w zależności od pozycjonowania).

int dx = T.X - S.X; // difference in position
int dy = T.Y - S.Y;

if (dx > MapX / 2) // if distance is bigger than half map width, then looping must be closer
    dx = (dx - MapX) * -1; // reduce distance by map width, reverse 
else if (dx < -MapX / 2) // handle the case that dx is negative
    dx = (dx + MapX) * -1;

//Do the same for dy
if (dy > MapY / 2)
    dy = (dy - MapY) * -1;
else if (dy < -MapY / 2)
    dy = (dy + MapY) * -1;

double dist = sqrt(dy*dy+dx*dx); // same as before
double angle = atan2(dy,dx) * 180 / PI; // provides angle in degrees

W takim świecie istnieje nieskończona liczba ścieżek od S do T. Oznaczmy współrzędne T przez (Tx, Ty), współrzędne S przez (Sx, Sy)i wielkość świata według (Wx, Wy). Zawinięte współrzędne T są (Tx + i * Wx, Ty + j * Wy), gdzie ii jsą liczbami całkowitymi, to znaczy elementami zestawu {..., -2, -1, 0, 1, 2, ...}. Wektory łączące S z T to (Dx, Dy) := (Tx + i * Wx - Sx, Ty + j * Wy - Sy). Dla danej (i, j)pary odległość jest długością wektora sqrt(Dx * Dx + Dy * Dy), a kierunek w radianach to atan(Dy / Dx). Najkrótszej ścieżki jest jednym z tych, w których ścieżki 9 ii jsą w {-1, 0, 1}:

Wartości ii jdla najkrótszej ścieżki można określić bezpośrednio:

int i = Sx - Tx > Wx / 2 ? 1 : Sx - Tx < -Wx / 2 ? -1 : 0;
int j = Sy - Ty > Wy / 2 ? 1 : Sy - Ty < -Wy / 2 ? -1 : 0;

Dziękuję, @IlmariKaronen, @SamHocevar i @romkyns za pomoc!

Oblicz jeden możliwy wektor kierunku, nawet jeśli nie jest on najkrótszy, a następnie zawiń jego współrzędną X, aby znajdowała się w [-MapX/2,MapX/2]zakresie, i to samo dla Y:

int DirX = (T.X - S.X + 3 * MapX / 2) % MapX) - MapX / 2;
int DirY = (T.Y - S.Y + 3 * MapY / 2) % MapY) - MapY / 2;

To jest to! Otrzymujesz również odległość bez dalszych obliczeń:

double dist = sqrt((double)(DirX*DirX + DirY*DirY));

Sądzę, że jest na to wiele sposobów. Oto 2, o których mogę myśleć z góry:

# 1: Obsługuj skrzynki ręcznie

Jest dokładnie 10 przypadków, które mogą się zdarzyć:

• Jest na tej samej płytce co S
• Znajduje się w dowolnym z 8 sąsiadujących pól
• W ogóle go nie znaleziono.

Jednak dla każdej z otaczających płytek są to kombinacje różnych obliczeń dla komponentu odległości X lub Y. Ponieważ jest to skończona liczba przypadków, możesz po prostu ustalić, jak je obliczyć i znaleźć najkrótszą odległość między nimi wszystkimi.

Oto ilustracja 2 przypadków do znalezienia dx. Przypadek 1, gdzie Tjest na tym samym kafelku co S, dx jest po prostu S.x - T.x. Dla płytek po prawej dxstronie zostanie obliczony jako TileWidth - S.x + T.x.

               :         
               :  T    
               :         
:--------------:---------
:              :
:           S  :
:  |--------|--:--|
:dx=(S.x-T.x) dx=(TileWidth-S.x+T.x)
:  T           :
:              :
:--------------:

W ramach małej optymalizacji znajdź minimalną odległość przed pierwiastkiem kwadratowym. Następnie oszczędzasz do 7 sqrtpołączeń.

# 2: Wyodrębnij współrzędne

Jeśli potrzebujesz zrobić coś bardziej „płynnego” przestrzennie, na przykład algorytm znajdowania ścieżki, po prostu wyodrębnij współrzędne, aby algorytm znajdujący ścieżkę nawet nie zdawał sobie sprawy, że świat składa się z powtarzających się kafelków. Algorytm znajdowania ścieżki może teoretycznie iść w dowolnym kierunku w dowolnym kierunku (no cóż, będziesz ograniczony limitami liczbowymi, ale dostaniesz sens).

Dla prostego obliczania odległości nie zawracaj sobie tym głowy.

Nie przejmuj się „9 kierunkami”. Powodem jest to, że wśród tych 9 jest 5 zdegenerowanych przypadków: „prosto na północ”, „prosto na zachód”, „prosto na południe”, „prosto na wschód” i „identycznie”. Na przykład prosta północ jest zdegenerowana, ponieważ reprezentuje przypadek, w którym północno-zachodni i północny wschód łączą się i dają ten sam wynik.

Zatem masz 4 kierunki do obliczenia i możesz po prostu wybrać minimum.

Dzięki za wszystkie odpowiedzi na końcu użyłem Toomai pod redakcją Scotta Chamberlaina. Miałem też kilka zmian ze względu na fakt, że mój układ współrzędnych zaczyna się od y w lewym górnym rogu i rośnie wraz z ruchem w dół (zasadniczo odwrócony w porównaniu do normalnych współrzędnych wykresu dla y).

Wysłałem na wypadek, gdyby ktokolwiek znalazł tę stronę i miał ten sam system.

  int dx = T.X - S.X; // difference in position
int dy = S.Y - T.Y;

if (dx > MapX / 2) // if distance is bigger than half map width, then looping must be closer
    dx = (dx - (MapX / 2)) * -1; // reduce distance by half map width, reverse 
else if (dx < -MapX / 2) // handle the case that dx is negative
    dx = (dx + (MapX / 2)) * -1;

//Do the same for dy
if (dy > MapY / 2)
    dy = (MapY - dy)) * -1;
else if (dy < -MapY / 2)
    dy = (dy + MapY);

double angle = atan2(dy,dx) * 180 / PI; // provides angle in degrees

angle = 180 - angle; //convert to 360 deg