[게임개발] 타일형 랜덤맵에서 고립된 공간 만들지 않기. Flood Fill 활용.

#  목표　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　

타일형 랜덤 맵을 만들기 위해서

빈 타일을 미리 깔아놓고, 랜덤 한 좌표에 일정 갯수의 벽 타일을 생성하는 방법을 사용합니다.

이럴 때 아래의 오른쪽 그림과 같이 벽 타일로 둘러쌓여서 고립된 공간이 생기기 마련입니다.

이 고립된 공간이 생기지 않도록 하는 방법을 알아보겠습니다.

오른쪽 맵에 고립된 공간이 있습니다.

 

# Flood Fill 알고리즘

플러드 필 알고리즘은 다차원 배열에서 연결된 영역(공간)을 찾는 알고리즘입니다.

그림판에서 사각형을 그려놓고 픽셀로 둘러쌓여진 곳 안에

연결된 부분에 모두 색칠하는 방법으로 사용하는 것이 대표적입니다.

 

모서리 방향을 연결된 것으로 볼 것이냐 아니냐에 따라 4방향 탐색, 8방향 탐색이 있습니다.

4방향 탐색 결과 : 8방향 탐색 결과

오른쪽 아래에 위치한 타일에서 시작했을 경우

녹색 타일은 연결되어 있는 영역입니다.

빨간색 타일은 4방향 탐색으로는 연결되지 않은 영역이고,

8방향 탐색으로는 연결되어 있는 영역입니다.

흰색 타일은 어떤 방법으로든 연결되지 않는 영역입니다.

 

 

# 탐색 이론 ( 4방향 탐색 )

 

 

 

이 탐색을 벽 타일이 놓을 때마다 체크를 해야합니다.