[💬] 지구케잌 최외각 벽 구하는법

[익명(221.157)]

맵이 있습니다.

맵 제너레이팅 해줄때 에초에 맵보다 가로세로 2그리드씩 크게 잡은뒤 실제 맵은 사이즈 -2씩 제너레이팅 하게 해주세요.

(맵 배열 크기가 x =100, y= 200이면 맵 제너레이팅 할때는 x =98, y= 98로 제너레이팅 하면 최외곽부가 쫙 이어짐)

(0,0)좌표에 flood fill 알고리즘 적용해주면 최외각 걸러짐

flood fill이 뭔지 말하자면

쉽게말해서

그림판의 요 페인트임

좀더 자세히 설명하자면

요렇게 시드점 기준으로 우선 자기자신을 원하는 색으로 칠하고 한방향을 체크해서 자기랑 같은 색이면 자기 자신을 재귀 호출.

만약 다르면 무시.

그렇게 네방향을 체크(원하면 8방향 체크해도 무관)

이러면 이어져있는건 모두 색칠됨.

요건 위키에 누가 올려둔 flood fill이 어떻게 작동하는지 움짤로 만들어둔거.

여기서는 벽을 체크해야되니깐

시드점 기준으로 같은 색(막힌 공간)이면 자기자신을 호출, 벽이면 최외각벽값을 주고 자기자신을 호출하지 않음.

이런식으로 주면 최외곽 벽만 전부 칠해짐.

flood fill 소스야 여기저기 널렸는데

이거 그냥 재귀 호출 함수로 짜면 조금만 사이즈 커져도 오버플로우 뜨고 성능 개판됨.

그래서 스택이나 큐 쓴 알고리즘 긁어오면됨.

구글에

flood fill using queue

flood fill without recursion

요런 검색어 치면 재귀함수 형태로 안하고 스택이나 큐써서 만든 알고리즘 넘쳐흐름.

생각보다 쉽게 만들 수 있고 생각보다 재미있으니깐 한번 구현해봐!

근데 이게 사이즈가 무지무지무지 크면 성능저하도 쉽게 일어나서

만드는 게임에 맞는 알고리즘인지는 나도 잘 모르겟음 ㅋㅋ

 

[지구케잌(1.238)]

아이고 미안합니다 고생하셨네