algorithm - Mueve indefinidamente objetos al azar sin colisión
meta tags seo 2018 (5)
Tengo una aplicación en la que necesito mover una cantidad de objetos alrededor de la pantalla de forma aleatoria y no pueden toparse entre sí. Estoy buscando un algoritmo que me permita generar las rutas que no crean colisiones y pueden continuar por un tiempo indefinido (es decir, los objetos siguen moviéndose hasta que un evento dirigido por el usuario los elimina del programa).
No soy un programador de juegos, pero creo que esto parece un problema de IA y ustedes probablemente lo resuelvan con los ojos cerrados. Por lo que he leído, A * parece ser la "idea básica" recomendada, pero realmente no quiero invertir mucho tiempo en ella sin una confirmación.
¿Alguien puede arrojar algo de luz sobre un enfoque? ¿Movimiento antigravedad tal vez?
- Esto se implementará en iOS, si eso es importante
- Se deben generar nuevas rutas al final de cada ruta
- No hay ''rejilla'' visible. El movimiento es completamente libre en el espacio 2D.
- Los objetos son insectos que caminan alrededor de la pantalla hasta que son matados.
¡No puede planear las trayectorias antes de tiempo por una duración indefinida!
Sugiero un enfoque más simple en el que solo predice la próxima colisión (conocer las posiciones y velocidades de los objetos le permite saber si van a chocar y cuándo), y resolverlo cambiando la velocidad o la dirección de cualquiera de los objetos (rebotar antes de que los objetos se toquen). ).
¡Asegúrese de rehacer un cheque por colisiones en caso de que haya creado una colisión aún anterior!
El verdadero desafío en su caso es predecir de manera eficiente las colisiones entre numerosos objetos, a priori una tarea O (N²). Acelerará eso mediante la superposición de una cuadrícula gruesa en el campo de juego y verá los objetos en las celdas vecinas solamente.
También puede ser posible mantener una lista de pares de objetos que "podrían interferir en algún futuro" (es decir, considerando su distancia y velocidad relativa) y mantenerla actualizada. Comprobar que una pareja puede abandonar la lista es relativamente fácil; La verificación eficiente de nuevos pares que necesitan ingresar a la lista no lo es.
Considere un ciclo hamiltoniano : la idea es una ruta que visita todas las posiciones en una cuadrícula una vez (y solo una vez). Si construyes el ciclo por adelantado (es decir, lo calculas con anticipación), y configuras a los insectos con algún desplazamiento entre ellos, nunca colisionarán, simplemente porque el camino nunca se cruza.
Además, para los puntos de bonificación, las rutas hamiltonianas tienden a ''moverse'' y, como es un bucle, se puede predecir (y precalcular) la ruta hacia el futuro indefinido.
Siempre puede usar los nodos de la cuadrícula como puntos de nudo para una spline para suavizar el movimiento, o incluso desplazar aleatoriamente todos los puntos desde sus estrictas posiciones de cuadrícula 2D, hasta que tenga el movimiento deseado.
Ejemplo de ciclo hamiltoniano de Wikimedia:
En una nota al margen, si desea generar una ruta de este tipo, considere construir un bucle a través de muchos puntos y simplemente mover los puntos alrededor de tal manera que nunca se crucen con un borde existente. Con algo de estímulo para moverse dentro de los huecos y alejarse unos de otros, deberían establecerse en algún camino largo y que nunca se cruce. Almacene el resultado y utilícelo para su bucle.
Mira this y this que describió un programa de IA para reproducir automáticamente el juego de Mario.
Entonces, en este enlace, lo que el autor hizo fue usar un algoritmo A * star para guiar a Mario Get to the right border of the screen as fast as possible. Avoid being hurt. Get to the right border of the screen as fast as possible. Avoid being hurt.
Así que la idea es para cada período de tiempo, tendrá un entorno que describa la posición actual de otros objetos en la escena y para cada acción (arriba, abajo a la izquierda, a la derecha y no hacer nada), calcula su función de costo y toma una decisión. Del siguiente movimiento basado en esto.
Fuente: http://www.quora.com/What-are-the-coolest-algorithms
Para A * necesitaría una cuadrícula 2D incluso si no está visible. Si entiendo bien tu idea, podrías hacer lo siguiente.
Implemente un pathfinding (por ejemplo, A *) luego genere puntos de destino aleatorios en la pantalla y calcule la ruta. Una vez que el insecto llegue al destino, genere otro punto de destino / celda de la cuadrícula y proceda hasta que el insecto muera.
Como lo veo, A * solo tendría sentido si tienes obstáculos en la pantalla por los que el insecto debería navegar, de lo contrario sería suficiente calcular una trayectoria de vector recto y tal vez manejar la colisión con otros insectos / objetos.
Nota: A* vez implementé A* , luego descubrí que el algoritmo de Lee hace lo mismo pero fue más fácil de implementar.
A* es un algoritmo para encontrar la ruta más corta entre una configuración de inicio y una de objetivo (en términos de lo que usted define como corto: comunes son, por ejemplo, distancia, costo o tiempo euclidiano, distancia angular ...). Sus insectos parecen no tener un objetivo específico, ni siquiera necesitan un camino más corto. Ciertamente no iría por A* . (Por cierto, dado que está teniendo un entorno dinámico, D* habría sido una idea, aún así está destinado a encontrar un camino de A a B).
Abordaría el problema de la siguiente manera:
Rutas aleatorias y siguiendolas
Para los caminos al azar veo dos métodos. El primero sería una caminata aleatoria simple ( haga clic aquí para ver una animación en 2D agradable con explicaciones ), que puede sufrir fluctuaciones y no se ve muy bien. El segundo necesita explicaciones un poco más detalladas.
Para cada insecto, genere cuatro puntos aleatorios alrededor de ellos, tal vez comenzando en una sinusoide. Con una interpolación spline se genera una curva suave entre esos puntos. Tenga cuidado de tener continuity C1 (en 2D) o C2 (en 3D). (Sugerencia: splines Hermite ) Con las splines Catmull-Rom puede encontrar sus configuraciones mientras se mueve a lo largo de la curva.
Una aplicación de un enfoque similar se puede encontrar en esta publicación del blog sobre pistas de carreras de procedimientos , y también se puede encontrar una explicación más técnica (pero aún no demasiado técnica) en estas diapositivas antiguas (pdf) de un curso de animaciones por computadora.
Cuando un insecto comienza a moverse, puede moverse constantemente entre el segundo y el tercer punto, cuando siempre quita el primero y agrega un nuevo punto cuando el insecto llega al tercero, lo que lo convierte en el segundo punto.
If third point is reached
Remove first
Append new point
Recalculate spline
End if
Para una curva más suave, agregue más puntos en total y muévase en algún lugar en el medio, el principio sigue siendo el mismo. (Personalmente, solo utilicé esto en entornos fijos, también debería funcionar en entornos dinámicos).
Esto puede, si su generación de puntos aleatorios es buena (tal vez puede usar un enfoque similar al proporcionado en la publicación del blog vinculado anterior, o echar un vistazo a los algoritmos en el PCG Wiki ), lo que conduce a caminos suaves en toda la pantalla.
Evitar otros insectos
Para evitar otros insectos, tres métodos diferentes vienen a mi mente.
- Algoritmos de error
- Vehículos braitenberg
- Una aplicación de campos potenciales.
Para los campos potenciales, recomiendo leer este documento sobre la planificación dinámica del movimiento (pdf) . Es de la robótica, pero también bastante fácil de aplicar a su problema. Puede usar el siguiente punto de spline de los robots como objetivo y establecer su velocidad en 0 para aplicar este enfoque. Sin embargo, podría ser demasiado para tu juego simple.
Una discusión de los vehículos Braitenberg se puede encontrar aquí (pdf) . La idea original era más bien un método técnico (conducir hacia o lejos de una fuente de luz dependiendo de cómo está acoplado su motor con el receptor fotográfico) y se usa a menudo para mostrar cómo aplicamos conceptos emocionales como el miedo y la atracción a otros objetos. El comportamiento del "miedo" es un enfoque utilizado para evitar obstáculos en la robótica.
El tercer método, y probablemente el más simple, son los algoritmos de error (pdf) . Siempre tengo problemas con los límites siguientes, lo cual es un poco complicado. Pero para evitar otro insecto, estos algoritmos, sin importar cuál uses (sugiero el Bug 1 o Tangent Bug), deberían hacer el truco. Son muy simples: avanza hacia tu objetivo (en esta aplicación con las splines catmull-rom) hasta que tengas un obstáculo al frente. Si el obstáculo está cerca, cambie el estado del insecto a "evitación de obstáculos" y ejecute su algoritmo de error. Si les da a los dos insectos "en colisión" la misma dirección de giro, automáticamente se rodearán y seguirán su camino original.
Como una variación, podría simplemente dejarlos girar y volver a calcular una nueva spline a partir de ese momento.
Conclusión
La búsqueda de caminos y la generación de caminos aleatorios son cosas diferentes. Tienes que experimentar en torno a lo que se ve mejor para tus insectos. Definitivamente, A * está diseñado para encontrar rutas más cortas, no para crear rutas aleatorias y seguirlas.