Advertisement
Guest User

Untitled

a guest
May 25th, 2015
160
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 3.89 KB | None | 0 0
  1. private static List<PathNode> FindPath (Node start, Node target)
  2.         {
  3.             float startTime = Time.realtimeSinceStartup;
  4.  
  5.             //The nodes on the calculated path.
  6.             List<PathNode> path = new List<PathNode>();
  7.  
  8.             //The nodes which have been navigated.
  9.             List<Node> closed = new List<Node>();
  10.             //The nodes to be evaluated.
  11.             List<Node> open = new List<Node>();
  12.  
  13.             //Cost from start node to the current node.
  14.             Dictionary<Node, float> g_cost = new Dictionary<Node, float>();
  15.             //Total movement cost from a node to the target node.
  16.             Dictionary<Node, float> f_cost = new Dictionary<Node, float>();
  17.            
  18.             //Add the starting node to the open set.
  19.             open.Add(start);
  20.  
  21.             f_cost.Add(start, start.DistanceTo(target));
  22.             g_cost.Add(start, 0f);
  23.  
  24.             //How many times the loop has been ran.
  25.             int iterations = 0;
  26.  
  27.             Node previous = start;
  28.  
  29.             //While the open set isn't empty;
  30.             //while there are nodes to evaluate.
  31.             while (open.Count > 0)
  32.             {
  33.                 Node current = GetNextNode(open, f_cost);
  34.                 path.Add(new PathNode(previous, current));
  35.                 previous = current;
  36.  
  37.                 Debug.Log("i: " + iterations);
  38.                 if (current == null)
  39.                 {
  40.                     Debug.Log("No current node!");
  41.                     break;
  42.                 }
  43.  
  44.                 open.Remove(current);
  45.                 closed.Add(current);
  46.  
  47.                 if(current == target)
  48.                 {
  49.                     Debug.Log("Found complete path!");
  50.                     break;
  51.                 }
  52.  
  53.                 foreach(Node n in current.neighbours)
  54.                 {
  55.                     if (closed.Contains(n))
  56.                         continue;
  57.  
  58.                     if(!open.Contains(n))
  59.                     {
  60.                         open.Add(n);
  61.                         float g = n.DistanceTo(n);
  62.                         g_cost.Add(n, g);
  63.                         f_cost.Add(n, n.DistanceTo(target) + g);
  64.                         //parent.put(n,p)
  65.                     }
  66.                     else
  67.                     {
  68.                         float g = g_cost[current] + n.DistanceTo(n);
  69.                         if(g < g_cost[n])
  70.                         {
  71.                             g_cost.Add(n, g);
  72.                             f_cost.Add(n, n.DistanceTo(target) + g);
  73.                             //parent.put(n,p)
  74.                         }
  75.                     }
  76.                 }
  77.  
  78.                 //Exit the loop if we have iterated too many times.
  79.                 iterations++;
  80.                 if (iterations > _maxIterations)
  81.                 {
  82.                     if (current != target)
  83.                         Debug.LogWarning("Was unable to find a complete path to the target! Iterations exceeded!");
  84.                     break;
  85.                 }
  86.             }
  87.  
  88.             if(open.Count == 0)
  89.             {
  90.                 Debug.Log("Failed to find complete path! List of open nodes is empty!");
  91.             }
  92.  
  93.             float endTime = Time.realtimeSinceStartup;
  94.             Debug.Log("Generated path in " + (endTime - startTime).ToString("F5") + "ms");
  95.             return path;
  96.         }
  97.  
  98.         private static Node GetNextNode (List<Node> openList, Dictionary<Node, float> f_cost)
  99.         {
  100.             Node lowest = null;
  101.             float score = Mathf.Infinity;
  102.  
  103.             Debug.Log(openList.Count);
  104.             foreach(Node n in openList)
  105.             {
  106.                 float f = f_cost[n] + n.weight;
  107.                 if(score > f_cost[n] && n.isWalkable)
  108.                 {
  109.                     lowest = n;
  110.                     score = f;
  111.                 }
  112.             }
  113.  
  114.             return lowest;
  115.         }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement