2D MMO 라이브 서비스 - (2 - 4) A* 알고리즘 개선

- 개요

몬스터는 Map 클래스의 FindPath 함수는 A* 알고리즘을 기반으로 추적합니다.

그러나 배열 위주로 로직이 구성되어 맵의 크기가 커질수록 순회에 많은 시간을 소모한다는 단점이 있습니다.

따라서 배열에서 빠른 탐색이 가능한 딕셔너리와 해쉬셋을 사용하는 방식으로 코드를 개선해보겠습니다.

 

1) 메인 Program 클래스

 

우선, Program 클래스의 Main 함수를 위와 같이 수정하였습니다.

• Task 대신에 Thread를 사용하여 별개의 스레드 구현 : 디버깅이 용이함
• GameRoom 관련 로직을 메인 스레드에서 수행하고, DB 관련 로직을 별개의 스레드에서 수행

 

2) Map 클래스

좌표를 나타내는 Pos 구조체

 

Pos 구조체를 위와 같이 수정하였습니다.

기존의 Map에서는 Pos 구조체의 X / Y 값을 사용하여 맵을 탑색했지만,

이제는 수정하여 Pos 구조체 자체를 사용하여 맵을 탐색하도록 수정합니다.

따라서 위와 같이 필요한 연산자를 오버라이딩하여 Pos 구조체를 사용할 수 있도록 설정합니다.

 

FindPath 함수 변경 (1)

 

방문한 좌표인지 여부를 저장할 컨테이너를 배열에서 위와같이 HashSet으로 변경하였습니다.

또 저장하는 값을 불리언 값이 아닌 방문한 좌표의 Pos 값으로 저장하도록 수정하였습니다.

 

FindPath 함수 변경 (2)

 

이어서 경로 + 경로에 대한 최종 점수를 저장할 컨테이너와 현재 좌표 이전의 좌표를 저장할 컨테이너도

마찬가지로 배열에서 Dictionary로 변경하였습니다.

 

FindPath 함수 변경 (3)

 

탐색하기 위한 시작점을 설정하는 로직을 수정한 컨테이너에 맞게 수행하도록 로직을 변경하였습니다.

 

FindPath 함수 변경 (3)

 

이후 가장 이상적인 후보를 찾는 로직에서도 수정한 컨테이너에 맞게 수행할 수 있도록 로직을 수정합니다.

 

 

탐색한 리스트를 뒤집어 경로를 설정하는 CalcCellPathFromParent 함수에서

인자로 배열이 아닌 딕셔너리를 사용하도록 수정합니다.