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

11

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)

insira a descrição da imagem aqui

sfphilli
fonte
Ainda será capaz de mover a mesma distância (total). Portanto, a questão é realmente descobrir "até que ponto ele vira?" / "Quanto ele precisa virar?" / "Para onde ele precisa virar?". Você provavelmente precisa começar a determinar o caminho regular e, em seguida, recuar um ângulo de início acima de um determinado valor; observe que a distância final será mais longa no caminho linear (mais recente) do que nas curvas.
Clockwork-Muse
Sim, a distância percorrida é o principal fator limitante. Meu maior obstáculo aqui é que eu preciso levar em conta que a peça pode girar e continuar girando, a qualquer momento que puder alcançar, desde que ainda tenha distância disponível.
Sfphilli
Como assim, o alcance que uma unidade pode mover? Você quer dizer os pontos para os quais ele pode se mover? Você conhece a álgebra linear (vetores)?
BlueRaja - Danny Pflughoeft
1
Que cenário da vida real você está tentando modelar? Seu problema é muito vago nos requisitos, resultando em muitas abordagens de solução propostas. Existem abordagens bem conhecidas para (virtualmente) todos os problemas específicos nessa área, mas todo mundo está adivinhando quais desses problemas você realmente está enfrentando.
Pieter Geerkens
1
@PieterGeerkens Suponho que, porque o OP não está solicitando código, está solicitando um algoritmo. E fornecemos detalhes suficientes sobre o cenário para que um algoritmo pudesse ser razoavelmente concebido. Isso é comum e aceitável.
MichaelHouse

Respostas:

4

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.

Sean Middleditch
fonte
Não exatamente como eu explicaria o conceito, ou como o implementaria, mas certamente a abordagem correta.
Pieter Geerkens
Meu entendimento do algoritmo, como está, é que o deslocamento do nó precisa ser independente do caminho. Portanto, para conseguir isso, você precisará adicionar outro grau de liberdade (outro eixo no qual criar seus nós) dedicado a enfrentar. Em outras palavras, você teria um nó para cada combinação de diferentes X, Y, potencialmente Z e Face. Caso contrário, encontrar o caminho mais curto para entrar em um nó não faz distinção entre as diferentes faces ao deixá-lo. Isso está correto? Se for esse o caso, esse método é possivelmente muito intenso?
TASagent
@ Tasagent: bom ponto, eu não pensei nisso completamente. Talvez o algoritmo esteja um pouco errado, mas a abordagem deve funcionar.
Sean Middleditch
@PieterGeerkens: Concordo que é uma má explicação. Você deve fazer sua própria resposta que explique tudo melhor.
23813 Sean Middleditch
Parece que está muito perto do que eu preciso, mas devo admitir que nunca ouvi falar desse algoritmo e, portanto, não sei como generalizá-lo para o que preciso. Você tem um link para alguma boa informação ou tutoriais?
Sfphilli
4

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.

insira a descrição da imagem aqui

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)

MichaelHouse
fonte
3

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.

TASagent
fonte
1
Isto e excelente. Precisarei fazer uma pequena pesquisa sobre o algoritmo e experimentá-lo no meu jogo, mas isso realmente me parece o ajuste perfeito, especialmente porque eu posso generalizá-lo para outras partes importantes do jogo.
Sfphilli
1

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.

TASagent
fonte
Definitivamente, quero usar a segunda opção, de subir (por exemplo) 45 graus em qualquer ponto, e potencialmente em todos os pontos do caminho. Também haverá obstáculos, cada um maior que os pedaços (pense em pedras gigantes). A maneira como eu originalmente pensava nisso era gerar um cone de possíveis pontos finais e, em seguida, para cada um desses pontos finais, gerar um novo cone, e assim por diante, para todos os locais possíveis até atingir a distância máxima percorrida. Dito isto, não tenho muita certeza de como proceder para implementar isso sem uma supercomplicação louca.
Sfphilli
Hmmm, parece que não sou claro sobre alguns detalhes. Revendo a questão, vejo que você especificou 'baseado em turnos' e que as unidades podem 'girar ou mover' na sua vez. Isso significa, então, que o jogador planeja suas ações muitas vezes antes, e você deseja encontrar o caminho enquanto se move? Mais esclarecimentos sobre como o movimento deve funcionar seria útil.
TASagent
Não, o que eu quis dizer foi que, em um determinado turno, o jogador pode girar sua peça no lugar, da maneira que quiser, ou pode se mover na direção que já está olhando. Se eles se moverem, eles podem percorrer uma distância específica ao longo de um caminho e podem girar ou dirigir até um ângulo específico (portanto, de -45 a 45 graus, por exemplo) enquanto se movem. Imagine que um caminho escolhido envolva uma curva para mover para a esquerda ou direita. O caminho seria determinado pelo jogador escolher um ponto para o qual deseja ir, dentro do intervalo de pontos possíveis que estou tendo problemas para determinar.
sfphilli
Ok, parece que, infelizmente, suas características desejadas são possivelmente muito restritivas para o algoritmo Dijkstra de que estamos falando acima: - \. Possivelmente. Vou esboçar algumas coisas para isso mais tarde, quando chegar em casa.
TASagent
Convém editar algumas dessas informações reunidas para esclarecer o problema na pergunta original, para que as pessoas que vierem mais tarde possam começar com mais informações.
TASagent