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:
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!
Respuestas:
¿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!
fuente
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.
fuente
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.
fuente
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.
fuente
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:
http://gamma.cs.unc.edu/research/crowds/
fuente
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
fuente