目次
実際に動かす
ボードが描画できたので、次は幅優先探索のアルゴリズムを組み込んで、実際に動かしてみます。Squareクラスは同じですが、sketch.jsのコードはずいぶん長くなります。
const gridSize = 4;
let gridWidth;
let grid = [];
let startSquare;
function setup() {
createCanvas(320, 320);
background(200);
stroke(120);
textSize(20);
gridWidth = width / gridSize;
for (let i = 0; i < gridSize; i++) {
grid[i] = [];
for (let j = 0; j < gridSize; j++) {
const square = new Square(i, j, gridWidth, 'empty');
grid[i][j] = square;
square.display();
}
}
startSquare = grid[0][0];
startSquare.setStatus("start");
startSquare.display();
grid[2][2].setStatus("goal");
grid[2][2].display();
grid[1][1].setStatus("obstacle");
grid[1][1].display();
grid[1][2].setStatus("obstacle");
grid[1][2].display();
grid[1][3].setStatus("obstacle");
grid[1][3].display();
grid[2][1].setStatus("obstacle");
grid[2][1].display();
// pathFind()関数にスタート用Squareオブジェクトを渡して経路探索を開始
const result = pathFind(startSquare);
print('結果 : ' + result); // ["south", "south", "south", "east", "east", "north"]
}
// スタート用Squareオブジェクトを受け取り、
// スタート位置からゴール位置までの1マスごとの移動方向を含む配列(最短経路)を返す
function pathFind(startSquare) {
// startSquareを含む配列queueを作成
// アルゴリズムの(1)
const queue = [startSquare];
// queue配列に要素が含まれている限り繰り返す
// アルゴリズムの(5)
while (queue.length > 0) {
// アルゴリズムの(2)
// queueの最初の要素を取り出す。取り出した要素はqueueから削除される
// => 先入れ先出しのキュー構造(Array.shift()メソッド)
const targetSquare = queue.shift();
// 暫定的なSquareオブジェクト
let tempSquare;
// 取り出したSquareオブジェクトを方向別に調べ、
// 結果を、実際のSquareオブジェクトと同等の暫定Squareオブジェクトとして得る
// 返されるtempSquareは、それまでに通過できた方向を持つpath配列と、
// 実際の状態を表すstatusプロパティを持っている
// 北側
tempSquare = checkNeighborSquare(targetSquare, 'north');
// tempSquareの状態がゴールなら
if (tempSquare.getStatus() === 'goal') {
// 調べた方向のパスを返して終了
// アルゴリズムの(3)
return tempSquare.getPath();
// tempSquareの状態が有効なら
}
else if (tempSquare.getStatus() === 'valid') {
// queueにtempSquareを追加 => whileループはさらにつづく
// アルゴリズムの(4)
queue.push(tempSquare);
}
// 南側
tempSquare = checkNeighborSquare(targetSquare, 'south');
// アルゴリズムの(3)
if (tempSquare.getStatus() === 'goal') {
return tempSquare.getPath();
}
else if (tempSquare.getStatus() === 'valid') {
// アルゴリズムの(4)
queue.push(tempSquare);
}
// 東側
tempSquare = checkNeighborSquare(targetSquare, 'east');
// アルゴリズムの(3)
if (tempSquare.getStatus() === 'goal') {
return tempSquare.getPath();
}
else if (tempSquare.getStatus() === 'valid') {
// アルゴリズムの(4)
queue.push(tempSquare);
}
// 西側
tempSquare = checkNeighborSquare(targetSquare, 'west');
// アルゴリズムの(3)
if (tempSquare.getStatus() === 'goal') {
return tempSquare.getPath();
}
else if (tempSquare.getStatus() === 'valid') {
// アルゴリズムの(4)
queue.push(tempSquare);
}
// 確認用
for (let i = 0; i < queue.length; i++) {
// queue内のSquareオブジェクトを出力
print(queue[i]);
// そのSquareオブジェクトのpath配列を出力
print(queue[i].getPath())
}
print('---------------------');
// tempSquareはお役御免
tempSquare = null;
}
// 経路がない場合はfalseを返す
return false;
}
// 渡されたSquareオブジェクトのdirection側(東西南北)について調べ、
// 同等で、調べた方向をpathプロパティに持つ暫定Squareオブジェクトを返す
function checkNeighborSquare(currentSquare, direction) {
print('(' + currentSquare.getFromTop() + ', ' + +currentSquare.getFromLeft() + ')の' + direction + 'を探索中');
// currentSquareのpath配列をそのままコピー
const nextDirection = currentSquare.path.slice();
// その配列にdirection(調べたい方向)を加える
// => たとえば、pathに"south"を持っているcurrentSquareに、direction="south"が指定されている場合には、
// nextDirectionは["south","south"]になる => ["前に通過できた方向","次に通過したい方向"]
// このnextDirectionは、この後作成する暫定的なSquareオブジェクト(tempSquare)のpathプロパティに指定される
nextDirection.push(direction);
// currentSquareの(top, left)位置
let top = currentSquare.getFromTop();
let left = currentSquare.getFromLeft();
// 方向別に、調べたい(top, left)位置を設定
// => 北向きに調べるのなら、その位置は(top-1, left)になる
if (direction === 'north') {
top -= 1;
}
else if (direction === 'south') {
top += 1;
}
else if (direction === 'east') {
left += 1;
}
else if (direction === 'west') {
left -= 1;
}
// 調べたい(top, left)位置の、暫定的なSquareオブジェクトを作成する
// nextDirectionは['これまで通過できた方向(ある場合)','次に調べたい方向']
const tempSquare = new Square(top, left, gridWidth, 'unknown', nextDirection);
// 暫定的なSquareオブジェクトと同じ位置にある、実際のSquareオブジェクトの状態を調べる
const status = getSquareStatus(tempSquare);
// 暫定的なSquareオブジェクトをその状態に設定する
tempSquare.setStatus(status);
// 状態が有効なら
if (tempSquare.getStatus() === 'valid') {
// grid内の実際のSquareオブジェクトの状態を書き換え、描画し直す
// => 調べたSquareオブジェクトはライトグレーになる
grid[top][left].setStatus('visited');
grid[top][left].display();
}
// 確認用
print(' -> ' + tempSquare.getStatus());
// 結果を暫定Squareオブジェクトで返す
return tempSquare;
}
// 渡された暫定Squareオブジェクトと同じ位置にある、実際のSquareオブジェクトの状態を調べて返す
function getSquareStatus(square) {
// (top, left)位置を特定
const top = square.getFromTop();
const left = square.getFromLeft();
// グリッドの範囲外なら無効
if (top < 0 || top >= gridSize || left < 0 || left >= gridSize) {
return 'invalid';
// グリッドの範囲内なら
}
else {
// 暫定Squareオブジェクトと同じ位置にある実際のSquareオブジェクトを特定
const targetSquare = grid[top][left];
// その状態
const status = targetSquare.getStatus();
// 状態別に結果を返す
if (status === 'goal') {
return 'goal';
// 'obstacle'か'visited'か、'start'のいずれか
}
else if (status !== 'empty') {
return 'blocked';
}
else {
return 'valid';
}
}
}pathFind()関数の探索は一瞬で終わるので、変化が分かりづらいですが、pathFind()関数が調べた正方形は白からうすいグレーに変化しています。未チェックの正方形は白いままです。
またプログラム内にいくつかprint()関数を仕込んでいるので、[コンソール]に探索の進行状況が表示されます。
アルゴリズムはどこに？
「2: Pathfinding(経路探索) Breadth-First Search(幅優先探索) アルゴリズム p5.js – 解説」で見た幅優先探索のアルゴリズムは、pathFind()関数の下図の部分で実装しています。
- 開始のノードをキューに追加する -> startSquareはgrid[0][0]のSquareオブジェクトです。これを[と]に含めることで、配列queueを作成しています。
- キューにノードがあれば取り出す。なければ全ノードの探索は終わった -> Arrayのshift()メソッドは、配列から最初の要素を取り出し、取り出した要素を配列から削除します。これはFIFOの要領です。
- 取り出したノードが目的のノードであれば探索終わり -> tempSquareのstatusが’goal’なら、tempSquareのpathプロパティの値を呼び出し元に返して、関数を終わります。
- 取り出したノードに隣接するノードの中で、未探索のノードをキューに追加する -> 目的の正方形にはまだ到達していないので、queueの末尾にtempSquareを追加します。
- (2)に戻り、以降を繰り返す -> queue.length > 0 を条件にwhileループを繰り返します。
探索の進行状況
では[コンソール]の出力結果を見ながら、pathFind()関数の探索がどのように進んだかを見ていきましょう。出力結果では、破線(—–)を探索のひと区切りとして見ます。
- pathFind()にスタート用Squareオブジェクトを渡してスタート
const result = pathFind(startSquare); - スタート用Squareオブジェクトを要素に持つ配列queueを作成
const queue = [startSquare]; - whileループに入る
while (queue.length > 0) { - queue配列の最初の要素を取り出す(FIFO方式)
const targetSquare = queue.shift(); - checkNeighborSquare()関数を方向別に呼び出す
tempSquare = checkNeighborSquare(targetSquare, ‘north’);
実際の出力に入るのはこの後です。checkNeighborSquare()関数には、東西南北方向の状態を調べたいSquareオブジェクトと、調べたい方向を指定します。
１回めのループではstartSquare、つまり(0,0)の正方形を渡しているので、黄色の矩形の東西南北方向の状態を調べています。下図はそのときの出力結果を説明する図です。
(0,0)の北側は範囲外なので探索は無効(invalid)です。(0,0)の南側にある(1,0)はそこに移動できるので有効(valid)です。有効な結果(tempSquare)はqueue配列に追加します。この時点でqueueには(1,0)相当のtempSquare１つが含まれています。
if (tempSquare.getStatus() === 'goal') {
return tempSquare.getPath();
}
else if (tempSquare.getStatus() === 'valid') {
// 有効なtempSquareはqueueの末尾に追加する
queue.push(tempSquare);
}次いで(0,0)の東側を調べます。この(0,1)も有効なので、この(0,1)相当のtempSquareをqueue配列に追加します。この時点でqueueには、(1,0)相当のtempSquareと(0,1)相当のtempSquareの２つが含まれています。
最後に西側を調べます。ここは範囲外なのでinvalidです。
1回めのwhileループでqueue配列には２つのtempSquareが含まれているので、ループはさらにつづき、const targetSquare = queue.shift();によって、queueの１つめの要素である(1,0)相当のtempSquareが取り出され、queueには(0,1)相当のtempSquareが残ります。
そして(1,0)相当のtempSquareを対象にした東西南北の探索が始まります。
(1,0)の北は探索の開始位置なので調べる必要はありません。開始のSquareオブジェクトのstatusはその作成時に’start’に設定されていて、探索の対象になるときには、getSquareStatus()関数によって、statusが’blocked’に変更されます。
// 渡された暫定Squareオブジェクトと同じ位置にある、実際のSquareオブジェクトの状態を調べて返す
function getSquareStatus(square) {
// (top, left)位置を特定
const top = square.getFromTop();
const left = square.getFromLeft();
// グリッドの範囲外なら無効
if (top < 0 || top >= gridSize || left < 0 || left >= gridSize) {
return 'invalid';
// グリッドの範囲内なら
}
else {
// 暫定Squareオブジェクトと同じ位置にある実際のSquareオブジェクトを特定
const targetSquare = grid[top][left];
// その状態
const status = targetSquare.getStatus();
// 状態別に結果を返す
if (status === 'goal') {
return 'goal';
// 'obstacle'か'visited'か、'start'のいずれか
}
else if (status !== 'empty') {
return 'blocked';
}
else {
return 'valid';
}
}
}(1,0)の南は(2,0)なので有効です。したがってqueueには(2,0)相当のtempSquareが追加されます。
(1,0)の東は障害物です。障害物のSquareオブジェクトは生成時にstatusが’obstacle’に設定されています。障害物のSquareオブジェクトが探索されるときには、開始のSquareオブジェクトと同様に、getSquareStatus()関数によってstatusが’blocked’に変更されます。
(1,0)の西は範囲外なので、無効です。したがってここまでで、queueには、(0,1)相当のtempSquareと(2,0)相当のtempSquareの２つが含まれていることになります。
出力結果を見ると、queueの１つめとして(0,1)相当のtempSquareが出力されていて、そのpathは’east’です。これは、そのSquareオブジェクトが前に探索されたときに通過できる方向として、checkNeighborSquare()関数内で設定されたものです。
function checkNeighborSquare(currentSquare, direction) {
print('(' + currentSquare.getFromTop() + ', ' + +currentSquare.getFromLeft() + ')の' + direction + 'を探索中');
// currentSquareのpath配列をそのままコピー
const nextDirection = currentSquare.path.slice();
// このnextDirectionは、この後作成する暫定的なSquareオブジェクト(tempSquare)のpathプロパティに指定される
nextDirection.push(direction);
// currentSquareの(top, left)位置
let top = currentSquare.getFromTop();
let left = currentSquare.getFromLeft();
// 方向別に、調べたい(top, left)位置を設定
// => 北向きに調べるのなら、その位置は(top-1, left)になる
if (direction === 'north') {
top -= 1;
}
else if (direction === 'south') {
top += 1;
}
else if (direction === 'east') {
left += 1;
}
else if (direction === 'west') {
left -= 1;
}
// 調べたい(top, left)位置の、暫定的なSquareオブジェクトを作成する
const tempSquare = new Square(top, left, gridWidth, 'unknown', nextDirection);
// 暫定的なSquareオブジェクトと同じ位置にある、実際のSquareオブジェクトの状態を調べる
const status = getSquareStatus(tempSquare);
// 暫定的なSquareオブジェクトをその状態に設定する
tempSquare.setStatus(status);
// 状態が有効なら
if (tempSquare.getStatus() === 'valid') {
// grid内の実際のSquareオブジェクトの状態を書き換え、描画し直す
// => 調べたSquareオブジェクトはライトグレーになる
grid[top][left].setStatus('visited');
grid[top][left].display();
}
print(' -> ' + tempSquare.getStatus());
// 結果を暫定Squareオブジェクトで返す
return tempSquare;
}探索の対象は、const targetSquare = queue.shift()によってqueue配列からtargetSquareとして取り出され、４回呼び出されるcheckNeighborSquare()関数に渡されます。
tempSquare = checkNeighborSquare(targetSquare, 'south');checkNeighborSquare()関数では、渡された探索対象のSquareオブジェクト(currentSquare)のpath配列をそのままコピーし、渡された調べたい方向であるdirectionを追加します。Squareオブジェクトのpathプロパティは生成時に空の配列として作成されます。たとえばpathが空で、directionが’south’の場合には、pathは[‘south’]になります。このsouthはこの時点では”次に通過したい方向”です。
そしてその後、調べたい位置(top,left)を持つSquareオブジェクトを作成するときのpathプロパテの値として、この配列が指定されます。暫定的なSquareオブジェクトと呼んでいたのはこれです。
// currentSquareのpath配列をそのままコピー
const nextDirection = currentSquare.path.slice();
// その配列にdirection(調べたい方向)を加える
// このnextDirectionは、この後作成する暫定的なSquareオブジェクト(tempSquare)のpathプロパティに指定される
nextDirection.push(direction);
...
// 調べたい(top, left)位置の、暫定的なSquareオブジェクトを作成する
const tempSquare = new Square(top, left, gridWidth, 'unknown', nextDirection);tempSquareはこの後、checkNeighborSquare()関数とそこから呼び出されるgetSquareStatus()関数で、その位置(top,left)が範囲内にあるかや、実際に描画しているgrid配列内のSquareオブジェクトの状態を照会してその状態に設定し、実際のSquareオブジェクト相当の暫定的なSquareオブジェクトとして返されます。
このときには、statusがvalidである暫定的なSquareオブジェクトのpathは”通過できた有効な方向”となっています。
(ずいぶん前になってしまいましたが)[コンソール]に出力されたqueue配列の２つめのtempSquareは、(top,left)が(2,0)、statusが’valid’、pathが[‘south’,’south’]です。pathに２つの方向が含まれているということは、ここまで南 -> 南 と進んで通過できた、ということを意味しています。
２回めのループ後、queue配列には(0,1)相当のtempSquareと(2,0)相当のtempSquareの２つが含まれているので、３回めのループに入り、queue配列の最初の要素である(0,1)相当のtempSquareが取り出されます。この時点でqueueには(2,0)相当のtempSquareが残ります。
[コンソール]には下図の結果出力されます。
(0,1)の北は範囲外なので無効、南は障害物なので’blocked’、東の(0,2)は有効なので、(0,2)のtempSquareがqueue配列に追加されます。この時点でqueueには(2,0)相当のtempSquareと(0,2)相当のtempSquareが入っています。西は開始位置なので’blocked’です。
queue配列の出力を見ると、(2,0)相当のtempSquareのpathは[‘south’,’south’]で、(0,2)相当のtempSquareのpathは[‘east’,’east’]です。これは、(0,0)から探索を開始し、ここまでで南 -> 南 と、”東” -> “東”の２つが有効な経路として上がっている、ということです。
このボードの経路を見つける場合、人間なら、まず間違いなく目的地を見定めながら進むでしょうが、幅優先探索のアルゴリズムは目的地をまったく意識していないどころか、必要とすらしていない印象を受けます(実際、このアルゴリズムはゴールがあることを開始前に確認していません)。
これは、「1: Pathfinding(経路探索) Breadth-First Search(幅優先探索) アルゴリズム p5.js – 導入」で述べた、幅優先探索は「通ることのできる長さが1の経路を全部調べ、次に通るのことのできる長さが2の経路を全部調べるということを、正方形”A”から”B”への最短経路が見つかるまでつづける」というまさに”しらみつぶし”の方法であることを実感させ、「2: Pathfinding(経路探索) Breadth-First Search(幅優先探索) アルゴリズム p5.js – 解説」で述べた「正解が存在する場合は必ず解決できる(正解がない問題には対処できない)」という特徴を裏付けるものです。
queue配列が空になるまで、whileループの繰り返しごとにqueueから最初のtempSquareを取り出して、それの東西南北を調べ、有効な方向を持つtempSquareをqueueに追加する幅優先探索は、このようにして進み、そしてあるとき、checkNeighborSquare()関数が返したtempSquareのstatusが’goal’であったとき、突然、探索は終了します。
tempSquare = checkNeighborSquare(targetSquare, 'north');
// tempSquareの状態がゴールなら
if (tempSquare.getStatus() === 'goal') {
// 調べた方向のパスを返して終了
// アルゴリズムの(3)
return tempSquare.getPath();
// tempSquareの状態が有効なら
}
else if (tempSquare.getStatus() === 'valid') {
// queueにtempSquareを追加 => whileループはさらにつづく
// アルゴリズムの(4)
queue.push(tempSquare);
}