(팀 프로젝트) 특수한 스킬을 가진 쥐로 미로의 출구 찾기

소개

• 인원 : 4인
• 담당 : 팀장 및 프로그램 구현
• 팀원 : 팀원1 - 미로 작성, 팀원2 - 보고서 작성, 팀원3 - PPT작성
• 개발 환경 : Visual Studio 2015
• 문제
  • 미로는 .txt파일로 입력된다.
  • 미로의 모양은 사각형이긴 하지만 크기는 임의의 으로 미리 그 크기를 알 순 없고, 미로 내에 있는 1개의 출구의 위치 또한 미리 알 수 없다. 단, 미로의 입구는 (0, 1)이다
  • 미로에서 출구를 찾는 쥐는 최초에 의 에너지와 0의 마나를 지닌다.
  • 쥐는 미로의 상하좌우만 움직일 수 있고, 사선으로 움직일 수 없다.
  • 쥐는 미로를 한 칸 움직일 때마다 에너지를 1 소모하게 되며, 마나를 1 획득하게 된다.
  • 쥐는 10의 마나를 소모해서 임의의 만큼 미로를 스캔할 수 있고, 30의 마나를 소모해서 벽 한 칸을 뚫을 수 있다. 단, 외벽은 파괴할 수 없다.
• 소스코드 : 특수한 스킬을 가진 쥐로 미로의 출구 찾기

내용

알고리즘 설계

• 탐욕적 알고리즘을 적용한다.
  (현재 위치로부터 가상의 목적지까지 가장 거리가 짧은 방향으로 이동한다.)
• 쥐는 지금까지의 이동경로를 모두 기억하고 있다.
• 쥐가 스캔을 통해 목적지를 찾았을 경우, 목적지 주변 일정한 부분을 스캔으로 탐색합니다.
• 쥐는 막다른 길에 도달했거나 스캔을 통해 목적지를 찾았을 경우, 자신이 기억하고 있는 경로를 통해 목적지로 향하는 최단(최적)경로를 찾아간다.
• 목적지를 스캔을 통해 찾았을 경우, 그 주변으로 스캔 범위를 넓혀간다.
• 현재 쥐의 위치부터 목적지까지의 경로 중, 스캔을 통해 찾아낸 경로나 쥐가 이동을 통해 찾아낸 가장 짧은 경로로 이동한다.
• 마나가 30이상이며 스캔을 통해 출구를 찾았으며, 최적의 경로로 출구를 향해 이동중일 때 벽을 만났는데 마나가 4 이상인 경우, 진행방향으로 스캔을 뿌려보고 벽이 1칸 있으면 그 벽을 뚫고 지나간다.
  

어려웠던 점

일반적인 미로찾기가 아니라 마나와 스킬을 가진 미로찾기여서 어떻게 알고리즘을 구현하는 것이 효율적일지 생각하는 것이 가장 어려웠습니다. 그래서 평균적으로 확률을 높이는 것이 가장 좋은 방법이라고 생각해서 위와 같은 알고리즘으로 구현하게 되었습니다.

배운 점

평소에는 콘솔 기반의 프로그램을 위주로 만들었지만, 이번에는 GUI를 이용해서 프로그램을 만들었습니다. 그렇다보니 그림의 배치나 색 등 여러가지 고려할 부분이 늘어나서 처음에는 생각보다 잘 안되었지만, 이런 부분을 해결해나가는 과정에서 자료 검색 능력이나 문제를 해결하는 센스가 더욱 늘어났습니다.