距離計測(p5js)
格子状の迷路におけるスタート地点から各地点までの距離計測
スタート地点からの距離計測をp5jsで実装したいと思います。
今回作るもの
今回は図1のようにスタート地点（左上）から各マスまで何マスで行けるのかを調べるプログラムを作成します。マスの数は上下左右の移動のみとし、斜め移動はできないものとします。
余談ですが、この距離を計る問題は7 Billion Humansの61年目にも似たようなものがありました。興味があればぜひ（こちらは斜め方向もあり）。
p5jsでの実装
距離の計測は図2のように数値が既に入ってるマスの上下左右の空白マスに、そのマスの値+1の値を入れていくことで調べることができます。この図の例では7の上下左右の空白マスに7に1を加えた8を代入していくことになります。
この処理を繰り返していき、既に数値が入ってる場所の上下左右に空白マスがなくなると計測完了となります。
プログラムの具体的な内容
mapxとmapyによりマップサイズを決定しています。
xは横の大きさ、yは縦の大きさです。
・searchop(x,y,op)
配列に対しpushとshift操作を行います。
今回はpush,shift操作を行う度にx座標を格納する配列と、y座標を格納する配列の2つを操作するため関数にしました。
引数はxにx座標を、yにy座標を、opに操作('push' or 'slide')を入力します。
slideの場合はx座標、y座標に何を入れても処理は変わりません。
pushとshift操作については図3のイメージ図を参照してください。
・setup
使用する色やボタンの生成などを行います。
・draw()
STARTボタンを押すと動作し、距離計測と距離の描画を行います。
・mapclear
描画処理を停止し、マップの状態や距離計測の情報をリセットします。
・mouseClicked
クリックしたときに動作。
押したマスの位置に壁があった場合消去、何もない場合壁を作成します。
座標(0,0)の位置はスタート地点としているため、クリックしても反応しないようif文で処理しています。
・drawblock(x,y)
入力された座標(x,y)にあるブロックの状態を描画します。
ブロックの状態が-1の場合は壁を、そうでないばあいは空白マスを描画します。
・blockset(x,y)
マウスでクリックしたときの壁と空白マスの反転を行います。
壁は-1、空白マスは0で処理しているため、
mapstate = (-1) * (mapstate + 1);
で処理することができます。
[-1の場合] -1 × (-1+1) = 0
[0の場合] -1 × (0 + 1) = -1
・stepcount
STARTボタンを押すと作動します。
座標(0,0)に1を代入し、隣接マスに空白マスが存在するか否かを調べ、隣接する空白マスの座標を配列に保存します。
0でなく1を代入する理由は、空白マスを0と定義しており、0にすると空白マスと未探索マスの区別がつかなくなるため、1を代入しています。
そのためこのプログラムで距離は配列に代入されている-1,0以外の数値から1引いた値になります。
・stepcountripple(x,y)
配列に保存された空白マスの座標に距離を代入する処理を行います。
代入後はそのマスに隣接する空白マスの座標を配列に保存します。
・printnum(x,y)
入力された座標(x,y)の距離を描画します。
完成したプログラム
まとめ
距離を調べるプログラムを作成するのが大変なのではと思ったが、意外となんとかなりました。
実はこのプログラムを作成する前に再帰関数で作成したのですが、非効率な上draw関数を1周しないと描画されないprocessingには不向きなプログラムでした。
（おまけ）再帰関数を使用した距離計測
基本的には距離計測の処理(stepcountripple)部分だけが変わったものなので、その部分の処理の概要を図4に置いておきます。
隣接する空白マスを探し再起動を呼び出す際に、上下左右同時に調べることができないため、「右を調べて再帰関数→下を調べて再帰関数→左を調べて再帰関数→上を調べて再帰関数」という風に一つずつ行っており、図5のように遠回りして距離を計測してしまう問題がありました。この問題を解消するために、差が2以上のマスも再度調べるようにしていますが、既に調べたマスを調べる事になり非効率かなと思い没になりました。
