MouseRun

[AJ NW]

Mouse Run es un programming game que consiste en realizar un raton que recorra un laberinto en busca de un queso. Digamos que tengo que implementar una especie de ia que memorize el laberinto una vez que el raton ha pasado por encima de cada casilla (el propio raton implementa una lista con las casillas que ha "pisado").
No quiero que me hagan el ejercicio, lo que quiero es que me orienten a como podria dotar a mi raton de dicha "inteligencia" para que él mismo reconozca el camino mas corto del laberinto para llegar al queso (una vez el raton ha reccorido el laberinto).
El tablero es una matriz de una clase a la que llamamos bloque (grid) que se crea de forma aleatoria.
Lo que yo he pensado es interpretar el tablero como un vector de numeros naturales (es decir, si el tablero es x1y1, x1y2, x2y1, x2y2 hacer que el tablero sea simplemente 1,2,3,4) y tras hacer esto, como el queso se inicializara en la casilla del 1 al 4 (en este ejemplo, ya que el tablero suele ser elegido de 20x20) hacer que el raton vaya a dicha casilla mediante un grafo que tenga en cuenta las casillas "conocidas".
Pero no me convence del todo u.u , por favor, alguna otra estrategia para dotar a mi raton de inteligencia?

[El Benjo]

Lo más común en estos casos y creo que lo ideal es el algoritmo de Tremaux

https://es.wikipedia.org/wiki/Algoritmo_de_Tremaux

La forma más común para este algoritmo (cuando la matriz o laberinto no es muy grande) es con una función recursiva. Lo que se hace en este caso es tratar al laberinto como si se tratara de un árbol donde cada nodo hijo corresponde a un espacio hacia el cual el 'ratón' puede moverse. Cuando no hay más espacios que recorrer a partir de la posición actual entonces se regresa al nodo padre.

Si dispones de un libro viejo de programación seguro encontrarás información (con código incluido), pues la mayoría de estos libros lo tenían a modo de ejemplo.

[AJ NW]

mmm gracias!!! pero me ha surgido un nuevo problema a la hora de intentar implementar el algoritmo (mas bien es una duda). el algoritmo de tremaux esta muy bien, pero solo serviria en caso de que al llegar a la salida se termine el juego.
En mi caso, al llegar a la salida (el queso), esta reaparece en otro sitio. Bien, lo que tengo que conseguir es que el raton, que ya ha memorizado algunas casillas llegue a la salida que ha reaparecido en cualquier otro sitio del mapa. Para ello, como el raton ha memorizado (si no todo) parte del laberinto, quiero que consulte si el queso se encuentra en una casilla que ya ha visitado, y de ser asi,  que "construya" el camino mas corto para encontrar la salida.
De nuevo, mi problema surge al intentar dotar de esta inteligencia a mi raton. Gracias por la ayuda y aver si pueden seguir orientarme con esta tarea :/

[El Benjo]

El problema que planteas se resuelve con el mismo algoritmo. Aquí el problema (me parece) es que no eres capaz de reconocer las implicaciones en la resolución del propio problema. Me explico:

Si el ratón 'memoriza' el recorrido, igual tendría que buscar el camino (esté dentro del recorrido que tiene memorizado o no esté) con el mismo algoritmo. Lo que tienes que hacer cuando reaparezca el queso es pasar los nuevos parámetros a tu función con el algoritmo de Tremaux, donde los parámetros son: Localización del queso y localización del ratón.

[AJ NW]

mmm interesante, me has ayudado mucho de verdad. Gracias!!! Voy aver si sigo con este proyecto y ya posteare los resultados cuando tenga tiempo!! que no doy a basto. Un saludo!!

[El Benjo]

Muy bien, AJ. Espero de verdad haberte sido de ayuda. Y ya sabes que si tienes dudas con el código, aquí nos ayudamos entre todos. Suerte en tu código.

[AJ NW]

para que te hagas a la idea, la implementacion cuando la termine sera una mezcla del algoritmo de Tremaux donde dentro del algoritmo, usando distancias de Manhatan "creo" el camino mas corto midiendo distancias (que era "la clave" que me faltaba). Yo creo que eso debe de funcionar.
Gracias por la ayuda y ya posteare el codigo cuando lo termine.