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


20

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.


Jakie są współrzędne T w prawym górnym rogu?

Nigdy nie widziałem gry z zawijaniem po przekątnej. Zwykle masz po jednym owinięciu dla każdego kierunku (N, E, S, W).

5
Każda gra z zawijaniem poziomym i pionowym ma domyślnie zawijanie po przekątnej.

Pomyśl o każdej współrzędnej jako żyjącej w kręgu i ustal indywidualnie dwie możliwe odległości dla każdej współrzędnej.
Kerrek SB

1
@crazy: Wyszukaj „torus” na Wikipedii ...
Kerrek SB 15.11

Odpowiedzi:


8

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

1
Potrzebujesz trochę pracy nad znakami dx i dy, ponieważ kod, jak się zepsuje, jeśli TX jest mniejszy niż SX lub TY jest mniejszy niż XY Poza tym jest to najlepsze rozwiązanie IMHO.
Scott Chamberlain

Właśnie wtedy to naprawię.

1
Wciąż pojawia się kilka błędów dotyczących znaku dx i dy, gdy wszystko zostanie powiedziane i zrobione, czy mogę edytować?
Scott Chamberlain,

Dlaczego jest to akceptowana odpowiedź? To nawet nie działa . Załóżmy, że MapXjest to 100, T.Xto 90 i S.Xto 10. dxpowinno być wyraźnie 20, ale ten algorytm zwróci 30!
sam hocevar

Ugh właśnie tak się dzieje, kiedy nie musisz testować kodu przed opublikowaniem go. Naprawię. Jeśli ktoś znajdzie z tym kolejny błąd, prawdopodobnie po prostu go usunę, zanim zbyt wielu ludzi będzie wprowadzać w błąd.
Toomai

11

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}: wprowadź opis zdjęcia tutaj

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!


1
Możesz zrobić coś więcej: jeśli abs(Tx-Sx) < Wx/2, to i=0jest optymalne; w przeciwnym razie optymalnym wyborem jest i=-1lub i=1, w zależności od znaku Tx-Sx. To samo dotyczy Ty-Syi j.
Ilmari Karonen

1
Ta odpowiedź jest niezwykle skomplikowana w przypadku tak prostego problemu. Nie ma potrzeby korzystania z wyszukiwania liniowego, gdy minimalną wartość można obliczyć bezpośrednio.
sam hocevar,

Fajne zdjęcie, ale sugerowany algorytm nie zasługuje na żadne opinie, które otrzymała ta odpowiedź.
RomanSt

5

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));

Dzięki! Wersja GLSL:vec2 toroidalNearestWay (vec2 from, vec2 to, vec2 mapSize) { return (mod((to - from + 3.0 * mapSize / 2.0), mapSize)) - mapSize / 2.0; }
1j01

0

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.


Sprytny pomysł na porównanie kwadratowej wartości odległości przed podjęciem sqrt!
Scott Chamberlain,

Ach, rozumiem, @Kol ma podobną odpowiedź z bardziej matematycznym wyjaśnieniem, dzięki czemu daje mi to coś do pracy

Porównanie kwadratowej odległości może być mądrzejsze niż pobranie sqrt, ale korzystanie z odległości Manhattan jest jeszcze mądrzejsze, ponieważ nie wymaga w ogóle mnożenia.
sam hocevar

0

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.


Nie sądzę, że to prawda, lub całkowicie cię źle zrozumiałem. Jeden z dwóch.

-1

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

Ten kod jest nieco lepszy niż Toomai, ale też nie działa.
sam hocevar

1
Musisz także zrozumieć, dlaczego musiałeś wprowadzić te zmiany. To nie z powodu swojej koordynować uruchomienia systemu z yna szczycie. Jest tak, ponieważ pożądane zachowanie ma zawijać współrzędne na krawędzi świata, podczas gdy ponownie użyty kod odzwierciedlał współrzędne na każdej granicy.
sam hocevar
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.