Hola chicos, espero estén muy bien, llevo un tiempo pensando en un proyecto de estrategia con tile movement y pathfinding, he logrado algunas cosas, pero no he podido entender el algoritmo de pathfinding (Y créanme, lo he intentado). Hay muchos recursos en ingles, en youtube esta quill18 que explica todo el sistema, pero mi ingles es bastante malo y me pierdo en algunas partes de la explicación. He llegado al foro con la esperanza de que alguien me explique o tenga un tutorial a la mano del algoritmo de dijkstra en español o algún otro algoritmo de búsqueda del camino mas corto, en el foro encontré algo parecido a lo que buscaba pero esta en ingles y de verdad que me cuesta entender la lógica de ese algoritmo.
 
Cabe mencionar que utilizo C# y Unity.
 
Algunos de los tutoriales que he leído he intentado:
 
Tutoriales de Quill18 en youtube
 
A* Pathfinding para Principiantes
 
ALGORITMO DE BÚSQUEDA A* (PATHFINDING A*) – XNA
 
Tutoriales de Sebastian Lague en youtube
 
 
 
Cabe destacar que he seguido paso a paso los tutoriales de youtube, pero sigo sin entender la lógica, puedo mover objetos en el grid, pero no entiendo la lógica para poder agregar mecanicas de juego.
 
 
 
Muchas gracias y un saludo,
 
Nelbi Alvarado.

Hola,
 
¿Qué es exactamente lo que no entiendes?
 
Si divides tu problema en problemas más pequeños puedes encontrar en que parte estás fallando, he programado varios algoritmos de pathfinding en varios lenguajes, no tuve muchos problemas, aunque la verdad es que siempre he usado manhattan que no es complicado y hay bastante información como los enlaces que has puesto.
 
Es en Inglés, pero está página contiene mucha y muy buena documentación:
 
http://www-cs-students.stanford.edu/~amitp/gameprog.html#Paths
 
No entiendo la última parte:
 

Cita de: nlbi21 date=1481239697Cabe destacar que he seguido paso a paso los tutoriales de youtube, pero sigo sin entender la lógica, puedo mover objetos en el grid, pero no entiendo la lógica para poder agregar mecanicas de juego.
   
   
       
   

 
 
El algoritmo lo único que hace es encontrar el camino por el cual debes ir, tú después ya debes implementar lo que quieras (movimiento, mécanicas, etc...)

Hola OldGuy,
 
Antes que nada agradecer tu pronta respuesta, sobre la cita, te cuento que seguí el tutorial al pie de la letra y funciona pero no entiendo la lógica.
 
Pasos que sigo:
 

1. 
      Creo una variable enum para los tipos de tiles existentes, en mi caso (CAMINABLE, NOCAMINABLE).
   


2. 
      Creo el mapa (Tiles) uno a uno con un metodo repetitivo en este caso un For.
   


3. 
      Le asigno a cada uno un valor en el plano cartesiano (X,Y) y su respectivo enum.
   


4. 
      Asigno cada tile a un array.
   


5. 
      Necesito dos variables para guardar el origen y el destino, para empezar hacer los cálculos  (Hasta este punto entiendo la lógica).
   

Ya que desde allí empieza todo, se que necesito algo para identificar los vecinos, también el coste del movimiento, pero ya desde aquí me pierdo y no entiendo nada. Agradecería cualquier ayuda, por cierto esa pagina me falto colocar la verdad esta muy completa, hasta tiene un apartado de C# pero que va no entiendo el algoritmo y eso lo que deseo entender la lógica mas que todo.
 
 
 
Muchas gracias de nuevo OldGuy.

Si los tiled's por ejemplo son de 1x1 es facil saber sus vecinos, (x+1, x-1, y+1,y-1...etc). Y asi obtener las coordenadas de los nodos vecinos.

Cita de: GSG3D date=1481247490Si los tiled's por ejemplo son de 1x1 es facil saber sus vecinos, (x+1, x-1, y+1,y-1...etc). Y asi obtener las coordenadas de los nodos vecinos.
   

Ummm... claro recorrería todos los array hasta encontrar el destino.
 
Vamos con los ejemplos:
 
Imaginemos que es un mapa 5 x 5, Este estaría conformado por
 

// Ojo solo es un ejemplo para entender el algoritmo.
// este seria el array del mapa, aca identificamos cada uno en el plano cartesiano.
int[] map = [   (0,0),(0,1),(0,2),(0,3),(0,4),
(1,0),(1,1),(1,2),(1,3),(1,4),
    (2,0),(2,1),(2,2),(2,3),(2,4),
    (3,0),(3,1),(3,2),(3,3),(3,4),
    (4,0),(4,1),(4,2),(4,3),(4,4) ];
   
// 2 array uno con el origen y otro con el destino.
int[] origen = [(0,0)];
int[] destino = [(4,4)];
// ¿un for para que busque en cada uno hasta encontrar el destino?
for (int x = 0; x < map.Length; x++ ){
if(map
 == destino[0]){
        Debug.Log ("Encontro el camino");
    }else{
       Debug.Log ("No encuentra el camino");
    }
}

 
¿Algo así?, ¿como guardaría cada uno de los mas cercanos? esto para ir moviendo paso a paso lo que deseo mover.
 
Un saludo y gracias.

Exactamente no, para que sea mas facil deberias tener una clase node, la cual tiene las coordenas propias y de sus vecinos (haciendo un recorrido u otro metodo) usando lo que te comente, por coordenadas.
 
Lo mas importante es que investigues sobre los costos de cada recorrido. Y asi realizar la busqueda por el menor costo.
 
En si este sistema(dijksta) es un grafo que busca el camino con menor "valor".

Hola de nuevo,
 
Para empezar yo me crearía una clase para manejar cada nodo, en la clase como mínimo debes de tener variables para poder almacenar los valores de coste desde el punto inicial, coste estimado desde principio al final (heurística) y el costo total. 
 
También necesitas tener una referencia al Nodo padre, que es muy importante, ya que es el que te va calculando el total de coste de los nodos anteriores. 
 
Algo así:
 

public class Node  {
    public float posX;
    public float posY;
    public int tileType;
    public Node father;
    public int costTotal;
    public int costFromInitialPoint;
    public int costForFinalPoint;
}

 
 
 
Después también necesitas listas para ir controlando que nodos sacas, cuales introduces en la lista abierta, cerrada, etc...  
 
El proceso para el manhattan por ejemplo sería algo así:
 
- Empezamos por el nodo final (así es más fácil, porque el camino siempre te sale al revés, y no tienes que darle la vuelta).
 
- Miramos todos sus nodos adyacentes, y calculamos sus costes. (importante poner que son hijos del primero)
 
- El que tiene menor coste lo pasamos a la lista cerrada, y vamos calculando de nuevo los costes de los adyacentes, poniendo como padre al nuevo seleccionado.
 
- Y así es un bucle hasta que el el nodo con menor valor es igual al nodo final (en este caso sería en nodo inicial, ya que hemos comenzado al revés), una vez ahí el recorrido termina, ya solo debemos seguir el camino comenzando por el nodo inicial y mirar cual es su padre, de está forma cada padre de cada nodo es el siguiente nodo al que debemos continuar.
 
 
 
Es importante entender la teoría antes de programar nada, una vez la entiendes programarlo es fácil. Si no entiendes alguno de los pasos, pregunta, y vemos como te lo puedo explicar mejor (que reconozco que no sé me da bien jeje)
 
Un saludo.
 
 

@OldGuy Gracias por la ayuda a ambos, hoy haré un prototipo rápido en cuando llegue de hacer unas cosas, les publicare lo que pude lograr, ya por lo menos tengo una idea, comentare el código y eso para que me digan como voy, lo mas importante para mi es entender la lógica del algoritmo y que me den algunos consejos de como implantarlo. Me molesta un poco que ame los juegos de estrategia y no pueda hacer uno .
 
Sabes @OldGuy no entiendo porque utilizas floats en las posiciones, yo pensaba usar enteros para que el tile en si sea la posición no se si me entiendes, osea el centro del tile seria la posición. Otra cosa que no entiendo es lo del nodo padre, si puedes por favor agradecería que me explicaras eso.
 
Lo de la clase Nodo lo entiendo.
 
En lo que llegue posteare un ejemplo (con los ejemplos me explico mejor).
 
Un saludo, y gracias de nuevo a ambos.

@GSG3D He vuelto miren por ejemplo estos códigos:
 

• 
     Clase TipoTile
  


• 
     Generador del mapa
  

De estos dos scripts obtengo Generación del mapa, ahora agrego un nuevo script:
 

• 
     Script posición clikeada
  

Esto seria la base para empezar el estudio del algoritmo, aun no he hecho ni el nodo ni nada, quisiera que partiéramos de aquí. Desde este punto ya puedo mover la unidad seleccionada a cualquier tile, pero "teletransportandolo" no va de tile en tile, ni respetando ninguna regla en este punto es necesario el pathfinding.
 
No se sí hice doble post /: o sí esta mal puesto el post ya que debí (creo yo), colocarlo en la sección de scripting, pero como estamos divagando en el tema del camino mas corto no lo creí conveniente, aunque pienso que tiene un poco de ambos ademas de que seria útil para el foro en general.
 
De antemano gracias, un saludo.

Lo de los float, es para una posición 2D real del mundo, utilizo los float en vez de un vector2 porque me facilita realizar operaciones con ellos. Si utilizara enteros ya estoy reduciendo el algoritmo a un tipo determinado de tamaño del tile, cuando lo interesante es que se pueda utilizar en otros tamaños, por ejemplo. El algoritmo una vez creado se puede utilizar en otros juegos fácilmente, y esto te facilita que se pueda implementar en varios tamaños de tile o modelos 3D.
 
Lo de mover olvídate de momento, eso es lo último una vez ya sabes cual es el camino. Ahora una vez que tienes el nodo inicial (donde se encuentra el jugador o lo que deseas mover) y el nodo final (donde haces click), hay que empezar con el algoritmo. Deberías crear métodos para comprobar adyacentes, calcular costes, e introducirlos en la lista abierta.

@OldGuy Gracias por responder, disculpa lo tarde es que participe en el ludum dare y estaba full con eso pero ya termine, ahora en cuando tenga un tiempo me pongo a hacer la comprobación de adyacentes y te aviso por acá, claro sí no te molesta.
 
Y gracias otra vez por la paciencia, un saludo.