4

javascript で再帰的なバックトラッキング迷路生成アルゴリズムを実装しようとしています。これらは、ここでトピックに関する一連の素晴らしい投稿を読んだ後に行われました

アルゴリズムの再帰バージョンは非常に簡単でしたが、同等の反復は私を困惑させました。

概念は理解しているつもりでしたが、私の実装では明らかに間違った結果が得られました。私はそれを引き起こしている可能性のあるバグを突き止めようとしてきましたが、私の問題がロジックの失敗によって引き起こされていると信じ始めていますが、もちろんどこにあるのかわかりません.

反復アルゴリズムの私の理解は次のとおりです。

  • セル状態の表現を保持するスタックが作成されます。

  • 各表現は、その特定のセルの座標と、隣接するセルにアクセスするための方向のリストを保持します。

  • スタックが空でない間、スタックの一番上の方向を繰り返し、隣接するセルをテストします。

  • 有効なセルが見つかった場合は、それをスタックの一番上に置き、そのセルを続行します。

これが私の再帰的な実装です（注：キーダウンしてステップを進めます）：http://jsbin.com/urilan/14

そして、これが私の反復実装です（もう一度、キーダウンして前進します）：http://jsbin.com/eyosij/2

助けてくれてありがとう。

編集：私の質問が明確でない場合はお詫び申し上げます。私の問題をさらに説明しようとします。

反復ソリューションを実行すると、さまざまな予期しない動作が発生します。何よりもまず、アルゴリズムはバックトラックする前に利用可能なすべてのオプションを使い果たすわけではありません。むしろ、有効なセルが 1 つ残っているときに、ランダムにセルを選択しているように見えます。ただし、全体として、動きはランダムではないようです。

var dirs = [ 'N', 'W', 'E', 'S' ];
var XD = { 'N': 0, 'S':0, 'E':1, 'W':-1 };
var YD = { 'N':-1, 'S':1, 'E':0, 'W': 0 };


function genMaze(){

var dirtemp = dirs.slice().slice();    //copies 'dirs' so its not overwritten or altered
var path = [];                         // stores path traveled.

var stack = [[0,0, shuffle(dirtemp)]]; //Stack of instances. Each subarray in 'stacks' represents a cell
                                       //and its current state. That is, its coordinates, and which adjacent cells have been
                                       //checked. Each time it checks an adjacent cell a direction value is popped from 
                                       //from the list

while ( stack.length > 0 ) {

  var current = stack[stack.length-1]; // With each iteration focus is to be placed on the newest cell.

  var x = current[0], y = current[1], d = current[2];
  var sLen = stack.length;             // For testing whether there is a newer cell in the stack than the current.
  path.push([x,y]);                    // Store current coordinates in the path

  while ( d.length > 0 ) {
    if( stack.length != sLen ){ break;}// If there is a newer cell in stack, break and then continue with that cell

    else {
      var cd = d.pop();
      var nx = x + XD[ cd ];
      var ny = y + YD[ cd ];

      if ( nx >= 0 && ny >= 0  && nx < w && ny < h && !cells[nx][ny] ){

        dtemp = dirs.slice().slice();
        cells[nx][ny] = 1;
        stack.push( [ nx, ny, shuffle(dtemp) ] ); //add new cell to the stack with new list of directions.
                                                  // from here the code should break from the loop and start again with this latest addition being considered.


      }
    }

  }

  if (current[2].length === 0){stack.pop(); } //if all available directions have been tested, remove from stack


}
return path;
}

質問の解決に役立つことを願っています。それでも不足している物質がある場合は、お知らせください。

再度、感謝します。

4

2 に答える 2

3

私は JavaScript があまり得意ではありませんが、再帰コードを反復的に実装しようとしています。Forスタックにもインデックスを保存する必要があります。コードは次のようになります。

function genMaze(cx,cy) {

    var dirtemp = dirs;    //copies 'dirs' so its not overwritten
    var path = [];                         // stores path traveled.    
    var stack = [[cx, cy, shuffle(dirtemp), 0]];  // we also need to store `for` indexer

    while (stack.length > 0) {

        var current = stack[stack.length - 1]; // With each iteration focus is to be placed on the newest cell.

        var x = current[0], y = current[1], d = current[2], i = current[3];
        if (i > d.length) {
            stack.pop();
            continue;
        }
        stack[stack.length - 1][3] = i + 1; // for next iteration

        path.push([x, y]);    // Store current coordinates in the path
        cells[x][y] = 1;

        var cd = d[i];
        var nx = x + XD[cd];
        var ny = y + YD[cd];

        if (nx >= 0 && ny >= 0 && nx < w && ny < h && !cells[nx][ny]) {

            dtemp = dirs;
            stack.push([nx, ny, shuffle(dtemp), 0]);
        }
    }
    return path;
  }
于 2011-11-11T07:14:25.500 に答える
0

この小さなコードも役に立ちますか?

/**
Examples
var sum = tco(function(x, y) {
  return y > 0 ? sum(x + 1, y - 1) :
         y < 0 ? sum(x - 1, y + 1) :
        x
})
sum(20, 100000) // => 100020
**/

function tco(f) {
  var value, active = false, accumulated = []
  return function accumulator() {
    accumulated.push(arguments)
    if (!active) {
      active = true
      while (accumulated.length) value = f.apply(this, accumulated.shift())
      active = false
      return value
    }
  }
}

クレジット、説明、詳細情報は github https://gist.github.com/1697037にあります

コードを変更しないという利点があるため、他の状況にも適用できます。それが役立つことを願っています:)

于 2012-03-04T13:14:00.140 に答える