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.
fonte
Respostas:
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:
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.
fonte
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:
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:
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.
fonte
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); } }
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.
fonte