Encontrar o caminho mais curto em uma grade hexagonal

14

Estou escrevendo um jogo baseado em turnos que tem alguns elementos de simulação. Uma tarefa em que estou desligado atualmente é encontrar o caminho. O que eu quero fazer é mover a cada turno um aventureiro de IA um bloco para mais perto de seu alvo usando seu x, y atual e seu alvo x, y.

Ao tentar descobrir isso sozinho, posso determinar 4 direções sem problemas usando

dx = currentX - targetY
dy = currentY - targetY

mas não sei como determinar qual das seis direções é realmente a rota "melhor" ou "mais curta".

Por exemplo, da maneira como está configurada atualmente, eu uso Leste, Oeste, NE, NW, SE, SW, mas para chegar ao bloco NE, movo para leste e depois para NW, em vez de apenas para NW.

Espero que nem tudo tenha sido divagado. Mesmo apenas um ou dois links para começar, seria bom. A maioria das informações que encontrei é sobre o desenho de grades e o esquisito sistema de coordenadas necessário.

Timothy Mayes
fonte
5
A * dá-lhe caminho mais curto, independentemente da forma de seu gráfico (grade, hex, de forma livre ..)
Jari Komppa

Respostas:

21

Algumas respostas!

O sistema de coordenadas que eu tenho visto com mais frequência em travessias baseadas em hexadecimal é aquele em que o jogador pode se mover em todas as direções NSEW normais, assim como NW e SE. Então você apenas renderiza cada linha de deslocamento de meio quadrado. Como exemplo, o local (2,7) é considerado adjacente a (1,7), (3,7), (2,6), (2,8) e os estranhos: (1,6) e (3,8) Enquanto isso, se assumirmos que (2,7) é renderizado no centro da tela, (2,6) será renderizado para cima e para a direita, (2,8) será renderizado para baixo e para -a-esquerda, (1,7) e (3,7) irá colocá-lo à esquerda e à direita, respectivamente, e (1,6) e (3,8) se colocarão no canto superior esquerdo e no canto inferior direito, respectivamente.

Um diagrama do que quero dizer:

insira a descrição da imagem aqui

Se você está fazendo isso dessa maneira, não é difícil encontrar o caminho direto mais curto - percorra a distância NW / SE máxima possível sem ultrapassar seu alvo ao longo de um eixo cardinal e, em seguida, viaje diretamente ao longo desse eixo até o alvo.

Mas é claro que isso o levará felizmente através de montanhas ou outro terreno intransitável. Para responder a uma pergunta que você ainda não fez: O algoritmo A * Search é uma abordagem comum e razoavelmente boa para a busca de caminhos. Ele lidará não apenas com layouts estranhos que não sejam da grade, mas lidará felizmente com obstáculos e até com terreno obstruído / lento.

ZorbaTHut
fonte
Obrigado pelo link para o algoritmo de pesquisa A *. A única maneira que eu posso imaginar ser capaz de atravessar nsew e nw / se é um hexágono inclinado. O que parece estranho na minha cabeça. Você pode me vincular a um exemplo disso?
Timothy Mayes
4
Estou dizendo que sua imagem renderizada não tem muita semelhança com a estrutura interna. Estou sugerindo que internamente você use NSEW e NW / SE, mas você o exibe para o usuário como se fosse uma grade. Colocar um diagrama explicativo para a resposta inicial :)
ZorbaTHut
2
Representação interessante para uma grade hexadecimal. Eu costumo fazer um padrão irregular, então a adjacência é diferente para linhas pares e ímpares. Isto introduz uma complexidade adicional mínimo no caminho de procura, mas usa uma matriz bidimensional de forma mais eficiente (supondo que toda a área de jogo é um retângulo.
Panda Pajama
2
@PandaPajama: irregular funciona melhor para armazenar mapas retangulares com eficiência; você pode fazer as coordenadas não-irregulares trabalhar bem com este truque
amitp
2
@PandaPajama, há outro truque interessante que você pode usar - você pode usar a representação não irregular para coordenadas e depois abstrair o suporte para o armazenamento de dados atrás de algo que use o método "irregular". Eu encontrei o sistema de coordenadas de não recortada é muito mais fácil de lidar, mas é claro que uma vez que é abstraída, o backend pode fazer o que gosta de fazer coisas eficiente :)
ZorbaTHut
5

Acabei de publicar uma biblioteca de utilitários de grade hexadecimal no CodePlex.com aqui: https://hexgridutilities.codeplex.com/ A biblioteca inclui localização de caminhos (usando A- * a Eric Lippert) e inclui utilitários para conversão automatizada entre cordadas irregulares (denominadas Usuário) e coordenadas não irregulares (denominadas Canonical). O algoritmo de localização de caminho permite que o custo da etapa para cada nó varie tanto com a entrada hexadecimal quanto com o lado hexagonal percorrido te (embora o exemplo fornecido seja mais simples). Além disso, é fornecido um campo de visão elevado usando projeção de sombras, [editar: palavras removidas].

Aqui está um exemplo de código que converte prontamente entre três sistemas de coordenadas de grade hexadecimal:

static readonly IntMatrix2D MatrixUserToCanon = new IntMatrix2D(2,1, 0,2, 0,0, 2);
IntVector2D VectorCanon {
  get { return !isCanonNull ? vectorCanon : VectorUser * MatrixUserToCanon / 2; }
  set { vectorCanon = value;  isUserNull = isCustomNull = true; }
} IntVector2D vectorCanon;
bool isCanonNull;

static readonly IntMatrix2D MatrixCanonToUser  = new IntMatrix2D(2,-1, 0,2, 0,1, 2);    
IntVector2D VectorUser {
  get { return !isUserNull  ? vectorUser 
             : !isCanonNull ? VectorCanon  * MatrixCanonToUser / 2
                            : VectorCustom * MatrixCustomToUser / 2; }
  set { vectorUser  = value;  isCustomNull = isCanonNull = true; }
} IntVector2D vectorUser;
bool isUserNull;

static IntMatrix2D MatrixCustomToUser = new IntMatrix2D(2,0, 0,-2, 0,(2*Height)-1, 2);
static IntMatrix2D MatrixUserToCustom = new IntMatrix2D(2,0, 0,-2, 0,(2*Height)-1, 2);
IntVector2D VectorCustom {
  get { return !isCustomNull ? vectorCustom : VectorUser * MatrixUserToCustom / 2; }
  set { vectorCustom  = value;  isCanonNull = isUserNull = true; }
} IntVector2D vectorCustom;
bool isCustomNull;

IntMatrix2D e IntVector2D são implementações inteiras [edit: homogêneas] de affine2D Graphics Vector and Matrix. A divisão final por 2 nas aplicações vetoriais é normalizar novamente os vetores; isso pode estar oculto na implementação do IntMatrix2D, mas a razão do sétimo argumento para os construtores do IntMatrix2D é menos óbvia. Observe o cache combinado e a avaliação lenta de formulações não atuais.

Essas matrizes são para o caso:

  • Grão hexagonal vertical;
  • Origem no canto superior esquerdo para coordenadas canônicas e de usuário, e no canto inferior esquerdo para coordenadas personalizadas;
  • Eixo Y verticalmente para baixo;
  • Eixo X retangular horizontalmente; e
  • Eixo X canônico para o nordeste (ou seja, para cima e para a direita, a 120 graus CCW do eixo Y).

A biblioteca de códigos mencionada acima fornece um mecanismo igualmente elegante para seleção hexadecimal (ou seja, identificar o hex selecionado com um clique do mouse).

Nas coordenadas canônicas, os 6 vetores de direção cardinais são (1,0), (0,1), (1,1) e seus inversos para todos os hexágonos, sem a assimetria de coordenadas irregulares.

Pieter Geerkens
fonte
Uau! Faça um voto negativo pela publicação de uma biblioteca de códigos de trabalho, com exemplos e documentação, que responda à pergunta / problema colocado pelo OP.
Pieter Geerkens
5
Embora eu não tenha sido a favor do voto negativo (e a etiqueta geralmente sugere deixar um comentário explicando o voto negativo), suspeito que o voto negativo foi porque (a) a publicação sai soando como publicidade e (b) colocando a maior parte da resposta na outra O lado de um link geralmente é desaprovado, porque os links tendem a apodrecer e os sites SE tentam ser independentes. As informações fornecidas aqui são interessantes, mas não respondem à pergunta do usuário , e as únicas informações que podem responder à pergunta estão do outro lado do link.
Steven Stadnicki
Bons pontos; obrigado. Expandi o post com trechos que abordam a questão de como manter eficientemente várias coordenadas de grade hexadecimal. A biblioteca de código postado é freeware
Pieter Geerkens
Opa! A divisão por 2 funciona apenas para números inteiros positivos. (Obrigado novamente, K&R.) Ele deve ser substituído por uma chamada para o método Normalize () no IntVector2D:
Pieter Geerkens
public IntVector2D Normalize() { if (Z==1) return this; else { var x = (X >= 0) ? X : X - Z; var y = (Y >= 0) ? Y : Y - Z; return new IntVector2D(x/Z, y/Z); } }
Pieter Geerkens
0

Este é um problema resolvido, com muita literatura para apoiá-lo. O melhor recurso que conheço é o Red Blob Games: https://www.redblobgames.com/grids/hexagons/ .

Em resumo, o motivo mais provável é que você começou com o sistema de coordenadas errado. O uso de um sistema de coordenadas Cube implementando o algoritmo A * é bastante simples. Veja demonstração ao vivo no link acima.

Se você realmente deseja usar outro sistema, converta para e quando necessário.

david.pfx
fonte