Implementação de prevenção de colisão a 100%

21

Eu sou um iniciante absoluto no desenvolvimento de jogos e, tudo o que sei sobre prevenção / resolução de colisões, aprendi no ou através deste site na semana passada ... então não hesite em me corrigir se o que estou perguntando aqui é com base em suposições erradas / mal-entendidos. Eu tentei o meu melhor para ficar claro, mas, dito isso, o assunto ainda é novo para mim.

Veículos

No meu jogo, tenho veículos que se movem autonomamente. Eles são colocados em um espaço 3D e seu movimento é governado por várias variáveis ​​diferentes para cada veículo. Os de interesse aqui são principalmente:

  • Apenas movimento para frente .
  • Uma velocidade que pode variar entre min e max, mas cujo min não é (nem próximo de) zero.
  • Um raio de direção dependente da velocidade (quanto maior a velocidade, maior o raio)
  • Duas acelerações máximas (para diminuir e aumentar a velocidade)

Objetivo

Meu objetivo é implementar algum tipo de IA que evite colisões com 100% de precisão (ou seja, vou ter certeza de que os veículos nunca colidirão).

desenhar

  • Embora eu prefira mais a idéia de ter a IA "onboard" (ou seja, cada veículo com sua própria "AI de prevenção de colisão", eventualmente consultando e / ou enviando mensagens para outros veículos), também é possível implementar o CA AI em um nível central (despachando comandos para os veículos).
  • Na maioria dos casos, o veículo simplesmente terá que se afastar um do outro em qualquer direção, mas sob certas circunstâncias, eles terão que evitar colisões e seguir em direção ao mesmo alvo.

O que encontrei até agora e onde fiquei preso

Dentro dos muitos links que encontrei em outras perguntas neste site, achei particularmente útil os seguintes:

  1. Colisão entre bolas de bilhar
  2. Prevenção de colisão não designada
  3. Filas

Embora esses três links "tenham aberto meus olhos" de várias maneiras, não está claro para mim como usar essas informações no meu caso. Em particular, o artigo 2 apenas "tenta" evitar colisões (mas as colisões acontecem de tempos em tempos). Embora o artigo # 3 precise às vezes parar os veículos para evitar colisões.

O que eu também notei é que os algoritmos de prevenção de colisão vinculados acima usam uma "projeção instantânea" de velocidade linear para verificar se algo está a caminho do veículo. Eu queria saber se isso é suficiente no meu caso ou se eu tenho que projetar minha posição de uma maneira mais realista (por exemplo: se eu estiver 60 ° em uma direção 90 ° para a direita, devo calcular minha posição pelo resto do 30 ° da curva e assumindo movimento linear).

Finalmente, estou particularmente com medo de impasses . Em outras palavras: embora a densidade de veículos no mundo seja bastante baixa, estou preocupado que, dado um certo número de veículos convergindo para o mesmo ponto, uma vez que eles percebam que estão em rota de colisão, qualquer manobra evasiva seja impossível. pois traria o veículo em um caminho de colisão com alguns outros.

Questão

Como posso alcançar meu "objetivo"? Uma explicação detalhada é, obviamente, muito apreciada, mas os links para recursos externos também seriam de grande ajuda (tenho certeza de que não sou o primeiro com esse problema, mas provavelmente usei as palavras-chave erradas para pesquisar na web? )

Agradeço antecipadamente por sua ajuda!

Mac
fonte
20
Faça com que todo veículo pare. 100% de evitação alcançada.
Martin Sojka
2
É o suficiente se eles param em relação um ao outro. Ou seja, todos eles se movem exatamente na mesma direção, exatamente na mesma velocidade. O maior problema é que é (provavelmente) impossível obter qualquer algoritmo que o faça a uma taxa de 100% para todas as configurações possíveis. Por exemplo, considere dois veículos com raios de viragem muito grandes a uma distância mínima igual a zero um do outro, voando entre si com velocidade máxima.
Martin Sojka
12
@mac - Uma coisa a ter em mente ao desenvolver esse algoritmo é que é um jogo. Se você está gastando muito tempo tentando resolver esse problema, talvez esteja tentando resolver o problema errado. Você pode trapacear - mover veículos ou violar suas regras de manuseio se detectar uma situação difícil, especialmente se o jogador não puder vê-la. Certifique-se de que as regras de manuseio de veículos que você cria não acabem parecendo chatas, é mais importante ser divertido do que estar certo.
Virar
3
@mac Bem, eu provavelmente usaria um controlador global com A *. Sei que você queria ficar longe dessa solução, mas faz mais sentido, pois tem uma visão global dos veículos e pode pré-calcular os caminhos. Você também pode colocar uma prioridade nos veículos (o mais próximo ao alvo recebe uma prioridade mais alta, portanto o caminho permanece inalterado e outras pessoas o redirecionam em torno dele).
22811 Jonathan Connell
6
@Flip Um simulador de vôo ainda é considerado um jogo, mas se você 'trapaceou', isso quebraria o jogo para qualquer jogador que percebesse isso.
22411 Jonathan Connell

Respostas:

5

Você já olhou para algoritmos de agrupamento ? Quando olho para a sua descrição, é isso que me vem à mente. Existem muitos artigos para isso, eis um que eu gosto . Provavelmente você não usará todos os aspectos do flocagem, como a coesão. A maioria dos aspectos seria útil para o que você está tentando fazer, como alinhamento e separação, os quais ajudariam a evitar colisões. Você acabaria com algo um pouco diferente de se reunir, mas isso deve ajudá-lo a começar.

Boa sorte!

MichaelHouse
fonte
2
O termo de pesquisa relevante aqui é Boids . No entanto, eu não acho que é isso que o OP estava procurando - parece mais que ele quer carros indo de todas as formas.
BlueRaja - Danny Pflughoeft
Flocagem ainda é sobre a IA, evitando colisões entre si.
Matt Jensen
O OP pede uma prevenção confiável de colisões. O flocagem não oferece garantias, pois o modelo baseado em força não incorpora restrições rígidas. Embora o agrupamento seja certamente um bom ponto de entrada para entrar no tópico, a resposta é, portanto, equivocada. Sugiro que o OP procure "obstáculos de velocidade".
Tobias Gurdan
@TobiasGurdan Se você tiver uma resposta mais apropriada (e eu concordo que sim), crie uma resposta.
MichaelHouse
3

Aqui está uma abordagem: todo veículo possui um caminho curto projetado, onde o veículo no final diminui a velocidade e entra em um loop, esses caminhos podem não se sobrepor. Sempre que um veículo chega ao ponto em que está definido para abrandar, você tenta gerar um novo caminho que não se sobreponha a nenhum dos existentes. Se isso não for possível, o veículo continua no caminho indicado e tenta fazer um novo caminho periodicamente.

O método pode ser aprimorado para permitir tráfego mais restrito, permitindo que os caminhos que levam aos loops se sobreponham e loops, onde é possível determinar que isso não causará uma colisão.

aaaaaaaaaaaa
fonte
0

Tenha um método em cada veículo em que ele faça uma pesquisa radial em torno de si; se houver outros veículos dentro desse raio, afaste-se da maneira que você mais gosta: 1) Mova-se no vetor oposto, 2) diminua a velocidade, 3) acelerar, etc.

Você pode até fazer combinações: Se o vetor do outro veículo não estiver diretamente à frente ou diretamente atrás: afaste-se; caso contrário, se for sempre em frente: diminua a velocidade; mais: acelerar.

Casey
fonte
0

Meu objetivo é implementar algum tipo de IA que evite colisões com 100% de precisão (ou seja, vou ter certeza de que os veículos nunca colidirão).

Se isso fosse possível, já teria sido colocado em todas as aeronaves do mundo.

Sugiro relaxar o aspecto 'autônomo' e ter uma função que resolva colisões previstas entre 2 (ou mais) veículos. Pode ser tão ingênuo quanto escolher novas direções aleatórias para viajar e ver se isso resolve o problema, mas o importante é que a função só retorne quando for alcançado um acordo que atenda aos dois veículos.

Sugiro também que qualquer veículo que se previna colidir em um futuro próximo reduz sua velocidade, mantendo a mesma distância antecipada - isso dará aos seus veículos mais oportunidades para evitar colisões, assim como na vida real.

Kylotan
fonte
Desde que ele está projetando as regras do universo, é absolutamente possível. O mundo real é obviamente mais complicado, mas tenho certeza de que as aeronaves do mundo real usam uma tonelada de técnicas para evitar colisões ...
BlueRaja - Danny Pflughoeft
0

Parece-me que a simulação de multidão pode ser o tópico mais relevante para o que você está tentando alcançar. O grupo GAMMA da UNC tem um grande corpo de trabalho sobre o assunto que vale a pena examinar. A descrição deles:

A simulação de multidões e multi-agentes é o processo de simular um grande número de pessoas, criaturas ou outros personagens, cada um interagindo em um ambiente. Espera-se que esses atores sigam seus objetivos, interajam com o ambiente e respondam um ao outro. As simulações de multidões têm muitos usos, incluindo a melhoria do planejamento arquitetural, a melhoria dos ambientes de treinamento e das realidades virtuais, e condução de personagens artificialmente inteligentes (IA) em jogos e filmes. Nosso grupo trabalhou em muitos problemas na simulação de multidões, incluindo rapidez, garantia, prevenção de colisões, planejamento de trajetos e movimentos em tempo real, fluxos de multidões e comportamentos direcionados.

http://gamma.cs.unc.edu/research/crowds/

user_123abc
fonte
-1

Eu não acho que exista um método de evasão de 100%, mas se os veículos possuírem informações completas sobre o mundo, você poderá colocar cada veículo em uma caixa cujo comprimento depende da velocidade e executar uma verificação de colisão nessas caixas. Se houver realmente uma colisão, afaste-se, com uma força que depende da iminência do impacto (ou da área da colisão entre as duas caixas) e do fluxo lento (mas mantenha sua caixa do mesmo comprimento durante a operação de prevenção).

Obviamente, isso não funcionará se o veículo não possuir informações completas, mas neste caso nada garantirá 100% de evasão (exceto, como já foi dito, movimento paralelo)

alguns métodos descritos aqui provavelmente seriam úteis, notadamente este: Comportamento desalinhado da direção para evitar colisões

Saudações

PATRY Guillaume
fonte
1
Você leu a pergunta original? Esse link você recomendou já está na pergunta ...
bummzack