Die Fahrtrichtung in einer Welt mit umwickelten Rändern finden

20

Ich muss die kürzeste Entfernungsrichtung von einem Punkt in meiner 2D-Welt zu einem anderen Punkt finden, an dem die Kanten gewickelt sind (wie Asteroiden usw.). Ich weiß, wie man die kürzeste Entfernung findet, aber ich habe Mühe herauszufinden, in welche Richtung es geht.

Die kürzeste Entfernung ergibt sich aus:

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

Beispiel der Welt

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

Im Diagramm sind die Kanten mit: und - dargestellt. Ich habe oben rechts auch eine verpackte Wiederholung der Welt gezeigt. Ich möchte die Richtung in Grad von S nach T finden. Der kürzeste Abstand ist also die Wiederholung von T oben rechts. Aber wie berechne ich die Richtung in Grad von S nach der Wiederholung von T oben rechts?

Ich kenne die Positionen von S und T, aber ich nehme an, ich muss die Position des wiederholten T finden, aber dort mehr als 1.

Das Weltkoordinatensystem beginnt bei 0,0 oben links und 0 Grad für die Richtung könnten bei West beginnen.

Es scheint, dass dies nicht zu schwierig sein sollte, aber ich konnte keine Lösung finden. Ich hoffe jemand kann helfen? Alle Websites würden geschätzt.

verrückt
quelle
Was sind die Koordinaten für das T oben rechts?
Ich habe noch nie ein Spiel mit Diagonalverpackung gesehen. Normalerweise haben Sie eine Umschlingung für jede Richtung (N, E, S, W).
5
Jedes Spiel mit horizontaler und vertikaler Umrandung hat standardmäßig eine diagonale Umrandung.
Stellen Sie sich jede Koordinate als Kreis vor und ermitteln Sie für jede Koordinate einzeln den kürzeren der beiden möglichen Abstände.
Kerrek SB
1
@ Crazy: Nachschlagen "Torus" auf Wikipedia ...
Kerrek SB

Antworten:

8

Sie müssen Ihren Algorithmus ein wenig optimieren, um den Winkel zu berechnen. Derzeit erfassen Sie nur den absoluten Positionsunterschied, aber Sie benötigen den relativen Unterschied (dh er kann je nach Positionierung positiv oder negativ sein).

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
Toomai
quelle
1
Sie müssen etwas an den Vorzeichen von dx und dy arbeiten, da der Code so wie er ist kaputt geht, wenn TX kleiner als SX oder TY kleiner als XY ist. Abgesehen davon ist dies meiner Meinung nach die beste Lösung.
Scott Chamberlain
Genau dann werde ich das beheben.
1
Haben Sie noch ein paar Fehler bezüglich des Vorzeichens von dx und dy, wenn alles gesagt und getan ist?
Scott Chamberlain
Warum ist das die akzeptierte Antwort? Es funktioniert nicht einmal . Angenommen, MapX100, T.X90 und S.X10. dxsollten eindeutig 20 sein, aber dieser Algorithmus gibt 30 zurück!
Sam Hocevar
Ugh das ist, was passiert, wenn Sie nicht Gelegenheit haben, Code zu testen, bevor Sie ihn veröffentlichen. Wird reparieren. Wenn jemand einen anderen Fehler findet, werde ich ihn wahrscheinlich einfach löschen, bevor zu viele Leute irregeführt werden.
Toomai
11

In einer solchen Welt gibt es unendlich viele Wege von S nach T. Wir bezeichnen die Koordinaten von T by (Tx, Ty), die Koordinaten von S by (Sx, Sy)und die Größe der Welt by (Wx, Wy). Die umbrochenen Koordinaten von T sind (Tx + i * Wx, Ty + j * Wy), wo iund jsind ganze Zahlen, das heißt, Elemente der Menge {..., -2, -1, 0, 1, 2, ...}. Die Vektoren, die S mit T verbinden, sind (Dx, Dy) := (Tx + i * Wx - Sx, Ty + j * Wy - Sy). Für ein bestimmtes (i, j)Paar ist der Abstand die Länge des Vektors sqrt(Dx * Dx + Dy * Dy)und die Richtung im Bogenmaß atan(Dy / Dx). Der kürzeste Weg ist einer der 9 Wege, auf denen iund jin denen {-1, 0, 1}: Bildbeschreibung hier eingeben

Die iund jWerte für den kürzesten Weg können direkt ermittelt werden:

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;

Vielen Dank, @IlmariKaronen, @SamHocevar und @romkyns für Ihre Hilfe!

Gemeinschaft
quelle
1
Sie können es besser machen: wenn abs(Tx-Sx) < Wx/2, dann i=0ist es optimal; ansonsten ist die optimale Wahl i=-1oder i=1, je nach Vorzeichen Tx-Sx. Gleiches gilt für Ty-Syund j.
Ilmari Karonen
1
Diese Antwort ist für ein so einfaches Problem unglaublich kompliziert. Es ist keine lineare Suche erforderlich, wenn der Minimalwert direkt berechnet werden kann.
Sam Hocevar
Nettes Bild, aber der vorgeschlagene Algorithmus verdient keine der Upvotes, die diese Antwort erhalten hat.
RomanSt
5

Berechnen Sie einen möglichen Richtungsvektor, auch wenn er nicht der kürzeste ist, und wickeln Sie seine X-Koordinate so um, dass er sich im [-MapX/2,MapX/2]Bereich befindet. Dies gilt auch für 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;

Das ist es! Sie erhalten die Entfernung auch ohne weitere Berechnungen:

double dist = sqrt((double)(DirX*DirX + DirY*DirY));
sam hocevar
quelle
Vielen Dank! GLSL Version:vec2 toroidalNearestWay (vec2 from, vec2 to, vec2 mapSize) { return (mod((to - from + 3.0 * mapSize / 2.0), mapSize)) - mapSize / 2.0; }
1j01
0

Ich denke, es gibt eine Reihe von Möglichkeiten, dies zu tun. Hier sind 2, die mir auf den ersten Blick einfallen:

# 1: Fälle manuell behandeln

Es gibt genau 10 Fälle, die auftreten können:

  • Es ist in der gleichen Fliese wie S
  • Es ist in einem der 8 umliegenden Kacheln
  • Es ist überhaupt nicht gefunden.

Für jede der umgebenden Kacheln handelt es sich jedoch um Permutationen verschiedener Berechnungen für die X- oder Y-Entfernungskomponente. Da es sich nur um eine begrenzte Anzahl von Fällen handelt, können Sie die Berechnung der Fälle einfach fest programmieren und den kürzesten Abstand zwischen allen Fällen ermitteln.

Hier ist eine Illustration von 2 Fällen zum Auffinden dx. Fall 1, Tin dem sich die gleiche Kachel wie befindet S, ist dx gerecht S.x - T.x. Für die Kacheln rechts dxwird berechnet als TileWidth - S.x + T.x.

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

Bestimmen Sie als kleine Optimierung den Mindestabstand, bevor Sie eine Quadratwurzel ziehen. Dann sparen Sie sich bis zu 7 sqrtAnrufe.

# 2: Zählen Sie die Koordinaten auf

Wenn Sie räumlich etwas "Fließenderes" tun möchten, wie einen Pfadfindungsalgorithmus, abstrahieren Sie einfach die Koordinaten, damit Ihr Pfadfindungsalgorithmus nicht einmal erkennt, dass die Welt aus sich wiederholenden Kacheln besteht. Der Pfadfindungsalgorithmus könnte theoretisch unendlich in jede Richtung gehen (ok, Sie werden durch numerische Grenzen begrenzt sein, aber Sie verstehen den Punkt).

Machen Sie sich für eine einfache Entfernungsberechnung nicht die Mühe.

zehn vier
quelle
Intelligente Idee zum Vergleichen des quadratischen Abstandswerts vor der Aufnahme des sqrt!
Scott Chamberlain
Ah, ich verstehe, @Kol hat eine ähnliche Antwort mit einer mathematischeren Erklärung, danke, das gibt mir etwas zum Arbeiten
Der Vergleich der quadratischen Distanz ist vielleicht klüger als der Vergleich der quadratischen Distanz, aber die Verwendung der Manhattan-Distanz ist noch klüger, da sie überhaupt keine Multiplikation erfordert.
Sam Hocevar
0

Kümmere dich nicht um die "9 Richtungen". Der Grund ist, dass es 5 entartete Fälle unter diesen 9 gibt: "gerader Norden", "gerader Westen", "gerader Süden", "gerader Osten" und "identisch". Zum Beispiel ist der gerade Norden degeneriert, weil Nordwesten und Nordosten sich vereinigen und dasselbe Ergebnis erzielen.

Sie müssen also 4 Richtungen berechnen und können einfach das Minimum auswählen.

MSalters
quelle
Ich glaube nicht, dass das richtig ist, oder ich habe dich völlig missverstanden. Einer der Beiden.
-1

Vielen Dank für all die Antworten, die ich am Ende mit Toomai von Scott Chamberlain erhalten habe. Ich musste auch ein paar Änderungen vornehmen, da mein Koordinatensystem oben links mit y beginnt und sich erhöht, wenn Sie sich nach unten bewegen (im Vergleich zu normalen Diagrammkoordinaten für y grundsätzlich invertiert).

Ich habe geschrieben, falls jemand diese Seite findet und dasselbe umgekehrte System hat.

  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
verrückt
quelle
Dieser Code ist etwas besser als der von Toomai, funktioniert aber auch nicht.
Sam Hocevar
1
Außerdem müssen Sie verstehen, warum Sie diese Änderungen vornehmen mussten. Es liegt nicht daran, dass Ihr Koordinatensystem oben beginnt y. Es ist , weil das gewünschte Verhalten angeblich wickeln Koordinaten auf der Welt Rand, während der Code , den Sie erneut verwendet werden gespiegelt die Koordinaten an jeder Grenze.
Sam Hocevar