ダイクストラ法とA-StarアルゴリズムをJavaScriptで実装してみた。
ダイクストラ法は確かに動いているように思えるけど、A-Starの方はうまく動いていないように見えるというか、全然高速化されていない。こんなもんなのかな?知ってる人いたら教えてください。
Create Map:
10x10
20x20
30x30
40x40
50x50
A-STAR
( function () { var start; var tdList; var mapSize = 10; var map; var dijkstra = function (sx, sy, gx, gy, astar) { var startTime = new Date().getTime(); var masterList = new NodeList(); var openList = new NodeList(); var closeList = new NodeList(); var maxWidth = map[0].length; var maxHeight = map.length; message('' ); for ( var i = 0, len = map.length; i < len; i++) { for ( var j = 0, jlen = map[i].length; j < jlen; j++) { masterList.add(new Node(j, i)); } } var targetNode = masterList.get(sx, sy); targetNode.score = 0; closeList.add(targetNode); var whileCount = 0; while ( true ) { whileCount++; var checkNodePositions = [[targetNode.x, targetNode.y - 1], [targetNode.x, targetNode.y + 1], [targetNode.x - 1, targetNode.y], [targetNode.x + 1, targetNode.y]]; for ( var i = 0, len = checkNodePositions.length; i < len; i++) { var checkNodePosition = checkNodePositions[i]; if (checkNodePosition[0] < 0 || checkNodePosition[0] > maxWidth - 1 || checkNodePosition[1] < 0 || checkNodePosition[1] > maxHeight - 1) { continue ; } var checkNode = masterList.get(checkNodePosition[0], checkNodePosition[1]); if (checkNode.type == 0) continue ; if (closeList.get(checkNodePosition[0], checkNodePosition[1])) continue ; if (!openList.get(checkNodePosition[0], checkNodePosition[1])) { openList.add(checkNode); } var score; if (astar) { score = targetNode.score + 1 + Math.abs(checkNodePosition[0] - gx) + Math.abs(checkNodePosition[1] - gy); } else { score = targetNode.score + 1; } if (isNaN(checkNode.score) || checkNode.score > score) { checkNode.score = score; checkNode.parent = targetNode; } } if (openList.length() == 0) { message('No route!' ); return ; } targetNode = openList.getMin(); openList.remove(targetNode); closeList.add(targetNode); targetNode.score = targetNode.score; if (targetNode.x == gx && targetNode.y == gy) break ; } var endTime = new Date().getTime(); message(endTime - startTime + 'ms' + ' whileCount:' + whileCount); showRoute(targetNode); } var message = function (value) { document.getElementById('message' ).innerHTML = value; } var showRoute = function (targetNode) { var td = tdList.get(targetNode.x, targetNode.y); td.className = 'scotch route' ; td.style.backgroundColor = 'green' ; var parent = targetNode.parent; if (parent) showRoute(parent); } var createMapData = function (count) { map = []; start = [0, 0]; for ( var i = 0, len = mapSize * count; i < len; i++) { var row = []; for ( var j = 0, jlen = mapSize * count; j < jlen; j++) { var r = Math.floor(Math.random() * 100) % 5; row.push(r); } map.push(row); } } var createMap = function () { var graph = document.getElementById( 'graph' ); graph.innerHTML = '' ; var table = graph.appendChild(document.createElement( 'table' )); table.style.borderCollapse = 'collapse' ; var tbody = table.appendChild(document.createElement( 'tbody' )); tdList = new Table(); for ( var i = 0, len = map.length; i < len; i++) { var tr = tbody.appendChild(document.createElement( 'tr' )); var row = []; for ( var j = 0, jlen = map[i].length; j < jlen; j++) { var td = tr.appendChild(document.createElement( 'td' )); observe(td, 'click' , analyse); td.style.border = '1px solid white' ; td.style.width = '10px' ; td.style.height = '10px' ; if (map[i][j] == 0) { td.className = 'scotch wall' ; td.style.backgroundColor = 'red' ; } else td.className = 'scotch' ; tdList.set(j, i, td); } } } var analyse = function (event) { var target = event.target || event.srcElement; var trChildren = target.parentNode.children; var tbodyChildren = target.parentNode.parentNode.children; var x,y; for ( var i = 0, len = trChildren.length; i < len; i++) { if (trChildren[i] == target) { x = i; break ; } } var tr = target.parentNode; for ( var i = 0, len = tbodyChildren.length; i < len; i++) { if (tbodyChildren[i] == tr) { y = i; break ; } } if (start[0] == x && start[1] == y) { message('Start is equals to Goal' ); return ; } if (target.className.indexOf( 'wall' ) != -1) { message('Your clicked cell is wall' ); return ; } tdList.each(function (td) { var className = td.className; var classNameList = className.split(/ /); for ( var i = classNameList.length - 1; i >= 0; i--) { if (classNameList[i] == 'route' ) { classNameList.splice(i, 1); td.style.backgroundColor = '' ; } } td.className = classNameList.join(' ' ); }); var astar = document.getElementById( 'astar20090824' ).checked; dijkstra(start[0], start[1], x, y, astar); start = [x, y]; } var observe = function (target, type, listener) { if (target.addEventListener) target.addEventListener(type, listener, false ); else target.attachEvent( 'on' + type, function () { listener.call(target, window.event); }); } var Node = function (x, y) { this .x = x; this .y = y; this .type = map[y][x]; } Node.prototype.score = NaN; Node.prototype.parent = null ; var NodeList = function () { this .data = {}; } NodeList.prototype.add = function (value) { this .data[value.x + ',' + value.y] = value; } NodeList.prototype.get = function (x, y) { return this .data[x + ',' + y]; } NodeList.prototype.length = function () { var count = 0; for ( var key in this .data) { count++; } return count; } NodeList.prototype.remove = function (value) { delete this .data[value.x + ',' + value.y]; } NodeList.prototype.getMin = function () { var data = this .data; var min = null ; for ( var node in data) { if (!min) { min = data[node]; continue ; } if (min.score > node.score) min = data[node]; } return min; } var Table = function () { this .data = {}; } Table.prototype.set = function (x, y, value) { this .data[x + ',' + y] = value; } Table.prototype.get = function (x, y) { return this .data[x + ',' + y]; } Table.prototype.each = function (func) { var data = this .data; for ( var key in data) { func(data[key]); } } observe(document.getElementById('mapSelect20090824' ), 'change' , function (event) { var target = event.target || event.srcElement; var value = target.value; createMapData(value); createMap(); }); createMapData(1); createMap(); })(); (function() {
var start;
var tdList;
var mapSize = 10;
var map;
var dijkstra = function(sx, sy, gx, gy, astar) {
var startTime = new Date().getTime();
var masterList = new NodeList(); // Node全てを格納するリスト
var openList = new NodeList(); // スコアが確定していないノードを格納するリスト
var closeList = new NodeList(); // スコアが確定したノードを格納するリスト
var maxWidth = map[0].length; // 地図の幅
var maxHeight = map.length; // 地図の高さ
message(''); // ログ
// 地図データからノードを作成
for (var i = 0, len = map.length; i < len; i++) {
for (var j = 0, jlen = map[i].length; j < jlen; j++) {
masterList.add(new Node(j, i));
}
}
// スタートノードの設定
var targetNode = masterList.get(sx, sy);
targetNode.score = 0;
closeList.add(targetNode); // スタートノードはcloseListに格納しておく
var whileCount = 0;
while (true) {
whileCount++;
// 次のノードを探索
var checkNodePositions = [[targetNode.x, targetNode.y - 1], [targetNode.x, targetNode.y + 1], [targetNode.x - 1, targetNode.y], [targetNode.x + 1, targetNode.y]];
for (var i = 0, len = checkNodePositions.length; i < len; i++) {
var checkNodePosition = checkNodePositions[i];
// 地図の範囲外であれば探索しない
if (checkNodePosition[0] < 0 || checkNodePosition[0] > maxWidth - 1 ||
checkNodePosition[1] < 0 || checkNodePosition[1] > maxHeight - 1) {
continue;
}
var checkNode = masterList.get(checkNodePosition[0], checkNodePosition[1]);
if (checkNode.type == 0) continue; // 壁だったら処理しない
if (closeList.get(checkNodePosition[0], checkNodePosition[1])) continue; // スコアが確定していればなにもしない
if (!openList.get(checkNodePosition[0], checkNodePosition[1])) {
openList.add(checkNode); // openListにもcloseListにも無ければopenListに格納しておく
}
var score;
if (astar) {
score = targetNode.score + 1 + Math.abs(checkNodePosition[0] - gx) + Math.abs(checkNodePosition[1] - gy);
//console.log(score);
} else {
score = targetNode.score + 1; // この経路を辿ったときのスコアはtargetNode.score + 1
//console.log(score);
}
// スコアが格納されていない、またはほかの経路よりも効率が良ければスコアと、一つ前のノードをセットする
if (isNaN(checkNode.score) || checkNode.score > score) {
checkNode.score = score;
checkNode.parent = targetNode;
}
}
// openListが0になってしまったら、辿ることができないということ
if (openList.length() == 0) {
message('No route!');
return;
}
// 現在openListに格納されている最小のスコアのノードはスコアを確定し、closeListに格納する
targetNode = openList.getMin();
openList.remove(targetNode);
closeList.add(targetNode);
targetNode.score = targetNode.score;
if (targetNode.x == gx && targetNode.y == gy) break;
}
var endTime = new Date().getTime();
message(endTime - startTime + 'ms' + ' whileCount:' + whileCount);
showRoute(targetNode); // ルートを表示する
}
var message = function(value) {
document.getElementById('message').innerHTML = value;
}
var showRoute = function(targetNode) {
var td = tdList.get(targetNode.x, targetNode.y);
td.className = 'scotch route';
td.style.backgroundColor = 'green';
var parent = targetNode.parent;
if (parent) showRoute(parent);
}
var createMapData = function(count) {
map = [];
start = [0, 0];
for (var i = 0, len = mapSize * count; i < len; i++) {
var row = [];
for (var j = 0, jlen = mapSize * count; j < jlen; j++) {
var r = Math.floor(Math.random() * 100) % 5;
row.push(r);
}
map.push(row);
}
}
var createMap = function() {
var graph = document.getElementById('graph');
graph.innerHTML = '';
var table = graph.appendChild(document.createElement('table'));
table.style.borderCollapse = 'collapse';
var tbody = table.appendChild(document.createElement('tbody'));
tdList = new Table();
for (var i = 0, len = map.length; i < len; i++) {
var tr = tbody.appendChild(document.createElement('tr'));
var row = [];
for (var j = 0, jlen = map[i].length; j < jlen; j++) {
var td = tr.appendChild(document.createElement('td'));
observe(td, 'click', analyse);
td.style.border = '1px solid white';
td.style.width = '10px';
td.style.height = '10px';
if (map[i][j] == 0) {
td.className = 'scotch wall';
td.style.backgroundColor = 'red';
}
else td.className = 'scotch';
tdList.set(j, i, td);
}
}
}
var analyse = function(event) {
var target = event.target || event.srcElement;
var trChildren = target.parentNode.children;
var tbodyChildren = target.parentNode.parentNode.children;
var x,y;
for (var i = 0, len = trChildren.length; i < len; i++) {
if (trChildren[i] == target) {
x = i;
break;
}
}
var tr = target.parentNode;
for (var i = 0, len = tbodyChildren.length; i < len; i++) {
if (tbodyChildren[i] == tr) {
y = i;
break;
}
}
if (start[0] == x && start[1] == y) {
message('Start is equals to Goal');
return;
}
if (target.className.indexOf('wall') != -1) {
message('Your clicked cell is wall');
return;
}
// routeをクリアする
tdList.each(function(td) {
var className = td.className;
var classNameList = className.split(/ /);
for (var i = classNameList.length - 1; i >= 0; i--) {
if (classNameList[i] == 'route') {
classNameList.splice(i, 1);
td.style.backgroundColor = '';
}
}
td.className = classNameList.join(' ');
});
var astar = document.getElementById('astar20090824').checked;
dijkstra(start[0], start[1], x, y, astar);
start = [x, y];
}
var observe = function(target, type, listener) {
if (target.addEventListener) target.addEventListener(type, listener, false);
else target.attachEvent('on' + type, function() { listener.call(target, window.event); });
}
var Node = function(x, y) {
this.x = x;
this.y = y;
this.type = map[y][x];
}
Node.prototype.score = NaN;
Node.prototype.parent = null;
var NodeList = function() {
this.data = {};
}
NodeList.prototype.add = function(value) { this.data[value.x + ',' + value.y] = value; }
NodeList.prototype.get = function(x, y) { return this.data[x + ',' + y]; }
NodeList.prototype.length = function() {
var count = 0;
for (var key in this.data) {
count++;
}
return count;
}
NodeList.prototype.remove = function(value) { delete this.data[value.x + ',' + value.y]; }
NodeList.prototype.getMin = function() {
var data = this.data;
var min = null;
for (var node in data) {
if (!min) {
min = data[node];
continue;
}
if (min.score > node.score) min = data[node];
}
return min;
}
var Table = function() {
this.data = {};
}
Table.prototype.set = function(x, y, value) { this.data[x + ',' + y] = value; }
Table.prototype.get = function(x, y) { return this.data[x + ',' + y]; }
Table.prototype.each = function(func) {
var data = this.data;
for (var key in data) {
func(data[key]);
}
}
observe(document.getElementById('mapSelect20090824'), 'change', function(event) {
var target = event.target || event.srcElement;
var value = target.value;
createMapData(value);
createMap();
});
createMapData(1);
createMap();
})();