广度首先遍历对象

问题描述

我正在制作一个解决益智游戏的程序，它会在棋盘上找到所有可能的移动并将所有可能产生的棋盘放在一个对象中。然后它会找到所得到的电路板的所有可能移动，依此类推。该对象看起来像这样：

I am making a program that solves a puzzle game, and it finds all the possible moves on a board and puts all the possible resulting boards in an object. Then it finds all the possible moves for the resulting boards, and so on. The object will look something like this:

{
  "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":[{}]
    }]
}

我可以弄清楚如何从顶层板添加可能的移动，但我无法弄清楚如何遍历所有在第二级产生的板，并找出他们可能的移动，然后循环所有第三列el board等。如何使用广度优先搜索添加可能的移动并遍历对象？

I can figure out how to add the possible moves from the top-level board, but I cannot figure out how to loop through all the resulting boards in the second level and figure out their possible moves, and then loop through all the third level boards and so on. How can I add the possible moves and traverse the object using a breadth-first search?

推荐答案

递归。

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

编辑：对于广度优先搜索，尝试这样的事情。它不使用递归，而是遍历不断增长的队列。

For a breadth-first search, try something like this. It doesn't use recursion, but instead iterates over a growing queue.

function traverse(state) {
    var queue = [],
        next = state;
    while (next) {
        if (next.possibleMoves) {
            $.each(next.possibleMoves, function(i, possibleMove) {
                queue.push(possibleMove);
            });
        }
        next = queue.shift();
    }
}

这篇关于广度首先遍历对象的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！