2011-03-23 4 views
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":[{}] 
    }] 
} 

나는 최상위 보드에서 가능한 동작을 추가하는 방법을 알아낼 수 있습니다,하지만 두 번째 수준에있는 모든 결과 보드를 통해 방법 루프를 알아낼 수 없으며, 가능한 모든 동작을 파악한 다음 모든 세 번째 레벨 보드를 반복합니다. 가능한 움직임을 추가하고 너비 우선 탐색을 사용하여 객체를 트래버스 할 수 있습니까?

+1

여기에서 "재귀"및 "재귀 함수"에 대한 검색을 수행하는 것이 좋으며 일반적으로 웹은 풍부한 정보 여야합니다. – prodigitalson

+0

재귀에 익숙합니까? – climbage

답변

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

두 번째 생각에서 첫 번째 레벨을 처리 한 다음 두 번째 레벨의 첫 번째 보드를 통과하여 처리하고 세 번째 레벨의 첫 번째 보드를 통과하는식이 아닌가? 첫 번째 보드를 처리 한 다음 두 번째 레벨의 보드를 모두 통과 한 후에 세 번째 레벨의 보드를 처리하기를 원합니다. –

+0

오른쪽. 이 경우 대기열을 구현해야합니다. 내가 보여준 것은 깊이 우선 탐색입니다. 폭 넓은 탐색을 원합니다. 알맞은 알고리즘을 보려면 http://en.wikipedia.org/wiki/Breadth-first_search를 확인하십시오. –

+0

확인. 나는 내가 원하는 것을 분명히 알지 못했다고 생각한다. 나는 그 질문을 개정했다. –

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

나는 자바 스크립트에 대한 설명을하지 않아도하지만 난 미개척 노드의 큐를 유지하여 그것을 일반적으로 것입니다.

  1. 큐의 루트 노드로 시작하십시오.
  2. 이 단계로 돌아갑니다이있는 경우 큐의 모든 노드가있는 경우는 큐
  3. 확인의 뒷면에 탐사 중 발견 된 모든 노드를 추가 탐색 큐의 전면에서 항목을 팝업 2
  4. 귀하의 수행

또한 위키 백과 페이지에 일부 pseudopod뿐만 아니라 좀 더 설명 또한 HERE

빠른있다 Google 검색은 목적에 맞게 구부릴 수있는 유사한 알고리즘을 나타냅니다. HERE

관련 문제