Pathfinding Algorithm Visualizer 구현 후기
배경
회사 업무 관련해서 길 찾기 알고리즘인 JPS에 대한 이해가 필요해서 만들어보게 되었다.
길 찾기 알고리즘을 구현해보고 싶었는데 이를 시각화할 툴도 필요했기 때문이다.
작업하면서 많이 헤매기도 하고, 초반에 잘못 설계해서 중반을 넘어가면서 고생도 했어서 작업 내용을 기록으로 남기려고 한다.
목표
- 맵 편집 기능 구현
- A*, JPS 길 찾기 알고리즘 구현
- 길 찾기 결과 시각화 기능 구현
기본 동작 방식은 길찾기 시각화 사이트( https://qiao.github.io/PathFinding.js/visual/)를 참고함.
작업 내용 소개
소스코드: https://github.com/choisb/PathFinding
이 프로그램은 A* 알고리즘과 JPS 알고리즘을 시각적으로 확인할 수 있는 간단한 프로그램이다.
아이콘 설명
- 🟩 초록색: 시작 지점
- 🟥 빨간색: 도착 지점
- ⬛ 검정색: 벽
- ⭐ 노란 별: 최단 경로
- 🔵 진한 파란 원: 닫힌 노드(Closed Set)
- 🔵 연한 파란 원: 열린 노드(Open Set)
맵 편집
- 시작/도착 노드는 드래그로 이동
- 빈칸 클릭 → 벽 생성
- 벽 클릭 → 벽 제거
단축키
| 단축키 | 기능 |
|---|---|
| C | 모든 벽 제거 |
| A | A* 알고리즘 실행 |
| J | JPS 알고리즘 실행 |
구현한 길 찾기 알고리즘
A* 알고리즘
A* 알고리즘은 휴리스틱값과 경로 비용 값을 활용하여 최단거리 검색을 보장하는 알고리즘.
맵이 커질 경우 탐색량이 커짐.
자세한 내용: A* 알고리즘 설명(개인 블로그)
JPS 알고리즘
대칭 경로에 대한 불필요한 탐색을 줄여 넓은 맵에서 A* 대비 성능을 향상시킨 알고리즘.
격자형식의 맵에서만 사용 가능.
자세한 내용: zerowidth positive lookahead
평가
설계는 꼼꼼히 하자
개인 프로젝트다 보니 평소 회사에서 하던 방식과는 다르게 대충 설계하고 작업에 들어갔다. 그래서 중간에 코드를 썼다 지웠다를 반복하다 보니 코드가 꼬이고 시간이 많이 지체됐다. 최소한 작업할 모든 클래스들의 구조, 객체의 생명 주기, 알고리즘의 수도코드, 인터페이스의 시그니처 등은 정리를 하고 작업했으면 지금보다 더 빠르게 완성했을 듯하다.
테스트 및 디버깅 기능도 설계 시 함께 고려
처음 구현이 끝났을 때 역시나 버그가 많았다. 로그를 찍어봐도 알고리즘이 복잡하니 로그만 보고 버그의 원인을 찾기는 쉽지 않았다. 길 찾기 과정이 많게는 수백 수천 스텝을 거치는 경우도 있는데, 어떤 노드에서 오류가 발생했는지 확인도 어려웠다. 로직이 복잡한 경우 시각화할 수 있는 툴도 함께 고려해 보면 좋을 듯하다.
추가로 한번 발생한 이슈를 재현하기 위해서는 동일한 맵을 만들어야하는데, 이슈가 발생한 맵을 항상 캡처 뜨고 그대로 그리는 것도 번거로운 일이다. 한번 만든 지형을 텍스트 파일로 저장 & 불러오는 기능이 있다면, 테스트를 더 편하게 할 수 있을 것 같다.
객체 관리 방식에 대한 정리 필요
기존 Game Programming in C++의 코드를 베이스로 수정 작업을 진행했다. 해당 교재에서는 편의상 로우 포인터를 new delete 하면서 객체를 관리한다. 그래서 Actor 관리를 시스템화하기 위해 모든 Actor를 Game 오브젝트에서 수명 관리를 하고, Actor를 제거하기 위해서는 Actor의 상태를 Dead로 설정한다.
나는 로우 포인터보다 안전한 스마트 포인터를 사용하려고 구조를 변경했다. 이때 단순히 객체를 스마트 포인터로만 변경하니 객체의 수명을 관리하는 구조가 중복되는 구조가 되니 Actor를 제거하기 위해서 Dead 설정과 참조해제 두 개를 모두 해야 하는 번거로움이 발생했다. 하나의 동작을 위해서 두 가지를 하는 것은 추후 실수를 유발할 수도 있는 구조이다.
끝맺으며
물론 모든 개선사항에도 비용이 발생한다. 디버깅 기능을 추가하면 디버깅 속도는 향상될 수 있으나 그 기능을 구현하는 시간이 더 소요될 수 있다. 다음 작업에는 이런 사항들을 고려해서 적정한 적절히 균형을 맞춰봐야겠다.
