Como encontrar a direção da viagem em um mundo com bordas enroladas

20

Preciso encontrar a direção da distância mais curta de um ponto no meu mundo 2D para outro ponto em que as bordas estão envolvidas (como asteróides etc.). Eu sei como encontrar a menor distância, mas estou lutando para encontrar em que direção está.

A menor distância é dada por:

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

Exemplo do mundo

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

No diagrama, as arestas são mostradas com: e -. Também mostrei uma repetição do mundo no canto superior direito. Quero encontrar a direção em graus de S a T. Portanto, a distância mais curta é a repetição no canto superior direito de T. mas como faço para calcular a direção em graus de S para o T repetido no canto superior direito?

Conheço as posições de S e T, mas suponho que preciso encontrar a posição do T repetido, porém há mais de 1.

O sistema de coordenadas do mundo começa em 0,0 no canto superior esquerdo e 0 graus para a direção pode começar no oeste.

Parece que isso não deve ser muito difícil, mas não consegui encontrar uma solução. Espero que alguém possa ajudar? Qualquer site seria apreciado.

louco
fonte
Quais são as coordenadas para o T no canto superior direito?
Eu nunca vi um jogo com quebra diagonal. Geralmente você tem um envoltório para cada direção (N, E, S, W).
5
Qualquer jogo com quebra horizontal e vertical tem quebra diagonal por padrão.
Pense em cada coordenada como vivendo em um círculo e calcule a menor das duas distâncias possíveis para cada coordenada individualmente.
Kerrek SB
11
@crazy: olhar para cima "toro" na Wikipedia ...
Kerrek SB

Respostas:

8

Você precisará ajustar um pouco o algoritmo para calcular o ângulo - atualmente, você só registra a diferença absoluta na posição, mas precisa da diferença relativa (ou seja, pode ser positiva ou negativa, dependendo do posicionamento).

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
fonte
11
Você precisa de algum trabalho sobre os sinais de dx e dy, pois o código atual será quebrado se TX for menor que SX ou TY for menor que XY. Fora isso, essa é a melhor solução IMHO.
Scott Chamberlain
Nesse momento eu vou consertar isso.
11
Ainda tenho alguns erros sobre qual será o sinal de dx e dy quando tudo estiver dito e feito, importa se eu editar?
Scott Chamberlain
Por que essa é a resposta aceita? Nem funciona . Suponha que MapXé 100, T.Xé 90 e S.Xé 10. dxdeve ser claramente 20, mas esse algoritmo retornará 30!
21411 Samurai Hocevar
É isso que acontece quando você não precisa testar o código antes de publicá-lo. Fixará. Se alguém encontrar outro erro com isso, provavelmente o excluirei antes que muitas pessoas sejam enganadas.
Toomai
11

Nesse mundo, há um número infinito de caminhos de S a T. Vamos denotar as coordenadas de T por(Tx, Ty) , as coordenadas de S por (Sx, Sy)e o tamanho do mundo por (Wx, Wy). As coordenadas agrupadas de T são (Tx + i * Wx, Ty + j * Wy), onde ie jsão números inteiros, isto é, elementos do conjunto {..., -2, -1, 0, 1, 2, ...}. Os vetores que conectam S a T são (Dx, Dy) := (Tx + i * Wx - Sx, Ty + j * Wy - Sy). Para um determinado (i, j)par, a distância é o comprimento do vetor sqrt(Dx * Dx + Dy * Dy)e a direção em radianos é atan(Dy / Dx). O caminho mais curto é um dos 9 caminhos, onde ie jestão {-1, 0, 1}: insira a descrição da imagem aqui

Os valores ie jpara o caminho mais curto podem ser determinados diretamente:

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;

Obrigado, @IlmariKaronen, @SamHocevar e @romkyns por sua ajuda!

Comunidade
fonte
11
Você pode fazer melhor que isso: se abs(Tx-Sx) < Wx/2, então i=0é ideal; caso contrário, a escolha ideal é i=-1ou i=1, dependendo do sinal de Tx-Sx. O mesmo vale para Ty-Sye j.
Ilmari Karonen
11
Esta resposta é incrivelmente complicada para um problema tão simples. Não há necessidade de usar a pesquisa linear quando o valor mínimo pode ser calculado diretamente.
21711 Samurai Hocevar
Boa foto, mas o algoritmo sugerido não merece nenhum dos votos positivos que esta resposta recebeu.
RomanSt
5

Calcule um vetor de direção possível, mesmo que não seja o menor, depois envolva sua coordenada X para que fique no [-MapX/2,MapX/2]intervalo e o mesmo para 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;

É isso aí! Você também obtém a distância sem cálculos adicionais:

double dist = sqrt((double)(DirX*DirX + DirY*DirY));
sam hocevar
fonte
Obrigado! Versão do GLSL:vec2 toroidalNearestWay (vec2 from, vec2 to, vec2 mapSize) { return (mod((to - from + 3.0 * mapSize / 2.0), mapSize)) - mapSize / 2.0; }
1j01 04/07/2018
0

Eu acho que existem várias maneiras de fazer isso. Aqui estão 2 que eu consigo pensar em cima da minha cabeça:

# 1: Manipular casos manualmente

Existem exatamente 10 casos que podem acontecer:

  • Está no mesmo bloco que S
  • Está em qualquer um dos 8 azulejos ao redor
  • Não foi encontrado.

Porém, para cada um dos ladrilhos circundantes, são permutações de cálculos diferentes para o componente de distância X ou Y. Por ser um número finito de casos, você pode apenas codificar como calculá-los e encontrar a menor distância entre todos eles.

Aqui está uma ilustração de 2 casos para encontrar dx. Caso 1, onde Testá no mesmo bloco que S, dx é justo S.x - T.x. Para os ladrilhos à direita, dxserá calculado como TileWidth - S.x + T.x.

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

Como uma pequena otimização, encontre a distância mínima antes de obter uma raiz quadrada. Então você economiza até 7 sqrtchamadas.

# 2: Abstraia as coordenadas

Se você precisar fazer algo mais "espacial" espacialmente, como um algoritmo de localização de caminhos, basta abstrair as coordenadas para que o algoritmo de localização de caminhos nem perceba que o mundo é feito de blocos repetitivos. O algoritmo de localização de caminho pode ir infinitamente em qualquer direção teoricamente (ok, bem, você será limitado por limites numéricos, mas você entendeu).

Para um cálculo simples da distância, não se preocupe em fazer isso.

dez quatro
fonte
Idéia inteligente sobre a comparação do valor da distância ao quadrado antes de tomar o sqrt!
Scott Chamberlain
Ah eu vejo, @Kol tem uma resposta semelhante com uma explicação mais matemática, graças isso me dá algo para trabalhar
Comparar a distância ao quadrado pode ser mais inteligente do que usar o sqrt, mas usar a distância de Manhattan é ainda mais inteligente, pois não requer multiplicação.
Sam Hocevar
0

Não se preocupe com as "9 direções". A razão é que existem 5 casos degenerados entre os 9: "norte reto", "oeste reto", "sul reto", "leste reto" e "idêntico". Por exemplo, o norte direto é degenerado porque representa o caso em que o noroeste e o nordeste se unem e produzem o mesmo resultado.

Assim, você tem quatro direções para calcular e pode escolher apenas o mínimo.

MSalters
fonte
Eu não acho que isso esteja certo, ou eu o entendi completamente. Um dos dois
-1

Obrigado por todas as respostas no final, usei Toomai editado por Scott Chamberlain. Eu também fiz algumas alterações devido ao fato de que meu sistema de coordenadas começa com y no canto superior esquerdo e aumenta à medida que você desce (basicamente invertido em comparação com as coordenadas normais do gráfico para y).

Publiquei caso alguém encontre essa página e tenha o mesmo sistema invertido.

  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
louco
fonte
Este código é um pouco melhor que o de Toomai, mas também não funciona.
21411 Samurai Hocevar
11
Além disso, você precisa entender por que você fez essas alterações. É não porque o seu coordenar começa sistema com yno topo. É porque o comportamento desejado supostamente envolve as coordenadas na borda do mundo, enquanto o código que você reutilizou espelhava as coordenadas em cada limite.
111311 Sam_Hocevar