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.

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.

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.

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.

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

Ok, gracias. En cuanto pueda cuelgo el proyecto.

No creo que puedan estár desordenados los puntos ya que los creo con un script

Está bien, Hosuko, lo de poner os obstáculos aleatorios, aunque siendo totalmente aleatorio, la matriz te puede quedar muy liosa y difícil. Yo ahora me he hecho otro script que funciona en edit mode, y lo que hace es cambiar la casilla seleccionada de transitable a obstáculo, pulsando una tecla, para cambiar rápidamente el mapa sin tener que volver a meterme en scrips.

Por otro lado, sigo atascado con mi player, no se que pasa que desde que me creé la matriz con este método, con el que al final conseguí tenerla bien ordenada con el 0000 arriba a la izquierda, no he conseguido que trace bien los caminos. Todo el rato se me va al 0000, o incluso se pasa y se va fuera de la matriz y  se queda allí xD.

Seguiré investigando a ver por qué ahora no me va  :dry:  

Muy buena pinta tiene el A* de lonog.

Buenas, he escrito unos scripts para crearme el escenario con solo decir un número de filas y de columnas en el inspector.

El problema es que me lo crea de abajo a arriba y de izquierda a derecha... y luego el pathfinding no funciona, creo que debido a eso.

Puede ser esa la causa? Que no empiecen por arriba a la izquierda?


De todos modos os dejo aquí los scripts por si os interesan.
Solo necesitáis tener 2 prefabs; uno de PuntoMatriz y otro de Obstaculo. Con sus tags y todo lo necesario para que se vean.

CrearTablero.js // Este yo lo pongo en el player, por ejemplo.

var plano : GameObject;
var obstaculo : GameObject;
var alto: int;
var ancho  : int;

function Start () {

for (var i : int = alto; i >=0; --i)
{
        for (var j : int = 0; j 12)   
           Instantiate(plano,Vector3(i,0,j),Quaternion.identity);
           else
           Instantiate(obstaculo,Vector3(i,0,j),Quaternion.identity);
   }
}

}

RenombradoCelda.js  // ponedlo en los 2 prefabs que hablé antes.

private var nameaux : String;
private var cero : int;

function Start () {

cero = 0;

if(transform.position.z

Un saludo

Muy buena la página de Starco, si señor. Qué de información sobre PathFinding!

Yo voy a seguir con este script... Esta mañana en el trabajo traté de hacerme un script que me creara todo el conjunto de planos que conforman la cuadrícula, para así no tener que ir poniendo nombres tipo 0103 a cada plano. Ya casi lo tenía pero me vi con un lío de arrays así que ya lo tocaré otro día.

Como dices Hosuko, es limitado y servirá para pocos juegos, pero si se investiga un poco más sobre él, creo que puede valer perfectamente para un mapa complejo.

Un saludo!

Entendido.

Muy buena explicación, con matrices y todo. Gracias de nuevo.

Pues exactamente eso es lo que he hecho y por eso he llegado a esos resultados, jeje. Ponérselo dificil al algoritmo, vaya, ya que le había puesto obstáculos en los bordes y también obstáculos en U...


Lo de los numeritos ya me di cuenta que sería por lo de tener un mapa más grande.

Intentaré mejorar el algoritmo en cuanto pueda ya que quiero seguir con mi idea de RTS. Me está gustando esto.

Un saludo!

Buenas.

Tengo una duda a la hora de poner en marcha el pathfinder.

En la escena qué tengo que crearme, un plano por cada punto de la matriz, y renombrarlo con 0000,0100,0101, etc?

El caso es que no entiendo bien porqué al hacer el Parseint, usas los 2 caracteres para cada componente. Si tenemos una matriz de 10x10, no haría falta solo 1 carácter por componente?

EDITO:

Ya he conseguido hacer que funcione. He añadido unas frases para que me coloree las casillas de obstáculo de verde y así ver si funciona bien.

Tras probar un buen rato, he visto que funciona bastante bien y tiene mucho potencial. Hay veces que funciona perfecto, y alguna vez que no se por qué, al buscar un camino, se va hasta la casilla (0,0) y luego desde allí busca el camino en vez de buscar desde donde se encuentra en principio. Te ha pasado lo mismo?

Seguiré haciendo pruebas.

Un saludo.

Guau, ya he leído tu código y entendido creo que todo. Está perfectamente comentado, enhorabuena.

Solo me falta ponerme a usarlo en el unity. A ver si tengo hoy un ratillo y lo intento.

Además, con tu código, he aprendido que hacer clases con Js no es tan diferente de C#.

Un saludo. Te seguiré informando.

Muchas gracias Mantis. He bajado el código del pathfinding de Arongramberg usando raycast, y la verdad es que está trabajado. Lo iré estudiando poco a poco.

De todos modos también he bajado tu package y he visto que el código es simple y muy entendible. Creo que probaré a hacer cosas con él.
Ya te contaré qué tal me va. Además entiendo mucho mejor el Js que el C# no sé por qué.

Un saludo.

Muy buen tema. Horas y horas he echado yo a intentar idear un pathfinder basado en raycast, pero las soluciones siempre me han salido muy acaparadoras de recursos, y al fin y al cabo, es mejor dividir el escenario en cuadrados o nodos y hacer un pathfinder inspirado en A*.

De todos modos, este que comentáis, me voy a bajar el código para estudiarlo bien, porque tiene pinta de estar bastante optimizado, y como bien decís, a veces no necesitas el camino más corto, si no simplemente llegar al punto esperado.

Gracias por eel aporte.