알고리즘) 플러드 필 (Flood Fill)

플러드 필 (Flood Fill)

 

플러드 필이라는 알고리즘은 다차원 배열(2차원 이상)에서 화면을 격자(Grid)로 분할하거나 체우는과정에서 사용되는 알고리즘이다.

이번에 필자는 특정 맵을 포인트화하는 과정에서 해당 알고리즘을 사용했다.

타일맵으로 만드는 과정에서 굉장히 많이 사용한다.

반응형

< 구현방법 >

구현방법은 다음과 같다.

 

특정 기준이되는 좌표를 정한다.

기준좌표의 방향(4방향 , 8방향)에 대한 확장형 로직을 작성한다.

해당 로직을 재귀처리한다.

재귀처리를 하는과정에서 해당 조건이 맞지 않으면 종료한다. (조건은 맵의 크기 or 갈수없는 영역 등등)

 

작업된 코드는 다음과 같다.

< 코드 >

  private void GetGridPoint(int _x, int _z){
        
        SceneInGame scene = SceneManager.Instance.GetScene<SceneInGame>();
        Vector3 pos = new Vector3(_x, 0.5f,_z);
        string key = this.GetGridKey(_x,_z);
        if(true == scene.GetGameController().CheckMapPosition(pos, 0.5f)){
            if(false == this.m_DicMap.ContainsKey(key)){
                this.m_DicMap.Add(key, new MapItem(pos));
                this.GetGridPoint( _x + Define.MAP_GRID, _z);
                this.GetGridPoint( _x - Define.MAP_GRID, _z);
                this.GetGridPoint( _x, _z + Define.MAP_GRID);
                this.GetGridPoint( _x, _z - Define.MAP_GRID);
            }
        }
    }

 

Navmesh로 되어있는 영역을 플러드 필로 처리할 경우에는 다음과 같다.

 

★★☆☆☆