home *** CD-ROM | disk | FTP | other *** search
/ 404 Jogos / CLJG.iso / Diversos / pi_climber.swf / scripts / Dijkstra.as < prev    next >
Encoding:
Text File  |  2008-09-24  |  5.9 KB  |  205 lines
  1. package
  2. {
  3.    public class Dijkstra
  4.    {
  5.        
  6.       
  7.       private var startNode:int = 0;
  8.       
  9.       private var numberOfNodes:int;
  10.       
  11.       private var nodesLeft:Array;
  12.       
  13.       private var previousNode:Array;
  14.       
  15.       private var h:int;
  16.       
  17.       private var infiniteDistance:int = 100000;
  18.       
  19.       private var bestPath:int;
  20.       
  21.       private var visited:Array;
  22.       
  23.       private var distance:Array;
  24.       
  25.       private var endNode:int;
  26.       
  27.       private var w:int;
  28.       
  29.       private var aDecimal:Array;
  30.       
  31.       public function Dijkstra(param1:Array, param2:int, param3:int)
  32.       {
  33.          startNode = 0;
  34.          infiniteDistance = 100000;
  35.          super();
  36.          this.w = param2;
  37.          this.h = param3;
  38.          this.aDecimal = param1;
  39.          numberOfNodes = param2 * param3;
  40.          endNode = numberOfNodes - 1;
  41.          distance = new Array();
  42.          previousNode = new Array();
  43.          visited = new Array();
  44.          bestPath = 0;
  45.          nodesLeft = new Array();
  46.       }
  47.       
  48.       private function nodesNotVisited(param1:Array) : Array
  49.       {
  50.          var _loc2_:* = undefined;
  51.          var _loc3_:* = undefined;
  52.          _loc2_ = new Array();
  53.          _loc3_ = 0;
  54.          while(_loc3_ < numberOfNodes)
  55.          {
  56.             if(!param1[_loc3_])
  57.             {
  58.                _loc2_.push(_loc3_);
  59.             }
  60.             _loc3_++;
  61.          }
  62.          return _loc2_;
  63.       }
  64.       
  65.       private function findBestPath(param1:Array, param2:Array) : Number
  66.       {
  67.          var _loc3_:* = undefined;
  68.          var _loc4_:* = undefined;
  69.          var _loc5_:* = undefined;
  70.          _loc3_ = infiniteDistance;
  71.          _loc4_ = 0;
  72.          _loc5_ = 0;
  73.          while(_loc5_ < param2.length)
  74.          {
  75.             if(param1[param2[_loc5_]] < _loc3_)
  76.             {
  77.                _loc3_ = param1[param2[_loc5_]];
  78.                _loc4_ = param2[_loc5_];
  79.             }
  80.             _loc5_++;
  81.          }
  82.          return _loc4_;
  83.       }
  84.       
  85.       private function updateDistanceAndPrevious(param1:Number) : void
  86.       {
  87.          var _loc2_:* = undefined;
  88.          var _loc3_:int = 0;
  89.          var _loc4_:int = 0;
  90.          var _loc5_:int = 0;
  91.          var _loc6_:int = 0;
  92.          _loc2_ = 0;
  93.          while(_loc2_ < 4)
  94.          {
  95.             _loc4_ = infiniteDistance;
  96.             _loc5_ = param1 % w;
  97.             _loc6_ = param1 / w;
  98.             switch(_loc2_)
  99.             {
  100.                case 0:
  101.                   _loc3_ = param1 - w;
  102.                   if(_loc6_ > 0)
  103.                   {
  104.                      _loc4_ = Math.abs(aDecimal[param1 - w] - aDecimal[param1]);
  105.                   }
  106.                   break;
  107.                case 1:
  108.                   _loc3_ = param1 + 1;
  109.                   if(_loc5_ < w - 1)
  110.                   {
  111.                      _loc4_ = Math.abs(aDecimal[param1 + 1] - aDecimal[param1]);
  112.                   }
  113.                   break;
  114.                case 2:
  115.                   _loc3_ = param1 + w;
  116.                   if(_loc6_ < h - 1)
  117.                   {
  118.                      _loc4_ = Math.abs(aDecimal[param1 + w] - aDecimal[param1]);
  119.                   }
  120.                   break;
  121.                case 3:
  122.                   _loc3_ = param1 - 1;
  123.                   if(_loc5_ > 0)
  124.                   {
  125.                      _loc4_ = Math.abs(aDecimal[param1 - 1] - aDecimal[param1]);
  126.                   }
  127.                   break;
  128.             }
  129.             if(distance[param1] + _loc4_ < distance[_loc3_])
  130.             {
  131.                distance[_loc3_] = distance[param1] + _loc4_;
  132.                previousNode[_loc3_] = param1;
  133.             }
  134.             _loc2_++;
  135.          }
  136.       }
  137.       
  138.       private function getResults() : int
  139.       {
  140.          var _loc1_:* = undefined;
  141.          var _loc2_:* = undefined;
  142.          var _loc3_:* = undefined;
  143.          var _loc4_:* = undefined;
  144.          _loc1_ = new Array();
  145.          _loc2_ = endNode;
  146.          _loc1_[_loc2_] = new Array();
  147.          _loc3_ = null;
  148.          _loc4_ = _loc2_;
  149.          _loc1_[_loc2_].push(_loc2_);
  150.          while(_loc3_ != this.startNode)
  151.          {
  152.             _loc1_[_loc2_].push(this.previousNode[_loc4_]);
  153.             _loc3_ = this.previousNode[_loc4_];
  154.             _loc4_ = this.previousNode[_loc4_];
  155.          }
  156.          _loc1_[_loc2_].reverse();
  157.          trace("---------------------------------------");
  158.          trace("The shortest distance from the startNode: " + startNode + ", to node " + _loc2_ + ": is -> " + distance[_loc2_]);
  159.          trace("The shortest path from the startNode: " + startNode + ", to node " + _loc2_ + ": is -> " + _loc1_[_loc2_]);
  160.          trace("---------------------------------------");
  161.          return distance[_loc2_];
  162.       }
  163.       
  164.       public function findShortestPath() : int
  165.       {
  166.          var _loc1_:* = undefined;
  167.          _loc1_ = 0;
  168.          while(_loc1_ < numberOfNodes)
  169.          {
  170.             visited[_loc1_] = 0;
  171.             distance[_loc1_] = infiniteDistance;
  172.             previousNode[_loc1_] = 0;
  173.             _loc1_++;
  174.          }
  175.          visited[0] = 1;
  176.          distance[0] = 0;
  177.          distance[1] = aDecimal[1] - aDecimal[0];
  178.          distance[w] = aDecimal[w] - aDecimal[0];
  179.          while(somethingLeft(visited))
  180.          {
  181.             nodesLeft = nodesNotVisited(visited);
  182.             bestPath = findBestPath(distance,nodesLeft);
  183.             updateDistanceAndPrevious(bestPath);
  184.             visited[bestPath] = 1;
  185.          }
  186.          return getResults();
  187.       }
  188.       
  189.       private function somethingLeft(param1:Array) : Boolean
  190.       {
  191.          var _loc2_:* = undefined;
  192.          _loc2_ = numberOfNodes - 1;
  193.          while(_loc2_ > 0)
  194.          {
  195.             if(!param1[_loc2_])
  196.             {
  197.                return true;
  198.             }
  199.             _loc2_--;
  200.          }
  201.          return false;
  202.       }
  203.    }
  204. }
  205.