En los lenguajes de programación de alto nivel (C, Java, etc.) las llamadas a rutinas, funciones, procedimientos, métodos, o como queramos llamarlo, se implementan mediante una pila de llamadas. Una pila es una estructura de datos LIFO – List In First Out, es decir, el último dato que se mete en la pila tiene que ser el primero en salir:
Las pilas las podemos pintar creciendo o apilando hacia arriba o hacia abajo. Lo más natural resulta pintarlas creciendo hacia arriba, ya que en la naturaleza las cosas se apilan así (la gravedad tira hacia abajo
En cualquier caso, en la pila de llamadas se mete, por cada función llamada:
- La dirección de retorno: Esto permite continuar la ejecución del programa en el sitio correcto cuando termine la función.
- Los parámetros con que fue llamada la función.
- Variables y constantes de carácter local a la función.
Si ahora aplicamos esto a una función recursiva, es decir una función que se llama a sí misma, la pila tendría una apariencia así:
Lo que es importante observar es que cada llamada a la función recursiva tiene su propia copia de los parámetros de entrada. Por tanto, el programa no se pierde: sabe qué función está ejecutando, con qué parámetros, y dónde volver o continuar.
Sin embargo, si llevamos esto al C64, su pila (página uno), y las llamadas a rutinas en ensamblador con "jsr", lo primero que observamos es que los parámetros no se pasan a las rutinas mediante la pila (aunque se podría hacer). Lo normal es pasar los parámetros:
- Mediante los registros del microprocesador (acumulador, registro X y registro Y).
- O mediante posiciones de memoria, ya sean de la página cero o de cualquier otra página.
Las rutinas del Kernal suelen funcionar pasando parámetros en los registros del microprocesador. A mí me parece más claro, y por tanto me gusta más, usar posiciones de memoria.
Lo importante es observar que, si se usan posiciones de memoria (o registros del microprocesador), no hay una copia de los parámetros por cada llamada a la rutina recursiva. Todas las llamadas comparten las mismas posiciones de memoria y, por tanto, según se van produciendo las llamadas recursivas unos valores de entrada van "machacando" a los anteriores. Esto puede hacer que las rutinas recursivas "se pierdan".
Y esto es, precisamente, lo que ocurría en la entrada anterior. Y por este motivo el árbol de juego no se generaba de forma completa, sino que sólo se generaba en su máxima profundidad (la elegida por el usuario) en la primera rama, quedándose incompletas el resto de ramas.
La solución pasa porque los parámetros de entrada a la rutina "desarrollaUnNivel" no sean posiciones de memoria simples, sino tablas. De este modo, si usamos la profundidad (que es la variable que sirve para controlar las sucesivas llamadas recursivas y cuándo se ha llegado al final) como índice para acceder a estas tablas, cada ejecución de la rutina puede acceder a los parámetros de entrada que le corresponden:
Al cambiar la definición de la rutina (sus parámetros de entrada) lógicamente hay que adaptar las llamadas a la misma, tanto desde el programa principal "RYG.asm" como las llamadas recursivas que se hace a sí misma.
Y con esta solución la versión 10 del proyecto ya no "se pierde" y el árbol de juego se genera de forma completa independientemente del nivel de profundidad elegido por el usuario (1, 2 ó 3):
El siguiente paso ya será evaluar el árbol de juego, para que el C64 pueda tomar una decisión sobre qué jugada realizar. Pero antes de eso haremos algunas reflexiones sobre la memoria que ocupa el árbol, cuántos niveles de profundidad admite, cómo se podrían admitir más niveles, etc.
Código del proyecto: RYG10
No hay comentarios:
Publicar un comentario