Determinando a localização final do movimento da IA ​​em grupos em um RTS 2D

8

Eu escrevi um jogo RTS (na verdade, uma demo para um mecanismo de jogo) em que a interação básica do usuário com o jogo é selecionar um monte de soldados e clicar com o botão direito do mouse no mapa para movê-los para o local especificado. Isso está em JavaScript e você pode brincar com ele aqui ( código ).

Ignorando o problema de como os soldados se deslocam da sua localização atual para o seu destino, minha pergunta é sobre como determinar qual é o seu destino real. Aqui está o que eu tentei até agora:

  • Tentativa 1: Diga a todos os soldados selecionados para moverem para as coordenadas em que o mouse clicou. Isso tem o comportamento estranho de que todos os soldados irão se agrupar em torno do alvo de maneira não natural.
  • Tentativa 2: encontre as coordenadas médias de todos os soldados selecionados, encontre o deslocamento desse ponto central para cada soldado e, finalmente, traduza esse deslocamento em torno das coordenadas do mouse. Isso funciona bem, exceto que, se os soldados selecionados estiverem afastados, eles não chegarão perto do alvo.
  • Tentativa 3: Crie uma grade em torno das coordenadas do mouse e coloque cada soldado selecionado em uma célula da grade. Se cada soldado chegar à sua cela designada, isso funcionará muito bem. No entanto, os soldados são designados para células da grade na ordem em que os soldados foram gerados; portanto, às vezes eles colidem (ou seja, todos os soldados do lado direito tentam ir para o lado esquerdo), o que não parece natural.
  • Tentativa 4: Use uma grade como antes, mas primeiro classifique os soldados por local, para que eles se alinhem de forma sensata. Por exemplo, se você clicou abaixo do grupo, os soldados na parte inferior do grupo terminarão na parte inferior da grade quando chegar ao seu destino. Isso funciona muito bem, mas às vezes há falhas e não sei por que.

Aqui está a função que determina as coordenadas de destino:

function moveSelectedSoldiersToMouse() {
  var w = 0, h = 0, selected = [];
  // Get information about the selected soldiers.
  myTeam.soldiers.forEach(function(soldier) {
    if (soldier.selected) {
      selected.push(soldier);
      w += soldier.width;
      h += soldier.height;
    }
  });
  var numSelected = selected.length, k = -1;
  if (!numSelected) return;
  // Build a grid of evenly spaced soldiers.
  var sqrt = Math.sqrt(numSelected),
      rows = Math.ceil(sqrt),
      cols = Math.ceil(sqrt),
      x = Mouse.Coords.worldX(),
      y = Mouse.Coords.worldY(),
      iw = Math.ceil(w / numSelected), // grid cell width
      ih = Math.ceil(h / numSelected), // grid cell height
      wg = iw*1.2, // width of gap between cells
      hg = ih*1.2; // height of gap between cells
  if ((rows-1)*cols >= numSelected) rows--;
  w = iw * cols + wg * (cols-1); // total width of group
  h = ih * rows + hg * (rows-1); // total height of group
  // Sort by location to avoid soldiers getting in each others' way.
  selected.sort(function(a, b) {
    // Round to 10's digit; specific locations can be off by a pixel or so
    var ax = a.x.round(-1), ay = a.y.round(-1), bx = b.x.round(-1), by = b.y.round(-1);
    return ay - by || ax - bx;
  });
  // Place the grid over the mouse and send soldiers there.
  for (var i = 0; i < rows; i++) {
    for (var j = 0; j < cols; j++) {
      var s = selected[++k];
      if (s) {
        var mx = x + j * (iw+wg) - w * 0.5 + s.width * 0.5,
            my = y + i * (ih+hg) - h * 0.5 + s.height * 0.5;
        // Finally, move to the end destination coordinates
        s.moveTo(mx, my);
      }
    }
  }
}

Você pode colar esta função no console JavaScript do seu navegador ao visualizar a demonstração e mexer nela para alterar o comportamento dos soldados.

Minha pergunta é: existe uma maneira melhor de determinar o local de destino de cada soldado para o qual se mudar?

IceCreamYou
fonte
Algo chamado "flocagem" pode ser muito útil para você e fornecer o tipo de funcionalidade que você está procurando. Tente: processing.org/examples/flocking.html ou apenas pesquise no Google "flocking" ou "Boids". Isso pode colocá-lo na direção certa.
319 Dean Dean Knight
2
Relacionados: gamedev.stackexchange.com/questions/44361 Eu diria que as "falhas" que você está enfrentando são de unidades que estão tentando mudar para uma posição que já foi reivindicada. Certifique-se de que a posição em que estão se mudando já não seja o alvo de outra unidade e que você tenha resultados bastante decentes.
MichaelHouse
@ DeanKnight, estou ciente de como os comportamentos de flocagem funcionam, mas isso determina como os bots vão do ponto A ao ponto B, e não ao ponto B.
precisa
@ Byte56: obrigado pelo link. Não estou literalmente colocando unidades em slots de grade - na implementação não há como várias unidades serem direcionadas para o mesmo local. Parece que o problema é mais que a classificação às vezes fica confusa.
precisa
11
Outra idéia: Pathfinding Swarm . Nesse caso, você não daria a cada unidade um ponto final diferente; basta que eles parem quando não houver caminho até o ponto final (porque todas as outras unidades estão no caminho) ou não parem e deixem a detecção de colisão fazer seu trabalho.
BlueRaja - Danny Pflughoeft

Respostas:

2

Aqui estão minhas sugestões sobre suas idéias:

Tentativa 1: Para corrigir essa situação, você pode implementar a idéia "suficientemente próxima" que Spencer trouxe. Eu faria algo como desenhar uma bolha em torno do ponto final, que cresce com base em uma proporção do número e tamanho das unidades já nele. Digamos que a bolha comece com o tamanho de uma unidade e, quando a primeira chegar, o raio dobrará nas próximas duas unidades, etc.

Tentativa 2: uma solução para esse problema seria levar a distância média do grupo um do outro e, em seguida, diminuir a distância dos valores discrepantes para que o grupo acabasse mais agrupado do que originalmente (a métrica poderia ser mais curta / mais do que a média, o que quer que pareça decente ou, eventualmente, defina um tamanho máximo de formulário com base no número / tamanho das tropas novamente). A única coisa com que você precisa se preocupar é quando você altera o caminho de um outlier. preciso verificar e garantir que não interfira nos outros caminhos

Tentativa 3: você melhorou esta na tentativa 4

Tentativa 4: Parece que este funcionaria bem se você encontrar quaisquer falhas que estejam provocando isso. No entanto, eu recomendaria brincar com picos diferentes da formação de uma grade, para tornar o movimento um pouco mais natural, a menos que você esteja realizando um estilo militar / militar; nesse caso, pode ser legal tê-los "em forma "antes de se mudar, mas isso pode ficar irritante para o jogador depois de um tempo.

A tentativa 4 parece ser a mais próxima de remover o comportamento de fresamento no seu problema, mas em termos de manter o movimento fluindo sem qualquer ajuste que não seja o necessário, meu favorito provavelmente seria a tentativa 2.

Mas, como uma solução totalmente diferente, você pode ter dois tipos de objetos quando se trata de busca de caminhos; cada unidade, bem como um objeto "esquadrão" invisível.

Esquadrão - Você constrói o objeto de esquadrão no centro do grupo, como as outras soluções, e usa o caminho para direcioná-lo para o objetivo.

Unidades - As unidades ignoram completamente o objetivo e, em vez disso, usam o caminho para se manter a uma certa distância (ou formação, ou qualquer outra métrica acaba fazendo o movimento parecer melhor) do objeto do esquadrão.

Isso separa os diferentes aspectos da busca de caminhos e permite ajustar os dois lados isoladamente para obter mais controle sobre a aparência.

David M
fonte
Ótima resposta. Obrigado pelas novas idéias. A abordagem Esquadrão + Unidade é interessante, provavelmente exige que as unidades podem mover mais rápido em modo de "catch-up"
IceCreamYou
Sim, uma solução define a velocidade de movimento do objeto "esquadrão" para um pouco abaixo do máximo que as unidades individuais podem se mover, para permitir que elas se movam, se necessário, sem ficar para trás.
9133 David M #
2

A tentativa 3 pode funcionar, mas precisa de um pouco de refinamento.

Pense no conceito de formação (sua grade é um começo). Uma formação deve ter um local (isto é, as coordenadas de clique ou o soldado / edifício alvo) e uma rotação (isso pode ser fixo, aleatório ou determinístico). A formação deve ter o mesmo número de posições que o número de soldados selecionados.

Um exemplo simples de formação pode ser um círculo ao redor do alvo. O espaço é posicionado igualmente ao redor e aumenta o raio do círculo para acomodar todos os soldados sem colidir.

O próximo problema é decidir qual soldado caminha para qual posição na formação. Uma solução simples seria fazer com que cada soldado se movesse para a posição mais próxima dele. Se aquele já foi 'escolhido' por outro soldado, tome a próxima posição mais próxima etc.

As formações podem se tornar bastante interessantes. Abaixo está uma imagem da 'formação de chifre de touro' usada com grande sucesso por Shaka, o zulu . (A imagem vem do TotalWar Formation Mod )

formação de chifre de touro

Willem
fonte
"O próximo problema é decidir qual soldado caminha para qual posição na formação". Na verdade, esse é o problema inteiro desta questão. :) Promovido o voto por sugerir uma formação de círculo em vez de uma grade, mas isso é ineficaz para mais do que alguns soldados, e mover soldados para o local mais próximo deles causa mais conflitos do que a minha solução acima de classificar as unidades por local.
usar o seguinte
0

Ao clicar no usuário, desenhe um vetor de cada soldado para o local clicado. Obtenha o ângulo médio do vetor a partir dos vetores desenhados para cada soldado e mova cada soldado o comprimento do seu vetor individual nessa direção com o mesmo ângulo. Isso deve dar a aparência das unidades se movendo em formação ao ponto e deve impedir que as unidades se aglomerem.

Se você quiser que as unidades saiam de formação, você pode apontar o ângulo de cada soldado diretamente no local clicado. No entanto, sem colisão, as unidades começarão a convergir. Para combater isso, adicione colisão e force as unidades a pararem de se mover quando estiverem "perto o suficiente" até o ponto clicado. As primeiras unidades a chegar estarão exatamente no ponto e as últimas a chegar devem ser direcionadas para que parem de se mover quando estiverem próximas o suficiente ou após um certo período de tempo.

Você pode calcular o comprimento do caminho e a velocidade da unidade para determinar quando uma única unidade deve chegar e forçar a unidade a parar de se mover se exceder esse tempo em um determinado valor. Você precisará jogar um pouco com esse número.

Spencer
fonte
A solução vetorial que você está sugerindo é a mesma da minha tentativa 2 acima. Um dos requisitos desta pergunta é que as unidades selecionadas podem não estar em formação.
usar o seguinte
E eu escrevi sobre uma solução na qual eles não se moveriam em formação. (Segundo parágrafo)
Spencer