농부가 대체 되었다 - 트레모(tremoux) 알고리즘을 사용해서 미로 공략 (코드 포함)
(16x16 시현 영상과 코드는 맨 아래 있어요)
미로를 해금하고 덤불에다가 비료를 주면 NxN 사이즈의 미로를 만들 수 있다.
생성된 미로는 여러가지의 조건이 있다
미로의 한 칸은 xy 좌표로 표현된다
미로를 시작하는 드론은 무조건 왼쪽 맨 아래의 꼭짓점에서 시작한다.
-> 그러니까 (0,0) 위치에서 3크기 만큼의 미로를 만들면 (0,0)에서 (2,2)까지 대각선으로 미로가 생성된다
미로와 보물은 썸네일 처럼 생성할 때마다 랜덤으로 생성된다
드론은 보물의 위치를 모른다.
길을 잘못 들었을 때 다시 원래의 길로 돌아 가야한다.
여러 목적지 찾기 알고리즘을 찾아 봤을 때, DFS(깊이우선탐색), BFS(넓이우선탐색), Flood-fill, A-star 같은 알고리즘이 추천된다.
그중 Flood-fill, A-star는 미로에서 목표를 찾는 마이크로 마우스 대회에서 자주 사용되며,
Flood-fill 알고리즘이 가장 빠르며, 대회에서 항상 우승을 한다고 한다.
하지만 이 세 가지 알고리즘은 이 게임에서 사용할 수 없다.
왜냐하면 마이크로 마우스 대회에서는 목표의 위치를 대략적으로 알려준다.
세 개의 알고리즘은 목표를 알아야만 활용이 가능하거나, 목표를 알아야만 효율이 올라간다.
그래서 "3. 드론은 보물의 위치를 모른다"라는 조건이 있기 때문에 사실상 사용할 수 없는 알고리즘이다.
그러면 DFS나, BFS를 활용해서 구현할 수 있지만, 치명적인 효율 문제가 있다. 이 게임의 드론은 갈림길에서 뻗어 나간뒤에 그 갈래가 시작되는 지점을 순간이동 해서 돌아올 수 없다.
그래서 DFS던, BFS던 다시 갈래가 시작되는 지점까지 이동 해야 한다는 것이다.
하지만 보물의 위치를 모르기 때문에 우리는 어쩔 수 없이 왔던 길을 돌아와야 하는 비용을 감당해야 한다.
이 돌아오는 비용을 줄이는 방법 중 하나가 바로, DFS를 개선한 트레모(tremoux) 알고리즘이다
DFS와 트레모 알고리즘의 차이는 DFS는 왔던 길에 대해 표시를 하지 않는 것이고,
트레모 알고리즘은 지나간 길에 표시를 한다는 것이다.
헨젤과 그레텔로 표현하면 지나간 길에 빵 조각이 떨어져 있는 것과 같다.
트레모는 지나온 셀과 도착한 셀을 간선으로 정의하고 표시한다.
트레모 알고리즘에는 지켜야 할 규칙이 있다.
(0,0) -> (1,0)으로 이동 했다면, (0,0)-(1,0) 간선이 생겨나야 한다.
-> 간선은 방향성을 고려하지 않는다. (0,0)-(1,0)-(0,0)으로 이동 했다고 해서 (0,0)-(1,0), (1,0)-(0,0) 두 개의 간선이 생기지 않는다는 말이다.
셀과 셀끼리 이동 했다면 해당 간선에 표시를 해야 한다.
-> (0,0) -> (1,0)로 이동 했다면, (0,0)-(1,0) 간선의 값은 1이 된다.
-> (0,0) -> (1,0) -> (0,0)로 이동 했다면, (0,0)-(1,0) 간선은 값은 2가 된다.
간선의 표시 값의 대한 구분은 다음과 같다.
0은 아직 지나가지 않은 간선
1은 한번 지나간 간선
2는 두 번 지나간 간선 그리고 해당 간선으로는 출입 금지.
우리는 미로의 특징과 트레모 알고리즘의 규칙을 통해 코드 로직을 만들 수 있다.
대략 다음과 같다.
갈 수 있는 길을 탐색 (동서남북 중 하나)
현재 드론의 좌표와 갈 수 있는 길의 좌표 파악
간선이 없다면 생성, 간선의 표시는 0으로
만약 길이 2개 이상이라면 간선의 표시가 0인 길을 우선으로 탐색, 표시가 2라면 아예 출입 금지
이동
이동 후, 이동 전 좌표와 이동한 좌표의 해당하는 간선의 표시 더하기
이제 해당 로직이 인게임에서 어떻게 작동하는지 스크린샷을 통해 알아보자.
처음 드론은 동서남북으로 위치를 파악하여 이동할 수 있는 길을 파악한다.
이때 (1,0), (0,1)의 우선 순위는 directions 배열이 동 쪽을 먼저 가리킴으로 (1,0)으로 먼저 이동 계획을 잡는다.
그리고 { (0,0),(1,0) : 0 } 간선을 생성하게 된다.
이동 계획대로 (0,0) -> (1,0)으로 이동하면
(0,0) - (1,0) 간선의 표시는 1로 업데이트 된다.
이후 다시 한 사이클을 돌아서 동서남북으로 위치를 파악하여 이동 계획을 잡는다.
이동 계획대로 (1,0) -> (0,0)으로 이동하면
(0,0) - (1,0) 간선의 표시는 2로 업데이트 된다.
이제 한 사이클이 돌고, 드론은 동서남북으로 위치를 파악하여 이동 계획을 잡는데,
현재 이동 가능한 좌표는 (1,0) 와(0,1)이다
하지만 (0,0) -> (1,0) 이동 계획에 대해서 검토하지만 해당 간선의 표시가 2라서 되어 스킵하고,
(0,0) -> (0,1)의 대한 간선 { (0,0),(0,1) : 0 }을 생성한다.
그리고 이동 계획에 (0,1)으로 가는 계획이 추가 된다.
따라서 트레모 규칙 3에 "두 번 지나간 간선 그리고 해당 간선으로는 출입 금지"를 충족 하는 것이다.
만약 갈림길이 3개 이상인 경우는 어떻게 작동할까 ?
역시 인게임 스크린샷을 통해 알아보자.
만약 드론이 (2,1)까지 이동 했다고 가정 했을 때,
이동 계획시 서(1,1), 북(2,2), 남(2,0)을 갈 수 있다.
하지만 (1,1), (2,1) 간선의 표시는 1이므로,
간선의 표시가 0인 북쪽이나 남쪽으로 이동 계획을 잡게 된다.
즉, DFS(깊이 우선 탐색)의 특성을 따르게 된다.
영상 16x16 시현.
코드
https://github.com/hirosh788/farmer
던진 픽셀들
실시간으로 던진 픽셀들
아직 댓글이 없습니다
첫 번째 댓글을 작성해보세요!
