Conseguido!!!   :D :D :D

Era eso que calculaba mal la G. Bueno, mi máximo agradecimiento, es todo un logro para mi, haber conseguido y entendido realizar esto, con toda vuestra ayuda, que no ha sido poca. Aunque lo importante es que ahora lo entiendo, a parte de saber hacerlo, y el subidon que te pega cuando realizas algo en lo que llevas tanto esforzandote, estoy muy contento en este momento.

Se que para muchos es fácil, pero para mi es todo un logro, lograr aplicar algo así cuando nunca antes he programado.

Lo dicho que muchas gracias por vuestra ayuda, seguro que sin ella no habría podido lograrlo, o entenderlo, y que siento haber sido tan pesado.

Saludos.

Bueno, he conseguido un pasito más, ahora ya llego al final de camino, pero ahora el problema lo tengo al volver hacia atrás, pasando de hijo a padre.

El problema que tenía lo solucione como decíais, me buscaba la F más baja, pero a veces esa F ya estaba en la lista cerrada, con lo que al comprobar vecinos, siempre daba los mismos, y se quedaba en bucle. Lo que he hecho, ha sido una vez cogido el valor F más bajo, comprobar que no esta en la listaCerrada, y si es así coger el segundo valor más bajo F, el tercero, etc...

No creo que sea la mejor solución, pero de esta forma llego al final del camino, comprobando todos los posibles caminos.

Ahora tengo el problema, como decía en volver hacia atrás, voy pasando de hijo a padre, pero llega un momento, que se queda en bucle en dos cuadros, pasando entre ellos de hijo a padre. Esto es supongo, por que a la hora de crear el camino, tengo que tener al conflicto a la hora de asignar o cambiar el padre de cada nodo vecino.

Este es el código para ir hacia atrás, que creo que esta bien:

Código [Seleccionar] Expand


if(!listaPadres.Contains(nodo[inicioX,inicioY]))
{
int aux;
int auy;
aux = inicioX;
auy = inicioY;
listaPadres.Add(nodo[aux,auy]);
inicioX = nodo[aux,auy].padre.x;
inicioY = nodo[aux,auy].padre.y;

}


Aunque el fallo, pienso que tiene que estar como digo, a la hora de asignar o comprobar el padre (si tiene un valor G más bajo):

Código [Seleccionar] Expand


         if(listaAbierta.Contains(nodo[ix, iy]))
         {           
            if(nodo[ix,iy].valorG <= nodoRecorrido.valorG)
            {
               nodo[ix,iy].padre = nodoRecorrido;
               nodo[ix,iy].CalcularG();
               nodo[ix,iy].CalcularF();
            }
         }
         else {
               nodo[ix, iy].padre = nodoRecorrido;
               nodo[ix, iy].valorH = 10*(Mathf.Abs(ix  - fx) + Mathf.Abs(iy - fy));
               nodo[ix, iy].CalcularG();
               nodo[ix, iy].CalcularF();
               listaAbierta.Add(nodo[ix, iy]);               
         }


También es posible que siga calculando mal la G?? y cuando compruebo si un nodo que ya esta en la lista abierta tiene un valor G más bajo, y le cambio el padre por el nodo comprobado, y que de esta manera tambien me falle al asignar el padre, no??

Bueno, gracias a vosotros, poquito a poquito parece que lo voy consiguiendo, también es verdad que cada vez me canso más, llevo ya varios días dedicandole muchas horas a este código, y frusta no conseguir algo, y aunque no suelo rendirme, esta casi a punto de superarme, jeje.

Saludos.

Hola blau,

he seguido probando, he probado tu código, y me sigue fallando, aunque los padres escogidos son diferentes. Estoy probando por ejemplo el camino de 1,1 a 5,5, y haciendo un poco de pruebas, veo que se me meten en la listaCerrada los siguientes cuadros:

1,1 -- 1,2 -- 2,1 -- 2,2 -- 3,1 -- 4,1

Después he visto que se me queda comprobando todo el rato los cuadros 1,2 y 3,1 y de ahi no sale el bucle.

Puede que el problema este en la forma de hacer esas comprobaciones?? el código es el siguiente:

Código [Seleccionar] Expand



               if(activo)
{
if(nodo[inicioX,inicioY] != nodo[finalX,finalY])
{
VecinosYCalculoFFF(nodo[inicioX,inicioY], nodo[finalX,finalY]);
ListaOrdenarF();
inicioX = listaAbierta[0].x;
inicioY = listaAbierta[0].y;
listaCerrada.Add(nodo[inicioX,inicioY]);
}
if(nodo[inicioX,inicioY] == nodo[finalX,finalY])
{
Debug.Log("son iguales");
}
}



O en la forma de calcular la G?? en la clase Nodos:

Código [Seleccionar] Expand



public void CalcularG()
{
if(padre != null)
{
valorG = 10 + padre.valorG;
}
else
{
valorG = 10;
}
}




Creo que la cosa tiene que andar por ahí no?? Ya que se me queda todo el rato comprobando dos cuadros, que supongo que no encuentra un F menor y siempre va comprobando los mismos??

Por cierto, que manera de optimizar el código, lo que yo tenia en un tocho, los ha optimizado a 4 lineas, la verdad he aprendido bastante solo mirando tu código, lo fácil que lo has hecho.

Y muchas gracias por la ayuda, no me canso de decirlo, pero es que me siento pesado al preguntar tanto y no poder conseguirlo.

Un saludo.

Puede que el problema sea que no calculo las diagonales??

Yo pensaba que al no tener que usarlas, no hace falta calcularlas, pero estoy equivocado??

Es que he visto que videos donde se utiliza Manhattan que el camino se forma sin utilizar diagonales, pero en cambio he visto algunos que dicen ser Manhattan tambien, que utilizan diagonales en algunos sitios, pero por ejemplo donde hay Pared/NoTransitable la hace sin diagonal, cual es el metodo Manhattan correcto? O son los dos, y están adaptados de distinta forma?

Por cierto, no es que esten espesos, estoy seguro que es problema mio y mi forma de programar, soy un poco mayor ya y esto la verdad es que cuesta, cuando toda tu vida te has dedicado al diseño, aunque intento no rendirme nunca, e intentar aprender cada día un poco más.

Gracias, saludos.

Hola Vicente,

a ver si se explicarme, que seguro que es más eso a que tu estes espeso jeje.

La manera de inicializarlo, es, tengo una clase Nodos, en las que almaceno sus coordenadas en el mapa, sus valores F, etc tal como así:

Código [Seleccionar] Expand



public class Nodos
{
public int x;
public int y;

public int valorG;
public int valorH;
public int valorF;

public GameObject objeto;
public Nodos padre = null;

public bool pared = false;

public Nodos()
{
if(padre == null)
{
valorG = 10;
}
}

public void CrearNodo(int XX, int YY, GameObject obj)
{
x = XX;
y = YY;
objeto = obj;
}

public void CalcularF()
{
valorF = valorG + valorH;
}

public void CalcularG()
{
if(padre != null)
{
valorG = 10 + padre.valorG;
}
else
{
valorG = 10;
}
}


}




Después inicializo esta clase con un for, creando tantas filas y columnas como necesite, de esta manera:

Código [Seleccionar] Expand



nodo = new Nodos[numeroCeldas, numeroCeldas];
listaAbierta = new List<Nodos>();
listaCerrada = new List<Nodos>();

for (int i = 0; i < numeroCeldas; i++)
{
for (int j = 0; j < numeroCeldas; j++)
{


GameObject pl = GameObject.CreatePrimitive(PrimitiveType.Plane);
nodo[i,j] = new Nodos();
nodo[i,j].CrearNodo(i,j,pl);
nodo[i,j].objeto.transform.localScale = new Vector3(.097f,.097f,.097f);
nodo[i,j].objeto.transform.position = new Vector3(i,0,j);
nodo[i,j].objeto.renderer.material = matCelda;
nodo[i,j].objeto.name = "Nodo" + i + "_" + j;





En cuanto a la heurística, si que es manhattan, lo multiplico por 10 por que el valor me iba mejor para calcular otras cosas que tenia en mente, pero en principio eso tiene que dar igual, por que todos los nodos es el mismo valor, no??


Pongo una imagen, de como lo tengo ahora, los nodos resaltados, son los nodos que se van metiendo en la lista cerrada.




En este caso, estoy intentando ir desde la casilla 1,1 a la casilla 5,5. Siendo 0,0 esquina inferior izquierda y 5,5 esquina superior derecha.

El G lo calculo en cada vecino, lo que hago es sumar 10 (al ser todo movimientos sin diagonal) a la G de su padre.

Bueno, aquí estoy de nuevo, la verdad es que es muy interesante toda la información que habéis dado.

He seguido trabajando en el Algoritmo, y casi que lo tengo, pero algo me falla. Cuando el camino es directo y no tiene que buscar alternativas, lo hace bien, pero cuando encuentra más de un camino, a veces me falla.

A ver si sabéis en que estoy fallando, la verdad es que no paro de intentarlo, he escrito ya varias veces comenzando desde 0, pero al aprender todo por mi cuenta, es posible que algunas cosas las haga mal.

Esta hecho en C#:
Esta es el proceso:

Código [Seleccionar] Expand


if(activo)
{
if(nodo[inicioX,inicioY] != nodo[finalX,finalY])
{
VecinosYCalculoF(nodo[inicioX,inicioY], nodo[finalX,finalY]);
ListaOrdenarF();
inicioX = listaAbierta[0].x;
inicioY = listaAbierta[0].y;
listaCerrada.Add(nodo[inicioX,inicioY]);

}
if(nodo[inicioX,inicioY] == nodo[finalX,finalY])
{
Debug.Log("son iguales");
}
}



Para situarnos y no poner todo el código, tengo un mapa creado con distintos cuadros, cada uno almacenado con su posición, y valores G, H, F. Lo que hago es comprobar que el nodo de inicio que le paso no es igual al nodo final, y mientras me va creando el algoritmo, creo que aquí debería ir un while, pero no me encuentra nunca el final, y hace que el programa se bloquee.

Código [Seleccionar] Expand



public void VecinosYCalculoF(Nodos nodoRecorrido, Nodos nodoFinal)
{
int ix = nodoRecorrido.x;
int iy = nodoRecorrido.y;
int fx = nodoFinal.x;
int fy = nodoFinal.y;


//Izquierda
if((ix - 1) >= 0)
{
if(listaAbierta.Contains(nodo[ix - 1, iy]))
{

if(nodo[ix - 1,iy].valorG < nodo[ix,iy].valorG)
{
nodo[ix - 1,iy].padre = nodo[ix,iy];
nodo[ix - 1,iy].CalcularG();
nodo[ix - 1,iy].CalcularF();
}
}
else if(nodo[ix - 1, iy].pared == false)
{
if(listaCerrada.Contains(nodo[ix - 1, iy]) == false)
{
nodo[ix - 1, iy].padre = nodo[ix,iy];
nodo[ix - 1, iy].valorH = 10*(Mathf.Abs((ix - 1) - fx) + Mathf.Abs(iy - fy));
nodo[ix - 1, iy].CalcularG();
nodo[ix - 1, iy].CalcularF();
listaAbierta.Add(nodo[ix - 1, iy]);
}
}
}

//Derecha
if((ix + 1) <= 5)
{
Debug.Log("comprueba si es menor de 5");
if(listaAbierta.Contains(nodo[ix + 1, iy]))
{

Debug.Log("Comprueba que no esta en la lista abierta");
if(nodo[ix + 1,iy].valorG < nodo[ix,iy].valorG)
{
Debug.Log("G es menor");
nodo[ix + 1,iy].padre = nodo[ix,iy];
nodo[ix + 1,iy].CalcularG();
nodo[ix + 1,iy].CalcularF();
}
}
else if(nodo[ix + 1, iy].pared == false)
{
Debug.Log("B = no es pared");
if(listaCerrada.Contains(nodo[ix + 1, iy]) == false)
{
Debug.Log("B = No esta en la lista cerrada");
nodo[ix + 1, iy].padre = nodo[ix,iy];
nodo[ix + 1, iy].valorH = 10*(Mathf.Abs((ix + 1) - fx) + Mathf.Abs(iy - fy));
nodo[ix + 1, iy].CalcularG();
nodo[ix + 1, iy].CalcularF();
listaAbierta.Add(nodo[ix + 1, iy]);
}
}
}

//Arriba
if((iy + 1) <= 5)
{
if(listaAbierta.Contains(nodo[ix,iy + 1]))
{

if(nodo[ix,iy + 1].valorG < nodo[ix,iy].valorG)
{
nodo[ix,iy + 1].padre = nodo[ix,iy];
nodo[ix,iy + 1].CalcularG();
nodo[ix,iy + 1].CalcularF();
}
}
else if(nodo[ix,iy + 1].pared == false)
{
if(listaCerrada.Contains(nodo[ix,iy + 1]) == false)
{
nodo[ix,iy + 1].padre = nodo[ix,iy];
nodo[ix,iy + 1].valorH = 10*(Mathf.Abs(ix - fx) + Mathf.Abs((iy + 1) - fy));
nodo[ix,iy + 1].CalcularG();
nodo[ix,iy + 1].CalcularF();
listaAbierta.Add(nodo[ix, iy + 1]);
}
}
}

//Abajo
if((iy - 1) >= 0)
{
if(listaAbierta.Contains(nodo[ix,iy - 1]))
{

if(nodo[ix,iy - 1].valorG < nodo[ix,iy].valorG)
{
nodo[ix,iy - 1].padre = nodo[ix,iy];
nodo[ix,iy - 1].CalcularG();
nodo[ix,iy - 1].CalcularF();
}
}
else if(nodo[ix,iy - 1].pared == false)
{
if(listaCerrada.Contains(nodo[ix,iy + 1]) == false)
{
nodo[ix,iy - 1].padre = nodo[ix,iy];
nodo[ix,iy - 1].valorH = 10*(Mathf.Abs(ix - fx) + Mathf.Abs((iy - 1) - fy));
nodo[ix,iy - 1].CalcularG();
nodo[ix,iy - 1].CalcularF();
listaAbierta.Add(nodo[ix, iy - 1]);
}
}
}



Este es el método que llamo al principio, y que me selecciona todos los vecinos(solo me calcula el los laterales, superiores e inferiores, porque necesito que sea así, ya que solo quiero movimientos rectos, no diagonales.

La primera comprobación que hace para cada vecino, es para saber que no me paso en la matriz, y no me devuelva una objeto de la matriz del mapa vacío (es decir que no hay mapa).

Después compruebo si el vecino esta en la lista abierta, si es así compruebo si su valor G es menor al nodo analizado, y si es así, le cambio el padre del vecino al nodo analizado. Si no es así entonces compruebo que no sea pared o este en la lista cerrada, y calculo F y lo meto en la lista abierta.

Después el proceso comenzaría de nuevo, ordena la lista abierta, coge el valor F más bajo y lo mete en la lista cerrada, coge a los vecinos de este ultimo, etc... hasta encontrar el ultimo nodo.

____________________

No se donde puedo fallar, estaría super agradecido si me ayudarais un poco, o que al menos me guiaseis con alguna pista de lo que pueda estar haciendo mal.

Gracias, un saludo.

Creo que ahora si que lo acabo de entender, tenías razón, me faltaba por entender la función del padre, que además de servir para seleccionar todos los Nodos vecinos, sirve para saber a la vuelta el camino correcto, pasando de hijo a padre.

Muchas gracias de verdad, ojalá todo el mundo fuera como aquí, hay veces que en algunos foros uno ya no se atreve a preguntar, por la manera en que se trata a uno, cuando los demás saben una cosa, que tu no sabes.

Voy a tirarme todo el día hasta la noche a intentar plasmarlo en el código, con los conceptos mejor entendidos por vuestra ayuda. Como puede enganchar tanto esto?? Me levanto pensando ya en el código...

Saludos!

Muchas gracias por la pronta respuesta, Vicente.

Sí, como dices, al menos como he leído hasta ahora, lista abierta es para poner los nodos que se van a analizar(nodos vecinos), descartando las paredes, etc... y la lista cerrada, se ponen los elegidos con el valor F más bajo.

Entonces, según me dices, si cojo el que quiera, a la hora de un empate, hay veces que me encuentra el camino más largo, que tengo que hacer?? analizar todos los posibles caminos, y después volviendo para atras es cuando se va eligiendo el camino correcto y más corto?

A la hora de llegar al final, que tengo que recorrer la lista cerrada hacia atrás, esto la verdad es que no entiendo mucho, el resultado no tendría que ser el mismo??

A ver si es que no estoy entendiendo el concepto bien, y por eso no me sale:

Tengo un Punto de inicio y un Punto final, el Punto de Inicio directamente lo añado a la lista cerrada, entonces cojo todos los vecinos transitables de este Punto, los meto en la lista abierta, calculo su valor F, y cojo el que tiene menor valor F, y lo meto en la lista cerrada. En caso de haber dos valores iguales F que son los más bajos, meto los dos en la lista cerrada. A partir de aqui obtengo todos los nodos vecinos del Nodo que he metido en la lista cerrada, y si son dos, obtengo los de los dos, y voy haciendo esto hasta llegar al Punto Final.

Una vez llegado a este Punto final, que tengo que hacer, ir recorriendo al revés, es decir desde punto final a punto inicio, haciendo los mismos pasos que al llegar hasta el punto final? O tengo que ir siguiendo, a traves de la lista cerrada o abierta, conseguida con el camino de ida??

Mas o menos, esto es la idea que he entendido, de lo que he podido leer.

Como ves estoy un poco perdido en el concepto, mañana volveré a intentarlo, hoy llevo todo el día con el, pero no lo he conseguido, pero no me gusta rendirme.

Gracias de nuevo por la ayuda.

Hola, me sabe mal registrarme en un foro para comenzar pidiendo ayuda, pero no llevo mucho tiempo en esto, y buscando por internet donde podría encontrar ayuda, he visto que este era uno de los mejores foros para ello.

Mi duda es más que de entender lo que hace que de programación, a ver si se explicarme correctamente:

Según entiendo, el algoritmo coge el primer nodo, lo convierte en padre, y mira todo los nodos vecinos, los mete en la lista abierta, y el nodo padre a la lista cerrada.
Después calcula el F de todos los nodos vecinos, y el que tenga el F más bajo, pasa a la lista cerrada.
Aquí el algoritmo empieza de nuevo, con el nuevo nodo padre, a buscar los nuevos nodos vecinos (descartando paredes, etc...) y volver a calcular el F.

Esto es lo que yo entiendo, pero aquí me surgen las dudas, que pasa cuando se encuentran dos Nodos vecinos con el mismo valor F??

Claro según como tengo configurados los nodos, el que lee primero como nodo con F más bajo es que pilla, pero a veces ese camino es el más largo.

Otra cosa que no entiendo muy bien, es como se hace al final cuando se llega al Nodo Objetivo, para dar la vuelta recorriendo todos los nodos, para que? si ya los has calculado en la ida??

Una ultima cosa, cada vez que se empiezan a analizar los Nodos Vecinos, hay que dejar la lista Abierta vacía?? y empezar a meter los nodos vecinos en la lista vacía??

Un saludo.