Buenos días.

He estado haciendo algún cambio y he conseguido ya que me funcione, con el mapa creado por scripts.

Ahora me toca ponerme a optimizarlo.

Después de ver una cosilla que fallaba, metí esta línea:

Matriz[PosicionPlayerSiguiente.x][PosicionPlayerSiguiente.y] = -2;
Matriz[PosicionPlayerActual.x][PosicionPlayerActual.y] = -2;

Al igual que actualizamos la casilla a la que vamos con valor -2, he actualizado también la casilla en la que estamos a -2, de forma que no la concibe como una casilla transitable en el resto del camino.

Creo que habrá casos en los que esto empeore el funcionamiento, pero en general, en mis pruebas, lo ha mejorado.
Me explico: Tengo la siguiente situación:

 6, 5, 4, 3, #, #, T, 1, 2, 3
 6, 5, 4, 3, #, #, 1, #, #, #
 6, 5, 4, 3, #, #, 2, #, #, #
 6, 5, 4, 3, 3, 3, 3, #, #, #
 #, #, #, 4, 4, #, #, #, #, #
 #, #, #, 5, 5, #, #, #, #, #
 #, #, #, #, 6, #, #, #, #, #
 #, #, #, #, 7, 7, P, #, #, #
 #, #, #, #, 8, 8, 8, #, #, #
 #, #, #, #, 9, 9, 9, 9, 9, 9

# = Obstáculo

P se encuentra en una casilla con un valor de 7.

Al usar la funcion PathFinder, elige desplazarse hacia la izquierda ya que 7 vale menos que 8. (Uso desplazamientos solo 4 direcciones)

Como no es el target, sigue moviéndose, y vuelve a recorrer las adyacentes:
como la casilla donde estaba el player era un 7, y es la última que recorre, se queda con esa como "siguiente posición", por lo que en vez de avanzar por el camino más coherente, vuelve a la casilla de inicio, y luego como la de la izquierda de P la dejó en valor -2, tira hacia abajo.

Si meto la línea que actualiza a -2 la casilla en la que se encuentra el player al principio, no vuelve a pasar por esa posición, por lo que en este mapa, el camino es bastante mejor. Izquierda y luego arriba en lugar de dar una vuelta.


Se que es una solución muy fácil y que en un callejón sin salida, te dejaría sin posibilidad de volver. Aunque sin esta línea ya te deja sin posibilidad de volver, en los callejones sin salida.

Hay que pensar alguna manera de que las casillas retomen su valor cuando ve frustrada su salida de un callejón. Me pondré con esto.

Un saludo

Buenas.

Os explico un poco un par de cambios que he hecho...

1ª Optimización:
Se trata sobretodo de la funcion Pathfinder, y unos contadores de casillas.
El primero, para tener en cuenta el número de posibles casillas que optan por ser la siguiente. Desechando las que quedan con -2, y los obstáculos.

De este modo, cuando hay solo 2 casillas que pueden ser elegidas, empleará otro método muy parecido al original, con el fin de no quedarse sin PosicionSiguiente, e irse al nodo (0,0).

Cuando este contador es 0, es decir, que no hay casillas libres a las que ir y por tanto el player está rodeado de casillas con valores -1 o -2, empieza otro método que contiene un contador más.

Este método va dando nuevos valores cada vez más negativos a las casillas que se han pisado repetidamente. Y recorriendo un ultimo for, el player se desplaza a la casilla que tenga un valor más alto esta vez. (en este caso todos los valores van a ser iguales o menores que -2)  

El contador de este método de momento sólo me sirve para debuguear. No le he dado uso aún.

El resultado, al menos en mis pruebas ha sido satisfactorio en cierto modo. Hay veces que si le pongo mucha velocidad al player, no le da la gana de pasar por alguna casilla, no se por qué, pero por lo demás, ahora no se va al nodo (0,0) ya que puede pasar por casillas marcadas con -2 y de hecho sigue buscando un camino tras pasar por ellas.


2ª Optimización:
También he cambiado la manera de recorrer el array que define las direcciones de las casillas adyacentes. (Solo lo he implementado para cuando usamos 4 direcciones posibles, sin diagonales).

Lo que hago es mirar dónde se encuentra el target relativamente al player, y cambiar el orden en el que se recorre el array de las posiciones adyacntes, de modo que en caso de tener dos posibles direcciones, deja para la última en chequear, la que es más intuitiva si no hubiese obstáculos.

Con esto se consigue tener más puntería a la hora de elegir un camino u otro en muchos casos.



Os dejo ahí el proyecto.  


[attachment=723]UnityProyecto3.part01.rar[/attachment]

[attachment=724]UnityProyecto3.part02.rar[/attachment]

[attachment=725]UnityProyecto3.part03.rar[/attachment]

No me dejaba subirlo de golpe en un archivo...

Espero que lo probéis y me digáis qué tal os funciona. Y las pegas que le veáis, o malas implementaciones que haya hecho.

Un saludo.

Que tal

He estado probando el proyecto. Ahora ya no va a (0,0) cuando no encuentra el camino y sigue buscando. En uno de los intentos ha estado buscando un buen rato pero al final lo ha encontrado jeje.

El algoritmo está bien y es rápido lo que pasa es que siempre estará en desventaja frente a el A* o el Brushfire ya que estos van almacenando el camino en un ArrayList y una vez encontrado es cuando empieza a moverse el personaje.

Habría que modificar el script pathfinder.js para que busque el camino y si existe lo almacene en un ArrayList, y una vez que tenemos todos los puntos del camino se dirija hacia el target. Y en el caso de que no lo encuentre no se mueva del sitio. Creo que es por ahí por donde se podría mejorar.

De todas formas sigo pensando que para un escenario simple funciona muy bien.  Yo voy a estudiar (cuando tenga tiempo) el Brushfire, que es muy parecido a este, pero te garantiza que va a encontrar el camino. Primero almacena los puntos y una vez tiene el camino es cuando el player se dirige hacia él.

Si lo implemento en unity lo colgaré en el foro.

Usaré tus scripts para la creación de la matriz.

He encontado esto sobre el algoritmo Brushfire o Wavefont:

Algoritmo brushfire en c++

web original:http://www.societyofrobots.com/programming_wavefront.shtml

Buenas.

Si, hay algún caso en el que al no poder escojer la opción correcta en una división de caminos, ya se va por otro lado y se pone a usar el último for que le puse al algoritmo, hasta que encuentra el camino.
Se recorre todo el mapa y ya cuando vuelve al punto conflictivo, lo hace bien. Supongo que ahora el algoritmo vale apra más casos. Mientras no se líe mucho el laberinto. la verdad es que el que le he puesto yo para probar, parece un poco Pac-Man.

Pero si lo que se quiere hacer es un RTS, por ejemplo, creo que podría ser bastante útil.

De todos modos voy a mirar yo también el Brushfire este del que habláis, que tiene buena pinta.

Un saludo.

Por lo que he visto con tan solo modificar la funcion ActualizarMatriz()  podemos tener el pathfinder.js por el método brushfire.

Estoy en ello.

Parece sencillo, si. Pero no entiendo el valor inicial que cogen las celdas adyacentes al target.
De donde sacan ese valor?

Por lo demás, parece que hay que usar recursividad para rellenar el tablero.

Cuanto más investigo lo del brushfire, más se me parece al A*... que lío.

Parece sencillo, si. Pero no entiendo el valor inicial que cogen las celdas adyacentes al target.
De donde sacan ese valor?

Por lo demás, parece que hay que usar recursividad para rellenar el tablero.

Cuanto más investigo lo del brushfire, más se me parece al A*... que lío.[/quote]

La diferencia parece estar en que el A* usa Heurística para encontrar el camino más cercano mientras que el brushFire No.

Estoy trabajando en como crear la matriz para el método BrushFire, por ahora no lo he conseguido.  Una vez consiga crear la matriz la sustituire por ActualizarMatriz() y deberia funcionar.  Pero no es tan sencillo crear la matriz

He encontrado este programita por si te interesa, donde se ejecuta el método Brushfire o WaveFront:

A mi me ha servido para ver como va contruyendo la matriz.

Ya veo. Es que, en realidad todo el problema de busqueda del camino óptimo se hace al calcular los valores de la matriz.
Ayer estuve con un amigo informático que me contó más o menos cómo tenía que ser.
Me dijo que él una vez usó algo parecido para un problema de rellenado de polígonos.

Y si, lo de la diferencia, parece que es solo lo de la heurística. De todos modos, el brushfire encuentra el camino con mucha más lógica que el que teníamos. Yo creo que si sacamos este, ya iríamos sobrados para cualquier necesidad de pathfinding.  :side:

Bueno luego el problema será correlaccionar estas casillas con un terreno 3d por ejemplo, o cosas así.

Un saludo y ánimo.

Yo sigo por mi parte intentándolo también, con este pseudocódigo:

Funcion Inundación(x, y, col1, col2)
color = LeerPixel (x,y)
Si (color!=col1 && color!=col2) entonces
PintaPixel (x,y,col1)
Inundación (x+1, y, col1, col2);
Inundación (x-1, y, col1, col2);
Inundación (x, y+1, col1, col2);
Inundación (x, y-1, col1, col2);

Lo saqué de aquí. Creo que el método es el mismo:
Relleno por Inundación


Por cierto, el .exe que has puesto está muy bien. Es útil si no quieres rellenar a mano . Vi ayer alguno parecido por ahí, y muchas gente que usaba el brushfire para movimientos de robots.

He estado mirando lo de colorear poligonos y he encontrado algo parecido.

Ve a la pagina 13.

EDITADO: Tengo problemas para subir el archivo te lo pongo aquí directamente:

5.3 Naive shortest paths through 
ooding
Our rst attempt was to use a slight modication of a shortest paths algorithm.
We call this a \
ooding" algorithm. This is a simple implementation of Kruskal's
shortest path algorithm made specic to mazes. Imagine a hose being placed
in a cell in the maze, and water being allowed to 
ow from a cell to a neighbor
in one unit time. A simple recursive algorithm will yield the amount of time
12
it takes for water to reach any point in the maze from any other point in the
maze, and an appropriate traversal of the matrix of 
ood values will yield the
shortest path.
Code for this algorithm is shown below. The 
ood values are represented
as a 16x16 array of integers (maze), and the wall congurations are represented
with four 16x16 boolean arrays called north, south, east, and west.

void Flood(int x, int y, int flood_val)
{
if (maze[y]
 > flood_val)
{
maze[y]
 = flood_val;
if (!east[y]
)
Flood(x+1,y,flood_val+1);
if (!west[y]
)
Flood(x-1,y,flood_val+1);
if (!north[y]
)
Flood(x,y+1,flood_val+1);
if (!south[y]
)
Flood(x,y-1,flood_val+1);
}
}

Once we have a 
ooding routine, it is easy to answer the question \what
is the best path from point a to point b". We simply 
ood the maze starting
at b with a 
ood value of zero, and then traverse the maze starting at a and
following decreasing 
ood values until we reach b. This works because once

ooding is done, the 
ood value at a is exactly the length of the path from a
to b. Therefore, if we follow the 
ood values in a monotonic decreasing order,
we are guaranteed to reach b in exactly the minimum amount of steps. Note
that the path generated by this algorithm is not unique, as there may be several
paths from a to b with identical lengths.
Also, because we know that the center of the maze is open, the maximum

ood value for any 
ood in any square is 254, so we can use 255 to initialize the

ood array, and can therefore represent the entire array of 
ood values in 256
bytes of memory. This is because the worst case for 
ooding is a spiral in which
the 
ow has to touch every square. If our 
ood starts at one corner of the maze,
and spirals towards the center, it will have length 252 when it enters the center
13
of the maze. Because we know that the center is an open 2x2 square, it will take
254 steps to get to the corner of the center, not 255 in the closed-center worst
case. Therefore, if all 
ood values are initialized to 255, a 
ood value of 255
represents an unreachable portion of the maze. MicroMouse maze designers will
often put these in the maze (i.e., a fully walled o square) to test the robustness
of the MicroMouse algorithms.
Although the straightforward 
ooding algorithm works well for a shortest
path com***tion, it does not allow our mouse to take full advantage of its acceleration
capabilities, and its ability to traverse diagonal paths without turning.
That is, because of how thin our mouse is, and the precise spacing of the sensors,
if we intend to traverse a \stairstep" pattern in the maze, we can simply turn 45
degrees and go straight without turning at all. This is a huge advantage, and is
yet another thing that MicroMouse maze designers will intentionally put in the
maze. The maze 
ooding algorithm is the one typically used by student mouse
projects when they are simply interested in getting something that works. It is
not a world class implementation of a physical maze solving algorithm, and we
clearly needed something better.

Si, todo esto es parecido.  Estoy intentándolo con algo de esta forma, basándome en ese algoritmo:

void ActualizarMatriz(Nodo NuevoTarget, int NuevoPeso){
   Target.x = NuevoTarget.x;
   Target.y = NuevoTarget.y;
   private int u,v;
   for (i = 0; i 


Antes de llamar a la función en el Start(), he puesto otro bucle que inicializa las celdas transitables a 9999.

Voy a ver qué tal va. 

Nota: Está en C# porque he cambiado otra vez a C#, simplemente para familiarizarme con él, Que quiero empezar a usarlo un poco más.

Un saludo.

Creo que lo he conseguido con el método de colorear poligonos. :cheer:

He creado una función llamada Flood() que es la que "inunda" la matriz. y he dejado ActualizarMatriz para que la inicialice a 99 o como tu dices a 9999 para no tener problemas con una Matriz mayor. Esta es la muy buscada y trabajosa  función Flood() jeje: :silly:

function Flood(x : int, y : int, flood_val: int){
    if (Matriz
[y] > flood_val && x = 0 && y >= 0){
        //Debug.Log("pos "+x+","+y+":"+Matriz
[y]);        
        Matriz
[y] = flood_val;
        if (Matriz
[y]!=-1 && x+1 = 0)
           Flood(x-1,y,flood_val+1);
        if (Matriz
[y]!=-1 && y+1 = 0)
            Flood(x,y-1,flood_val+1);
   }
}

En el bloque :

if(Input.GetKeyDown(KeyCode.Mouse0)){ 

}

He añadido :

 ActualizarMatriz(); //inicializa los valores de la matriz a 99
Flood(Target.x,Target.y,0); //inunda Matriz para meodo Brushfire o Wavefront

Ahora mismo me rellena toda la matriz pero con una leve modificación haré que se pare al dar con el Player

Pruebala   a ver que tal

He estado probando la función y Siempre encuentra el camino :silly: .

Te pongo una imagen de uno de los caminos que le he puesto: ( Lo encontró perfectamente sin desviarse ni hacer cosas raras

Le he puesto una matriz de 40 x 40 . Aún no he encontrado la manera de  que pare y no siga rellenando la matriz cuando encuentre al Player.

Ahí estamos!
En cuanto pueda la pruebo.
Estoy terminando mi implementación en C# de todo esto. A  ver si me funciona. Si veo que tengo muchos errores, me cojo tu Flood, y me vuelvo al Js.

Buen laberinto le has hecho, jeje. Es que está claro. Este método es mucho más eficaz.
Ahora habría que ponerse a pensar en lo que tú dices de que pare cuando encuentra al target, y luego ya mejoras en cuanto a costes de ir en diagonal , o en ortogonal, o distintos niveles de altura, que también cueste distinto subir, etc.
Lo veo asequible y muy útil.

Un saludo.

He estado haciendo cambios en Funcion Flood. La primera version era una locura, pisaba los valores de la matriz y se ejecutaba demasiadas veces.  Ahora compruebo que el valor de la casilla no ha sido asignado antes deañadir uno nuevo