Encontrando o trajeto em um 2d jogo Java?

StackOverflow https://stackoverflow.com/questions/623095

Pergunta

Essencialmente seu um jogo clone pacman que estou trabalhando. Eu tenho uma classe Inimigo, e 4 instâncias desta classe criado que todos representam 4 fantasmas do jogo.

Todos os fantasmas iniciar-se em áreas aleatórias da tela e, em seguida, eles têm que trabalhar seu caminho para o personagem pacman. Como o jogador controla o pacman, movê-lo, eles devem segui-lo e tomar o caminho mais próximo possível para ele.

Não há labirinto / obstáculos (ainda) para que o mapa inteiro (400x400 pixels) é terreno aberto para eles.

Para o jogador e cada Santo, posso recuperar o X, Y, largura e altura da imagem atributos. Além disso, eu já tenho um algoritmo de detecção de colisão, por isso não se preocupou com isso, apenas sobre os fantasmas encontrando seu caminho para pacman.

Foi útil?

Solução

Para um algoritmo bom pathfinding, usando A * provavelmente seria uma boa idéia, no entanto, para um jogo simples que não requer sofisticado, eficiente, nem eficaz busca caminho, simplesmente ter os personagens se movem em direção a um alvo por descobrir a direção do alvo deve ser suficiente.

Por exemplo, a decisão de fazer o movimento de caráter, em pseudocódigo: 

if (target is to the left of me):
    move(left);
else
    move(right);

if (target is above me):
    move(up);
else
    move(down);

Sim, o personagem não vai fazer o movimento mais eficiente, mas ele vai ficar cada vez mais perto do alvo em cada iteração do loop do jogo.

É também o meu palpite de que um jogo de arcade do início dos anos 80, provavelmente não estaria usando algoritmos pathfinding sofisticados.

Outras dicas

Se você só tem uma grade de pixels - um "campo grande" em que pacman e fantasma pode se mover livremente -, então o caminho mais curto é fácil -. Uma linha reta entre o fantasma e o pacman

Mas "caminho mais curto" invariavelmente significa que estamos a tentar resolver um problema-teoria dos grafos. (Estou assumindo o conhecimento de gráficos, alguns teoria dos grafos, adj. Matrizes, etc!)

No caso acima, considere cada pixel para ser um nó em um gráfico. Cada nó é ligado aos seus vizinhos por uma aresta, e cada borda tem igual "peso" (movendo-se para o nó em "acima" não mais lento do que se deslocam para o nó "abaixo" é).

Então você tem isso: ( "*" = nó "-, /, \, |" = borda) 

*-*-*
|\|/|
*-*-*  ... (etc)
|/|\|
*-*-*

Se Pacman está no centro, ele pode mover-se para qualquer outro nó com muita facilidade.

Algo mais próximo da realidade pode ser esta: 

*-*-*
| | |
*-*-*  ... (etc)
| | |
*-*-*

Agora, pacman não pode se mover na diagonal. Para ir do centro para o canto inferior direito requer 2 "saltos" em vez de um.

Para continuar a progressão: 

*-*-*-*
| | | |
| | | |
| | | |
*-*-*-*
| | | |
*-*-*-*

Agora, para ir de um nó no meio de um nó no topo, você precisa de 3 saltos. No entanto, para se mover em direção ao fundo leva apenas 1 hop.

Seria fácil de traduzir qualquer configuração do jogo de bordo em um gráfico. Cada "interseção" é um nó. O caminho entre dois cruzamentos é uma vantagem, e o comprimento do referido caminho é o peso da referida borda.

Digite A *. Através da construção de um gráfico (usar uma matriz adjency ou uma lista de nós), você pode usar o algoritmo A * para encontrar o caminho mais curto. Outros algoritmos incluem Dijkstra. E muitos outros! Mas primeiro você precisa para enquadrar o problema em termos de um gráfico, e depois brinquedo com a forma como você ir de um nó (pacman) para o nó B (fantasma).

Espero que ajude!

Tem sido um tempo muito longo, mas a partir da memória os fantasmas em Pac-Man não fez muito na maneira de pathfinding. Eles fariam um percurso labirinto randomizado bastante normal até que "manchou" você, que envolveu encontrar um caminho desobstruído ao longo do eixo de um corredor em direção a você, e então eles se mover diretamente para você até que desapareceu de sua linha de visão, depois do que eles vai retomar um padrão aleatório. Em níveis mais elevados Pac-Man deixaria trilhas invisíveis atrás dele por um tempo que os fantasmas que "cheiro" e às vezes seguir.

Quando Pac-Man tem um poder acima, a única diferença no algoritmo é que, quando avistaram você, os fantasmas fugiria você, em vez de se mover em direção a você.

Assim, para uma experiência autêntica, você provavelmente não precisa de um algoritmo de pathfinding muito sofisticado em tudo. Se você quer ser fantasia, é claro, você pode implementar A *.

Passeio diretamente para seus inimigos é um começo, mas quando você adicionar um labirinto você vai querer adicionar um pouco mais esperto pathfinding para que seus fantasmas não ficar preso em curvas ou becos sem saída.

O tutorial a seguir é um grande guia leve para começar com o A *, com exemplos para download.

Path Finding on Tile baseados

em Pacman todas o fantasma tinha uma perseguição diferente algoritmo

  • Blinky -> Perseguições. Normalmente irá tomar o caminho mais curto para você, e tende a seguir.
  • Pinky -> As emboscadas. Tende a tomar uma forma mais indireta de pac-man. Mortal. (Mindinho e blinky tendem a fazer escolha diferente ao escolher uma direção, muitas vezes prendendo o jogador em um canto)
  • Inky -> Freak. Este gajo age de forma estranha. Ele se move sobre a bordo bastante aleatoriamente, mas às vezes persegue quando ele fica no fim.
  • Clyde -> Idiot. Move-se de forma aleatória. Não muito de uma ameaça.

Os fantasmas têm um padrão interessante programado em seus movimentos: de vez em quando, eles simultaneamente vai cessar e desistir sua busca de Pac-Man e retorno a seus respectivos cantos do labirinto, entrar "modo de dispersão"

.

há uma descrição completa do algo em o pacman dossier

relação

Guillaume

Você poderia começar olhando A * (uma estrela)

aqui é um página que tem links para outros algoritmos Encontrando o trajeto.

[editar] gah ... cérebro é muito lento ... esqueceu-se sobre este livro, é C ou C ++ (não me lembro qual), mas você ainda pode obter os conceitos de Java. Pode não ser o mais fácil para você ler, mas não é ruim em geral. AI para Game Developers por David M. Bourg, Glenn Seemann .

Eu acho que ir para o algoritmo de caminho mais curto a cada movimento feito por pacman. Uma boa implementação é de Dijkstra algoritmo .

Apenas para resumir: Visualize o labirinto como um gráfico com vértices e arestas. Cada aresta tem uma espera (no seu caso todas as arestas têm o mesmo peso). O algoritmo encontra o caminho mais curto do vértice fonte de alvo vértice movendo um passo para baixo de cada borda alcançável imediato. Em seguida, no próximo vértice você fazer o mesmo e continuar fazendo até que você chegar ao alvo. O primeiro caminho alcançado é o caminho mais curto. Pode haver muitas otimizações feitas para este algoritmo para acelerar as coisas como tendo em conta onde o pacman estava em sua posição anterior e em que direção ele mudou-se para que você possa obter algumas heiristics no algoritmo. Gostaria de sugerir encontrar o caminho mais curto de cada fantasma para pacman em cada movimento e mover o fantasma nessa direção. Eventualmente, a distância vai reduzir e você será capaz de capturar pacman.

Outra heurística que pode ser usado para encontrar todas as bordas imediatas acessível a partir pacman e tentar cobrir o maior número desses vértices possível por fantasmas. Então, em vez de definir pacman como o alvo vértice vamos definir os vértices immediatetly acessível por pacman como alvo, o resultado será que os fantasmas disponíveis vão tentar encobrir themajor rotas de fuga de pacman e pegá-lo.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top