Soluciones para el Desafío del Laberinto

[okram]

Hola a todos,

Abro este tema para que publiquemos y comentemos los códigos que se fueron elaborando a lo largo del desafío publicado originalmente en http://www.forosdelweb.com/f18/desafio-laberinto-472702/.

Solucion de alvlin [Código]
Solucion de caricatos [Código]
Solucion de DeeR [Código]
Solucion de Falhor [Código]
Solucion de IngProd
Solucion de nicolaspar [Código]
Solucion de okram [Código]
Solucion de oso96_2000 [Código]
Solucion de Panino5001 [Código]

Estas son todas las soluciones posteadas, y como el plazo era hasta hoy, ya podemos liberar los códigos.

Propongo que demos toda esta semana para comentar los códigos, y que el fin de semana (31/03 - 01/04) sometamos los scripts/soluciones a votación.

Por ahora, este tema está dedicado únicamente a comentar los códigos, sin establecer ningún tipo de competencia aún.

Un saludo,

[AlvaroG]

http://www.tallerwebmaster.com/alvli...laberinto.phps

Ahí está el código fuente....
Básicamente los pasos que sigue el ratón es:

1.- "mira" si tiene camino libre al queso, si lo tiene se establece la dirección y no se cambia. (función Mirar)

2.- Si no se encuentra, se "mira" en todas las direcciones para ver a dónde se mueve. Se descartan las paredes, y la dirección a seguir se determina según la cantidad de veces que se haya pasado por cada casilla adyacente. la dirección a seguir será la de la casilla con menos cantidad de pasadas, o una al azar entre las que tengan menos si hay más de 1 casilla con el menor número de pasadas.

3.- Luego simplemente se mueve al ratón.

Tuve muy poco tiempo, pero estoy conforme con el resultado. Después de todo, el ratón siempre encuentra al queso y creo que logré simular un ratón "real", que en verdad recorrerá el laberinto.

Ya me meteré con algoritmos más complejos


Saludos

[okram]

Mi solución está en:

http://myokram.phpnet.us/queso.codigo.php?

Básicamente lo que hago es, mediante la funcion search_pways() (no se xq me gusta usarlas en ingles) busco los caminos posibles de una coordenda, me refiero a arriba, abajo, derecha e izquierda. Obtengo un array con las direcciones posibles, y hago lo mismo con cada uno de sus elementos. Una vez que me topo con el queso, guardo en un array la secuancia que siguio hasta ese momento ($steps) y el numero de pasos que se necesito ($min)

A partir de ese momento, el raton sigue buscando nuevos caminos, pero solo guardara aquellos que tengan un menor numero de pasos hasta el queso.Si hay mas de un camino que tengan el menor numero de pasos, guardo todas las secuencias en un array ($fs), y finalmente escojo la que se encontro primero...

Esperando mas codigos...

Un saludo,

[Panino5001]

Por favor, marcar la mía como que tiene código (en realidad fui el primero en mostrarlo hoy a las 0 hs. de mi país en la misma hoja donde muestro las soluciones, y hasta tengo un comentario que, viniendo del gran caricatos(), me pone muy contento.)
Por cierto, caricatos también ha publicado su código y también habría que marcarlo.

[oso96_2000]

En mi solucion, al final esta el enlace al codigo fuente, pero pues lo pongo aqui tambien:
http://stuff.otaku-anime.com/Maze.class.php?source

Yo a falta de tiempo (y ganas xD) no me la quize complicar mucho sacando el camino mas corto, simplemente puse al raton a que recorriera el laberinto buscando el queso.

En si, la parte importante de mi clase seria el metodo solveMaze(), ya que este es el que se encarga de decidir (aleatoriamente) hacia que direccion moverse (buscando antes en que direcciones puede hacerlo) y volver a llamar la funcion hasta que se encuentre el queso.

Como se ve, el array original de laberinto esta modificado para que ocupe menos espacio, y no se si esto afecte el rendimiento (no deberia, creo yo), pero de ser asi entonces en cuanto pueda lo cambiaré por el arreglo original.

Al final quede contento con la solucion, ya que cumple su cometido y creo que es bastante flexible si se quisiera usar otro laberinto.

He estado viendo por encima las demas soluciones, y me parecen bastante ingeniosas, pero no las he visto tanto como para poder hacer un mejor comentario xD.. igual tenemos el transcurso de la semana para eso :3

[DeeR]

Bueno ya publique el Codigo Fuente de mi Solucion
Aleatoriamente
http://deerme.org/raton/test.php
Con Posiciones Fijas (en la URL)
http://deerme.org/raton/test.php?r=16,5&q=11,19
Source
http://deerme.org/foro/viewtopic.php?p=48#48

Al final me decidi en esta que es una Funcion Backtracking , ya que estaba solucionado el problema con Clases y Aplicando Backtraing y un poco de Dijstra (para el camino mas corto) y era muy lento y aveces encontraba el camino, asi que me decidi por esta nomas, le elimine un poco de probabilidad (en el sentido que tenia una Funcion que me permitia Selecionar un Direccion con cierta Probabilidad ( IZQ 40% , DOWN 30% , UP % 15 , DER = 15%), pero mejor le aplique un shuffle que desordena la matriz aleatoriamente (todas las direciones tienen la misma probabilidad de salir), asi era mas eficiente, al final al cabo, me ubiera gustado terminar mi Clase con Dijstra, pero el tiempo me tiene muy corto.

Asi que voy a estar mirando, las soluciones que entregan el camino mas corto :)

Pero lo mejor de todo, es que el Raton siempre se come el queso

Saludos

[okram]

Bien, solo faltan 3 códigos... Estuve leyendo los ya publicados, y pues no termine de entender el unico que comence a leer. A lo largo de la semana me tomare algo de tiempo para leerlos todos, ya que por lo que vi el mio se queda chico

Un saludo,

[nicolaspar]

Sorry se me paso la fecha, ando las corridas con mi vida laboral los últimos días :S

Les dejo el fuente: http://www.estudiowas.com.ar/desafioLaberinto/code.htm

Saludos, y estaré leyendo ;)

PD: Los debates serán en este mismo thread?

[caricatos]

Hola:

Sobre mi solución, la idea que tenía era marcar cada celda visitada para no volver a pasar por la misma (inicialmente con valor 0 = camino no-visitado), de tal modo que desde la última posición del ratón, chequear todas las direcciones posibles {[N|S|E|O] - inversa(dir-actual)} y con las celdas con un valor = 0 (no visitada) generan una nueva "ruta posible".

Por cada paso, entonces, se mantienen los viejos senderos y se adicionan algunos con un paso más, que serán los que perduren (con la función "aligernado()", se eliminan todos los caminos con menos pasos dados)... es algo difícil de explicar...

Por cada paso nuevo se suman todos los posibles nuevos caminos, y se descartan todos los que se han topado con paredes o con cruces anteriormente visitados.

Los senderos están codificados con las iniciales de las direcciones que siguen: /^[N|S|O|E]$/ y se guardan simplemente cadenas de este tipo en un array que se trunca dejando solo las cadenas "completas"...

Espero haberme explicado "medianamente bien"...

Saludos

[Falhor]

Bueno, yo lo posteo acá... Obvié la parte del array para el laberinto:

Código PHP:

  function dibujartodo(&$array,$p = NULL){
    for($i=0;$i < 24;$i++){
        echo('<br />');
        for($n=0;$n < 24; $n++){
            if($array[$i][$n] == 0){
                echo('<img src="0.jpg" width="8" height="8" alt="'.$i.' - '.$n.'" title="'.$i.' - '.$n.'">');
            }elseif($array[$i][$n] == 1){
                echo('<img src="1.jpg" width="8" height="8" alt="'.$i.' - '.$n.'" title="'.$i.' - '.$n.'">');
            }elseif($array[$i][$n] == 2){
                echo('<img src="2.jpg" width="8" height="8" alt="'.$i.' - '.$n.'" title="'.$i.' - '.$n.'">');
            }elseif($array[$i][$n] == 3){
                echo('<img src="3.JPG" width="8" height="8" alt="'.$i.' - '.$n.'" title="'.$i.' - '.$n.'">');
            }elseif($array[$i][$n] == 4){
                echo('<img src="4.jpg" width="8" height="8" alt="'.$i.' - '.$n.'" title="'.$i.' - '.$n.'">');
            }
        }
    }
}
function queso(&$array,$p = NULL)
{
     // Ingresar Queso al Laberinto
     $d=count($array);
     $t[0]=rand(0,($d-1));
     $t[1]=rand(0,($d-1));
    if ( $array[$t[0]][$t[1]] == 0 )
    {
         // Posicion Vacia
         // Guardamos Queso
         $array[$t[0]][$t[1]] = 2;
         global $quesox;
         $quesox = $t[0];
         global $quesoy;
         $quesoy = $t[1];
         echo("Posición del queso: " . $t[0] . " - " . $t[1] . "<br />");
         return TRUE;
    }      
     else
     {
        return ( queso($array) );
    }
}
queso($array);
function raton(&$array,$p = NULL)
{
     // Ingresar Raton al Laberinto
     $d=count($array);
     $t[0]=rand(0,($d-1));
     $t[1]=rand(0,($d-1));
    if ( $array[$t[0]][$t[1]] == 0 )
    {
         // Posicion Vacia
         // Guardamos Raton
         $array[$t[0]][$t[1]] = 3;
         global $ratonx;
         $ratonx = $t[0];
         global $ratony;
         $ratony = $t[1];
         echo("Posición inicial del ratón: " . $t[0] . " - " . $t[1] . "<br />");
         return TRUE;
    }      
     else
     {
        return ( raton($array) );
    }
}
raton($array);
dibujartodo($array);
echo("<br />");

//ESTA ES LA FUNCION QUE HACE TODO EL TRABAJO PARA ENCONTRAR EL QUESO

function mover(&$array, $ratonx, $ratony)
{
    for($i = 1;$i > 0;$i++){
        $mover = rand(0,3); //0 = ARRIBA, 1 = ABAJO, 2 = IZQUIERDA, 3 = DERECHA
        if($mover == 0){
            if($array[$ratonx - 1][$ratony] == 0 || $array[$ratonx - 1][$ratony] == 4){
                $array[$ratonx - 1][$ratony] = 4;
                $ratonx -= 1;
            }elseif($array[$ratonx - 1][$ratony] == 2){
                echo('Bien! Conseguimos el queso! A comerlo!');
                $i = -1;
            }elseif($array[$ratonx - 1][$ratony] == 3){
                $ratonx -= 1;
            }
        }
        if($mover == 1){
            if($array[$ratonx + 1][$ratony] == 0 || $array[$ratonx + 1][$ratony] == 4){
                $array[$ratonx + 1][$ratony] = 4;
                $ratonx += 1;
            }elseif($array[$ratonx + 1][$ratony] == 2){
                echo('Bien! Conseguimos el queso! A comerlo!');
                $i = -1;
            }elseif($array[$ratonx + 1][$ratony] == 3){
                $ratonx += 1;
            }
        }
        if($mover == 2){
            if($array[$ratonx][$ratony - 1] == 0 || $array[$ratonx][$ratony - 1] == 4){
                $array[$ratonx][$ratony - 1] = 4;
                $ratony -= 1;
            }elseif($array[$ratonx][$ratony - 1] == 2){
                echo('Bien! Conseguimos el queso! A comerlo!');
                $i = -1;
            }elseif($array[$ratonx][$ratony - 1] == 3){
                $ratony -= 1;
            }
        }
        if($mover == 3){
            if($array[$ratonx][$ratony + 1] == 0 || $array[$ratonx][$ratony + 1] == 4){
                $array[$ratonx][$ratony + 1] = 4;
                $ratony += 1;
            }elseif($array[$ratonx][$ratony + 1] == 2){
                echo('Bien! Conseguimos el queso! A comerlo!');
                $i = -1;
            }elseif($array[$ratonx][$ratony + 1] == 3){
                $ratony += 1;
            }
        }
    }
}
mover($array,$ratonx,$ratony);
dibujartodo($array);
?> 
  

[Panino5001]

En mi solución (la segunda, porque la de backtracking es menos eficiente y no muestra el camino más corto) lo que hago es extender secuencialmente brazos de igual longitud a partir de la posición del ratón y en todas las direcciones posibles. Al mismo tiempo que los brazos se extienden, la celda anterior a la última de cada brazo es guardada como una pseudopropiedad de la celda evaluada (llamo evaluada a la que en ese momento es última de cada brazo). Como los brazos crecen de forma pareja y en todas direcciones, cuando el queso es alcanzado por uno de ellos sé que éste se corresponde con el camino más corto. Entonces detengo la evaluación y recorro ese camino hacia atrás a partir de la celda que alcanzó al queso, guiado por la pseudopropiedad 'celda precedente' que había guardado antes. Al alcanzar al ratón, muestro la salida en pantalla.

[nicolaspar]

Panino5001, tres cosas...

1- No he visto los códigos en profundidad por lo que aún no me siento en el lugar de hablar o comentar de ninguno en particular.

2- Decís: "menos eficiente y no muestra el camino más corto", y no me parece mal, de hecho, emular un ratón tiene esta consecuencia, y esa era la consigna, ni más ni menos.

3- Me parece buena la lógica que planteas "Como los brazos crecen de forma pareja y en todas direcciones" ; pero hacer esto, no sale de la consigna y/o consume mas recursos?

Lo que menos quiero es generar mala onda o problemas entre nosotros, solo tratar de comprender el cometido que se planteo, comentar sobre estos, y aprender de los resultados. Ya he comentado esto, y me gustaría escuchar opiniones al respecto, y realmente si se cambio la consigna (cosa que no me entere) pido disculpa


Edit: Me puse a mirar un poco los códigos y hasta ahora me gusto la solución Falhor, si bien la idea me parece correcta, me gustaría verla mas en detalle, hay algo que no logro comprender bien en ella.
Por otro lado, también me resulto atractivo el de oso96_2000...

[Panino5001]

Mmm, depende de lo que entendamos por eficiente. Si hablamos de recursos, tiempos de resolución y cantidad de intentos, la resolución por inundación es mucho más eficiente que backtracking en todos y cada uno de esos aspectos.
Lo del planteamiento inicial, es posible que así sea, pero backtracking tampoco simula el comportamiento del ratón, ya que, entre otras diferencias, el ratón, para llegar a un punto de decisión en un árbol que terminó en error, debería recorrer nuevamente hacia atrás todas las casillas erróneas en lugar de saltar mágicamente al punto de decisión.
En ese caso, la simulación del comportamiento del ratón, la solución más plausible sería la de alvin: aunque no la veo muy eficiente, es la más cercana a la conducta del ratón.

[Falhor]

El de alvlin está muy bien pero es medio raro, en partes queda azul, además de que a veces aparecen pintados algunos cuadros a los que no llegó en realidad (A menos que se haya teletransportado).

Saludos.

PD: nicolaspar, cualquier duda sobre mi código decime... No soy muy ordenado, por eso capaz algo es difícil de entender, jeje.

[oso96_2000]

Yo estuve ya viendo algunos de los códigos, no mucho, pero al menos tratar de entender como funcionan xD.. el de Falhor tarde un poco en comprender como se resolvia, pero al final me parece una buena solucion.

El de nicolaspar, no estoy muy seguro pero creo que no tiene aleatoriedad de movimiento (creo, necesitaria verlo con mas tiempo).. me parece que siempre el primer camino que tratará de elegir es primero hacia abajo, a no ser que no peuda moverse en esa direccion.. en ese caso, se moverá a la derecha, zquierda y arriba, en ese orden.. no se si me explico con lo que quiero decir

La solucion que mas me gusta hasta el momento, es la de caricatos seguida de la de okram.. y creo que luego me gustaria colocar el de Falhor, por lo corto que es y porque emula el comportamiento del ratón xD

En mi codigo, lo que no me gusta es que, para usar la palabra que uso panino en su solucion, mi raton es miope XD.. si pasa al lado del queso, si no toca la direccion en que esta, se lo puede pasar de largo.. esto es facil de corregir, pero preferí no hacerlo hasta que termine esto de los comentarios y demases xD

Y si, a la hora de pintar el laberinto, el de alvlin resulta un poco extraño.. como que el raton tiene tanta hambre y se come las paredes xD

[nicolaspar]

depende de lo que entendamos por eficiente. Si hablamos de recursos, tiempos de resolución y cantidad de intentos, la resolución por inundación es mucho más eficiente que backtracking en todos y cada uno de esos aspectos

Lo mejor en estos casos, ya que la teoría aplica a ejemplos específicos, es medir tiempos y sacar promedios.

El de nicolaspar, no estoy muy seguro pero creo que no tiene aleatoriedad de movimiento (creo, necesitaria verlo con mas tiempo).. me parece que siempre el primer camino que tratará de elegir es primero hacia abajo, a no ser que no peuda moverse en esa direccion.. en ese caso, se moverá a la derecha, zquierda y arriba, en ese orden.. no se si me explico con lo que quiero decir

Si, eso hace!, no estoy seguro si aplicar un algoritmo probabilístico sea optimo, lo que si me gustaría haberle hecho es algún tipo de "olfato" al ratón, cosa que si pasa a dos posiciones del queso lo encuentre, pero no he tenido tiempo.

nicolaspar, cualquier duda sobre mi código decime... No soy muy ordenado, por eso capaz algo es difícil de entender, jeje.

El código lo entendí en su totalidad, lo que no logro comprender (por confusión seguramente) es porque el ratón no logra terminar el camino hasta chocar una pared o encontrar una nueva boca, dejando lugares sin recorrer, como que el ratón toma una recta y a la mitad de esta decide volverse....no estoy seguro si es un error en el algoritmo, o esta en algún lado (si es así es lo que no logro encontrar).

[shakaran]

Hola, estoy siguiendo muy de cerca este hilo y el original porque me esta sirviendo mucho para aprender tecnicas que ahora mismo estoy dando en la facultad. Les agradezco todo su esfuerzo y su medito, ademas de la generosidad de mostrar los codigos. Mi propuesta es que sigan poniendo "un reto" cada semana ya que motiva muchisimo y ademas mucha gente aprende.

Por otro lado, alguien ha contemplado la posibilidad de utilizar "PathFinding" o sea el metodo de A Star (A*) para php en alguna solución?

Otra posibilidad interesante seria dividir en sectores mucho mayores la busqueda y que hiciera descartes en cada iteracion de grandes sectores y luego fuera reduciendo para alcanzar la solución.

[oso96_2000]

nicolaspar, eso que dices de la solucion de Falhor es por que el movimiento del raton se deja al azar, es lo mismo que aplique yo. Primero revisaba en que direcciones podia moverse y despues de eso se elije al azar una de ellas.

En el código de Falhor, lo que hace eso es esta linea:

Código PHP:

  $mover = rand(0,3); //0 = ARRIBA, 1 = ABAJO, 2 = IZQUIERDA, 3 = DERECHA 
   

Bien puede que salga que se mueva Derecha, Derecha, Derecha, y luego toque la Izquierda.. es cosa de pura suerte xD

Yo tambien he pensado en ponerle una especie de olfato a mi raton.. digamos que el raton no tiene idea de donde esta el queso, pero en las distintas direcciones puede "olerlo", y dependiendo de la distancia el olor será mas fuerte o mas leve.. o sea, contar el numero de casillas hasta el queso (a menor numero de casillas, más fuerte será el olor del queso).. pero eso probablemente implica mas tiempo de procesamiento..

shakaran, no estoy muy seguro, pero el metodo A* no es parecido a lo que usa panino? Solo por entenderlo, ya que no conocia ese metodo, pero por lo que he leido en este ratito me parece que si no es lo mismo, al menos van algo ligados..

Lo de poner un reto mas seguido me parece una muy buena idea, estimula la creatividad y no nos deja "oxidarnos" xD

[Panino5001]

shakaran, no estoy muy seguro, pero el metodo A* no es parecido a lo que usa panino? Solo por entenderlo, ya que no conocia ese metodo, pero por lo que he leido en este ratito me parece que si no es lo mismo, al menos van algo ligados..

Van ligados en cuanto a lo de guardar la posición de la celda 'padre', pero (ojo, estoy hablando por lo que leí en tu link: yo tampoco conocía el método, en realidad hago lo que puedo basado en mis conocimientos autodidactas) creo que la diferencia principal está en el cálculo de costes para elegir una u otra opción, ya que se supone que hasta no encontrarlo, desconocemos dónde está el queso. En mi caso, en lugar de probar un camino en función a un cálculo de costo, elijo todos los caminos posibles y, pese a eso, la cantidad de iteraciones hasta la solución suele ser, en casi todos los casos, menor que con otras alternativas que probé.
Igualmente, el sistema descrito en el enlace me parece muy interesante.
Agrego: la solución de Falhor también imita muy bien el comportamiento del ratón por lo que estuve viendo.

[oso96_2000]

Si, precisamente en eso de guardar la posicion de la celda anterior es lo que me hizo pensar que estaban ligadas.. a mi me gusta el metodo que usas (panino) para encontrar el queso: ir inundando el laberinto..

Me lo imagino como si se tirara un vaso de agua sobre un punto del laberinto (el raton en este caso) y esta fuera recorriendo por cada lugar donde pueda pasar, asi hasta llegar al punto donde encuentra el queso, me parece que para sacar el camino mas corto es la solucion optima (aunque aun debo ver bien el de caricatos para ver como lo hace xD)

[shakaran]

Iniciado por Panino5001

Van ligados en cuanto a lo de guardar la posición de la celda 'padre', pero (ojo, estoy hablando por lo que leí en tu link: yo tampoco conocía el método, en realidad hago lo que puedo basado en mis conocimientos autodidactas) creo que la diferencia principal está en el cálculo de costes para elegir una u otra opción, ya que se supone que hasta no encontrarlo, desconocemos dónde está el queso. En mi caso, en lugar de probar un camino en función a un cálculo de costo, elijo todos los caminos posibles y, pese a eso, la cantidad de iteraciones hasta la solución suele ser, en casi todos los casos, menor que con otras alternativas que probé.
Igualmente, el sistema descrito en el enlace me parece muy interesante.
Agrego: la solución de Falhor también imita muy bien el comportamiento del ratón por lo que estuve viendo.

Un informatico sin espiritu autodidacta no va a ningun sitio ;) De ahi que los mejores sean los autodidactas. No te pierdes nada de la universidad, solo te enseñan bases, metodologias y la forma "mas correcta" de hacer las cosas (que en realidad no tiene porque ser la mejor o mas conveniente para la solución del problema).De informatico a Ingeniero Informatico solo hay un titulo por delante.

Bueno, aunque este fuera de tiempo y no sea participe en el concurso esta semana santa intentare hacer un algoritmo que se base en que el mapa es un grafo dirigido y valorado aplicando PathFinding a traves de A* con la funcion F=G+H para los costes.

En realidad estamos buscando una combinacion de que se consiga la solución optima, pero que no sea un optimo local (heuristica), si no un optimo global (la mejor solución posible de todas) aplicando en el problema que tenga el menor orden de complejidad posible y por lo tanto el menor tiempo de ejecución para su resolución.

[oso96_2000]

Si tienes tiempo, haz la solucion con el metodo A*, a mi me interesaria bastante verlo..

En un principio el desafio era solo hacer que el raton encontrara el queso, de cualquier forma que se pudiera xD.. eso lo logran todas las soluciones, y me alegró ver que todas las soluciones son distintas, con excepcion tal vez en la forma de resolver el laberinto, como Falhor y yo que lo hacemos de la misma forma (escoger la dirección al azar), aunque el codifo y la forma de afrentar el problema es distinta.

A mi lo que me gustaria, sería no encontrar la solución mas optima o que tenga el menor tiempo de ejecucion, sino que al final me gustaria tener una que emulara el comportamiento del raton. El que me parece mas cerca de ese comportamiento, es el de alvlin.. ya que parece como si el raton tuviera algo de memoria y sabe cuantas veces ha pasado por un lugar para asi tratar de evitar el solo dar vueltas.. aunque al final, con la representacion grafica, se ve que de todas formas puede pasar por el mismo lugar varias veces.

[shakaran]

Intentare hacerlo ;) Mas que nada porque tengo que aplicarlo en el juego RPG que estoy creando. Y debe ser un algoritmo eficiente y que consuma pocos recursos y por otro lado poco tiempo de ejecucion, ya que la productividad debe ser alta al ser ejecutado en el algun caso por varios usuarios a la vez (por poner un numero unos 100).



Respecto alo que dices de:

A mi lo que me gustaria, sería no encontrar la solución mas optima o que tenga el menor tiempo de ejecucion, sino que al final me gustaria tener una que emulara el comportamiento del raton. El que me parece mas cerca de ese comportamiento, es el de alvlin.. ya que parece como si el raton tuviera algo de memoria y sabe cuantas veces ha pasado por un lugar para asi tratar de evitar el solo dar vueltas.. aunque al final, con la representacion grafica, se ve que de todas formas puede pasar por el mismo lugar varias veces.

Creo que simular el comportamiento es algo mas complejo que hacer un rand (que creo que se deberia utilizar mejor mt_rand() que es mas eficiente) ya que el raton puede pararse, darse la vuelta, incluso si me apuras...roer partes del muro (si es debil) para atraversarlo.

Por otro lado creo que te contradices al decir que no quieres eficiencia y por otro lado decir que el raton no de vueltas o pase por el mismo sitio. Precisamente el algoritmo eficiente evitara los ciclos en el "grafo" y creara el arbol de recubrimiento minimo para no tener que pasar dos veces por el mismo sitio. Insisto esto es solo la "teoria" de lo que debe ser un algoritmo eficiente en este caso.

[nicolaspar]

Iniciado por shakaran

Por otro lado, alguien ha contemplado la posibilidad de utilizar "PathFinding" o sea el metodo de A Star (A*) para php en alguna solución?

Iniciado por nicolaspar

Ahora, una pregunta boludona DeeR...si o si tiene que ir el ratón al queso por si solo? o puedo "unir a ambos"? o sea, armar un camino directo entre ratón>queso (porque saber donde está el queso es simple).

Si bien el método no lo conocía, en un momento propuse hacer algo así, ya que saber la posición de ambos es simple.

El tema para el método A* es que, no solo debes conocer ambos puntos, sino que no emularía a un ratón.


Y ojo que lo que digo no le saca lo interesante a éste método ni al de otros resultados!, simplemente que no se si aplica a este caso.

Otra posibilidad interesante seria dividir en sectores mucho mayores la busqueda y que hiciera descartes en cada iteracion de grandes sectores y luego fuera reduciendo para alcanzar la solución.

No es lo que esta haciendo a grandes rasgos caricatos?...no lo vi en profundidad (a mi gusto es un código para bajarse y estudiarlo con pruebas y no he tenido tiempo) pero me parece....

[Panino5001]

shakaran, muy interesante todo lo que decís. Ojalá podamos ver esa solución y también que sigas haciendo estos interesantes aportes. Voy a intentar ver en profundidad todos los códigos el fin de semana. Estaría bueno que todos los comentáramos un poco para ayudarnos a entenderlos mejor.

[nicolaspar]

Estaría bueno que todos los comentáramos un poco para ayudarnos a entenderlos mejor.

Por supuesto!, cosa que vi que hiciste de 10!...en mi caso no encontrarás un //, #, o /**/ :p

Y en cuanto a los aportes y comentarios si, totalmente de acuerdo, nos nutren mucho!...

[oso96_2000]

Iniciado por shakaran

Por otro lado creo que te contradices al decir que no quieres eficiencia y por otro lado decir que el raton no de vueltas o pase por el mismo sitio. Precisamente el algoritmo eficiente evitara los ciclos en el "grafo" y creara el arbol de recubrimiento minimo para no tener que pasar dos veces por el mismo sitio. Insisto esto es solo la "teoria" de lo que debe ser un algoritmo eficiente en este caso.

Uhm.. a lo que me refiero con el comportamiento del raton, es que este dará vueltas por el laberinto.. puede pasar varias veces por el mismo lugar (hay muchos cruzes), pero al escoger las direcciones al azar, puede que se quede unos cuantos movimientos haciendo de: derecha, izquierda, derecha, izquierda, derecha, izquierda, etc

Por ejemplo mientras codificaba, quize intentar que evitara pasar por las casillas por las que habia pasado anteriormente, pero luego llegaba el punto en que ya no podia avanzar (rodeado de pared y casillas visitadas).. eso puede arreglarse, pero por falta de tiempo pues lo deje solo al aza

Si se saca un algoritmo que directamente le de el camino mas corto, pues es un raton inteligente.. mucho! xD.. el punto, como ya dijo nicolaspar, es que se parta de la idea de que solo se conoce el punto de inicio del raton, el del queso es totalmente desconocido.. al final, el raton tal vez no encontrará el camino mas corto, pero encontrará el queso sin dar tantas vueltas como lo hace al tomar una direccion al azar..

[Falhor]

Con respecto a lo del olfato, pensé en hacer dentro del for en la function mover(), antes del rand() algo así:

Código PHP:

  if($array[$ratonx - 1][$ratony] == 2){
     echo('Bien! Conseguimos el queso! A comerlo!');
     $i = -1; //Cierra el for
}elseif($array[$ratonx + 1][$ratony] == 2){
     echo('Bien! Conseguimos el queso! A comerlo!');
     $i = -1; //Cierra el for
}elseif($array[$ratonx][$ratony - 1] == 2){
     echo('Bien! Conseguimos el queso! A comerlo!');
     $i = -1; //Cierra el for
}elseif($array[$ratonx][$ratony + 1] == 2){
     echo('Bien! Conseguimos el queso! A comerlo!');
     $i = -1; //Cierra el for
} 
   

Eso sería para que no le pase por al lado sin comerlo...

Saludos, ahora me voy a poner a ver los códigos que todavía no tuve tiempo.

PD: Si quieren lo agrego al código pero ahora no lo puedo probar porque está lento el servidor y no sé si es mucho más lento por el script también o solo por el servidor... Pruébenlo ustedes.

EDITO: Lo pude probar, el código hay que ponerlo justo antes de que termine el for, sino podría aparecer dos veces "Bien! Conseguimos el queso! A comerlo!", no es un gran problema, pero también evita que se abra un for innecesario.

EDITO 2: El tema de ponerlo como dije al final es que si empiezan juntos se mueve antes de oler, entonces no lo descubre capaz...
Eso se podría arreglar poniéndolo antes (Arriba de todo, justo después de que empieza el for) y declarar otra variable o con el mismo $i, que controle si ya se llegó al queso que se saltee todo...

Código PHP:

  if($mover == 0 && $i <= 0){
...
if($mover == 1 && $i <= 0){
...
if($mover == 2 && $i <= 0){
...
if($mover == 3 && $i <= 0){ 
   

Osea, hay que agregar && $i <= 0 en los 4 ifs que se fijan el número que tocó en el random.

[nicolaspar]

La solución de olfato no es difícil, es más, no solo me parece correcta la que planteas, sino que creo que se puede mejorar dándole un poco mas de movimiento e inteligencia, el tema es que ya se entregaron las soluciones, no me parece correcto agregarlo ahora ...si postearlo como lo haz hecho; y ojo!, hacer pruebas NO lo veo mal, y menos mejorar las cosas, pero aparte de lo entregado obvio está.

Es algo que se podría haber puesto como solución y daría buenos resultados a quien lo hubiera implementado, pero beno...por mi parte como dije, tuve el tiempo* necesario para lo que entregué, siquiera he podido ponerme 15 minutos a ponerle comentarios (no tengo ni la cuenta de ftp acá).

Y algo que no he dicho es que este tipo de desafíos están bárbaros, ya tendremos una revancha

* entiéndase tiempo por tiempo libre con ganas de programar sin lucro alguno

[Falhor]

Lo que hice fue dejar el anterior en la misma dirección y con este par de detalles en la misma dirección, solo agregando un 2 antes del .php... El archivo quedó queso2.php