迷路を作って遊んでみる2
前回からの続きです。前回は、迷路と迷路を進むプレイヤーを作りました。今回は自動的にゴールを探してみます。
壁伝いに歩く
迷路は壁伝いに歩いていけばゴールにたどり着くとよく言われます。ただし、この方法は、壁とゴールが隣接している場合にしか使えません。今回は、壁とゴールが隣接しているという条件のもとで、ゴールを探します。
アルゴリズム
今回は左の壁伝いに歩くことを考えます。いくつかのケースを考えてみましょう。まず、左側に壁が無い場合は、左側に進みます。もし左側に壁があれば前にすすみます。このとき前側にも壁があれば、右側。右側にも壁があれば、後ろ側、つまり逆戻りします。これを実装したのが、以下のSearchオブジェクトのmoveAlongLeftWallメソッドになります。
var Search = { moveAlongLeftWall : function(maze) { maze.turnLeft(); for(var i = 0; i < 4; i++){ if( maze.moveStraight() ) return true; maze.turnRight(); } return false; } };
このプログラムでは、最初に進行方向の左側に向かって進もうとして、失敗すればそこから右に90度ずつ回転し、その方向に進めるかどんどんと試していきます。moveAlongLeftWallというメソッドを一回実行すると、一セル進みます。これをゴールにつくまで繰り返せば良いでしょう。タイマーを使うとプレイヤーの進行具合が見れるので面白いです。
setInterval( function(){ var _maze = maze; Search.moveAlongLeftWall(_maze); }, 300);
ちなみに、ゴールに辿りつけない場合は、迷路の周りをグルグルと回り続けます。これはこれで、面白いです。以下のURLで見れるようにしておきます。
右側の壁沿い
先ほどのSearchオブジェクトに、右側の壁に沿って進むメソッドも追加します。
var Search = { moveAlongLeftWall : function(maze) { maze.turnLeft(); for(var i = 0; i < 4; i++){ if( maze.moveStraight() ) return true; maze.turnRight(); } return false; }, moveAlongRightWall : function(maze) { maze.turnRight(); for(var i = 0; i < 4; i++){ if( maze.moveStraight() ) return true; maze.turnLeft(); } return false; } };
今回はきりがいいので、ここまでです。
