Flood Fill 알고리즘

https://ko.wikipedia.org/wiki/%ED%94%8C%EB%9F%AC%EB%93%9C_%ED%95%84

플러드 필 - 위키백과, 우리 모두의 백과사전

▲Flood Fill 알고리즘은 주어진 시작점으로부터 연결된 영역들을 찾아내는 알고리즘입니다.

그림판에의 페인트통 들이붓기 기능 (다른색이 나올때까지 같은 색은 모두 대체해버림)
혹은 기계가 본인 주변영역을 레이더처럼 검색하여 목적지를 찾는 길찾기에도 사용됩니다.

 

게임에 해당 알고리즘을 적용시키는 예라면, 빛이 한 지점으로부터 펼쳐져 나가거나,
본인이 탐색/이동/공격 가능한 범위를 표시할때라던가, 혹은 범위 내 적까지의 길찾기를
진행할 때 사용되지 않을까 생각합니다.

---

한쪽을 전부 다 깊게 검사한 후 다른곳을 찾아나서는 DFS(깊이 우선 탐색)
넓은 영역을 거쳐 본 후 범위를 넓혀나가는 너비 우선탐색 BFS(너비 우선 탐색)

 

Flood Fill은 DFS로도, BFS로도 구현 가능합니다.
그중에서 전 DFS 방식의 재귀를 이용해 하나 구현해보았습니다

 

 

▲태초의 시작은 이러합니다. 맨 처음 들어온 타일에 조건이 맞으면 행동을 취하고
상하좌우에 본인에게 받은 똑같은 명령을 하게 합니다. 재귀함수를 사용할것이기에
함수가 끝날 수 있는 엔드조건이 확실하게 존재해야합니다.

 

▲ 맨 위에서부터 코드를 요약하자면
1. 인덱스 예외조건에 걸렸으면 배열때문에 터지지 않게 재귀 멈춤
2. 재귀가 더 돌 수 조건을 여러개 체크 할 참거짓 자료형을 통해 재귀 엔드조건 추가
3. 엔드조건에 걸리지 않았다면 상하좌우 타일에 다시 재귀를 굴림.

 

사실 컴파일러 자동 최적화를 위해선 꼬리재귀를 해야하고, Flood Fill 알고리즘은 꼬리재귀로 분명 구현 가능하긴 하나
이해 및 가독성을 올리기 위해 위 일반적인 재귀로 구현해보았습니다. 

엔드조건이 나올때까지 본인 색을 바꾸고, 주변 다른 타일에게 지시를 계속 내리는 방식입니다.
생각 외로 이해하기 쉬운 알고리즘이라 구현기간이 짧아 시간 투자대비 가성비가 좋았던거같습니다