알고리즘:Recursive Backtracking

미로를 생성하는 알고리즘 중 가장 간편해 보이는 Recursive Backtracking 알고리즘.

Recursive Backtracking 알고리즘의 동작은 아래와 같습니다. (내가 보기에는...)

1. 무작위로 한 곳을 선택합니다.

2. 선택된 위치에서, 인접한 곳(상,하,좌,우)을 랜덤하게 탐색합니다.

3. 탐색한 곳의 벽이 전부 막혔다면 뚫고 그 장소로 이동합니다.

4. 인접한 곳에 이동할 곳이 없다면, 이전 위치로 돌아 갑니다.

5. 위 내용을 반복하여 모든 장소를 방문하면 미로가 완성 됩니다.

예)

개발은 MFC 환경에서 그리드를 이용했습니다.(후회 중...)

그리드 연결 및 표 생성은 생략하며, 알고리즘의 주요 부분만 포스팅

 

소스코드

1. 미로를 생성하기 위해 BackTracking() 함수를 작성하였습니다.

   - 함수 내부를 보면, 두 가지 함수를 호출하며, 기능은 아래와 같습니다.

   - CellRandSelect() : 무작위로 처음 위치를 선정(알고리즘 동작 1번)

   - MazeProcess() : 미로를 생성하며, 재귀 호출됩니다.

    

2. CellRandSelect() 함수

   - 처음 시작 위치를 랜덤하게 설정합니다.

         

3. MazeProcess() 함수

- 실질적인 미로 생성 함수로 내부에서 CellSearch, MoveTOMerge, PreviousCell 함수가 호출됩니다.

- CellSearch는 인접한 장소의 위치를 탐색하는 함수입니다.

- 탐색 결과가 True 인 경우 MoveToMerge 함수를 통해 벽을 허물고(셀 병합), 이동합니다.

- 탐색 결과가 False 인 경우 PreviousCell 함수를 호출하여, 이전 장소로 이동합니다.

- 이동할 장소가 없으면 미로가 완성된 것으로 판단합니다.

 

4. 위치 탐색 함수 CellSearch()

  - CellSearch함수는 우선 랜덤하게 탐색방향을 선정합니다.

  - 그 후 탐색 장소의 벽이 전부 막혀 있는 경우, 그 곳을 선택하고 True를 반환합니다.

  

  가. 랜덤위치 선정 방식

       - 벡터(4)를 생성 후 그 공간에 0~3 까지 순서되로 채웁니다.

       - 그 후 셔플 함수를 이용해 벡터의 내용을 섞은 후, 그 순서를 통해 방향을 선정했습니다.

   

 

  나. 선정된 위치 탐색 가능여부 확인

     - 탐색 방향이 선정되면 그 방향이 외벽이 아니거나, 이전 진행방향이 아닌 경우 탐색합니다.

   다. 선정된 위치를 탐색

      - 탐색이 가능한 위치인 경우, 사방이 막혔는지 탐색하고 막혔으면 TRUE를 리턴합니다.

      - 벽의 경우 미로크기의 N*N의 벡터 생성 후 값과 1:1 맵핑시켜 확인합니다.

      - 사방이 막힌 장소는 1, 벽을 허물었던(합병) 장소의 경우 0으로 셋팅했습니다.

      - 또한 탐색 장소가 진행방향으로 확정되면, 스택에 값을 저장합니다.

     

  

    라. 4 방향 모두 조건에 해당되지 않으면 False 를 리턴합니다.

5. MoveToMerge 함수

   - CellSearch() 함수가 True를 반환한 경우 호출되며, 탐색방향으로 벽을 뚫고, 이동합니다.

   - 이동 전 스택에 위치 값을 저장하며, 이동 후 MazeProcess 함수를 다시 호출합니다.

      

6. PreviousCell 함수

  - CellSearch 함수가 False를 리턴한 경우, 현재 위치에서 미로 확장이 가능한 장소가 없으므로 이전 위치로 

돌아갑니다.

  - 이동 좌표는 스택에 저장되어 있습니다.

  - 스택에 자료가 없는 경우, 미로 완성을 의미하기에 리턴합니다.

   

결과

   - 빨간 색은 최초 Start 지점이다.