Ширина первого обхода объекта

Question

Я делаю программу, которая решает игру-головоломку, и она находит все возможные ходы на доске и помещает все возможные получившиеся доски в объект.Затем он находит все возможные ходы для полученных досок и так далее.Объект будет выглядеть примерно так:

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

Я могу понять, как добавить возможные ходы с доски верхнего уровня, но я не могу понять, как перебрать все получившиеся доски во второйвыровняйте и выясните их возможные ходы, а затем переберите все доски третьего уровня и так далее.Как я могу добавить возможные ходы и пройти объект, используя поиск в ширину?

Answer 1

Рекурсия.

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();
    }
}

Answer 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);

Answer 3

У меня нет описания JavaScript, но я обычно делал бы это, сохраняя очередь неисследованных узлов.

1. Начинайте только с корневого узла в очереди.
2. Извлечь элемент из начала очереди
3. Изучить его и добавить все узлы, найденные в ходе исследования, в конец очереди
4. Проверить, есть ли какие-либо узлы вочередь, если есть, вернитесь к шагу 2
5. Готово

Также на странице Википедии есть несколько псевдоподов, а также некоторые другие объяснения ЗДЕСЬ

Кроме того, быстрый поиск в Google обнаружил похожий алгоритм, который можно было бы использовать для вашей цели ЗДЕСЬ