JavaScriptの迷路のソルバーアルゴリズム

Question

HTML

<div id="labirinth"> 
    <form style="text-align:center" name="forma1" autocomplete="on"> 
     <table style="margin:0 auto;"> 
      <tr> 
       <td style="float:right;">Height:</td> 
       <td><input type="text" id="height" name="height" autofocus="autofocus" maxlength="2" size="6" /></td> 
      </tr> 
      <tr> 
       <td style="float:right;">Width:</td> 
       <td><input type="text" id="width" name="width" maxlength="2" size="6" /></td> 
      </tr> 
     </table> 
    </form> 
    <input type="button" alt="submit" onClick="datas();" value="New" style="margin-top:10px;" /> 
</div> 
<pre id="out"></pre> 

はJavaScript

function datas() { 

    var height = parseInt(document.getElementById("height").value); 
    var width = parseInt(document.getElementById("width").value); 

    document.getElementById('out').innerHTML = display(maze(height,width)); 
} 

function maze(x,y) { 
    var n=x*y-1; 
    if (n<0) {alert("Bad numbers!");return;} 
    var horiz=[]; 
     for (var j= 0; j<x+1; j++) horiz[j]= []; 
    var verti=[]; 
     for (var j= 0; j<y+1; j++) verti[j]= []; 

    var here= [Math.floor(Math.random()*x), Math.floor(Math.random()*y)]; 
    var path= [here]; 
    var unvisited= []; 
    for (var j= 0; j<x+2; j++) { 
     unvisited[j]= []; 
     for (var k= 0; k<y+1; k++) 
      unvisited[j].push(j>0 && j<x+1 && k>0 && (j != here[0]+1 || k != here[1]+1)); 
    } 
    while (0<n) { 
     var potential= [[here[0]+1, here[1]], [here[0],here[1]+1], 
      [here[0]-1, here[1]], [here[0],here[1]-1]]; 
     var neighbors= []; 
     for (var j= 0; j < 4; j++) 
      if (unvisited[potential[j][0]+1][potential[j][1]+1]) 
       neighbors.push(potential[j]); 
     if (neighbors.length) { 
      n= n-1; 
      next= neighbors[Math.floor(Math.random()*neighbors.length)]; 
      unvisited[next[0]+1][next[1]+1]= false; 
      if (next[0] == here[0]) 
       horiz[next[0]][(next[1]+here[1]-1)/2]= true; 
      else 
       verti[(next[0]+here[0]-1)/2][next[1]]= true; 
      path.push(here= next); 
     } else 
      here= path.pop(); 
    } 
    return ({x: x, y: y, horiz: horiz, verti: verti}); 
} 

function display(m) { 
    var text= []; 
    for (var j= 0; j<m.x*2+1; j++) { 
     var line= []; 
     if (0 == j%2) 
      for (var k=0; k<m.y*4+1; k++) 
       if (0 == k%4) 
        line[k]= 'X'; 
       else 
        if (j>0 && m.verti[j/2-1][Math.floor(k/4)]) 
         line[k]= ' '; 
        else 
         line[k]= 'X'; 
     else 
      for (var k=0; k<m.y*4+1; k++) 
       if (0 == k%4) 
        if (k>0 && m.horiz[(j-1)/2][k/4-1]) 
         line[k]= ' '; 
        else 
         line[k]= 'X'; 
       else 
        line[k]= ' '; 
     if (0 == j) line[1]=line[3]=' ',line[2]= '1'; 
     if (m.x*2-1 == j) line[4*m.y]= '2'; 
     text.push(line.join('')+'\r\n'); 

    } 
    return text.join(''); 
} 

私は、HTMLの表のセルを使用せずにJavaScriptで完全に動作する迷路ジェネレータを作成しようとしています。今私はこの迷路の作成ソルバーに問題があります。

質問：私のコードにはどの迷路解決アルゴリズムを使用する必要がありますか？私はどうしたらいいですか？私はアルゴリズム全体を必要としません - 私はこの迷路ジェネレータに迷路ソルバを持つことが可能かどうかについてアドバイスが必要です。

JSbin - あなたが生成している迷路のために働く必要がありソルバのhttp://jsbin.com/uwoyon/1

Answer 1

私の推薦は、ダイクストラ法だろう。 horizとvertiのパラメータがどのように迷路構造を定義しているのか分かりませんが、Dijkstraのアルゴリズムは、 '1'の隣のセルから始め、そこから構築することであなたの状況で動作します。

どのように動作するかは、各セルにそのセルと開始セルの間のセル数を付けることです。空の隣接セル（壁によってブロックされていないもの）がある場合、標識された細胞の検査から作業

x 1 xxxxxxxxx 
x 1   x 
x xxxxxxxxx 
x   x 
x xxxxxxxxx 
x   2 
xxxxxxxxxxxxx 

を1繰り返しこのプロセスのことでセルの値をインクリメント：3x3のための最初のセルは次のようになり迷路すべての空のセル：

x 1 xxxxxxxxx 
x 1 2 3 x 
x xxxxxxxxx 
x 2 3 4 x 
x xxxxxxxxx 
x 3 4 5 2 
xxxxxxxxxxxxx 

ここで、末尾 '2'に隣接するセルから逆方向に作業します。これは、ソリューションが長さ5ステップのパスを持っていることを示しているので、5で始まり、隣接する4を見つけ、次に3などを1に戻します。

注：キューにラベルを付けるためのキューを使用することをお勧めします：

1最初のセルに「1」とラベル付けし、キューに入れます。

2キューからセルを取り出します。 - 正当なネイバー（壁によってブロックされていないもの）のラベルが付けられていないかどうかを確認します。 - 隣接セルのラベルが付けられていない場合は、現在のセル+1でラベル付けします。 - 隣接セルをキューに追加します。 - すべての潜在的な4つのネイバに対して繰り返します。

3-ステップ1と2を繰り返して、ラベルの付いていないセルがなくなるまで繰り返します。

EDITは：聞かない限り、私はそれがどのように動作するかについての詳細には触れませんので、ここで私が提案ものを使用してソルバーのためfiddleをだ、それが問題の迷路発生器に関係しない（それは少しですラフですが、その実装は十分に簡単に行う必要があります）。

Answer 2

完全な迷路（任意の2つのセル間に1つのパスのみ）の場合は、再帰的な壁フォロワが必要です。最初のセルから始め、周りのセルを指定された順序で、通常時計回りまたは反時計回りにチェックします。セルを入力できる場合は入力します。それが終わったら、あなたは完了です。そうでない場合、再発する。他の3つのパスをすべてチェックしても終了しない場合は、単に戻ってきます。最後に到達すると、コールスタックに解決策があります:)私が通常行うことは、「これは解決策が見つからなかった」または「これが解決策です」の「真」を返すことです。

あなたは、私はgithubの上で私の迷路アルゴリズムで解決方法を見ることができます。

https://github.com/mdchaney/jsmaze

あなたはjsmaze2.html機能を見れば、「find_depth」が実際にソルバーです。

jsmaze4.htmlは非常に複雑ですが、実際には再帰アルゴリズムで迷路を構築している間にソリューションを構築します。これは、ビルディング中にセルが「入力」されたときにどの壁がノックダウンされたかを追跡することによってこれを行います。他のアルゴリズムがあるので、迷路の入り口壁を設定する "find_depth"も含まれています。

これで十分です。

Answer 3

非再帰的な方法はあなたのために迷路を解決します。再帰（バックトラッキング・アルゴ）により、あなたはあなたの運を乗ることができます。

はこのドキュメントを参照してください： - http://cs.stanford.edu/people/eroberts/courses/cs106b/chapters/07-backtracking-algorithms.pdf

この質問は週末まで営業となります。私はコード化された答えを投稿します。

ありがとうございました