Implementación de colisión 100% evitada

21

Soy un principiante absoluto con el desarrollo de juegos y todo lo que sé sobre cómo evitar / resolver colisiones, lo aprendí en este sitio o a través de él la semana pasada ... así que no dude en corregirme si lo que pregunto aquí es basado en suposiciones erróneas / malentendidos. Hice todo lo posible para ser claro, pero dicho esto, el tema aún es nuevo para mí.

Vehículos

En mi juego, tengo vehículos que se mueven de forma autónoma. Se colocan en un espacio 3D y su movimiento se rige por una serie de variables que son diferentes para cada vehículo. Los de interés aquí son principalmente:

  • Solo movimiento hacia adelante .
  • Una velocidad que puede variar entre min y max, pero cuyo min no es (incluso cercano a) cero.
  • Un radio de dirección que depende de la velocidad (a mayor velocidad, mayor radio)
  • Dos aceleraciones máximas (para disminuir y aumentar la velocidad)

Gol

Mi objetivo es implementar algún tipo de IA que evite la colisión al 100% (es decir, estaré seguro de que los vehículos nunca colisionarán).

Diseño

  • Aunque preferiría más la idea de tener la IA "a bordo" (es decir, cada vehículo tiene su propia "IA para evitar colisiones", eventualmente consultar y / o enviar mensajes a otros vehículos) también es posible para mí implementar la CA AI en un nivel central (envío de comandos a los vehículos).
  • En la mayoría de los casos, el vehículo simplemente tendrá que alejarse unos de otros en cualquier dirección, pero en ciertas circunstancias, deberán evitar la colisión y dirigirse hacia el mismo objetivo.

Lo que encontré hasta ahora y dónde me quedé atrapado

Dentro de los muchos enlaces que encontré en otras preguntas en este mismo sitio, encontré de uso particular estos:

  1. Colisión entre bolas de billar
  2. Evitar colisiones no alineadas
  3. Haciendo cola

Si bien estos tres enlaces "me abrieron los ojos" de muchas maneras, no tengo claro de inmediato cómo usar esa información en mi caso. En particular, el artículo # 2 solo "intenta" prevenir la colisión (pero las colisiones ocurren de vez en cuando). Si bien el artículo 3 debe detener los vehículos a veces para evitar colisiones.

Lo que también noté es que los algoritmos para evitar colisiones vinculados anteriormente usan una "proyección instantánea" de velocidad lineal para verificar si algo está en camino del vehículo. Me preguntaba si esto es suficiente en mi caso o si tuve que proyectar mi posición de una manera más realista (por ejemplo: si tengo 60 ° en una dirección de 90 ° a la derecha, debo calcular mi posición para el resto del tiempo). 30 ° de la curva, y luego asumiendo un movimiento lineal).

Finalmente, tengo mucho miedo a los callejones sin salida . En otras palabras: aunque la densidad de vehículos en el mundo será bastante baja, me preocupa que, dado un cierto número de vehículos que convergen hacia el mismo punto, una vez que se den cuenta de que están en curso de colisión, cualquier maniobra evasiva será imposible ya que traería el vehículo en un camino de colisión con algunos otros.

Pregunta

¿Cómo puedo alcanzar mi "objetivo"? Una explicación en profundidad es, por supuesto, muy apreciada, pero los enlaces a recursos externos también serían de gran ayuda (estoy seguro de que no soy el primero en este problema, pero ¿probablemente utilicé las palabras clave incorrectas para buscar en la web? )

¡Gracias de antemano por su ayuda!

Mac
fuente
20
Haga que todos los vehículos se detengan. 100% de evitación lograda.
Martin Sojka
2
Es suficiente si se detienen uno con respecto al otro. Es decir, todos se mueven exactamente en la misma dirección, exactamente a la misma velocidad. El mayor problema es que es (probablemente) IMPOSIBLE lograr cualquier algoritmo que lo haga al 100% para cada configuración posible. Por ejemplo, considere dos vehículos con radios de giro muy grandes a una distancia mínima no igual a cero entre sí, volando entre sí con la velocidad máxima.
Martin Sojka
12
@mac: una cosa a tener en cuenta al desarrollar este algoritmo es que es un juego. Si pasa demasiado tiempo tratando de resolver este problema, tal vez esté tratando de resolver el problema incorrecto. Puede hacer trampa: mover vehículos o violar sus reglas de manejo si detecta una situación difícil, especialmente si el jugador no puede verla. Asegúrese de que las reglas de manejo del vehículo que se le ocurran no resulten aburridas, es más importante ser entretenido que tener la razón.
Voltear el
3
@mac Bueno, probablemente usaría un controlador global con A *. Sé que quería mantenerse alejado de esta solución, pero tiene más sentido ya que tiene una visión global de los vehículos y puede calcular previamente las rutas. También es posible que desee dar prioridad a los vehículos (el que está más cerca del objetivo obtiene una prioridad más alta, por lo que su ruta permanece sin cambios y otros cambian de ruta a su alrededor).
Jonathan Connell
66
@Flip Un simulador de vuelo todavía se considera un juego, pero si 'engañaste', rompería el juego para cualquier jugador que se diera cuenta de esto.
Jonathan Connell

Respuestas:

5

¿Has investigado los algoritmos de flocado ? Cuando miro tu descripción, eso es lo que me viene a la mente. Hay muchos artículos para esto, aquí hay uno que me gusta . Probablemente no usará todos los aspectos del flocado, como la cohesión. La mayoría de los aspectos serían útiles para lo que está tratando de hacer, como la alineación y la separación, los cuales ayudarían a evitar colisiones. Terminarías con algo un poco diferente a la congregación, pero debería ayudarte a comenzar.

¡Buena suerte!

MichaelHouse
fuente
2
El término de búsqueda relevante aquí es Boids . Sin embargo, no creo que esto sea lo que OP estaba buscando: parece que quiere que los autos funcionen en todas direcciones.
BlueRaja - Danny Pflughoeft
El agrupamiento todavía se trata de que la IA evite la colisión entre ellos.
Matt Jensen el
OP pide evitar colisiones de manera confiable. El agrupamiento no ofrece garantías, ya que el modelo basado en la fuerza no incorpora restricciones duras. Aunque la congregación es seguramente un buen punto de entrada para entrar en el tema, la respuesta está, por lo tanto, fuera de lugar. Sugiero que el OP busque "obstáculos de velocidad" en su lugar.
Tobias Gurdan
@TobiasGurdan Si tiene una respuesta más apropiada (y estoy de acuerdo en que sí), debe crear una respuesta.
MichaelHouse
3

Aquí hay un enfoque: cada vehículo tiene una ruta proyectada corta donde el vehículo al final se ralentiza y entra en un bucle, estas rutas pueden no superponerse. Cada vez que un vehículo llega al punto en el que está configurado para reducir la velocidad, intenta generar una nueva ruta que no se superponga con ninguna de las existentes. Si no se encuentra que sea posible, el vehículo continúa en el camino dado y reintenta realizar un nuevo camino periódicamente.

El método podría mejorarse para permitir un tráfico más estrecho al permitir que las rutas que conducen a los bucles se superpongan entre sí y los bucles donde se pueda determinar que esto no causará una colisión.

aaaaaaaaaaaa
fuente
0

Tenga un método en cada vehículo donde realice una búsqueda radial a su alrededor, si hay otros vehículos dentro de este radio, aléjese de una manera adecuada a su gusto: 1) Muévase en el vector opuesto, 2) disminuya la velocidad, 3) acelerar, etc.

Incluso puede hacer combinaciones: si el vector del otro vehículo no está recto o directamente detrás: aléjese; de lo contrario, si está todo recto: disminuya la velocidad; De lo contrario: acelerar.

Casey
fuente
0

Mi objetivo es implementar algún tipo de IA que evite la colisión al 100% (es decir, estaré seguro de que los vehículos nunca colisionarán).

Si esto fuera posible, ya se habría puesto en todos los aviones del mundo.

Sugiero relajar el aspecto 'autónomo' y tener una función que resuelva las colisiones previstas entre 2 (o más) vehículos. Puede ser tan ingenuo como elegir nuevas direcciones aleatorias para viajar y ver si eso resuelve el problema, pero lo importante es que la función solo regresa cuando se llega a un acuerdo que se adapta a ambos vehículos.

También sugiero que cualquier vehículo que se prediga que colisionará en el futuro cercano reduce su velocidad mientras mantiene la misma distancia de anticipación; esto le dará a sus vehículos más oportunidades para evitar colisiones, al igual que en la vida real.

Kylotan
fuente
Como está diseñando las reglas del universo, es absolutamente posible. El mundo real es obviamente más complicado, pero estoy seguro de que los aviones del mundo real utilizan un montón de técnicas para evitar colisiones ...
BlueRaja - Danny Pflughoeft
0

Me parece que la simulación de multitudes podría ser el tema más relevante para lo que estás tratando de lograr. El grupo GAMMA de UNC tiene una gran cantidad de trabajo sobre el tema que vale la pena analizar. Su descripción:

La simulación de multitudes y agentes múltiples es el proceso de simular un gran número de personas, criaturas u otros personajes, cada uno interactuando en un entorno. Se espera que estos actores se muevan hacia sus objetivos, interactúen con su entorno y se respondan unos a otros. Las simulaciones de multitudes tienen muchos usos, incluida la mejora de la planificación arquitectónica, los entornos de entrenamiento y las realidades virtuales, y la conducción de personajes artificialmente inteligentes (IA) en juegos y películas. Nuestro grupo ha trabajado en muchos problemas en la simulación de multitudes, incluyendo la prevención rápida y garantizada de colisiones, la planificación de rutas y movimientos en tiempo real, los flujos de multitudes y los comportamientos dirigidos.

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

user_123abc
fuente
-1

No creo que haya un método de evasión del 100%, pero si sus vehículos poseen información mundial completa, podrían encerrar cada vehículo en una caja cuya longitud dependa de su velocidad y realizar una verificación de colisión en esas cajas. Si efectivamente hay una colisión, aléjese, con una fuerza que dependa de la inminencia del impacto (o el área de la colisión entre las dos cajas), y disminuya lentamente (pero mantenga su caja del mismo largo durante la operación de evitación).

Obviamente, esto no funcionará si los vehículos no poseen información completa, pero en este caso nada garantizará una evasión del 100% (excepto, como ya se dijo, movimiento paralelo)

algunos métodos descritos aquí probablemente serían útiles, especialmente este: Comportamiento de dirección para evitar colisiones sin alinear

Saludos

PATRY Guillaume
fuente
1
¿Leíste la pregunta original? Ese enlace que recomendó ya está en la pregunta ...
bummzack