/* A*(えースター)アルゴリズムの実装 ver2
 * 二次元長方形の迷路から脱出する
 * 上下左右にしか移動できないとする
 */
// ゴールまでの推定移動コストのみでコストを算出
// 探索候補配列中のコスト最小の座標を、次に探索する座標とする
// 最短ルートは、「この座標のコストを求めたときの現在地」をゴール地点からたどって求める

/* マップその1(ゴールは1通り)
  this.mapCellsW = 40; // x軸方向の幅(セル数)
  this.mapCellsH = 10; // y軸方向の高さ(セル数)
  this.map = '' +
    '****************************************' +
    '*                                      *' +
    '*    ******************************    *' +
    '*    *         *    *G*    *    *   *  *' +
    '*    *         *                *   *  *' +
    '*    *    *    ***************      *  *' +
    '*    *    *           *      ********  *' +
    '*         *    *      ***    *      *  *' +
    '*S        *    *                  * *  *' +
    '****************************************';
*/
/* マップその2(ゴールは2通り)
  this.mapCellsW = 40; // x軸方向の幅(セル数)
  this.mapCellsH = 10; // y軸方向の高さ(セル数)
  this.map = '' +
    '****************************************' +
    '*                                      *' +
    '*    *********** ******************    *' +
    '*    *         *    *G*    *    *   *  *' +
    '*    *         *                *   *  *' +
    '*    *    *    ***************      *  *' +
    '*    *    *           *      ****** *  *' +
    '*         *    *      ***    *      *  *' +
    '*S        *    *                  * *  *' +
    '****************************************';
*/

var astarTest = {}; // namespace
// 定数
astarTest.MAXLOOPCOUNT = 500;  // ループ回数上限
astarTest.SHOWRESULT = true;  // 探索結果を表示するならtrue
astarTest.SHOWCOUNT = 50;  // 何回の探索ごとに結果を表示するか
astarTest.SHOWDIVID = 'outdiv'; // 探索結果表示divのid
// グローバル変数
/* 移動コストを格納した配列
 * 1つめのindexは迷路上のx座標(一番左が0)
 * 2つめのindexは迷路上のy座標(一番上が0)
 * 壁の値は Infinity
 */
astarTest.mazeCostToGArr = [];  // ゴール地点までの推定移動コスト
astarTest.backPosArr = [];  // この座標のコストを求めたときの現在地座標{x,y}

/* コスト格納クラス
 * {int} x 迷路上のx座標(一番左が0)
 * {int} y 迷路上のy座標(一番上が0)
 * {int} cost ゴール地点までの推定移動コスト
 */
astarTest.PosCost = function(x, y, cost) {
    // 座標は左上が(0,0)
    this.x = x;  // 現在のx座標
  	this.y = y;  // 現在のy座標
  	this.cost = cost;  // ゴール地点までの推定移動コスト。壁なら Infinity
};

// 探索候補配列操作クラス
astarTest.ForSearch = function() {
  // 探索候補配列
  this.fArr = [];
  
  /* 配列に値を格納
   * {PosCost} posCost コスト格納クラス
   * return なし
   */
  this.pushVal = function(posCost) {
    // posCostがPosCostクラスのインスタンスかのチェックは略
    this.fArr[this.fArr.length] = posCost;
  };
  /* 配列をcostの昇順にソート
   * return なし
   */
  this.sortArr = function() {
    this.fArr.sort(this.sortfunc);
  };
  /* this.sortArr()の比較関数
   * {PosCost} v1 比較対象
   * {PosCost} v2 比較対象
   * return {int} v1 > v2 なら正数 v1 < v2 なら負数 v1 == v2 なら 0
   */
  this.sortfunc = function(v1, v2) {
    return v1.cost - v2.cost;
  };
  /* 配列から値を削除
   * {int} idx 削除対象のidx(0から始まる)
   * return なし
   */
  this.delval = function(idx) {
    if ( idx < this.fArr.length && idx >= 0) {
      this.fArr.splice(idx,1);
    }
  };
};

// 迷路クラス
astarTest.Maze = function() {
  this.mapCellsW = 40; // x軸方向の幅(セル数)
  this.mapCellsH = 10; // y軸方向の高さ(セル数)
  var startC = 'S';  // マップ上のスタート地点を示す文字
  var goalC = 'G'; // マップ上のゴール地点を示す文字
  this.wallC = '*'; // マップ上の壁を示す文字
  // マップ文字列。*で壁を表す
  // stringであることを明示するため空文字列を足す
  this.map = '' +
    '****************************************' +
    '*                                      *' +
    '*    *********** ******************    *' +
    '*    *         *    *G*    *    *   *  *' +
    '*    *         *                *   *  *' +
    '*    *    *    ***************      *  *' +
    '*    *    *           *      ****** *  *' +
    '*         *    *      ***    *      *  *' +
    '*S        *    *                  * *  *' +
    '****************************************';
  
  // スタート地点が文字列の何番目か
  this.startP = this.map.indexOf(startC);
  // ゴール地点が文字列の何番目か
  this.goalP = this.map.indexOf(goalC);
  
  /* 文字列上の位置から迷路上の座標を求める
   * {int} index 文字列上の位置(0から始まる)
   * return {object} 迷路上の座標{x,y} (左上が{0,0})
   */
  this.getMatrixPosition = function(index) {
		return { x: (index % this.mapCellsW),
		         y: (Math.floor(index / this.mapCellsW)) };
	};
  /* 迷路上の座標からマップ文字列上の位置を求める
   * {int} x 迷路上のx座標(一番左が0)
   * {int} y 迷路上のy座標(一番上が0)
   * return {int} 文字列上の位置(0から始まる),エリア外だったら-1
   */
  this.getIndex = function(x, y) {
    if (x >= this.mapCellsW || x < 0) { return -1; }
    if (y >= this.mapCellsH || y < 0) { return -1; }
    return x + y * this.mapCellsW;
  };

  // スタート地点の迷路上の座標
  this.startM = this.getMatrixPosition(this.startP);
  // ゴール地点の迷路上の座標
  this.goalM = this.getMatrixPosition(this.goalP);


  /* 座標からゴールまでのコストを求める
   * {int} x 迷路上のx座標(一番左が0)
   * {int} y 迷路上のy座標(一番上が0)
   * return {int} 座標のコスト
   */
  this.calcCostToG = function(x, y) {
    var dx = Math.abs(x - this.goalM.x);  // 横方向のゴールまでの距離
    var dy = Math.abs(y - this.goalM.y);  // 縦方向のゴールまでの距離
    // 斜めには移動できないので、単純に足した値をコストとする
    return dx + dy;
  };
  
  /* 座標が壁かどうかチェック
   * {int} x 迷路上のx座標(一番左が0)
   * {int} y 迷路上のy座標(一番上が0)
   * return {boolean} 壁またはエリア外だったらtrue
   */
  this.isWall = function(x, y) {
    var strIndex = this.getIndex(x, y); // マップ文字列上の位置
    if (strIndex < 0) { return true; }
    if (this.map[strIndex] == this.wallC) { return true; }
    return false;
  };
};

/* 現在地の座標の周りの移動コストを求め、探索候補配列に格納
 * {int} x 現在地の迷路上のx座標(一番左が0)
 * {int} y 現在地の迷路上のy座標(一番上が0)
 * {Maze} Maze Mazeクラス
 * {ForSearch} ForSearch ForSearchクラス
 * return なし
 */
astarTest.search = function(x, y, Maze,ForSearch) {
  var tx, ty; // 座標のワークエリア
  var tempcost, tempPosCost; // ワークエリア
  for (var i = 0; i < 4; i++) {
    tx = x + astarTest.relMatrix[i][0];
    ty = y + astarTest.relMatrix[i][1];
    
    // コスト格納配列に無い場合はコストを求める
    if (!astarTest.mazeCostToGArr[tx][ty]) {
      if (Maze.isWall(tx, ty)) {
        // 該当座標が壁の場合
        astarTest.mazeCostToGArr[tx][ty] = Infinity;
      } else {
        // ゴール地点までの移動コストを求めて探索候補配列に格納
        tempcost = Maze.calcCostToG(tx, ty);
        astarTest.mazeCostToGArr[tx][ty] = tempcost;
        astarTest.backPosArr[tx][ty] = { x: x, y: y };
        tempPosCost = new astarTest.PosCost(tx, ty, tempcost);
        ForSearch.pushVal(tempPosCost);
      }
    }
  }
};
// 上下左右を調べるための相対座標
astarTest.relMatrix = [ [1,0], [0,-1], [-1,0], [0,1] ];

/* 探索結果出力
 * {int} count 現在のループカウンタ値
 * {int} x 現在地の迷路上のx座標(一番左が0)
 * {int} y 現在地の迷路上のy座標(一番上が0)
 * {object} Maze Mazeクラス
 * return なし
 */
astarTest.outSearch = function(count, x, y, Maze) {
  var outstr = '<br>count = ' + count + '<br>';  // 出力文字列
  var i1, i2, work, outc;
  for (i1 = 0; i1 < Maze.mapCellsH; i1++){
    for (i2 = 0; i2 < Maze.mapCellsW; i2++){
      work = astarTest.mazeCostToGArr[i2][i1];
      outc = "";
      if (work == undefined ) {
        // 未探索地点は空白で表示
        outc = '&nbsp;&nbsp;';
      } else if (work == Infinity) {
        // 壁は'**'で表示
        outc = Maze.wallC + Maze.wallC;
      } else {
        // コストを表示。100以上は99と表示
        if (work < 10) {
          outc = '0' + work;
        } else if (work < 100) {
          outc = work;
        } else {
          outc = '99';
        }
      }
      if (i1 == y && i2 == x) {
        // 現在地なら赤太字で表示
        outstr += '<b><font color="red">' + outc + '</font></b>';
      } else {
        outstr += outc;
      }
    }
    outstr += '<br>';
  }
  var outDiv = document.getElementById(astarTest.SHOWDIVID);
  outDiv.innerHTML += outstr;
};

/* onload時に実行される処理 */
astarTest.start = function() {
  var Maze = new astarTest.Maze();
  var ForSearch = new astarTest.ForSearch();
  // 移動コスト格納配列、移動前座標配列初期化
  for (var i = 0; i < Maze.mapCellsW; i++) {
    astarTest.mazeCostToGArr[i] = [];
    astarTest.backPosArr[i] = [];
  }

  // スタート地点の座標を取得しコストを格納
  var startM = Maze.getMatrixPosition(Maze.startP);
  var startCost = Maze.calcCostToG(startM.x, startM.y);
  astarTest.mazeCostToGArr[startM.x][startM.y] = startCost;
  var startPosCost = new astarTest.PosCost(startM.x, startM.y, startCost);
  ForSearch.pushVal(startPosCost);

  var thisPosCost = null; // 現在地のコスト格納クラス
  var loopCnt = 0;  // 無限ループ防止用ループカウンタ
  var loopflg = true; // falseならループを抜ける
  // 経路探索処理
  while (loopflg) {
    // ループ上限に達したら強制的にループを抜ける
    if (loopCnt > astarTest.MAXLOOPCOUNT) { break; }
    loopCnt++;

    // 調査対象の座標取得
    thisPosCost = ForSearch.fArr[0];
    if (!ForSearch.fArr[0]) {
      window.alert('ゴールに到達できません');
      return false;
    }
    // ゴール地点までの推定移動コストが0ならループを抜ける
    if (thisPosCost.cost == 0) {
      //window.alert('loopCnt=' + loopCnt + ' でゴール発見');
      break;
    }

    // 現在地の座標の周りのコストを求める
    !astarTest.search(thisPosCost.x, thisPosCost.y, Maze, ForSearch);
    ForSearch.delval(0);  // 現在地を探索候補配列から削除
    ForSearch.sortArr();  // 探索候補配列ソート

    // SHOWCOUNT回ごとに探索結果出力
    if (loopCnt % astarTest.SHOWCOUNT == 0) {
      astarTest.outSearch(loopCnt, thisPosCost.x, thisPosCost.y, Maze);
    }
  }

  // 探索後処理
  if (loopCnt > astarTest.MAXLOOPCOUNT) {
    window.alert('ループカウンタオーバーフロー');
  } else {
    var routeMap = [];  // 最短ルートを示したマップ配列
    // string[] は標準機能ではないため、Maze.mapを配列に格納
    for (var i = 0; i < Maze.map.length; i++) {
      routeMap[i] = Maze.map.charAt(i);
    }
    // 最短ルートをrouteMapに格納
    var lastCnt = loopCnt;  // ゴール発見までのループ回数
    loopCnt = 0;
    var tx, ty; // 現在地の座標
    var nx, ny; // 次の座標
    tx = Maze.goalM.x;
    ty = Maze.goalM.y;
    while (loopflg) {
      // ループ上限に達したら強制的にループを抜ける
      if (loopCnt > astarTest.MAXLOOPCOUNT) { break; }
      loopCnt++;

      nx = astarTest.backPosArr[tx][ty].x;
      ny = astarTest.backPosArr[tx][ty].y;
      // 次の座標がスタート地点ならループを抜ける
      if (nx == Maze.startM.x && ny == Maze.startM.y) {
        break;
      } else {
        // 次の座標をマップ上に'X'で格納
        routeMap[Maze.getIndex(nx, ny)] = 'X';
        tx = nx;
        ty = ny;
      }
    }
    // 最短ルート出力
    var outstr = '<br>count = ' + lastCnt + '<br>';  // 出力文字列
    var i1, i2, work, outc, thisIdx, thisCostToG;
    for (i1 = 0; i1 < Maze.mapCellsH; i1++){
      for (i2 = 0; i2 < Maze.mapCellsW; i2++){
        thisIdx = i1 * Maze.mapCellsW + i2; // 現在座標のrouteMap上のindex
        work = astarTest.mazeCostToGArr[i2][i1];
        outc = "";
        if (work == undefined ) {
          // 未探索地点は、壁でなければ空白で表示
          if (routeMap[thisIdx] == Maze.wallC) {
            outc = Maze.wallC + Maze.wallC;
          } else {
            outc = '&nbsp;&nbsp;';
          }
        } else if (work == Infinity) {
          // 壁は'**'で表示
          outc = Maze.wallC + Maze.wallC;
        } else {
          // コストを表示。100以上は99と表示
          if (work < 10) {
            outc = '0' + work;
          } else if (work < 100) {
            outc = work;
          } else {
            outc = '99';
          }
        }
        // routeMapの値に応じて表示内容を変える
        switch (routeMap[thisIdx]) {
          case 'G': {
            outstr += '<b><font color="red">' + 'GG' + '</font></b>';
            break;
          }
          case 'S': {
            outstr += '<b><font color="red">' + 'SS' + '</font></b>';
            break;
          }
          case 'X': {
            outstr += '<b><font color="blue">' + outc + '</font></b>';
            break;
          }
          default: {
            outstr += outc;
            break;
          }
        }
      }
      outstr += '<br>';
    }
    var outDiv = document.getElementById(astarTest.SHOWDIVID);
    outDiv.innerHTML += outstr;
  }
};