ダイクストラ法とA-StarアルゴリズムをJavaScriptで実装してみた。

ダイクストラ法は確かに動いているように思えるけど、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(); // 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();
})();