4

パズル ゲームを解くプログラムを作成しています。ボード上で考えられるすべての動きを見つけ、結果として得られるすべてのボードをオブジェクトに配置します。次に、結果のボードで可能なすべての動きを見つけます。オブジェクトは次のようになります。

{
  "board": {
      "starts": [[0,0],[0,3]],
      "blocks": [[3,0],[3,3]],
      "ends":   [[2,4]]
  },
  "possibleMoves": [
    {
      "board": {
        "starts": [[0,0],[2,3]],
        "blocks": [[3,0],[3,3]],
        "ends":   [[2,4]]
      },
      "possibleMoves":[
        {
          "board": {},
          "possibleMoves": [{}]
        }
      ]
    },
    {
      "board": {
        "starts": [[0,3]],
        "blocks": [[3,0],[3,3]],
        "ends":   [[2,4]]
      },
      "possibleMoves":[{}]
    }]
}

トップレベルのボードから可能な動きを追加する方法を理解することはできますが、2 番目のレベルで結果として得られるすべてのボードをループしてそれらの可能性のある動きを把握し、次にすべての 3 番目のレベルのボードをループする方法を理解できません。等々。可能な移動を追加し、幅優先検索を使用してオブジェクトをトラバースするにはどうすればよいですか?

4

3 に答える 3

21

再帰。

function traverse(state) {
    handle(state.board);
    if (state.possibleMoves) {
        $.each(state.possibleMoves, function(i, possibleMove) {
             traverse(possibleMove);
        });
    }
}

編集:幅優先検索の場合は、次のようなものを試してください。再帰を使用しませんが、代わりに成長するキューを反復処理します。

function traverse(state) {
    var queue = [],
        next = state;
    while (next) {
        if (next.possibleMoves) {
            $.each(next.possibleMoves, function(i, possibleMove) {
                queue.push(possibleMove);
            });
        }
        next = queue.shift();
    }
}
于 2011-03-23T20:41:52.257 に答える
2

完全にテストされていない:

var oo = {
    board: {
        starts: [[0,0],[0,3]],
        blocks: [[3,0],[3,3]],
        ends:   [[2,4]]
    },
    possibleMoves: [{
        board: {
            starts: [[0,0],[2,3]],
            blocks: [[3,0],[3,3]],
            ends:   [[2,4]]
        },
    }],
};


function traverseObject (o) {
    for (var prop in o) {
        if (typeof o[prop] == "array" || typeof o[prop] == "object") {
            traverseObject(o[prop]);
            console.log(prop);
        } else {
            console.log(prop, "=", o[prop]);
        }
    }
}

traverseObject(oo);
于 2011-03-23T20:45:41.317 に答える
1

JavaScript の説明はありませんが、一般的には、未調査のノードのキューを保持することで行います。

  1. キュー内のルート ノードのみから開始します。
  2. キューの先頭からアイテムをポップする
  3. 探索中に見つかったすべてのノードをキューの後ろに追加します
  4. ステップ 2 に戻る場合は、キューにノードがあるかどうかを確認します。
  5. あなたの完了

また、ウィキペディアのページに疑似ポッドがいくつかあり、ここにいくつかの説明があり ます

また、Googleで簡単に検索すると、目的に合わせて曲げることができる同様のアルゴリズムが 見つかりましたHERE

于 2011-04-02T07:48:40.547 に答える