Pathfinding
We'll be covering different algorithms in order to find the shortest route: Breadthwise, Depthwise and AStar.
using System.Collections.Generic; using UnityEngine; public class PathFinding { //algorithm to find a route between points //normally traversing a structure such as a graph //3 of them: //breadthwise search (uninformed) por nivel //Depthwise (uninformed) //A-Star (heuristic) //It will find a path public static List<Waypoint> Breadthwise(Waypoint start, Waypoint end){ //por niveles Queue<Waypoint> work = new Queue<Waypoint> (); List<Waypoint> visited = new List<Waypoint> (); Waypoint current = start; start.history = new List<Waypoint> (); work.Enqueue (start); visited.Add (start); List<Waypoint> result = new List<Waypoint> (); while (work.Count > 0) { current = work.Dequeue (); if (current == end) { result = current.history; result.Add (current); return result; } else { //add neighbors to queue for (int i = 0; i < current.neighbors.Length; i++) { //test if neighboor was visited Waypoint currentNeighbor = current.neighbors[i]; if(!visited.Contains (currentNeighbor)){ work.Enqueue (currentNeighbor); visited.Add (currentNeighbor); //who ever was your parents parents is there and you also add your parents currentNeighbor.history = new List<Waypoint> (current.history); currentNeighbor.history.Add (current); } } } } return null; } public static List<Waypoint> Depthwise(Waypoint start, Waypoint end){ Stack<Waypoint> stack = new Stack<Waypoint> (); List<Waypoint> visited = new List<Waypoint> (); stack.Push (start); visited.Add (start); start.history = new List<Waypoint> (); while(stack.Count > 0){ Waypoint actual = stack.Pop (); if (actual = end) { List<Waypoint> resultado = actual.history; resultado.Add (actual); return resultado; } else { for (int i = 0; i < actual.neighbors.Length; i++) { Waypoint hijoActual = actual.neighbors[i]; if (!visited.Contains (hijoActual)) { stack.Push (hijoActual); visited.Add (hijoActual); hijoActual.history = new List<Waypoint> (actual.history); hijoActual.history.Add (actual); } } } } return null; } public static List<Waypoint> AStar(Waypoint start, Waypoint end){ List<Waypoint> visited = new List<Waypoint> (); List<Waypoint> work = new List<Waypoint> (); work.Add (start); visited.Add (start); start.history = new List<Waypoint> (); start.g = 0; start.f = Vector3.Distance (start.transform.position, end.transform.position); //distancia lineal while (work.Count > 0) { Waypoint actual = work [0]; for (int i = 0; i < work.Count; i++) { // ver cual tiene la f mas pequeña if (work [i].f < actual.f) { actual = work [i]; } } work.Remove (actual); if (actual == end){ List<Waypoint> result = actual.history; result.Add (actual); return result; } else { for (int i = 0; i < actual.neighbors.Length; i++) { Waypoint hijoActual = actual.neighbors [i]; if(!visited.Contains(hijoActual)){ work.Add (hijoActual); visited.Add (hijoActual); hijoActual.history = new List<Waypoint> (actual.history); hijoActual.history.Add (actual); hijoActual.g = actual.g + Vector3.Distance (actual.transform.position, hijoActual.transform.position); float h = Vector3.Distance (hijoActual.transform.position, end.transform.position); hijoActual.f = hijoActual.g + h; } } } } return null; } }