Sugestões de IA do personagem PacMan para a próxima direção ideal

9

Em primeiro lugar, isso é IA para PacMan e não para os fantasmas .

Estou escrevendo um papel de parede ao vivo para Android que reproduz o PacMan em torno de seus ícones. Embora ele suporte sugestões do usuário por meio de toques na tela, a maioria do jogo é jogada por uma IA. Eu estou 99% pronto com toda a programação do jogo, mas a IA do PacMan ainda é extremamente fraca. Estou procurando ajuda para desenvolver uma boa IA para determinar a próxima direção de viagem do PacMan.

Meu plano inicial era este:

  1. Inicialize um contador de pontuação para cada direção com um valor zero.
  2. Comece na posição atual e use um BFS para percorrer as quatro direções possíveis, adicionando-as à fila.

  3. Retire um elemento da fila, verifique se ele ainda não foi "visto", verifique se é uma posição válida no quadro e adicione às direções iniciais correspondentes um valor para a célula atual com base em:

    1. Tem um ponto: mais 10
    2. Tem um poder acima: mais 50
    3. Tem uma fruta: mais o valor da fruta (varia de acordo com o nível)
    4. Tem um fantasma assustado: mais 200
    5. Tem um fantasma viajando em direção ao PacMan: subtraia 200
    6. Tem um fantasma viajando para longe do PacMan: não faça nada
    7. Tem um fantasma viajando perpendicular: subtraia 50
    8. Multiplique o valor da célula por uma porcentagem com base no número de etapas da célula; quanto mais etapas a partir da direção inicial, mais próximo o valor da célula será zero.

    e enfileire as três direções possíveis da célula atual.

  4. Quando a fila estiver vazia, encontre a pontuação mais alta para cada uma das quatro direções iniciais possíveis e escolha essa.

Pareceu-me bom no papel, mas os fantasmas cercam PacMan extremamente rapidamente e ele se contorce de um lado para o outro nas mesmas duas ou três células até que um o atinja. Ajustar os valores para a presença de fantasmas também não ajuda. O meu ponto BFS mais próximo pode pelo menos chegar ao nível 2 ou 3 antes do final do jogo.

Estou procurando código, pensamentos e / ou links para recursos para o desenvolvimento de uma IA adequada - de preferência os dois primeiros. Gostaria de divulgar isso no mercado em algum momento deste fim de semana, por isso estou com pressa. Qualquer ajuda é muito apreciada.

Para sua informação, isso foi originalmente publicado no StackOverflow

java ai path-finding Jake Wharton
fonte
Muito disso depende da IA ​​fantasma. Se você estiver usando exatamente o mesmo algoritmo de IA do jogo original, poderá fazer com que o pac-man siga um dos muitos padrões que já foram descobertos, nenhuma AI é necessária, exceto uma tabela de pesquisa. Se os fantasmas estão se aproximando rapidamente do seu pac-man, você considerou que o problema é a IA fantasma ser muito boa, e não a IA pac-man ser muito fraca?
31511 Ian Schreiber
@Ian A IA fantasma é exatamente como é no jogo, mas o layout do tabuleiro não é o mesmo. É apenas um layout de grade simples que limita seu layout de ícone (4x4, etc.). O PacMan atual é o ponto mais próximo que não tem um fantasma entre ele e o ponto. Ele irá diretamente em direção a um fantasma, desde que haja pontos no meio. Talvez eu precise apenas dar alguns passos além do ponto mais próximo e determinar se essa é uma boa direção a seguir. Uma vez que toda essa direção em busca da lógica deve ocorrer a cada movimento celular, também deve ser relativamente simples e rápida.
Jake Wharton
Analise a Difusão colaborativa, que pode ajudá-lo de alguma forma.
user712092

Respostas:

3

A ideia do algoritmo de escalada em tandem é boa. Outra é: alguma variação em A * para ver até onde você pode ir para ver como conseguir a pontuação mais alta nos próximos N turnos, onde N é ajustado para dar o resultado desejado.

Os valores de pontuação que você fornecer podem ser considerados como "custo para se mover" - você está basicamente no caminho certo, mas precisará ajustar os valores até obter o resultado desejado.

Em termos gerais (não específicos do PacMan), você precisa alocar valores apropriados para

  • Feriu o outro cara.
  • Matou outro cara.
  • Alcançou algum outro objetivo (além de matar)
  • Foi ferido.
  • Foi morto.

e depois procure a jogada que levará à pontuação máxima N voltas no futuro. Você também pode evitar movimentos que levem a uma pontuação abaixo de X (por exemplo, o custo da morte) N se transformará no futuro.

Depois de marcar todos os movimentos possíveis, adicione bônus por quão bem ele pode sair no futuro e deduzido o quão ruim pode acabar no futuro, então você apenas classifica a matriz e toma a melhor jogada.

Nos informe sobre o desfecho!

Olie
fonte
2

Definitivamente, dê uma olhada neste vídeo: http://www.youtube.com/watch?v=2XjzjAfGWzY

Você provavelmente vai querer algum tipo de hill-climbing algoritmo de encontrar caminho.

Adam Harte
fonte
0

Você vai fazer uma pesquisa.

  • Nó / Estado: localização de Pacman, localizações de fantasmas, localizações de pelotas, pontuação total, vidas totais.
  • Transição: Pacman se move para cima, baixo, esquerda ou direita. Se Pacman se move contra uma parede e muda de local, tudo fica bem (pode levar a algumas estratégias realmente interessantes). Se Pacman atingir um fantasma, remova uma vida e mova-o e os fantasmas para a origem.
  • Custo: Se Pacman se mover para um pellet 1, se ele se mover para um espaço vazio 2.
    O custo é um pouco complicado, pois não é óbvio. A função de custo que descrevi incentivará Pacman a terminar o nível. Isso impede uma possível estratégia e apenas acampar esperando a fruta bônus aparecer. Mas acho que queremos que o AI Pacman termine o labirinto, mesmo que produza uma pontuação mais baixa.
  • Objetivo: pontuação máxima atingida. Isso significa que todos os pellets, frutas e pellets de energia são consumidos.

A * ou UCS são ótimos quando se busca um objetivo. A maneira como descrevi o Estado / Transição / Objetivo encontrará um ótimo caminho para Pacman, a IA não precisa considerar especificamente evitar a morte ou buscar frutas. Ele fará isso sozinho. Como o jogo é completamente determinístico, você pode "pesquisar" a partir do local inicial do Pacman e encontrar o caminho ideal para o final (todos os pellets consumidos) como um pré-cálculo e apenas o AI Pacman seguir esse caminho, não em tempo real. A principal desvantagem dessa abordagem é que ela pode facilmente sair de controle no tempo da CPU e no consumo de memória.

Em vez de dedicar a CPU e a memória para realizar uma pesquisa completa, você pode realizar uma pesquisa parcial em tempo real.

Você ainda pode usar o UCS / A *, mas pare de procurar depois que os Nnós de inspeção foram inspecionados e apenas use o melhor caminho encontrado até agora. Essa abordagem é boa, pois você pode ajustar Npara encontrar o equilíbrio entre velocidade e precisão.

Outro método de que gosto particularmente é a pesquisa na árvore Monte-Carlo. Nesse método, você permite que o Pacman faça uma caminhada aleatória de Nmovimentos. Após cada caminhada aleatória, você registra seu lance inicial e a pontuação final. Faça Mcaminhadas aleatórias (ou continue fazendo até que você esteja sem tempo ou o que quer que seja). Escolha o movimento inicial com a melhor média dos passeios aleatórios.

Essas pesquisas parciais têm uma séria desvantagem. Se a pesquisa com o UCS e o Pacman não Nobtiver pontuação nos primeiros nós inspecionados, ele ficará paralisado e, como todos os movimentos são igualmente ruins.
A * não teria esse problema desde que a heurística tivesse o cuidado de aproximar Pacman de pelotas não consumidas.
O MCTS poderá evitar esse problema se a caminhada aleatória for tendenciosa para avançar em direção a pellets não consumidos e a caminhada aleatória nunca parar antes da pontuação (ou seja, a caminhada aleatória continuará se Pacman tiver 0 pontuação.

deft_code
fonte