Movendo-se / evitando obstáculos

12

Eu gostaria de escrever um "jogo", onde você pode colocar um obstáculo (vermelho), e o ponto preto tenta evitá-lo e chegar ao alvo verde.
Estou usando uma maneira muito fácil de evitá-lo, se o ponto preto estiver próximo ao vermelho, ele muda de direção e se move por um tempo, depois avança para o ponto verde.
Caminho "irrealista"

Como criar um caminho "suave" para o "player" controlado por computador?
Edit: Não a suavidade é o ponto principal, mas para evitar o bloqueio "parede" vermelho e não bater nele e , em seguida, evitá-lo.

Como eu poderia implementar algum algoritmo de localização de caminho se eu tivesse apenas 3 pontos?
(E o que tornaria as coisas muito mais complicadas, se você pudesse colocar vários obstáculos?)
Caminho suave

ai path-finding do utilizador
fonte

Respostas:

9

Uma abordagem muito comum e geral é dividir o espaço do seu mundo em grades e usar algoritmos como A *.

Esse link me ajudou a começar a entender e implementar o algoritmo A *.

Editar :

Um pensamento mais simples que me vem à cabeça é ... uma vez que você tenha o mundo em células de grade. Sempre, faça com que o ponto preto siga a distância de manhattan até o ponto verde. Em seguida, você pode atribuir pesos a cada célula. Os obstáculos podem ter um alto peso na célula da grade e o movimento livre pode (digamos) 0. À medida que você se move ao longo da distância de manhattan, para cada movimento, verifique se o peso da próxima célula não é maior que o peso da célula atual. Se for maior, verifique o peso da célula adjacente e siga em frente.

Espero que isto ajude

brainydexter
fonte
Este artigo sobre o algoritmo A * parece ser o que eu estava procurando, mas infelizmente o que ainda não sei é como dividir meu "mundo" em grades: S
user
Isso realmente depende. Pensamento: divida seu mundo em uma grade de 32 x 32, que representaria posições em uma matriz 2D. Por exemplo, no seu caso: o ponto vermelho é 120, 120 pixels (ou 120/32 x 120/32: 3,75 x 3,75) 3,75 x 3,75 representa uma posição na sua grade mundial (ou matriz 2D). Como matrizes são indexadas por números inteiros, você deseja apenas uma parte inteira. Assim, o ponto vermelho estaria em 3 x 3. Espero que isso ajude
brainydexter
18

Os comportamentos de direção são projetados para praticamente esse conjunto exato de problemas.

http://www.red3d.com/cwr/steer/

Basicamente, você combinaria o comportamento de evitar obstáculos com provavelmente o comportamento de busca ou busca. Essa página possui várias animações em java dos diferentes comportamentos e o que eles fazem. Existem várias implementações de código aberto de comportamentos de direção. Aqui está um.

Tetrad
fonte
Os comportamentos de direção são perfeitos para isso.
tenpn
2

Uma coisa fácil de tentar é ter um ponto invisível que vai à frente do ponto preto e executa o caminho na sua primeira imagem. O ponto preto segue o ponto invisível a uma pequena distância atrás.
Vi esse trabalho com bons resultados, mas é claro que pode não atender às suas necessidades.

Paulo Pinto
fonte