최근 집에만 있는데 다른 친구들은 다 놀이공원 놀러 가길래 나도 놀이공원이 가고 싶어졌다.
그런데 시간도 안 되고, 사정상 가기는 힘들어서 대신 놀이공원 길 찾기 프로그램을 만들고자 한다.
계획
우선 이미 있는 놀이공원 길 찾기를 찾아봤는데 네이버 지도가 이미 에버랜드 길 찾기를 지원하더라. 그래서 나는 롯데월드 길 찾기 프로그램을 만들 것이다.
어떤 플랫폼 기반으로 만들까? 아무래도 모바일 기반으로 만들어야 할 것이다. 모바일 기반이면 네이티브 앱을 만들 수도 있고, 웹 기반으로 만들수도 있다. 프로젝트를 크게 끌고 갈 생각은 없어서 익숙한 웹 기반으로 만들어보자.
개발환경 셋업
사실 할 건 없다. Visual Studio Code, NodeJS는 이미 깔아놨다.
작업 폴더를 만들고, npm init으로 작업환경을 구축했다.
그리고 GitHub 레포지토리까지 만들었다.
그리고 서버사이드 코드는 옛날에 만들어놓은거 복사 붙여넣기하고, 조금만 손봐서 마무리했다.
데이터 수집
일단 롯데월드 지도가 필요하다.
롯데월드 공식 홈페이지에서 가이드맵을 다운받아서 pdf를 이미지 파일로 변환하고, 필요한 부분만 잘라내서 얻었다.
이제 이 지도 위에 길을 표시할 것이다.
Waypoint 시스템 구축
이제 지도의 길 위에 waypoint를 찍을 것이다. waypoint는 내가 지도 위에서 있을 수 있는 점을 의미하며, 2차원 평면 위의 좌표들로 표현된다. 지도의 길 위에 waypoint들을 찍어주면 컴퓨터는 그곳이 길인 줄 알 것이다.
그런데 여기서 생각할 점이 지도의 크기가 고정되어있지 않다는 점이다. 여러 화면 크기의 디바이스에 대응하려면 지도크기를 유연하게 늘였다 줄일 수 있어야 하는데, 이는 즉 지도가 일정한 크기를 가지지 않을 수 있다는 것이다.
따라서 waypoint의 좌표를 화면에서 찍힌 좌표 그대로 저장하고 불러오면 내가 waypoint를 찍는 데 사용했던 바로 그 화면 크기에서만 waypoint가 제대로 보일 것이다. 만일 그렇지 않다면? waypoint와 지도의 길이 어긋나서 보일 것이다.
따라서 waypoint가 화면 크기 변화에 유연하게 대응하여 찍힐 수 있게 해야 한다.
이 문제를 해결하기 위해 우선 지도의 가로:세로 비율(aspect ratio)을 13:9로 고정하고, 모든 waypoint가 실제 화면 크기와는 상관없이 1300x900 크기의 지도 위에 있다고 가정했다. 이렇게 해면 일단 waypoint의 위치를 절대적인 값으로 저장할 수 있다.
이제 화면상의 좌표와 1300x900에서의 좌표를 마음껏 바꿀 수 있으면 된다. 이는 다음 비례식을 통해 할 수 있다.
$r_x:s_x=a_x:1300$
$s_x$는 화면의 실제 크기, $r_x$는 실제 화면에서의 입력 x 좌표, $a_x$가 고정된 x 좌표이다.
따라서 사용자가 입력한 x 좌표를 고정시키기 위해 다음 식을 통과시킨다.
$a_x=\mathrm{ROUND}\left(1300r_x/s_x\right)$
여기서 ROUND 함수는 반올림 함수이다. 나눗셈을 하면 소수 뒤로 길게 나올 수도 있는데 이런 것은 실제 화면에서 기껏해야 1px의 오차 정도이기 때문에 무시할 수 있다. 따라서 정수만 취해도 문제가 없다.
이제 사용자가 화면 위의 지점을 마우스로 찍으면 → 사용자 화면에서 지점의 좌표를 얻고 → 1300x900의 크기 위에 있도록 고정한 후 → 정수점으로 저장하면 waypoint를 저장할 수 있다. 물론 이 과정을 역순으로 진행하면 불러올 수도 있다.
이제 테스트용으로 지하 1층의 지도 위에 waypoint들을 찍어보자. 물론 이 과정은 매우 고달프기 때문에 이 과정을 도와주는 여러 기능을 같이 제작해준다.
지도 위에 svg 태그를 올려서 지도 위에 그림을 덧그릴 수 있게 했다. 그리고 여기에 마우스 이벤트 리스너를 등록해서 지도 위를 마우스로 클릭하면 그곳에 waypoint가 생성되도록 했다. 그렇게 길 위에 총 142개의 waypoint들을 찍었다.
길 완성하기
waypoint를 활용해서 어디가 갈 수 있고, 어디가 갈 수 없는 지점인지 컴퓨터에게 알려줬다. 하지만 아직 컴퓨터는 길을 모른다. 어떤 waypoint에서 다른 어떤 waypoint로 이동할 수 있는지 길을 안 알려줬기 때문이다. 따라서 각 waypoint들의 연결 정보를 포함하는 link 데이터를 만들어야 한다.
link 데이터는 각 waypoint마다 가지는 리스트로 자신과 연결되어있는, 즉 자기로부터 이동할 수 있는 waypoint들의 목록이 주어져 있다. 이때 연결은 반드시 쌍방이어야 한다. 예를 들어 waypoint A와 B가 연결되어 있으면 waypoint A의 link와 B의 link는 둘 다 서로를 가지고 있어야 한다. A만 B를 가지고 B는 A를 가지지 않는 경우, 물론 그럴 수도 있지만(일방통행인 경우) 롯데월드에 그런 길은 없다.
이제 142개의 waypoint들의 링크를 만들어서 서로서로 길로 연결해준다(참고로 위 그림은 waypoint를 찍고, 링크된 waypoint끼리 선을 이은 것이다. waypoint만 시각화하면 선 없이 길 위에 점들만 놓인다).
Waypoint와 Link 데이터 검증
나는 이런 걸 할 때면 어딘가 실수해서 데이터가 잘못 들어가지 않았을까 걱정된다. 그래서 Waypoint와 Link 데이터가 잘 입력되었는지 검증하는 기능이 있어야 한다.
"Check link error" 버튼을 누르면 자동으로 모든 waypoint의 링크 정보를 보고, 링크가 쌍방인지, 혹시 자기 자신을 링크하지는 않았는지 등을 검사해서 무언가 오류가 감지되면 알려줘서 수정할 수 있게 해 준다.
가장 가까운 waypoint 찾기
이제 조금 다른 결의 것을 만들어야 한다. 지도 위의 waypoint의 위치는 제한되어 있지만, 사용자는 어디든 있을 수 있다. 따라서 사용자가 원하는 위치를 찍었을 때 그곳에서 가장 가까운 waypoint를 찾아 그곳부터 길 찾기를 시작해야 한다.
이는 그리 어렵지 않게 구현할 수 있다. 평면 좌표에서 두 점의 거리는 다음 방법으로 구한다.
$d=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$
여기서도 같은 방법을 이용한다. 다만 정확한 거리가 아닌, 비교면 족하기 때문에 굳이 제곱근을 씌우지 않고 $d^2$의 값을 비교해서 가장 작은 waypoint의 번호를 알아내면 된다.
길 찾기
앞선 과정, 즉 waypoint를 찍고 link를 연결하는 과정은 모두 롯데월드에서 길 찾기 문제를 그래프에서 길 찾기 문제로 대응시키기 위함이다. 예를 들어 "정문에서 와일드 윙까지의 길을 찾으라"는 명령은 "노드 2번에서 노드 113번까지 최단경로를 찾으라"는 명령과 같다.
즉, 이제 롯데월드에서 길을 찾는 대신 노드 142개 있는 그래프에서 길을 찾는 문제와 같다.
그래프에서 경로를 찾는 알고리즘 하면 3가지가 떠오른다.
DFS, BFS, Dijkstra
우선 DFS는 가장 먼저 탈락했다. 최단거리를 찾아야 하는 특성상 탐색을 무조건 끝까지 해야 하는데, 이게 waypoint가 많아질수록 공간 효율, 시간효율이 떨어진다. 한마디로 단순 길을 찾는데 유용한 DFS는 최단경로를 찾고자 하는 지금의 필요에는 적합하지 못하다.
그리고 BFS와 Dijkstra 중에 고민했는데 결국 Dijikstra를 선택했다. 이유는 BFS는 가중치를 고려하기 힘들기 때문이다. 물론 할 수는 있는데 귀찮다. 그리고 결국 길 찾기 알고리즘 중 최고는 Dijkstra이다.
한번 Dijkstra가 어떻게 작동하는지 알아보자.
맨 위의 0번 노드에서 2번 노드까지 가는 길 중 최단경로는 무엇일까?
우선 노드 개수만큼 배열을 만든다. 그리고 시작점의 거리는 0으로 한다. 나머지는 INF(무한)으로 대입한다(물론 진짜 무한을 대입하지는 않고 적당히 큰 수를 대입한다).
| 노드 번호 | 0 | 1 | 2 | 3 |
| 거리 | 0 | INF | INF | INF |
이제 인접한 노드들의 거리를 업데이트해준다.
| 노드 번호 | 0 | 1 | 2 | 3 |
| 거리 | 0 | 2 | 5 | 1 |
이제 업데이트가 진행된 노드들 중 거리가 짧은 노드부터 아래 과정을 반복한다.
3번 노드의 거리가 가장 짧으니 이제 3번 노드에서 인접한 노드의 거리를 업데이트한다. 이때 3번 노드의 거리에 가중치를 더한다.
이때, 무조건 업데이트하는 것이 아니라 기존 최단거리와 비교해서 새 방법의 거리가 더 짧은 경우 업데이트한다. 즉, 항상 거리에는 그때까지 발견된 최단거리가 들어간다.
| 노드 번호 | 0 | 1 | 2 | 3 |
| 거리 | 0 | 2 | 5 | 1 |
3번에서 2번으로 가는 경로는 거리가 5이고, 이는 기존 방법보다 짧지 않으므로 업데이트하지 않는다.
이제 1번에서 과정을 반복한다.
| 노드 번호 | 0 | 1 | 2 | 3 |
| 거리 | 0 | 2 | 4 | 1 |
0에서 1을 거쳐 2로 가는 경로의 거리는 4이고, 이는 기존 경로보다 짧으므로 업데이트한다.
이제 더이상 가능한 노드가 없으므로 알고리즘은 끝나고, 2까지의 최단경로는 4가 된다.
롯데월드에서 길을 찾는 문제는 이 문제가 확장된 버전이다. 노드가 4개가 아닌 수백개인 그래프에서 길을 찾는 것이다.
이상의 방법으로 롯데월드에서 길을 찾는 프로그램을 만들었다. 물론 아직 끝난건 아니고, 층을 옮기면서 이동해야 하는 경우가 있을 수 있기 때문에 이것도 고려해야 하지만, 이정도 베이스를 만들어놓으면 그 뒤로는 쉬울듯 하다.
Github 레포지토리는 여기이다.
'이것저것' 카테고리의 다른 글
| SSMT PRIME 1차 (0) | 2022.03.26 |
|---|---|
| 영재학교 모의고사 1 - SSMT (0) | 2021.09.28 |