/* A*(えースター)アルゴリズムの実装 ver1
* 二次元長方形の迷路から脱出する
* 上下左右にしか移動できないとする
*/
// スタートからの移動コストと、ゴールまでの推定移動コストを足してコストを算出
// 現在地の座標から次に探索する座標を求める(次の座標は必ず現在地に隣接する座標)
// 移動コストよりも現在地になった回数が少ない方を優先して、次に探索する座標を求める
// 最短ルートは、「スタートからの移動コスト」が最小の座標をゴール地点からたどって求める
/* マップその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.mazeCostFrSArr = []; // スタート地点からの移動コスト
astarTest.mazeCostToGArr = []; // ゴール地点までの推定移動コスト
astarTest.mazeSerCntArr = []; // 該当座標が現在地になった回数
// 迷路クラス
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.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;
};
};
/* 現在地の座標から次に探索する座標を求める
* {object} pos 現在地の迷路上の座標{x,y} (左上が{0,0})
* {object} Maze Mazeクラス
* {boolean} after 探索後処理ならtrue
* return {object} 次の探索座標{x,y}
*/
astarTest.search = function(pos,Maze,after) {
var nextM = null; // 次の座標
var leastCost = Infinity; // 上下左右チェック中の最小コスト
var tempCost, tempSerCnt, nextSerCnt; // ワークエリア
var tx, ty; // 座標のワークエリア
var tpXArr = []; // x座標のワークエリア配列
var tpYArr = []; // y座標のワークエリア配列
// 現在地のスタート地点からの移動コスト
var thisCostFrS = astarTest.mazeCostFrSArr[pos.x][pos.y];
// 現在地の右の座標
tpXArr[0] = pos.x + 1;
tpYArr[0] = pos.y;
// 現在地の下の座標
tpXArr[1] = pos.x;
tpYArr[1] = pos.y + 1;
// 現在地の左の座標
tpXArr[2] = pos.x - 1;
tpYArr[2] = pos.y;
// 現在地の上の座標
tpXArr[3] = pos.x;
tpYArr[3] = pos.y - 1;
// 上下左右のうち最小コストを次の座標とする
for (var i = 0; i < 4; i++) {
tempCost = Infinity;
nextSerCnt = Infinity;
tx = tpXArr[i];
ty = tpYArr[i];
// コスト格納配列に無い場合はコストを求める
if (!astarTest.mazeCostToGArr[tx][ty]) {
if (Maze.isWall(tx, ty)) {
// 該当座標が壁の場合
astarTest.mazeCostToGArr[tx][ty] = Infinity;
astarTest.mazeCostFrSArr[tx][ty] = Infinity;
astarTest.mazeSerCntArr[tx][ty] = Infinity;
} else {
astarTest.mazeCostToGArr[tx][ty] = Maze.calcCostToG(tx, ty);
astarTest.mazeCostFrSArr[tx][ty] = thisCostFrS + 1;
astarTest.mazeSerCntArr[tx][ty] = 0;
}
} else if (astarTest.mazeCostToGArr[tx][ty] != Infinity) {
// スタート地点からの移動コストチェック
// 既存の値 > 現在地の値+1 の場合、既存の値を更新
if (astarTest.mazeCostFrSArr[tx][ty] > thisCostFrS + 1) {
astarTest.mazeCostFrSArr[tx][ty] = thisCostFrS + 1;
}
}
tempCost = astarTest.mazeCostToGArr[tx][ty];
tempSerCnt = astarTest.mazeSerCntArr[tx][ty];
// 次の座標候補か判定
if (tempCost != Infinity) {
if (nextM) {
nextSerCnt = astarTest.mazeSerCntArr[nextM.x][nextM.y];
}
// 現在地になった回数が少ない方を優先
if (tempSerCnt < nextSerCnt) {
leastCost = tempCost;
nextM = { x: tx, y: ty };
} else if (tempSerCnt == nextSerCnt) {
// ゴールに近い方を優先
if (tempCost < leastCost) {
leastCost = tempCost;
nextM = { x: tx, y: ty };
}
}
}
}
return nextM;
};
/* 探索結果出力
* {int} count 現在のループカウンタ値
* {object} pos 現在地の迷路上の座標{x,y} (左上が{0,0})
* {object} Maze Mazeクラス
* return なし
*/
astarTest.outSearch = function(count,pos,Maze) {
var outstr = '
count = ' + count + '
'; // 出力文字列
var nowx = pos.x; // 現在のx座標
var nowy = pos.y; // 現在のy座標
var i1, i2, work, outc, thisCostToG, thisSerCnt;
for (i1 = 0; i1 < Maze.mapCellsH; i1++){
for (i2 = 0; i2 < Maze.mapCellsW; i2++){
thisCostToG = astarTest.mazeCostToGArr[i2][i1];
work = (thisCostToG == Infinity || thisCostToG == undefined) ?
thisCostToG : astarTest.mazeCostFrSArr[i2][i1] + thisCostToG;
outc = "";
if (work == undefined ) {
// 未探索地点は空白で表示
outc = ' ';
} 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';
}
}
thisSerCnt = astarTest.mazeSerCntArr[i2][i1];
if (i1 == nowy && i2 == nowx) {
// 現在地なら赤太字で表示
outstr += '' + outc + '';
} else {
outstr += outc;
}
}
outstr += '
';
}
var outDiv = document.getElementById(astarTest.SHOWDIVID);
outDiv.innerHTML += outstr;
};
/* onload時に実行される処理 */
astarTest.start = function() {
var Maze = new astarTest.Maze();
// 移動コスト格納配列初期化
for (var i = 0; i < Maze.mapCellsW; i++) {
astarTest.mazeCostFrSArr[i] = [];
astarTest.mazeCostToGArr[i] = [];
astarTest.mazeSerCntArr[i] = [];
}
// スタート地点の座標を取得しコストを格納
var startM = Maze.getMatrixPosition(Maze.startP);
astarTest.mazeCostFrSArr[startM.x][startM.y] = 0;
astarTest.mazeCostToGArr[startM.x][startM.y] =
Maze.calcCostToG(startM.x, startM.y);
astarTest.mazeSerCntArr[startM.x][startM.y] = 0;
var thisM = startM; // 現在地の座標
var nextM = null; // 次の座標
var loopCnt = 0; // 無限ループ防止用ループカウンタ
var loopflg = true; // falseならループを抜ける
var thisCostFrS; // 現在地のスタート地点からの移動コスト
var nextCostFrS; // 次に探索する座標のスタート地点からの移動コスト
// 経路探索処理
while (loopflg) {
// ループ上限に達したら強制的にループを抜ける
if (loopCnt > astarTest.MAXLOOPCOUNT) { break; }
loopCnt++;
// ゴール地点までの推定移動コストが0ならループを抜ける
if (astarTest.mazeCostToGArr[thisM.x][thisM.y] == 0) {
//window.alert('loopCnt=' + loopCnt + ' でゴール発見' + "\n" +
// 'x=' + thisM.x + ' y=' + thisM.y);
break;
}
// 該当座標が現在地になった回数更新
astarTest.mazeSerCntArr[thisM.x][thisM.y]++;
// 次に探索する座標を求める
nextM = astarTest.search(thisM,Maze,false);
// nextMがnullなら例外処理
if (!nextM) {
window.alert('nextMがnullです(経路探索処理)');
return false;
}
thisM = nextM;
// SHOWCOUNT回ごとに探索結果出力
if (loopCnt % astarTest.SHOWCOUNT == 0) {
astarTest.outSearch(loopCnt,thisM,Maze);
}
}
// 探索後処理
if (loopCnt > astarTest.MAXLOOPCOUNT) {
window.alert('ループカウンタオーバーフロー');
} else {
//astarTest.outSearch(loopCnt,thisM,Maze);
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;
thisM = Maze.goalM;
var tx, ty; // 座標のワークエリア
var tpXArr = []; // x座標のワークエリア配列
var tpYArr = []; // y座標のワークエリア配列
var leastCost, thisCostFrS;
while (loopflg) {
// ループ上限に達したら強制的にループを抜ける
if (loopCnt > astarTest.MAXLOOPCOUNT) { break; }
loopCnt++;
nextM = null;
// 現在地の右の座標
tpXArr[0] = thisM.x + 1;
tpYArr[0] = thisM.y;
// 現在地の下の座標
tpXArr[1] = thisM.x;
tpYArr[1] = thisM.y + 1;
// 現在地の左の座標
tpXArr[2] = thisM.x - 1;
tpYArr[2] = thisM.y;
// 現在地の上の座標
tpXArr[3] = thisM.x;
tpYArr[3] = thisM.y - 1;
// スタート地点からの移動コスト最小を次の座標とする
leastCost = Infinity;
for (var i = 0; i < 4; i++) {
tx = tpXArr[i];
ty = tpYArr[i];
thisCostFrS = astarTest.mazeCostFrSArr[tx][ty];
if (thisCostFrS && thisCostFrS < leastCost) {
leastCost = thisCostFrS;
nextM = { x: tx, y: ty };
}
}
// nextMがnullなら例外処理
if (!nextM) {
window.alert('nextMがnullです(最短ルート出力処理)');
return false;
}
// 次の座標がスタート地点ならループを抜ける
if (thisCostFrS == 0) {
break;
} else {
// 次の座標をマップ上に'X'で格納
routeMap[Maze.getIndex(nextM.x, nextM.y)] = 'X';
thisM = nextM;
}
}
// 最短ルート出力
var outstr = '
count = ' + lastCnt + '
'; // 出力文字列
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
thisCostToG = astarTest.mazeCostToGArr[i2][i1];
work = (thisCostToG == Infinity || thisCostToG == undefined) ?
thisCostToG : astarTest.mazeCostFrSArr[i2][i1] + thisCostToG;
outc = "";
if (work == undefined ) {
// 未探索地点は、壁でなければ空白で表示
if (routeMap[thisIdx] == Maze.wallC) {
outc = Maze.wallC + Maze.wallC;
} else {
outc = ' ';
}
} 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 += '' + 'GG' + '';
break;
}
case 'S': {
outstr += '' + 'SS' + '';
break;
}
case 'X': {
outstr += '' + outc + '';
break;
}
default: {
outstr += outc;
break;
}
}
}
outstr += '
';
}
var outDiv = document.getElementById(astarTest.SHOWDIVID);
outDiv.innerHTML += outstr;
}
};