Projetando Snake AI

9

Eu sou novo nessa mudança de pilha gamedev, mas já usei os sites de matemática e cs antes.

Então, estou em uma competição para criar IA para uma cobra que competirá com outras quatro cobras em rodadas de 5 minutos, onde as regras são muito parecidas com o tradicional jogo de cobras da Nokia, exceto que há cinco cobras, o tabuleiro é 30x30 e existem uma série de pequenos obstáculos no campo.

Assim como o jogo Nokia, sua cobra cresce quando você chega à fruta e, se você se chocar contra outra cobra ou a parede, você morre. O jogo corre com um atraso de 30 ms entre as jogadas e o servidor envia o novo estado do jogo a cada 50 ms que o código deve analisar e o que não deve e gera a próxima jogada.

O vencedor é a cobra que teve o maior comprimento em qualquer ponto do jogo. Os desempates são decididos por mortes.

Até agora, o que fiz foi implementada uma pesquisa de gráfico A * de cada cobra para determinar se minha cobra é a mais próxima da maçã e, se for, ela vale para a maçã. Caso contrário, criei um pequeno algoritmo para determinar a área mais vazia do tabuleiro, para a qual minha cobra se destina, para antecipar a próxima maçã.

Fora isso, tenho algumas verificações de sobrevivência pequenas para garantir que minha cobra não esteja entrando em uma armadilha que não pode sair e, se ficar presa, tenho algo para lhe dar uma melhor chance de sair.

...

Enfim, testei minha cobra em um servidor de teste e funciona muito bem. Geralmente, minha estratégia de ir apenas para a maçã quando é algo certo e encontrar espaço quando não o faz crescer mais rápido do que qualquer outra cobra (algumas cobras fazem uma coisa semelhante, mas geralmente apenas vão para o meio ou para um canto) às vezes ganham nesses jogos de teste, mas é mais frequentemente derrotado pela mesma cobra que parece ter vantagem sobre a capacidade de sobrevivência (minha cobra cresce mais rápido, mas depois morre de alguma forma e essa outra cobra apenas caminha lentamente e ganha consistência.

Então, eu estava pensando em alguma idéia que alguém tenha para tentar melhorar minha cobra. Ou talvez idéias em uma nova abordagem a ser adotada. Minhas funções e classes são boas, portanto as mudanças que podem parecer drásticas não devem ser tão ruins. Encorajo todas as idéias.

Alguma ideia?

Rawb
fonte

Respostas:

5

Uma boa estratégia defensiva pode ser fazer uma forma perfeita (para que sua cabeça e as costas estejam sempre a um espaço de distância uma da outra e você faça um quadrado inteiro ou o que for possível formar no seu comprimento determinado), isso faria você praticamente imortal, já que nenhuma cobra jamais poderia entrar em sua área fechada e você nunca entraria em si mesmo (a menos que uma maçã de alguma forma surgisse em sua boca, mas eu imagino que seja impossível se não houver espaço).

Isso faria com que, se a maçã realmente aparecesse na sua área fechada, você pudesse ser programado para não buscá-la e as outras cobras provavelmente morreriam tentando pegá-la. Depois de algum tempo, você poderia obtê-la de maneira a fazer a transição de volta à sua forma o melhor possível (pode ser um algoritmo complicado, mas parece factível)

Quando comprar maçãs dependeria apenas de quão longe elas estão, talvez se você for o mais próximo por uma boa margem, você pode ir atrás, mas, de outro modo, mantenha-se conservador, difícil dizer que provavelmente precisará ajustá-lo com base em tentativa e erro , mas acho que seria uma boa estratégia.

Kevin DiTraglia
fonte
11
Então, basicamente, sua "cobra" deveria "tartaruga". xD +1 boa ideia.
cifra
Um bom. Mas existem obstáculos no quadro. Portanto, outros programadores de cobras devem ter feito suas cobras para verificar se há alguma obstrução (seja parede ou outra cobra que envolva a maçã). Eles podem não vir e apenas morrer. Uma coisa que pode ser feita para evitar esse problema é ter um espaçamento considerável entre a cabeça e a cauda.
Shashwat 20/09/12
hmm ideia interessante, acho que eu poderia implementar algo assim para quando minha cobra estiver esperando a próxima maçã aparecer .. haha, estou um pouco preocupado com a maçã que aparece na minha boca, isso resultaria em certas morte e estes jogos são muitas vezes decididas por uma morte prematura
Rawb
@Ronald Na verdade, se você detectar que a maçã aparece na boca, você pode se virar para dentro e para trás e continuar, já que a IA tem um reflexo perfeito, na verdade deve ser fácil remediar (e até se consertar) com base em como você o implementa.
Kevin DiTraglia
0

A cobra deve adaptar sua estratégia ao seu comprimento atual.

Uma cobra muito longa pode usar seu corpo para cercar os oponentes. Isso significa que ele deve fazer uma vedação com uma parede.

Se a cobra estiver viajando para o leste, com uma maçã a nordeste, deve percorrer todo o caminho até a parede antes de virar para o norte, para que as rotas possíveis para outras cobras sejam severamente limitadas.

  0123456789
a ··········
b ··········
c ········A·
d ··········
e ooooooC···
f o·········
g o·········
h oooooooo··
i ··········
j ··········

Essa cobra com cabeça C deve virar para o norte na e9, não na e8, para que qualquer oponente abaixo dela fique preso e incapaz de comer maçãs que aparecerem acima da linha 'e'.

Quanto maior a área que você pode cortar e quanto mais tempo você pode segurá-la, melhor.

Bram
fonte