Encontrar movimentos possíveis para uma entidade em um jogo 2D lado a lado

10

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

insira a descrição da imagem aqui

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

NRaf
fonte
Estou pensando que é chamado de localização de caminho, para um termo de pesquisa? Se você usar descoberta caminho, então você poderia ter contadores para lidar com o que você precisa
Exikle
Isso é essencialmente parte da localização do caminho (cálculo de metadados para custos de movimentação). Você determina apenas os locais que estão dentro do alcance, mas também não determina necessariamente a rota que você seguiria.
Mario
1
Não é em tempo real (RTS) se for baseado em turnos à la FFTactics. : p
Alayric 9/09
Em 2D, você poderia usar o cálculo do Taxicab / Manhattan en.wikipedia.org/wiki/Taxicab_geometry
Gerben Jacobs 11/13/13

Respostas:

5

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.

TASagent
fonte
Eu acho que o Dijkstra é um exagero neste caso. O OP não precisa de um caminho para todos os destinos possíveis de movimento, apenas uma resposta sim / não para saber se um agente pode chegar lá. Ele pode calcular um caminho mais tarde depois que o usuário escolher um.
Michael Kristofik
O custo de usar o algoritmo de Dijkstra para calcular o caminho após a decisão de um destino é quase exatamente o mesmo que usá-lo antecipadamente (a menos que você use uma abordagem heurística como A * para percorrer). Não fazer isso com antecedência simplesmente cria um trabalho redundante, pois Dijkstra responderia às perguntas 'para onde posso ir' e 'como chego lá?'. Ele também permite a adição de complicações ao ambiente que alteram o custo do movimento, embora isso possa ser desnecessário para a aplicação. Além disso, a abordagem está bem documentada, o que é útil para o implementador.
TASagent 9/09/13
1
Ao examinar a resposta de Mario, ele realmente descreve o algoritmo de Dijkstra, exceto que ele inverte a distância e não menciona que é Dijkstra.
TASagent 9/09/13
1
Não diria que é Dijkstra, porque você realmente não está procurando uma rota mais curta nem está tentando chegar a um ponto específico. É essencialmente a primeira parte do algoritmo de Dijkstra, embora seja verdade. O problema com sua redação, usando Dijkstra, pode ser enganador e acho que isso também confundiu Michael. Ele provavelmente pensou que você sugeriu o uso do Dijkstra uma vez para cada campo / célula.
Mario
1
Acabar usando essa abordagem, pois funcionou bem e é muito fácil de estender para lidar com obstáculos.
NRaf
12

A abordagem mais simples (e provavelmente a mais ingênua) em que posso pensar agora:

  • Comece com o seu personagem e marque todos os campos ao redor como steps - 1.
  • Faça uma iteração sobre todos os campos recém-marcados e marque novamente os campos adjacentes como steps - 1onde stepsseria o número da etapa do campo atual, a menos que o novo campo já tenha um número mais alto.
  • Repita a última etapa até ficar sem etapas.
Mario
fonte
1
Este algoritmo tem um nome: Flood Fill .
Michael Kristofik
6
@ MichaelKristofik: Eu chamaria isso de primeira pesquisa de largura . O preenchimento de inundação não controla distâncias.
BlueRaja - Danny Pflughoeft 9/09/13
2

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:

 012345678
0    0
1   00
2  000X
3 000C000
4  00000
5   000
6    0
 012345678

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.

Homem de Lata
fonte
O que você quer dizer com projetar sombras?
NRaf
1
Editado para esclarecimentos.
Homem de Lata