브라우저 게임에서 둘러싸인 공간을 효율적으로 감지하는 방법
2025-02-07
브라우저 게임에서 플레이어는 적을 방해하기 위해 장애물을 배치합니다. 플레이어가 자신이나 적을 둘러싸서 부정행위를 하는 것을 방지하기 위해 저자는 둘러싸인 공간을 효율적으로 감지하는 알고리즘을 설계했습니다. 초기의 무차별 대입 방식(각 셀의 홍수 채우기)은 너무 느린 것으로 판명되었습니다. 저자는 "열려 있는" 셀(장애물로 둘러싸여 있지 않은 셀)의 캐시를 활용하여 홍수 채우기 검색 공간을 줄이는 개선된 알고리즘을 고안했습니다. 장애물이 추가되거나 제거되면 알고리즘은 열려 있는 셀 집합을 업데이트하고 합법적인 배치 위치를 다시 계산합니다. 최악의 경우 시간 복잡도는 무차별 대입 방식과 같지만, 실제로는 이 알고리즘이 지연 시간을 크게 줄입니다. 저자는 반복적인 업데이트나 여러 장애물에 인접한 셀만 확인하는 등의 다른 최적화 기법에 대해서도 설명합니다. 마지막으로 저자는 사이클 감지 기반 알고리즘과 같은 다른 가능한 해결책을 언급합니다.
게임
둘러싸인 공간 감지