2012-01-22 26 views
5

Estoy escribiendo un juego para iOS (usando UIView), que tiene una ciudad en 2D generada aleatoriamente. Necesito atacar a A.I., que tomará un camino inteligente para encontrar al jugador (sin colisionar con los edificios). ¿Puede alguien señalarme en la dirección correcta qué tipo de algoritmos usaría para lograr esto?A.I. que puede navegar una ciudad en 2D generada aleatoriamente

Editar: He decidido usar A *. Crearé una cuadrícula en el mapa, probaré cada punto de intersección de la cuadrícula, si ese punto está dentro de un edificio, invalidaré el punto. El ataque A.I. el jugador se moverá desde su ubicación actual a un punto de cuadrícula válido, que está más cerca de su objetivo (dentro de un cierto radio de su ubicación).

+0

Votación para cerrar como herramienta rec/a amplia. –

Respuesta

7

Está buscando una clase de algoritmos llamada pathfinding algorithms. Hay muchos enfoques que puede usar.

Los algoritmos clásicos aquí son Dijkstra's algorithm y A* search, que pueden guiar un objeto de un lugar a otro a lo largo de la ruta óptima. Estos algoritmos funcionan modelando el mundo 2D como graph y luego encuentran la ruta más corta desde la ubicación de inicio del objeto hasta la ubicación de destino en ese gráfico. Estos dos algoritmos se usan ampliamente en IA y pathfinding, y le sugiero encarecidamente invertir el tiempo para leer más sobre ellos. Hay un solid tutorial on A* search disponible en línea si lo desea.

Si tiene muchos objetos diferentes que necesitan moverse a un objetivo sin interferir, puede buscar campos potenciales, que ofrecen un marco simple y flexible para tener múltiples objetos acercarse a un objetivo. Este enfoque fue utilizado por the Berkeley "Overmind" StarCraft AI, y se usa a menudo en la planificación de movimiento de robots. Intuitivamente, este enfoque funciona asignando un valor "potencial" a cada ubicación, luego haciendo que los objetos se muevan de un potencial alto a un potencial bajo hasta que lleguen al objetivo. Este enfoque es un poco más complicado para hacer las cosas bien, pero una vez que funciona, tiende a llevar a una IA flexible y personalizable que se comporta de manera inteligente.

Espero que esto ayude!

+0

+1, muy informativo – DGund

2

Esta pregunta aquí: Pacman: how do the eyes find their way back to the monster hole? es una buena encuesta de aproximaciones a la navegación AI de una cuadrícula 2D aleatoria en busca de un jugador en movimiento. El consenso general (y el enfoque utilizado por Pacman) es no preocuparse por hornear algoritmos inteligentes de ruta en la IA, sino utilizar el mapa en sí para almacenar información sobre la ubicación del jugador. Es una lectura fascinante, particularmente la segunda y la tercera respuesta (y sus enlaces externos) por ammoQ y Dan Vinton.

Este enlace aquí Pacman scent antiobject pattern describe un enfoque económico y eficaz.

+0

Aunque estoy de acuerdo en que este es un buen enfoque, si el mundo se genera de forma aleatoria, entonces no se puede codificar nada en el mundo y será necesario utilizar algoritmos más complejos para realizar la ruta inicial. Esto tampoco funcionará si el jugador se mueve constantemente a menos que almacene un * lote * de información adicional. – templatetypedef

+0

Lo siento @templatebydef, estaba refiriendo al interrogador a los enlaces segundo y tercero en lugar de la solución existente de la pregunta vinculada o la respuesta aceptada, que en verdad sufren los problemas que usted señala. He actualizado mi pregunta con un enlace al enfoque interesante que quiero que vea el OP. –

Cuestiones relacionadas