package worlds.utils     
{     
     public class AStar     
     {
      public static const HEX_GRID:String = "hexGrid";
      public static const ISO_GRID:String = "isoGrid";

      /**
       * Смещение для поиска соседних гексагонов в четных рядах
       */
      private static var evenHexNeighbors:Array = new Array([1, -1], [1, 0], [1, 1], [0, 1], [-1, 0], [0, -1]);
      /**
       * Смещение для поиска соседних гексагонов в нечетных рядах
       */
      private static var oddHexNeighbors:Array = new Array([0, -1], [1, 0], [0, 1], [-1, 1], [-1, 0], [-1, -1]);
      /**
       *     
       * @param    startPoint точка с которой начинается поиск пути.
       * @param    finishPoint точка к которой нужно найти путь.
       * @param    map параметр должен содержать двумерный массив с объектами CellPoint, содержащих свойство walkCost хранящее стоимость перехода. Если стоимость равняется -1, точка считается непроходимой.
       * @param    gridType принимает AStar.HEX_GRID или IAStar.ISO_GRID. При передаче другого значения будет заменено на ISO_GRID
       */
      public static function SearchPath(startPoint:CellPosition, finishPoint:CellPosition, map:Array, gridType:String):Path     
      {
       var Heuristic:Function;
       var GetNeighbor:Function;
       switch (gridType)
       {
        case HEX_GRID:
         Heuristic = HexHeuristic;
         GetNeighbor = Iso
         break;
        case ISO_GRID:
         Heuristic = IsoHeuristic;
         break;
        default:
         Heuristic = IsoHeuristic;
         break;
       }
       var path:Path = new Path(startPoint, finishPoint);
       /**
        * @private Проверяет, входит ли точка начала и окончания пути в карту
        */
       if (startPoint.x < 0 || startPoint.x >= map.length || startPoint.y < 0 || startPoint.y >= map[0].length ||
       finishPoint.x < 0 || finishPoint.x >= map.length || finishPoint.y < 0 || finishPoint.y >= map[0].length)
       {
        path.state = Path.NOT_POINT;
        return path;
       }
       /**
        * @private проверяет, можнет ли персонаж перейти в точку окончания пути.
        */
       if (map[finishPoint.x][finishPoint.y].walkCost == -1)
       {
        path.state = Path.INCORRECT_FINISH;
        return path;
       }
           
       var openList:Array = new Array();
       var closeList:Array = new Array();
       var start:CellPosition = map[startPoint.x][startPoint.y];
       var finish:CellPosition = map[finishPoint.x][finishPoint.y];
       openList.push(start);
       start.g = 0;
       start.h = Heuristic(start, finish);
       start.f = start.g + start.h;
           
       var node:CellPosition = start;
       while(node != finish)
       {
        var neighbor:Array = HexNeighbors(node, map, closeList);
        for (var i:int = 0; i < neighbor.length; i++)
        {
         var test:CellPosition = neighbor[i];
         var g:Number = node.g + 1;
         var h:Number = Heuristic(test, finish);
         var f:Number = g + h;
         if(openList.indexOf(test) != -1 || closeList.indexOf(test) != -1)
         {
          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;
          openList.push(test);
         }
        }
        closeList.push(node);
        if(openList.length == 0)
        {
         path.state = Path.NOT_PATH;
         return path;
        }
        openList.sortOn("f", Array.NUMERIC);
        node = openList.shift() as CellPosition;
       }
       path.path = new Array();
       var _node:CellPosition = finish;
       path.path.push(node);
       path.cost = new Array();
       while(_node != start)
       {
        _node = _node.parent;
        path.path.unshift(_node);
       }
       path.state = Path.FOUND_PATH;
       return path;
      }
      private static function HexNeighbors(cellPosition:CellPosition, map:Array, closeList:Array):Array
      {
       var arr:Array = new Array();
       var offsetNeighbors:Array = cellPosition.y % 2 ?  oddHexNeighbors: evenHexNeighbors;
       var x:int = 0;
       var y:int = 0;
       for (var i:int = 0; i < offsetNeighbors.length; i++)
       {
        x = Math.max(0, cellPosition.x + offsetNeighbors[i][0]);
        if (x >= map.length) continue;
        y = Math.max(0, cellPosition.y + offsetNeighbors[i][1]);
        if (y >= map[0].length) continue;
        if (map[x][y].walkCost == -1) continue;
        if (closeList.indexOf(map[x][y]) != -1)
        {
         continue;
        }
        arr.push(map[x][y]);
        map[x][y].parent = map[cellPosition.x][cellPosition.y];
       }
       return arr;
      }
      private static function IsoNeighbors(cellPosition:CellPosition, map:Array, closeList:Array):Array
      {
       var arr:Array = new Array();
       //TODO
       return arr;
      }
      private static function HexHeuristic(point:CellPosition, endPoint:CellPosition):Number
      {
       //Эвклидова эвристика
       var dx:Number = point.x - endPoint.x;
       var dy:Number = point.y - endPoint.y;
       return Math.sqrt(dx * dx + dy * dy);
      }
      private static function IsoHeuristic(point:CellPosition, endPoint:CellPosition):Number
      {
       //диагональная эвристика
       var dx:Number = Math.abs(point.x - endPoint.x);
       var dy:Number = Math.abs(point.y - endPoint.y);
       var diag:Number = Math.min(dx, dy);
       var straight:Number = dx + dy;
       return diag + (straight - 2 * diag);
      }
     }
}