topical media & game development

talk show tell print

lib-flex-animation-code-04-AStar.ax

lib-flex-animation-code-04-AStar.ax (swf ) [ flash ] flex


  package
  {
          public class @ax-lib-flex-animation-code-04-AStar
          {
                  private var _open:Array;
                  private var _closed:Array;
                  private var _grid:Grid;
                  private var _endNode:Node;
                  private var _startNode:Node;
                  private var _path:Array;
  //                private var _heuristic:Function = manhattan;
  //                private var _heuristic:Function = euclidian;
                  private var _heuristic:Function = diagonal;
                  private var _straightCost:Number = 1.0;
                  private var _diagCost:Number = Math.SQRT2;
                  
                  
                  public function @ax-lib-flex-animation-code-04-AStar()
                  {
                  }
                  
                  public function findPath(grid:Grid):Boolean
                  {
                          _grid = grid;
                          _open = new Array();
                          _closed = new Array();
                          
                          _startNode = _grid.startNode;
                          _endNode = _grid.endNode;
                          
                          _startNode.g = 0;
                          _startNode.h = _heuristic(_startNode);
                          _startNode.f = _startNode.g + _startNode.h;
                          
                          return search();
                  }
                  
                  public function search():Boolean
                  {
                          var node:Node = _startNode;
                          while(node != _endNode)
                          {
                                  var startX:int = Math.max(0, node.x - 1);
                                  var endX:int = Math.min(_grid.numCols - 1, node.x + 1);
                                  var startY:int = Math.max(0, node.y - 1);
                                  var endY:int = Math.min(_grid.numRows - 1, node.y + 1);
                                  
                                  for(var i:int = startX; i <= endX; i++)
                                  {
                                          for(var j:int = startY; j <= endY; j++)
                                          {
                                                  var test:Node = _grid.getNode(i, j);
                                                  if(test == node || 
                                                     !test.walkable ||
                                                     !_grid.getNode(node.x, test.y).walkable ||
                                                     !_grid.getNode(test.x, node.y).walkable)
                                                  {
                                                          continue;
                                                  }
                                                  
                                                  var cost:Number = _straightCost;
                                                  if(!((node.x == test.x) || (node.y == test.y)))
                                                  {
                                                          cost = _diagCost;
                                                  }
                                                  var g:Number = node.g + cost * test.costMultiplier;
                                                  var h:Number = _heuristic(test);
                                                  var f:Number = g + h;
                                                  if(isOpen(test) || isClosed(test))
                                                  {
                                                          if(test.f > f)
                                                          {
                                                                  test.f = f;
                                                                  test.g = g;
                                                                  test.h = h;
                                                                  test.parent = node;
                                                          }
                                                  }
                                                  else
                                                  {
                                                          test.f = f;
                                                          test.g = g;
                                                          test.h = h;
                                                          test.parent = node;
                                                          _open.push(test);
                                                  }
                                          }
                                  }
                                  for(var o:int = 0; o < _open.length; o++)
                                  {
                                  }
                                  _closed.push(node);
                                  if(_open.length == 0)
                                  {
                                          trace("no path found");
                                          return false
                                  }
                                  _open.sortOn("f", Array.NUMERIC);
                                  node = _open.shift() as Node;
                          }
                          buildPath();
                          return true;
                  }
                  
                  private function buildPath():void
                  {
                          _path = new Array();
                          var node:Node = _endNode;
                          _path.push(node);
                          while(node != _startNode)
                          {
                                  node = node.parent;
                                  _path.unshift(node);
                          }
                  }
                  
                  public function get path():Array
                  {
                          return _path;
                  }
                  
                  private function isOpen(node:Node):Boolean
                  {
                          for(var i:int = 0; i < _open.length; i++)
                          {
                                  if(_open[i] == node)
                                  {
                                          return true;
                                  }
                          }
                          return false;
                  }
                  
                  private function isClosed(node:Node):Boolean
                  {
                          for(var i:int = 0; i < _closed.length; i++)
                          {
                                  if(_closed[i] == node)
                                  {
                                          return true;
                                  }
                          }
                          return false;
                  }
                  
                  private function manhattan(node:Node):Number
                  {
                          return Math.abs(node.x - _endNode.x) * _straightCost + Math.abs(node.y + _endNode.y) * _straightCost;
                  }
                  
                  private function euclidian(node:Node):Number
                  {
                          var dx:Number = node.x - _endNode.x;
                          var dy:Number = node.y - _endNode.y;
                          return Math.sqrt(dx * dx + dy * dy) * _straightCost;
                  }
                  
                  private function diagonal(node:Node):Number
                  {
                          var dx:Number = Math.abs(node.x - _endNode.x);
                          var dy:Number = Math.abs(node.y - _endNode.y);
                          var diag:Number = Math.min(dx, dy);
                          var straight:Number = dx + dy;
                          return _diagCost * diag + _straightCost * (straight - 2 * diag);
                  }
                  
                  public function get visited():Array
                  {
                          return _closed.concat(_open);
                  }
          }
  }
  


(C) Æliens 18/6/2009

You may not copy or print any of this material without explicit permission of the author or the publisher. In case of other copyright issues, contact the author.