【JavaScript】自動生成迷路＋最短正解ルート表示

　どうも！LSSです！！

もう４か月も前になりますか。

【JavaScript】続・自動生成迷路 - Little Strange Software

というスクリプトを書いていました。

タイトル通り、自動的に迷路を生成するスクリプトでしたが、生成して表示するだけのものでした。

で、今回はそれに「最短正解ルート」を自動的に割り出し、表示する機能をつけてみました！

自動生成迷路

幅:

高さ:

スライダーで幅と高さを調節するたびに、そのサイズに合った迷路が自動生成されます。

そして迷路の下にある「search」ボタンを押すと、最短正解ルートが瞬時に割り出されて表示されます！

最短正解ルートの割り出しアルゴリズム

再帰呼び出しによる、かなりベタな方法を用いています。

スタート地点の位置情報を調査用配列変数に入れ、その位置の「上下左右隣の４マス」について調査します。

「迷路の範囲内」であり、「間が壁ではなく通過可能」であり、「調査用配列変数に未登録の位置」

という条件が全て成立した場合のみ、その（元のマスの上下左右隣の）調査したマスの位置を、調査用配列変数の末尾につけたし。（と同時に移動前のマスがどれかも別途記録）

「上下左右隣の４マス」を処理し終えると、調査用配列変数の次の要素に移動し、またその「上下左右隣の４マス」を同様に調査…というのを、
「調査用配列変数に追加したものがゴールマスだった！」
という条件が成立するまで、延々と繰り返します。

ゴールマスに到達すると上記処理は終了し、今度は、
「ゴールマスから一歩づつ移動前マスに引き返し、スタート地点に辿りつくまで、マスを水色に塗りながら進む」
という処理を実行。

調査用配列変数には「スタート地点からの歩数が少ない順に」記録されるため、これで最短ルートが見つかった事になります^^

コード

やたら長いので、見たい方だけここをクリックしてください。

コード

<p>幅:<br /><input id="rgx" style="width: 100%;" max="60" min="5" type="range" value="15" /></p>
<p>高さ:<br /><input id="rgy" style="width: 100%;" max="60" min="5" type="range" value="10" /></p>
<div id="gamen"></div>
<p><input id="btn" type="button" value="search" /></p>
<p>
<script>// <![CDATA[
xmax=0;
ymax=0;
mztxt='';
dd=0;
mps=[];
mz=(ax,ay)=>ax<0 || ax>=xmax || ay<0 || ay>=ymax?0:parseInt(mztxt.substr(ax+ay*xmax,1));
mzw=(ax,ay)=>{mztxt=mztxt.substr(0,ax+ay*xmax)+'0'+mztxt.substr(ax+ay*xmax+1);}
makemaze();
rgx.addEventListener('input',makemaze,false);
rgy.addEventListener('input',makemaze,false);

function makemaze(){
xmax=parseInt(rgx.value)*2+1;
ymax=parseInt(rgy.value)*2+1;
mztxt='';
for(i=0;i<xmax*ymax;i++){
mztxt+='1';
}
mps.splice(0);
mps.push([1,1]);
mzw(1,1);
dd=1;
do{
mpi=Math.floor(Math.random()*mps.length);
if(mz(mps[mpi][0]-2,mps[mpi][1])+mz(mps[mpi][0]+2,mps[mpi][1])+mz(mps[mpi][0],mps[mpi][1]-2)+mz(mps[mpi][0],mps[mpi][1]+2)==0){mps.splice(mpi,1);}else{
dig(mps[mpi][0],mps[mpi][1]);
}}while(dd<Math.floor(xmax/2)*Math.floor(ymax/2));
txt='幅 '+rgx.value+' ／高さ '+rgy.value+'<br/>';
txt+='<svg xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" width="100%" viewbox="0 0 '+(Math.floor(xmax/2)+0.2)+' '+(Math.floor(ymax/2)+0.2)+'">';
txt+='<defs>';
txt+='<path id="svgs" d="M 0.9,0.2 L 0.3,0.4 0.8,0.7 0.2,0.9" stroke-width="0.14" stroke="#ff4444" fill="none"></path>';
txt+='<path id="svgg" d="M 0.9,0.4 L 0.6,0.3 0.3,0.4 0.3,0.7 0.6,0.8 0.85,0.7 0.85 0.85" stroke-width="0.14" stroke="#ff4444" fill="none"></path>';
txt+='</defs>';
for(j=0;j<ymax;j++){for(i=0;i<xmax;i++){
if(mz(i,j)==1){txt+='<rect x="'+Math.floor(i/2)+'" y="'+Math.floor(j/2)+'" width="'+(i%2==0?0.1:1)+'" height="'+(j%2==0?0.1:1)+'" fill="#444444" stroke-width="0" stroke="#444444"></rect>';}
if(i%2+j%2==2){txt+='<rect x="'+(Math.floor(i/2)+0.1)+'" y="'+(Math.floor(j/2)+0.1)+'" width="1" height="1" fill="#ffffff" stroke-width="0" stroke="#444444" id="z'+i+'_'+j+'"></rect>';}
if(i==1 && j==1){txt+='<use xlink:href="#svgs" x="'+Math.floor(i/2)+'" y="'+Math.floor(j/2)+'"/>'};
if(i==xmax-2 && j==ymax-2){txt+='<use xlink:href="#svgg" x="'+Math.floor(i/2)+'" y="'+Math.floor(j/2)+'"/>'};
}}
txt+='</svg>';
gamen.innerHTML=txt;
szfinit();
}

function dig(xd,yd){
vt=Math.floor(Math.random()*4);
vy=Math.floor(vt/2-0.5);
vx=(vt*2-3)-vy*3;
if(mz(xd+vx*2,yd+vy*2)==1){
mzw(xd+vx*2,yd+vy*2);
mzw(xd+vx,yd+vy);
xd+=vx*2;yd+=vy*2;
mps.push([xd,yd]);
dig(xd,yd);
dd++;
}
}

btn.addEventListener('click',szf,false);
szm=[];
szn=[];
szr=[];
szp=0;
szfinit();

function szfinit(){
szm=[1+xmax];
szn=[0];
szr=[-1];
szp=0;
}

function szf(e){
for(i=0;i<4;i++){
szx=Math.floor(i/2)*(i%2*2-1);
szy=(1-Math.floor(i/2))*(i%2*2-1);
szs=szm[szp]%xmax+szx*2+(Math.floor(szm[szp]/xmax)+szy*2)*xmax;
if(szm[szp]%xmax+szx*2>0 && szm[szp]%xmax+szx*2<xmax && Math.floor(szm[szp]/xmax)+szy*2>0 && Math.floor(szm[szp]/xmax)+szy*2<ymax && mz(szm[szp]%xmax+szx,Math.floor(szm[szp]/xmax)+szy)==0 && szm.indexOf(szs)<0){
szm.push(szs);
szn.push(szn[szp]+1);
szr.push(szp);
}
}
szp++;
szl=szm.indexOf(xmax-2+(ymax-2)*xmax);
if(szl<0){szf();}else{
while(szl>=0){document.getElementById('z'+(szm[szl]%xmax)+'_'+Math.floor(szm[szl]/xmax)).setAttribute('fill','#aaccdd');szl=szr[szl];}
}
}
// ]]></script>
</p>

赤文字部分が正解ルート探索を行う追加部分です。

あとがき

なんだか「再帰呼び出しで何かプログラムしてみたい病」が発症したので、やってみましたｗ

こうして迷路の走査に成功したので、例えば迷路を歩くスクリプトで、「一歩づつ上下左右をポチポチして進む」という操作性から、「５歩以内で移動可能な範囲を示し、その範囲内をクリックで移動する」というような、クリック回数が少なくて済む操作性を実現する事もできますね^^

あと、この正解ルート表示できるようにした事で、「正解ルートがほぼ対角線移動に偏りがち」という、既知の難点がより分かりやすくなりました^^;;;;;

ってなとこで、今回はこのへんで！

次回もまた、よろしくお願いします^^