4.1 Métodos posibles de resolución
Existen dos métodos para resolver laberintos dependiendo si nos los miramos como una unidad o bien como un conjunto de unidades. En el primero de ellos, empezamos en un punto determinado y debemos llegar al siguiente para llegar hasta el final;
en el otro método lo que se hace es mirar todo el laberinto e invalidar pasadizos; de esta manera, solo quedará la solución.
Los algoritmos de resolución de laberintos pueden ser clasificados según los siguientes criterios: la velocidad que necesita el algoritmo para encontrar la solución, que es siempre proporcional al tamaño del laberinto y/o a las condiciones del ordenador; la memoria externa y/o de pila que programa necesita para su ejecución; también debemos añadir otro criterio: la capacidad del hombre para aplicar aquel algoritmo en la resolución de un laberinto, ya sea mirando un mapa o una versión de tamaño real. A continuación presentamos unos cuantos con características diferenciadas.
|
4.2 Métodos utilizados para resolver laberintos
 Los algoritmos que presentamos a continuación y otros que explicaremos en el apartado de generación de laberintos han sido creados previamente de manera individual y más adelante los hemos reunido para crear el archivo algoritm.pas.
Este algoritmo es muy sencillo; consiste en llenar todos los espacios de un determinado laberinto de este tipo. Lo que hace es fijar unas coordenadas al azar x e y, y a partir de estos, poner una señal por dónde ha pasado. Una vez puesta la señal, se aplica el mismo procedimiento por la misma coordenada x,y por la coordenada y+1, después por la y-1, x-1, x+1... Así sucesivamente hasta que ha pasado por todas las casillas que hay y ha llenado (y recorrido) absolutamente todo el laberinto. Es un método recursivo en el cual el procedimiento omple se va llamando a sí mismo.
Para resolver laberintos de este tipo el algoritmo que utilizamos es el mismo ya que en los dos casos, resuelve el laberinto. La única modificación que hemos aplicado al programa es que en el momento en el que vea el objeto llave, da como terminada la resolución. No obstante, al principio había la condición de que si se veía la llave se detuviera después de haber preguntado si en la coordenada en la que se encontraba había tierra; de esta manera el procedimiento llena no acababa nunca y la pila se iba cargando hasta que se llenaba por completo. Es por esta razón que nos dimos cuenta de que esta condición tenía que estar antes de preguntar si havia tierra y, efectivamente, funcionó. |
