[알고리즘] 이진 공간 분할법(BSP)란?

https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%EA%B3%B5%EA%B0%84_%EB%B6%84%ED%95%A0%EB%B2%95

 

 

트리의 형태로 생성과정으로는

 

"이진 공간 분할 법은 하나의 공간을 특정한 최종 목적을 만족할 때까지 공간을 재귀적으로 2개씩 분할하는 과정이다. 예를 들면, 충돌 감지를 목적으로 하는 경우에는 원래 물체가 충분히 충돌 검사를 간단하게 할 수 있도록 공간이 분할되며 렌더링을 목적으로 하는 경우에는 화가 알고리즘을 가장 효율적으로 사용할 수 있도록 볼록한 도형으로 공간이 분할된다."

 

 

https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%EA%B3%B5%EA%B0%84_%EB%B6%84%ED%95%A0%EB%B2%95

 

 

응용 방법

www.youtube.com/watch?v=1syQjkWeRZ0&ab_channel=Seunggeunjo

www.youtube.com/watch?v=FO12bZD3a5M&ab_channel=%EC%8B%A0%ED%98%95%EC%A2%85

 

아직 구현 해본적은 없지만, 나중에 필요로 할 때, 예를 들어 로그라이크 같은 장르(플레이 할때마다 맵의 형태가 다른) 의 게임에서 이런 식으로 랜덤 한 영역의 맵을 생성하는 데에도 좋은 알고리즘이 될 수 있을 것 같다. 이 정도로 알고만 있고 언젠간 나중에 필요로 할 때 구현해봐야겠다.