SHARE
TWEET

Pathfinder Code

a guest May 21st, 2016 60 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. static public function calculatePath(nodes : Array<INode>, start: INode, end :INode): Array<INode>
  2.     {
  3.         var ret : Array<INode> = new Array<INode>();
  4.         if (start == end) return ret;
  5.        
  6.         // reset all values
  7.         for (i in 0...nodes.length)
  8.         {
  9.             var n : INode = nodes[i];
  10.             n.Clear();
  11.         }
  12.        
  13.         var toCheck : Array<INode> = new Array<INode>();
  14.         toCheck.push(end);
  15.         end.NodeValue = 0;
  16.        
  17.        
  18.         var toCheckNext : Array<INode> = new Array<INode>();
  19.         var estimateMap : Map<INode, Float> = new Map<INode, Float>();
  20.         var hasfound : Bool = false;
  21.         while (!hasfound)
  22.         {
  23.             if (toCheck.length <= 0) break;
  24.             for (i in 0... toCheck.length)
  25.             {
  26.                 var n : INode = toCheck[i];
  27.                 n.Visit();
  28.                
  29.                 if (n == start)
  30.                 {
  31.                     hasfound = true;
  32.                     break;
  33.                 }
  34.                
  35.                 for (k in n.neighbours.keys())
  36.                 {
  37.                     if (!k.Visited)
  38.                     {
  39.                         if (k.NodeValue == -1 || k.NodeValue > n.NodeValue + n.neighbours.get(k))
  40.                         {
  41.                             k.NodeValue = n.NodeValue + n.neighbours.get(k);
  42.                         }
  43.                         //toCheckNext.push(k);
  44.                         if (!k.isInEstimateMap)
  45.                         {
  46.                             var v : Float = k.estimate(start);
  47.                             k.isInEstimateMap = true;
  48.                             estimateMap.set(k, v);
  49.                         }
  50.                     }
  51.                 }
  52.                 // get closest estimate from estimate map
  53.                 var min : Float = 5000000;
  54.                 var newTile : INode = null;
  55.                 for (e in estimateMap.keys())
  56.                 {
  57.                     if (estimateMap.get(e) < min)
  58.                     {
  59.                         newTile = e;
  60.                         min = estimateMap.get(e);
  61.                     }
  62.                 }
  63.                 if (newTile != null)
  64.                 {
  65.                     estimateMap.remove(newTile);
  66.                     toCheckNext.push(newTile);
  67.                 }
  68.                
  69.             }
  70.             while (toCheck.length != 0) toCheck.pop();
  71.             while (toCheckNext.length != 0)
  72.             {
  73.                 var n : INode = toCheckNext.pop();
  74.                 if (!n.Visited) toCheck.push(n);
  75.             }
  76.            
  77.         }
  78.        
  79.         // map has been created, now walk it downwards
  80.        
  81.         var current : INode = start;
  82.         ret.push(current);
  83.         var next : INode = null;
  84.         var atTheEnd : Bool = false;
  85.         while (!atTheEnd)
  86.         {
  87.             if (current == end)
  88.             {
  89.                 atTheEnd = true;
  90.                 break;
  91.             }
  92.    
  93.             // find biggest slope
  94.             var Min : Float = current.NodeValue;
  95.             var minTile : INode = null;
  96.             var M : Map<INode, Float> = current.neighbours;
  97.             for (k in M.keys())
  98.             {
  99.                 trace(123);
  100.                 if (k.NodeValue < Min && k.NodeValue != -1)
  101.                 {      
  102.                     Min = k.NodeValue;
  103.                     minTile = k;
  104.                     if (k.NodeID == end.NodeID)
  105.                     {
  106.                         atTheEnd = true;
  107.                         break;
  108.                     }
  109.                 }
  110.             }
  111.             trace(minTile);
  112.             ret.push(minTile);
  113.             current = minTile;
  114.         }
  115.        
  116.        
  117.        
  118.         return ret;
  119.            
  120.     }
RAW Paste Data
Top