Mundo Maker
¡Bienvenid@ a Mundo Maker!

¿Quieres aprender todo sobre el RPG Maker?



Regístrate y forma parte de Mundo Maker.
Conectarse

Recuperar mi contraseña

Temas importantes
----------------------------------------
Páginas con recursos RPG Maker
----------------------------------------
----------------------------------------
----------------------------------------
----------------------------------------
----------------------------------------
----------------------------------------
----------------------------------------
----------------------------------------
----------------------------------------
Afiliados
Estadísticas
Tenemos 4064 miembros registrados.
El último usuario registrado es cesarseb233.

Nuestros miembros han publicado un total de 84098 mensajes en 11979 argumentos.

[IA en juegos] El problema del patrullaje

Ver el tema anterior Ver el tema siguiente Ir abajo

[IA en juegos] El problema del patrullaje

Mensaje por mrhawi el 2015-07-27, 20:25

Traigo otro tutorial interesante respecto a la inteligencia artificial en juegos. Como dije en mi post anterior donde expliqué teoría básica de IA utilizando como ejemplo Path Finding, ahora se me ocurrió explicar otro problema interesante conocido como el problema del patrullaje (Patrolling Problem, que denotaré como PP).

En el problema se consideran "r" agentes (donde r >= 1) y se debe encontrar una estrategia óptima para patrullar un entorno dado. Para encontrar esta estrategia, los agentes deberán cooperar para maximizar una cierta "función de utilidad".

Aplicaciones:

- Minijuegos en RPG Maker jeje y otro tipo de juegos.
- Juegos de Estrategia
- Patrullaje Militar
- Detección de Intrusos
- Cyber-Security
- Limpieza utilizando Robots
- Etc.

Primero que todo ¿qué significa una estrategia óptima? Idealmente nos gustaría que los sitios, o zonas de un entorno dado, sea visitadas frecuentemente y de forma "equitativa", para reducir el tiempo en que las zonas pasan sin ser inspeccionadas. También nos gustaría que el tiempo de exploración del entorno (en caso de que éste sea desconocido) sea el mínimo. En la literatura se propone utilizar como heurística una variable llamada "ociosidad" o "idleness" del entorno, que representa la cantidad de tiempo en que una zona ha estado sin ser inspeccionada. El entorno se puede representar como una matriz (por ejemplo, 0 si una zona en la coordenada x, y es atravesable, y otro número en caso contrario... Para aplicarlo en el Maker dependerá de la configuración del tileset).

Una descripción gráfica de esto:



Se considerará que cada cierto intervalo de tiempo el idleness aumentará (Se asumirá de momento que todos los agentes del entorno tienen la misma velocidad de movimiento).

Ahora discutiré dos enfoques, dos soluciones tradicionales (para el engineer experto pero que no quiere pensar más allá XD) y una solución un poco más sofisticada.

Rutas predefinidas (Solución tradicional):

Predefinir la ruta de cada agente, básicamente "harcodear".

Desventajas:

- Mucho tiempo para cranearse con rutas que funcionarán dependiendo del mapa (muchas restricciones)
- Solución poco amigable para el makero
- Problema para definir buenas rutas.

Random (Solución tradicional):

Esta estrategia se basa en que el agente verá las acciones que puede tomar y escogerá una al azar.

Desventajas:

- Carecerá de "inteligencia" el sistema.
- Podría haber movidas ridículas.
- La dificultad del minijuego podría decaer tanto que terminaría no siendo un reto para el jugador.
- No hay cooperación entre agentes.

Modelo EVAP (Solución con IA):

Este enfoque está basado en colonias de insectos. Básicamente, un agente deja un rastro al inspeccionar una zona, este rastro se conoce como "feromonas digitales". Un agente deja una cantidad Qmax de feromonas digitales al inspeccionar una zona. Las feromonas se van evaporando con el paso del tiempo, de forma exponencial, bajo la siguiente relación:

q(t + 1) = q(t) * [1 - rho]

donde 0 < rho < 1; Para el propósito de la experimentación que se muestra más adelante, se consideró Qmax = 30, y rho = 0.001 (Ya que se obtienen buenos resultados según la literatura).

Finalmente, el agente utiliza la cantidad de feromonas que puede percibir a su alrededor para escoger la siguiente acción, pues las feromonas darán un indicio del "idleness" en una vecindad. Entonces el agente escogerá la acción que lo lleve al lugar donde haya menor cantidad de feromonas, pues esto es un indicio de que el lugar lleva mayor tiempo sin visitarse que el resto de la vecindad. En caso de "empates" se tomará una acción aleatoria, agregando una componente estocástica al método.

El algoritmo es el siguiente:



Ventajas:

- Simple implementación (En maker se podría implementar hasta con engines; dolor de cabeza en este caso)
- Aprovecha el conocimiento de otros agentes para mejorar el rendimiento de la exploración.
- Estrategia relativamente simple que no tiene un costo alto computacionalmente (Complejidad O(r + M*N); dependerá de las dimensiones del mapa y la cantidad de agentes)
- Logra resolver el problema de forma inteligente

Desventajas:

- Tiene problemas con algunos "loops" en laberintos.

Comparación entre enfoques:

Ahora se muestra un vídeo para ver en acción lo explicado:



Idleness Promedio del Entorno


"Iteraciones" para explorar un mapa


"Temperatura" para visualizar el idleness en el entorno:



Los resultados indican que el algoritmo permite resolver de forma eficiente el problema.

Y bueno, ese sería mi aporte de hoy.

saludos

mrhawi
Aventurero
Aventurero

0/3

Créditos 2668

Gracias : 89

Volver arriba Ir abajo

Re: [IA en juegos] El problema del patrullaje

Mensaje por 4ngel el 2015-07-28, 20:07

A pesar de que sea más lento y un dolor de cabeza, prefiero crear las rutas, aunque una vez que el jugador le pille el truco dejará de tener complejidad alguna.

Quizás haga algunas pruebas, a ver si cambio de idea rolleyes

Gracias por compartir esto.
avatar
4ngel
Principiante
Principiante

0/3

Créditos 123

Gracias : 18

http://xhystr.com

Volver arriba Ir abajo

Re: [IA en juegos] El problema del patrullaje

Mensaje por mrhawi el 2015-07-29, 01:56

Así es, hay veces en que se pueden aplicar rutas, cuando se tiene la intención de dar un patrón. En ese caso, quizás es mejor elección ese método.

Mi intención es sólo mostrar diferentes alternativas que podrían aplicarse y que no tienen una gran complejidad, porque podría agregar elementos interesantes a la jugabilidad. Lo genial es que uno puede cambiar el mapa y no tiene que rehacer todas las rutas.

Ahí si lo implementas lo muestras :).

saludos!

mrhawi
Aventurero
Aventurero

0/3

Créditos 2668

Gracias : 89

Volver arriba Ir abajo

Re: [IA en juegos] El problema del patrullaje

Mensaje por Contenido patrocinado


Contenido patrocinado


Volver arriba Ir abajo

Ver el tema anterior Ver el tema siguiente Volver arriba


Permisos de este foro:
No puedes responder a temas en este foro.