幅:
高さ:
どうも！LSSです！！
前から作ってみたかったもののひとつ、「自動生成迷路」をJavaScriptで作成してみました^^
スライダーを触るたびに迷路が再生成されます
「幅」と「高さ」を指定して、そのサイズの迷路を生成します。
一応、最小値と最大値を設定しています。
最大値でも問題ない速度で生成できるはず？ｗ
迷路生成のアルゴリズム
「迷路 自動生成」でググって出てきたいくつかのサイトを参考にさせていただきました。
「棒倒し」「壁伸ばし」「穴掘り」と何種類かのアルゴリズムがあるようで、今回は「穴掘り法」と呼ばれるものをJavaScriptで書いてみました。
これによって作成された迷路は、「全ての道が繋がっています」。
なので、どこがスタートでどこがゴールでも構わないという事になりますが、一応、左上をスタート、右下をゴールって事にしました。
また、「穴掘り法」の特性として「ループにはならない」というのがあります。
…これは迷路生成後に、適当に壁に穴を開けたらループを作る事もできそうですね。
迷路の描画にはSVGを使用しています。
壁を黒ベタ四角で描いているだけですが、ここも凝りようはありますねｗ
コード
<p>幅:<br /><input id="rgx" style="width: 100%;" max="99" min="11" step="2" type="range" value="21" /></p>
<p>高さ:<br /><input id="rgy" style="width: 100%;" max="99" min="11" step="2" type="range" value="15" /></p>
<div id="gamen"> </div>
<script>// <![CDATA[
xmax=0;
ymax=0;
mztxt='';
dd=0;
mps=[];
makemaze();
rgx.addEventListener('input',makemaze,false);
rgy.addEventListener('input',makemaze,false);
function makemaze(){
xmax=parseInt(rgx.value);
ymax=parseInt(rgy.value);
mztxt='';
for(i=0;i<xmax*ymax;i++){
mztxt+='1';
}
mps=[];
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/><svg xmlns="http://www.w3.org/2000/svg" width="100%" viewbox="0 0 '+xmax+' '+ymax+'">';
for(j=0;j<ymax;j++){for(i=0;i<xmax;i++){
if(mz(i,j)==1){txt+='<rect x="'+i+'" y="'+j+'" width="1" height="1" fill="black" stroke-width="0.1" stroke="black"></rect>';}
if(i==1 && j==1){txt+='<path d="M '+(i+0.8)+','+(j+0.2)+' L '+(i+0.2)+','+(j+0.4)+' '+(i+0.8)+','+(j+0.6)+' '+(i+0.2)+','+(j+0.8)+'" stroke-width="0.1" stroke="red" fill="none"></path>';}
if(i==xmax-2 && j==ymax-2){txt+='<path d="M '+(i+0.8)+','+(j+0.4)+' L '+(i+0.5)+','+(j+0.2)+' '+(i+0.2)+','+(j+0.4)+' '+(i+0.2)+','+(j+0.6)+' '+(i+0.5)+','+(j+0.8)+' '+(i+0.8)+','+(j+0.6)+' '+(i+0.8)+','+(j+0.8)+'" stroke-width="0.1" stroke="red" fill="none"></path>';}
}}
txt+='</svg>';
gamen.innerHTML=txt;
}
function dig(xd,yd){
vt=Math.floor(Math.random()*4);
vy=Math.floor( (vt-1)/2);
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++;
}
}
function mz(ax,ay){
if(ax<0 || ax>=xmax || ay<0 || ay>ymax){return 0;}
else{return parseInt(mztxt.substr(ax+ay*xmax,1));}
}
function mzw(ax,ay){
mztxt=mztxt.substr(0,ax+ay*xmax)+'0'+mztxt.substr(ax+ay*xmax+1);
}
// ]]></script>
※2021/5/3 コードに一部不備があったため修正
次の展望「日替わり迷路」
スクリプト中で２か所、Math.random() を使っていますが、これを「日付を基にした疑似乱数」に置き換え、サイズを固定すると「日替わり迷路」になりますね^^
その場合、迷路のサイズはどのぐらいが適切か…もまたちょっと考えるところです。
あと、もちろんブラウザ上で操作できるようにもしたいですね。
ってなとこで、今回はこのへんで！
次回もまた、よろしくお願いします^^
