幅優先探索 - 素人がプログラミングを勉強していたブログ

昔流行ったやつ。幅優先探索で迷路の経路を出す時は、ノードをリストにして逆算していくか、マップを0で初期化して、通るたびに0, 1, 2…というように徐々に増やしていって、ゴールについたら一つずつ減っていくような道を探す、という方法が使える。
それぞれ辺のコストが異なる場合はキューをPriority Queueにしてコストの合計が最小であるところから探索すれば良い。で、これを発展させるとダイクストラ法になって、更に、探索順序を改良すると、AStarになる。このへんは、一度書いてみると理解が深まるのでオススメ。

<!DOCTYPE html>
<html>
  <head>
    <meta charset="UTF-8">
    <title>迷路探索</title>
    <style>
      textarea {
        font-family: monospace;
      }
    </style>
  </head>
  <body>
    <p>ref. <a href="http://okajima.air-nifty.com/b/2010/01/post-abc6.html">人生を書き換える者すらいた。: 人材獲得作戦・４　試験問題ほか</a></p>
    <textarea rows="20" cols="30">
**************************
*S* *                    *
* * *  *  *************  *
* *   *    ************  *
*    *                   *
************** ***********
*                        *
** ***********************
*      *              G  *
*  *      *********** *  *
*    *        ******* *  *
*       *                *
**************************
    </textarea>
    <button>search</button>
  </body>
</html>
<script>

var button = document.querySelector("button");
button.addEventListener("click", onclick, false);

function onclick() {
  var textarea = document.querySelector("textarea");
  if (textarea.value.indexOf("$") >= 0) {
    textarea.value = textarea.value.replace(/\$/g, " ");
  } else {
    textarea.value = search(textarea.value);
  }
}

function search(map) {
  // マップは、文字の二次元配列とする
  var cols = map.split("\n").map(function (s) {
    return s.split("");
  });
  var queue = [];
  var v;

  // 最初はキューにスタート地点のみを入れておく
  queue.push(startNode(cols));

  // 訪問済み地点を記録するためのマップ
  var visited = {};

  find: {
    while (queue.length != 0) {
      v = queue.shift();
      if (cols[v.y][v.x] == "G") {
        // ゴールについたので抜ける、ゴール地点はv
        break find;
      }
      s = [v.x, v.y].join(",");
      if (!(s in visited)) { // 訪問済みでなければ、次の手をキューに入れる
        visited[s] = true;
        queue.push.apply(queue, build(cols, v));
      }
    }

    // ゴールに到達できなかった場合（ここは通らない）
    return;

  }

  // ゴール地点から逆算し経路を算出する
  for (v = v.p; v.p; v = v.p) {
    cols[v.y][v.x] = "$";
  }

  return cols.map(function (s) {
    return s.join("");
  }).join("\n")

}

function startNode(cols) {
  var x, y;
  // スタート地点の探索
  for (y = 0; y < cols.length; y++) {
    for (x = 0; x < cols[y].length; x++) {
      if (cols[y][x] == "S") {
        // キューの要素は、現在の地点を値とし一手前にリンクするリスト
        return {
          x: x,
          y: y,
          p: null
        };
      }
    }
  }
  // スタート地点が見つからなかった場合（ここは通らない）
  return null;
}

// 次の手
function build(cols, v) {
  // 現地点から次の手までの差分
  var ds = [
    {dx: -1, dy: 0},
    {dx: 1, dy: 0},
    {dx: 0, dy: -1},
    {dx: 0, dy: 1},
  ];
  return ds.map(function (d) {
    return {
      x: v.x + d.dx,
      y: v.y + d.dy,
      p: v
    };
  }).filter(function (v) {
    // Gも次の手に含まなねばならないので== " "ではない
    return cols[v.y][v.x] != "*";
  });
}

</script>