Noticias

Importante: ¡Si quieres publicar tu juego no olvides leer este tema!

Comunidad Game Maker

Bienvenid@ a la comunidad hispana de Game Maker. Nuestro objetivo es crear videojuegos y dar soporte en castellano de GM. Para mejorar nuestro servicio hemos implantado, como adicion al reglamento general, algunas normas especificas en los subforos más comunes. ¡No olvides informarte antes de participar!.

Autor Tema: Problema con recursividad  (Leído 178 veces)

0 Usuarios y 1 Visitante están viendo este tema.

Desconectado BssString

en: Marzo 25, 2020, 06:34:38 am
Estimados

Tengo un problema místico con un juego de estrategia de construcción. Quizás el problema parezca simple, pero no me funciona el código.
Estoy realizando un código de recursividad que correrá en mi IA al inicio del juego.

La idea es simple:
El robot puede gastar sus recursos para construir edificios, y si se queda sin recursos, tendrá que esperar para seguir construyendo.

No quiero que los bots suban los edificios al azar, quiero que cada bot tenga una personalidad diferente que le haga llevar ciertos edificios diferentes a cierto nivel y le de "señales" al player de la estrategia que está tomando para que el player pueda arruinar su estrategia o perecer en el intento.

La idea es que el robot calcule cuál es el orden en el que debe subir sus edificios para reducir al máximo el tiempo de construcción. Algunos edificios aumentan la producción en un monto fijo, otros la aumentan la producción de forma porcentual y otros reducen el tiempo de creación de los edificios.

Para programar la estrategia del robot, usé un sistema de "nodos" o "ramas" de decisión. El robot toma todas las decisiones posibles al mismo tiempo en todos los órdenes de construcción posibles y luego compara el tiempo que se demoró en subir TODOS los edificios por los diferentes caminos y elije el menor.

Al menos esa es la teoría, porque en la práctica Game Maker me arroja un error en la iteración número 32 diciendo que no puedo usar un sistema recursivo.
Código: [Seleccionar]
Este es el error que aparece:
PerformEvent recursion depth failure - check for infinite loops, check objects for parenting

Alguien tiene alguna idea de cómo resolver este problema?
« última modificación: Marzo 25, 2020, 06:36:27 am por BssString »

 


No Tienes Permisos Para Dar Puntos
point 0 Puntos

Este tema no recibió puntos.


Desconectado Clamud

Respuesta #1 en: Marzo 26, 2020, 07:36:31 pm
No recuerdo el número exacto, pero GM tiene un número limitado de niveles de recursión. Las opciones que tienes son simplificar el algoritmo para usar menos niveles de recursión o mejor no usar recursión y usar varias estructuras de datos (ds_). ¿Qué algoritmo estás usando?

 


Desconectado BssString

Respuesta #2 en: Marzo 28, 2020, 02:04:36 am
Hola Clamud

El problema es que he usado objetos para iterar en vez de Data Structures o Arrays... no supe cómo plantearlo y me pareció que con objetos podía manipular más fácilmente las variables. No voy a pegar el código completo porque son muchas líneas de lógica, pero explicaré cómo funciona en términos generales:

El código es "sencillo", tengo un objeto creador de la iteración que es el IA que tiene un array para los recursos que dispone y otro para el nivel en el que tiene cada edificio.
recursos[recurso.madera] = 100 //Ejemplo, eso siginifica que tiene 100 de madera
recursos[recurso.ladrillo] = 80 //Tiene 80 de ladrillos, etc
edificios[edificio.ayuntamiento] = 3 //Tiene el Ayuntamiento a nivel 3
edificios[edificio.cuartel] = 1 //Tiene el Cuartel a nivel 1, etc
Uso "enum" para definir el número asociado al index de cada array y no confundirme con los números.

Al inicio del juego, en un objeto control, cree una DS_GRID para almacenar los costes de construcción y los enfriamientos. El ID de la DS GRID la guardé en una variable global, así cualquier objeto del juego puede acceder a los costos de fabricación y Lead Times.
Luego el código recursivo es en realidad un objeto que se crea a sí mismo n veces (o eso es en la teoría, porque en la práctica sólo se crearon 32 instancias)
El objeto IA que crea el nodo:
var inst = instance_create(0,0,obj_IA_nodo)
with inst {
creator = other
event_perform(ev_other,ev_user0)
}
En el CREATE EVENT del nodo, se genera un array vacío que indica qué decidión ya tomó ese nodo. Un ejemplo rápido:
subir[2] = 0 //aún NO decide subir el edificio 2
subir[edificio.cuartel] = 0//aún NO decide subir el cuartel
subir[edificio.ayuntamiento] = 0//aún NO decide subir el ayuntamiento

En el evento EVENT USER 0 es como un "Post-Create" event falso, el nodo replica las variables de niveles, recursos y tiempo demorado que tiene su creador, suma recursos según la producción (calculada con la misma variable de tiempo), además revisa cuáles decisiones son IMPOSIBLES de tomar (ej: que para subir un edificio tenga como requisito tener construido otro edificio o que el edificio ya esté en el máximo nivel).
Ejemplo:
tiempo = creator.tiempo //Se trae el tiempo que ha tardado la decisión del nodo anterior para sumarle el tiempo que tomará mi decisión.
subir[edificio.cuartel] = 1 //Por alguna razón este nodo NO puede subir el edificio 1 (Cuartel), los que quedan con valor en "0" sí se pueden seguir subiendo.

Luego, en ese mismo ev_user0, toma "n" decisiones por cada variable del array "subir" que aún esté en cero. Si subir[edificio.ayuntamiento] es aún cero, quiere decir que SÍ puedo subir el Ayuntamiento y toma la decisión.
Eso hace la variable "subir[edificio.ayuntamiento] = 1", reduce los recursos según el coste de construcción, considera los Cooldown de construcción en la variable tiempo y crea otro NODO que ahora leerá las variables desde este nodo en vez del IA.

Y ahí es donde ocurre la recursividad, cada nodo crea nuevos nodos cuando aún pueden tomar decisiones y se eliminan a sí mismos cuando ya no quedan más decisiones que tomar, en ese punto se genera un output diciéndole al IA el tiempo que tardará en seguir esa alternativa.
Cuando un nodo se elimina, en el destroy event hace que su nodo creador cargue de nuevo el ev_user0 y traiga de nuevo los recursos y tiempos que tenía antes de tomar la decisión. La única diferencia es que ya no corre el CREATE EVENT, entonces la decisión "subir[edificio.ayuntamiento]" sigue en uno porque está tomada y ahora ese mismo nodo tomará una segunda decisión, ejemplo: "subir[edificio.cuartel]".

La idea original es comparar todos los output para ver cuál alternativa le conviene más al IA y elegir al azar dentro de las mejores alternativas.

En realidad es una locura lo que intento hacer porque con varios edificios para construir, las alternativas posibles se disparaban exponencialmente, lo calculé con estadística y necesitaba hacer como 28mil iteraciones y Game Maker sólo me deja hacer 32 hasta que se cuelga.

De momento el IA se mueve de forma aleatoria, pero es muy noob... es poco eficiente y cuando el juego progresa, el IA se va quedando muy por detrás... se notan mucho las malas decisiones.

Saludos
« última modificación: Marzo 28, 2020, 02:48:03 am por BssString »