[알고리즘] A* 치즈 찾기-PathFinding

개요

개요는 이전과 동일하다. A* 알고리즘을 2D Tile Map 환경에서 시뮬레이션해본다.

이전 Map Tool 글은 밑에 링크가 있다.

 

사진 및 프로젝트 설명

프로그램 화면

저번 글에 비해 프로그램 화면에 변화가 생겼다. 먼저 기존에 없던 Start 문구가 생겼으며 이미지의 자리 배치 변경 및 크기 변경을 진행했다.

 

위와 같이 쥐가 치즈를 찾기 위해 최단거리로 벽을 피해 가는 모습을 볼 수 있다. (GIF 재생속도를 증가시켰기 때문에 실제로는 이것보다 느리게 움직인다.)

 

 

A* 알고리즘의 미시적 관점

 

A* 길 찾기 알고리즘은 원래부터 게임에 써먹기 위해 만들어진 것은 아니므로 A*로 얻은 경로를 그대로 사용하면 캐릭터 이동이 그리 자연스럽게 보이지 않는다. 그렇기 때문에 게임에서의 길 찾기 알고리즘은 좀 더 미학적인 수정이 필요하다. [1]

 

 

위 사진을 보면 내가 원하는 길을 찾는 방식은 직선(파란색 숫자) 경로로 가는 것인데 여기서 A* 알고리즘은(빨간색 숫자) 경로를 최단거리로 내놨다. 이렇게 움직이면 술 취한 쥐처럼 움직이는 거 같고 또 최단거리가 아닌 거 같은 느낌이 든다.

하지만 실제로 숫자를 찍어서 비교해보면 파란색과 빨간색의 숫자는 동일하다는 것을 알 수 있다. A* 알고리즘은 경로의 비용이 같으면 이 둘을 구분할 수 없으며 단지 먼저 발견한 경로를 선택할 뿐이다. 이럴 때 필요한 게 A*의 미시적 최적화이다.

 

휴리스틱에 따른 길 찾기의 변화

이번에는 저번 이론에서 정리했던 휴리스틱 h(x)의 값에 따른 열린 목록과 닫힌 목록의 차이를 확인해보자 

이전에 작성했던 휴리스틱은 총 3가지가 있었다. 휴리스틱 비용이 0인 경우, 유클리드 거리로 계산한 경우, 휴리스틱 비용을 과대평가한 경우

 

 

먼저 휴리스틱 값을 0으로 한 경우이다.

 

h(x)=0

h(x)=0

휴리스틱이 0일 때의 탐색현황이다 여기서 각 숫자들이 나타내는 것은 가중치이다. 위에 이론과 비슷하게 원형으로 탐색을 진행한 것을 확인할 수 있다.

 

 

그다음은 휴리스틱 값을 유클리드 거리로 계산한 경우이다.

 

h(x)를 유클리드 거리로 계산한 경우

 

h(x)를 유클리드 거리로 계산한 경우

휴리스틱이 유클리드 거리일 때의 탐색현황이다 동일하게 각 숫자들이 나타내는 것은 가중치이다. 위에 이론과는 차이가 좀 있지만 휴리스틱 값이 0일 때에 비하면 타원 형태를 유지하는 것을 확인할 수 있다.

 

 

마지막은 휴리스틱 값을 과대평가한 경우이다.

 

h(x)를 과대평가한 경우

휴리스틱을 과대평가했을 때의 탐색현황이다 동일하게 각 숫자들이 나타내는 것은 가중치이다. 위에 이론과 비슷하게 마른모 나 육각형 모양을 띄는 것을 볼 수 있다. 과대평가는 기존 유클리드 방식에 *50 정도를 한 수준이라 이게 맞는지는 확실치가 않다.

 

마지막으로 각 휴리스틱에 따른 열린 목록과 닫힌 목록의 개수를 표로 정리해본다.

휴리스틱	열린 목록 크기(개수)	닫힌 목록 크기(개수)
h(x)=0	19	57
h(x)=유클리드	20	33
h(x)=과대평가	17	22

닫힌 목록의 최종 크기는 A*가 탐색한 노드들의 개수이며 열린 목록의 최대 크기로는 각 노드를 탐색하는 데 걸린 시간이 어느 정도인지를 알 수 있다.(목록이 클수록 목록을 처리하기 위한 시간도 길어짐) 휴리스틱 비용의 계산 방식을 결정할 때에는 검색 노드의 모양이나 수치 그리고 만들어진 경로의 모습을 시험해 보면서 검색 속도와 경로의 품질 사이의 적절한 타협점이 필요하다. [1]

 

 

후기

A* 알고리즘을 적용해서 길 찾기를 진행해보았다. 기존에 다익스트라 알고리즘을 이용해서 해본 적은 있는데 A*는 처음 적용해보았다. 앞으로 남은 거는 다수의 쥐가 다수의 치즈를 찾으러 가는 걸 구현으로 마무리할 생각이다. 

 

이 코드는 휴리스틱을 바꿔서 진행할 수 있도록 만든 함수이다. 화면에서는 보이지 않고 실행하기 전에 값을 바꿔야 하는데 화면에 띄우기는 아마 하지 않을 거 같고 접근성이 용이하게 전역 변수로 시작하기 전에 바꿀 수 있게 하는 정도까지 할 예정이다.

 

유의사항

* x86 환경에서 작동하며 화면 크기를 기존 크기에서 변경하면 마우스 클릭 오류가 있으니 가급적 기본 크기 화면으로 테스트 바랍니다.

* 해당 프로젝트는 예외 처리를 최소한으로 했기 때문에 버그가 있을 수 있습니다.

* 최종 모습이 아니기 때문에 코드와 화면에 변경이 있을 수 있습니다.

* 만약 이 블로그 글을 보고 잘못된 점이나 참고 가능한 것 등 공부가 가능한 게 있다면 댓글이나

   메일(SnowFleur0128@gmail.com)로 보내주시면 감사하겠습니다.

출처 및 소스코드 링크

[1] [Mark Deloura] [GAME PROGRAMMING GEMS]: 정보문화사

 

git:https://github.com/SnowFleur/2020-AStar-algorithm-Simulation

 

관련 글

[자료구조 알고리즘/탐색 알고리즘(Search)] - [알고리즘] A* 알고리즘

[자료구조 알고리즘/탐색 알고리즘(Search)] - [알고리즘] A* 치즈 찾기-맵 툴

[자료구조 알고리즘/탐색 알고리즘(Search)] - [알고리즘] A* 치즈 찾기-PathFinding2