ダイクストラ法とA-StarアルゴリズムをJavaScriptで実装してみた。
ダイクストラ法は確かに動いているように思えるけど、A-Starの方はうまく動いていないように見えるというか、全然高速化されていない。こんなもんなのかな？知ってる人いたら教えてください。
Create Map:
(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();
})();