Como determinar a amplitude de movimento possível no jogo de estratégia baseado em turnos e distância?

Estou criando um jogo de estratégia bidimensional baseado em turnos usando c ++ e SFML-2.0. O movimento é baseado na distância, e não na grade, com várias peças diferentes em forma de triângulo que, em um determinado turno, cada uma pode girar no lugar ou avançar.

O movimento funcionará de tal maneira que o jogador selecione um local para a peça mover, o que gera um caminho potencial para a peça seguir. Uma vez que o jogador confirme sua decisão, a peça se moverá ao longo desse caminho até o local desejado. Os caminhos são limitados por dois fatores: distância, a distância que uma peça pode percorrer, levando em consideração todas as curvas (portanto, se houver uma curva, será o comprimento ao longo da curva e não diretamente de um ponto a outro); e ângulo de direção, até que ponto a peça pode girar em qualquer ponto (e até todos) enquanto se move (por exemplo, de -30 a 30 graus).

Minha pergunta é: como devo determinar a variedade de locais em potencial que o jogador pode selecionar para mover a peça?

Não tenho muita certeza de quais equações e / ou algoritmos usar aqui. Meu plano original era extremamente complicado, a ponto de ser quase impossível de implementar, sem falar em explicar, e neste momento estou totalmente perdido com o projeto paralisado.

Como posso determinar o alcance que uma unidade pode mover, levando em consideração o raio de viragem?

Por exemplo, na imagem abaixo. As linhas vermelha, azul e verde teriam o mesmo comprimento. O círculo roxo indica a amplitude de movimento que a unidade pode mover. (O formato é provavelmente imprecisa e as linhas provavelmente não são realmente o mesmo comprimento, mas você começa a idéia)

Gere um campo de fluxo ou distância usando Dijsktra.

Essencialmente, preencha uma grade usando o algoritmo Dijkstra sem destino (provavelmente um nome diferente para isso; não sei). Apenas pegue cada nó aberto, calcule os vizinhos acessíveis, coloque-os na lista aberta, defina-os na lista fechada, atualize o caminho "próximo" do nó pai conforme apropriado, etc. Ao determinar o custo para alcançar um novo nó, considere as limitações de giro.

O resultado agora será que você possui uma rede de todos os seus nós sobre como voltar ao início. Os nós que não podem ser alcançados não serão tocados na primeira etapa. Os nós que podem ser alcançados terão um elemento "próximo nó ao longo do melhor caminho possível para o pai" calculado para que você possa destacar todos os nós e também usar essas informações para mostrar ou executar o caminho do movimento à medida que o usuário passa ou clica nas áreas destacadas.

Uma solução de força bruta seria:

1. Crie um círculo de vértices ao redor da unidade, com a unidade no centro. O raio do círculo é a distância máxima de movimento. A densidade dos vértices pode mudar dependendo de quão detalhado você deseja que o resultado final seja.
2. Para cada posição do vértice, simule o movimento da direção da unidade em direção a essa posição. Isso é feito em um loop restrito sem renderização.
3. Quando a distância máxima for atingida na simulação de direção, mova o vértice para o ponto da unidade simulada. Esse ponto é o mais próximo que a unidade poderia chegar desse vértice antes que a curva atual terminasse. Isso tem o efeito de reduzir o círculo ao tamanho do movimento real.
4. Use esses vértices, juntamente com um vértice centralizado na unidade para criar um círculo renderizado para desenhar as possíveis distâncias de movimento.

Então, começando com o círculo azul, você processaria seus caminhos, terminando com o círculo roxo. Em seguida, você pode usar esses pontos com um ponto central na unidade para criar os triângulos vermelhos necessários para exibir a forma. (Apenas fazer essa imagem me faz perceber que essa forma não está correta, mas será interessante ver o que está realmente correto)

Vou expandir a solução de Sean em uma resposta separada, pois representa uma abordagem diferente da que eu estava propondo inicialmente.

Essa solução provavelmente representa o método mais acessível. Requer particionar seu ambiente em nós. Sim, isso está reintroduzindo uma abordagem baseada em grade, mas pode ser feita relativamente bem ou usada para encontrar um caminho amplo com um posicionamento mais preciso tratado dentro do nó. Quanto mais grossa a estrutura do nó, mais rápida a busca de caminhos.

O grande problema aqui é que você está realmente lidando com o navio, então muitas soluções tradicionais de busca de caminhos não podem ser usadas sem modificações. Eles geralmente são independentes de caminho, pois não se importam com a maneira como você chegou ao nó em que está. Isso funciona bem quando a aceleração, a desaceleração e o giro são instantâneos e livres. Infelizmente para você virar não é gratuito. No entanto, como há realmente uma informação extra que é descartada nessa simplificação, podemos codificá-la como outra variável. Na física, isso seria conhecido como espaço de fase.

Supondo duas dimensões por enquanto, você pode extrapolar para 3:

Normalmente, você precisaria de um nó para cada posição de coordenada permitida e discreta. Por exemplo:

(0,0) - (1,0) - (2,0)
  | \  /  |  \  / |
(0,1) - (1,1) - (2,1)

Etc. Você constrói um gráfico de nó de pontos adjacentes e os conecta por adjacência espacial. Então você usaria o algoritmo de Dijkstra, matando nós que excedem o valor de movimento permitido para o turno, até que não existam nós vivos inexplorados permanecendo conectados aos nós explorados. Cada nó controla a menor distância necessária para alcançá-lo.

Para expandir esse método para ser utilizável com rotação, imagine esse mesmo gráfico de nodografia em 3 dimensões. A direção Z corresponde à rotação / orientação e é cíclica, ou seja, se você continuar viajando na direção + Z, voltará ao ponto em que começou. Agora, os nós correspondentes às posições adjacentes são conectados apenas através da face que corresponde a essa direção. Você itera pelos nós conectados aos nós já explorados, como de costume. Eu recomendaria restringir a N, NE, E, SE, S, SW, W, NW neste esquema.

Esta solução pode indicar todas as regiões acessíveis do espaço, bem como o melhor caminho para chegar lá, quanta rotação você tem quando chega lá e todas as orientações que você poderia ter ao chegar lá.

Então, ao executar o caminho, você pode interpolar / spline cúbico para torná-lo mais autêntico.

Parece que você pode precisar decidir primeiro como exatamente você gostaria que a mudança funcionasse. Opções como:

• Se eles se moverem dentro do cone, primeiro gire e comece a se mover. Esta é a solução mais fácil de implementar e localizar. Também é menos interessante, então eu não gostaria de usá-lo.

• Giro contínuo enquanto se move, até um total de 45 graus. Este é muito mais complicado, e espero que você esteja atrás. A integração numerosa ao longo do caminho usando um timestep fixo é provavelmente a maneira mais fácil de abordar esse. Seu cone será limitado pela rotação máxima (+ X graus a cada passo) e mínima (-X graus a cada passo).

A melhor maneira de percorrer o espaço com o segundo desses requisitos depende muito do ambiente em que eles estarão se movendo. Se houver muitos obstáculos que você precisará contornar, as coisas poderão ficar muito complicadas e caras. No entanto, se não houver, você poderá carregar a rotação (e até diminuir) a rotação para terminar no local desejado.

Tenho a sensação de que talvez tenha abordado apenas parcialmente os tópicos sobre os quais você fez uma pergunta, fique à vontade para adicionar mais nos comentários e posso expandir a discussão.