막 다른 길을 걸었을 때 프로그래밍 방식으로 미로를 통과하는 방법

Question

앞으로 미로를 통해 이동하는 것은 매우 쉽지만 일단 미로를 통과하면 미로를 통해 백업하는 방법을 알아낼 수 없습니다. 너무 멀리 돌아 가지 않고 막 다른 골목에?

Answer 1

이전 방향 결정의 스택을 유지하여 backtracking을 사용하십시오.

Answer 2

알고리즘을 구현하는 가장 간단한 방법은 역 추적을 통해 정보를 얻을 수없는 경우가 아니라면 지금까지 있었던 위치의 스택과 각 경로에서 가져온 경로를 유지하는 것입니다.

돌아가려면 스택에서 이전 위치를 튕겨 내고 테스트되지 않은 이탈이있는 이전 위치를 찾을 때까지 그 위치에서 더 많은 이탈을 확인하십시오.

매번 같은 순서로 출구를 일관되게 테스트하면 위치로의 역 추적이 내려간 경우 (즉, 이전 위치에서 마지막으로 내려간 경우) 다음 방향을 선택하기 만하면됩니다 아래로입니다.

나는 이 너무 멀리 돌아가는 것을 완전히 모르겠다.하지만 이전에 테스트하지 않은 경로가있는 곳으로 돌아가고 싶다고 생각 하겠지만, 원하는 것이 아니겠습니까?

출발점에서 현재 위치까지의 경로를 추적하려고 시도하지 않고 새로운 경로를 찾으려고 할 때 그 사각형을 피하지 않으면 서클로 돌아가 결국 결국 스택을 만들 수 있습니다 너무 큰.

경로를 표시하고 표시된 영역을 입력하지 않는 간단한 재귀 적 방법은 쉽게이 작업을 수행 할 수 있습니다.

미로를 통과하는 물체이 움직일 수있는 것보다 약간 똑똑하고 벽을 때리면 (벽에서 멈추는) 모든 방향에서 현재 지점에서 볼 수 있기 때문에 다른 알고리즘이 도움이 될 수 있습니다.

Answer 3

에릭 리 퍼트 (Eric Lippert)는 C# implemention of A*을 만드는 일련의 기사를 작성했는데, 이는 더 효율적일 수 있습니다.