Gracias caricatos ;) Ya sabes que te tengo gran admiración por las veces que me has ayudado ;)
Bueno cogiendo algunos trozos de la solución de alvlin para mostrar (renderizar) el laberinto (cogi el primer codigo para evitar perder tiempo en algo que ya estaba hecho, pues mi proposito, es mostrar como funcionaria el pathfinding y no presentar una solución de render del mapa XD).
He hecho una primera version de lo que pretendo (aun no funcional del todo, ahora os dire que inconveniente he encontrado).
Como os dije me baso en el metodo PathFinding conocido como A* (pronunciado A star), que calcula un mapa, laberinto, etc como si fuera un grafo conexo y valorado (si no sabeis que es un grafo conexo y valorado echadle un ojo a wikipedia o google). Por lo tanto, se define una funcion de costes como:
F=G+H
Donde:
G: es el coste del movimiento que se realiza a la casilla contigua (pe: vertical, horizontal o diagonal)
H: es la estimación desde la casilla actual a la casilla de destino (el queso) medida con alguna heuristica (yo he utilizado el metodo Manhattan con diagonales, ahora lo explicare, aunque se pueden utilizar otras muchas mas como las de Euclides, para gustos hay colores), sin considerar colisiones (muros u otros elementos).
F: es el coste mínimo de G+H en la casilla actual.
Lo que se prentende es aplicar F a cada casilla quedandonos con el mejor coste de las 8 posibilidades de movimiento en una casilla (4 en diagonal, 2 en vertical y 2 en horizontal) (yo he considerado que el raton se mueve en diagonal ya que es mas eficiente y puede darse el caso, pero en el codigo comentado pongo como seria H sin diagonales).
Por lo tanto conseguiremos el camino minimo para llegar desde un punto A(raton) a un punto (B) evitando colisiones y ciclos en el grafo.
Bien, ahora explicare el método Manhattan.
Heurística: Manhattan.
El cálculo de H puede ser estimado de diferentes maneras. El método que he usado se llama el método Manhattan, donde se calcula el número total de cuadros movidos horizontalmente y verticalmente para alcanzar el cuadrado destino desde el cuadro actual, sin hacer uso de movimientos diagonales o por el contrario haciendo uso de las diagonales. En mi caso he utilizado el uso de diagonales.
Nota: Se llama método Manhattan porque es como calcular el número de manzanas que hay desde un lugar a otro, donde no puedes acortar atravesando en diagonal una manzana. Cabe señalar que cuando calculamos H, ignoramos cualquier obstáculo que intervenga (de ahí que sea una estimación).
Un ejemplo de un trazo de la heurística Manhattan SIN diagonal:
Un ejemplo de un trazo de la heurística Manhattan CON diagonal:
Hasta aqui perfecto, pero esto es solo la teoría. Las complicaciones las he encontrado al entrar a la práctica. Ya que por ejemplo para una casilla A miraremos todos los posibles costes de F y lanzaremos la llamada para la que tenga menor coste de todas...que a su vez calculara el F con el menor coste en esa casilla etc. Pero faltara ir marcando en esa llamada, por las casillas que hemos mirado, ya que si encontramos un camino sin salida habra que hacer "Vuelta atras" y coger el siguiente F que menos coste tenga, por lo que aqui se me presenta la duda de como mantener estas listas "abiertas" y comprobar para el elemento minimo de esa lista y si no resulta para el siguiente de esa lista, teniendo en cuenta que cada elemento puede ser a su vez otra lista.
Por otro lado habria que ordenar esas listas de menor a menor con algun metodo como Quicksort (cosa que no se si tiene php o ahi que acudir a una clase de terceros o hacernosla nosotros).
Asi que ese es mi problema, se como hacerlo, pero no manejo php lo suficiente como para saber hacer esas listas, asi que mas bien es un problema de no saber sintaxis del lenguaje.
El codigo esta en
www.apogeusone.com/pathfinding.txt
y para la ejecutarlo:
www.apogeusone.com/pathfinding.php
A ver si me echais una mano con esto que os pido de las listas y os muestro lo eficiente que puede llegar a ser esto ya que se utiliza en juegos como Warcraft o Starcraft para el calculo de movimiento de unidades en mapas de mas de 256x256 (claro que aplican algunas tecnicas de reduccion de posibilidades, pero estos son los principios)