Estou tendo problemas para encontrar um termo de pesquisa específico para isso, mas como encontrar os possíveis movimentos em um jogo de estratégia baseado em turnos 2D (ou seja, FF: Tática, Emblema de Fogo, Guerras Avançadas).
Não estou pensando muito no terreno (ou mesmo na colisão) neste momento. Estou apenas imaginando qual algoritmo posso usar para descobrir que a entidade X pode mover 5 peças e atacar 2 peças mais distantes do que isso.
Eu sei que posso usar algo como Dijkstra para encontrar a distância entre dois pontos. Uma implementação possível é começar no local dos jogadores e depois se ramificar a partir daí até que a distância retornada por Dijkstra seja maior que a contagem de movimentos.
Apenas imaginando se alguém poderia me apontar na direção certa (ou seja, nome de algoritmos, técnica, artigos, etc.).
Respostas:
Eu acho que um Dijkstra limitado é exatamente o que você deseja usar. A maneira como Dijkstra encontra a distância entre dois pontos é mapeando a distância para cada nó de um nó de origem e, em seguida, 'seleciona' o caminho mais curto desse mapa de distância. Você deseja fazer praticamente o mesmo, exceto que deseja o gráfico do nó de distância criado como saída, em vez de um caminho para qualquer ponto específico.
A única modificação que você deseja fazer é ignorar o cálculo da distância dos nós que já excederam sua faixa máxima de movimento. Em seguida, você terá um gráfico de todos os nós para os quais a unidade pode se deslocar, além de uma borda, apenas recorte os nós que têm uma distância maior que a margem de movimento.
Viola.
Em outras palavras, praticamente o que você descreveu na sua pergunta é o que você precisa fazer. Ele também tem o benefício de poder usar a saída para encontrar o caminho, sem a necessidade de fazer cálculos adicionais.
fonte
A abordagem mais simples (e provavelmente a mais ingênua) em que posso pensar agora:
steps - 1
.steps - 1
ondesteps
seria o número da etapa do campo atual, a menos que o novo campo já tenha um número mais alto.fonte
Eu acho que o que você está procurando pode ser a distância de Manhattan . Assumindo que não há obstáculos, você pode dizer que um quadrado é alcançável simplesmente se:
| paraX-deX | + | paraY-deY | <maxMoveDistance
Esse algoritmo pode não ser a direção certa a seguir se você tiver obstáculos mais tarde; uma maneira possível de adaptá-lo pode envolver fazer com que os obstáculos projetem 'sombras' e reavaliar a partir do ponto mais próximo.
EDIT (porque eu tenho um pouco mais de tempo livre agora):
Por 'sombras', quero dizer algo assim, se 0 é um quadrado acessível, C é o personagem e X é um obstáculo:
Como (5, 2) é um obstáculo, você começa assumindo que não pode chegar a nada com x> = 5 AND y <= 2. Você pode recalcular a partir de outro quadrado; se você quiser ir para (5, 1), pode calcular a distância de manhattan de (4, 1) e ver se essa + a distância do personagem a (4, 1) é menor que a distância de movimento do jogador.
Este é um exemplo bastante trivial, mas se você tiver vários obstáculos e / ou um pouco mais de amplitude de movimento, ele poderá lidar com a complexidade.
Se realmente seria melhor do que apenas o preenchimento de inundações, seja na complexidade da programação ou na eficiência da execução, não tenho idéia. Pareceu uma maneira mais interessante de resolver o problema.
fonte