Cellular Automata 를 이용한 Forest Fire Modeling 구현 (2)

* CA를 이용한 Forest Fire Modeling

 

- 여러 cell (나무)이 모여 forest를 이루고 있음.
- 어느 한 곳에서 불이 나면 주변으로 번져 나가기 시작함.
- 번져가는 과정에서 바람 (번져 나가는 것을 도움), 장애물 (번져 나가는 것을 방해)등 여러 가지 요소의 영향을 받음.

- 위와 같은 여러 가지 사항을 고려하여 각 셀(cell)의 상태(state)와  간의 규칙을 정의하여 CA 를 설계하고, 구현.
- cell의 state중에 나무와 불은 필수사항으로 반드시 고려하고, 그 외의 다른 요소 추가 가능.
- 초기 state는 파일로 입력 받고, 그 후엔 정해진 규칙에 따라 변화.

- 문자를 이용, 콘솔 상에 전체 cell의 state 변화를 텍스트로 적절히 표현.

 

 

 

Solution.

 

[구현 요소]

* 숲에 불이 나면서 불의 확산을 표현.
* 바람에 의한 영향으로 불의 확산 방향이 달라짐을 표현.
* 나무가 불에 타게 되고, 그러한 결과로 재가 남음을 표현.
* 불이 지나가고 재만 남은 곳에서 새로운 나무가 재생되는 것(오랜 시간이 흐른 후, 새로운 자연이 만들어짐)을 표현.
* 불이 물이나 돌의 장애물에 부딪혔을 때, 확산되지 못하고, 꺼짐을 표현.

 

 

[규칙]

 

 1) 첫번째 규칙. 불의 진행 규칙 (기본)

 

* 어떤 좌표에 불이 존재한다면 해당 불은 다음 턴에 서쪽, 북쪽, 동쪽, 남쪽으로 번지게 됨. (대각선 방향으로는 한 턴에 불이 번지지 않음) 단, 불이 번지는 곳에 나무가 존재하여야 하며, 아래의 그림에서처럼 나무가 있는 북쪽에 위치한 좌표와 동쪽에 위치한 좌표는 다음 턴에 불로 변하게 되지만, 서쪽과 남쪽은 각각 돌과 물이 가로막고 있기 때문에 불이 진행하지 못함.

 

[그림 - 불의 진행 규칙]

 

* 다음 턴에 현재 불이 있는 좌표(가운데)는 잿더미로 변하게 됨. (물과 돌에 인접한 불은 더 이상 탈 물질이 없어서 곧 꺼져버리게 된다는 규칙 적용. 2-2-5 규칙 참조) 

 

 

 2) 두번째 규칙. 불의 진행 규칙 (바람의 영향)

* 불의 확산은 바람의 영향을 받음. (바람의 방향에 해당되는 값은 처음 프로그램을 실행시킬 때, 입력 받는 첫번째 인자 값에 해당.) 바람은 다음과 같은 값을 가질 수 있음.

 

 

값 (Value)	방향 (설명)
0	바람 없음
1	서풍 (서쪽에서 불어오는 바람)
2	북서풍 (북서쪽에서 불어오는 바람)
3	북풍 (북쪽에서 불어오는 바람)
4	북동풍 (북동쪽에서 불어오는 바람)
5	동풍 (동쪽에서 불어오는 바람)
6	남동풍 (남동쪽에서 불어오는 바람)
7	남풍 (남쪽에서 불어오는 바람)
8	남서풍 (남서쪽에서 불어오는 바람)

 

 

3) 세번째 규칙. 재(ashes)의 생성 규칙

* 재는 불이 타고 난 후, 생성되는 물질.

* 규칙 - 먼저 불이 있는 좌표를 검사. (재 생성 규칙은 항상 불이 있는 좌표에만 적용되며, 물이나 돌 등의 좌표에는 영향을 주지 않는 규칙) 그리고 불이 있는 좌표 주위의 8방향 좌표를 검사하여 해당 불의 좌표를 재로 바꿀 것 인지 아니면 그대로 놔둘 것 인지를 결정.

* 좌표 검사에서 다음을 만족하는 경우에 해당 좌표(불)를 재로 변경.
  a.) 주변의 8개 좌표 중에 5개 이상이 불의 좌표인 경우 (주위에 불이 많기 때문에 이미 연소될 물질이 고갈되어 불이 꺼지는 경우)
  b.) 주변의 8개 좌표 중에 5개 이상이 재의 좌표인 경우 (주위의 대부분이 이미 다 타고 재만 남은 지역이기 때문에 해당 좌표도 곳 불이 꺼지게 되는 경우)

* 참고 - 좌표 검사 시, 해당 좌표가 지도(map)의 테두리에 있는 좌표라면 주변의 5개 좌표 중에 2개 이상인 경우만을 검사. 왜냐하면 테두리에 있는 좌표의 경우 8방향의 좌표에 인접해 있는 것이 아니라, 3~5개의 좌표만이 인접해있기 때문. 그러한 이유로 지도 테두리에 있는 좌표들은 검사의 조건을 완화함.

 

[ 그림 - 재의 생성 규칙 ]

* 위의 경우에서 가운데에 있는 불의 좌표를 검사한다고 할 때, 주변에 4개의 재, 2개의 불, 한 개의 물, 한 개의 돌이 인접해 있으며, 이는 위에서 설명한 불이 재로 바뀌는 조건을 만족하지 않으므로 다음 턴에도 가운데에 있는 불은 여전히 불로 존재하게 됨.

 

4) 네번째 규칙. 나무 재생의 규칙
* 불이 다 타고 재가 남게 되면 그 곳으로부터 새로운 나무가 자라게 됨. (불이 타고 남은 재로부터 오랜 시간이 흐른 후, 자연이 다시 재생됨을 표현)

 

* 규칙 - 먼저 재가 있는 좌표를 검사. (나무 재생 규칙은 항상 재가 있는 좌표에만 적용되며, 불이나 물 등의 좌표에는 영향을 주지 않는 규칙) 그리고 재가 있는 좌표 주위의 8방향 좌표를 검사하여 해당 불의 좌표를 재로 바꿀 것 인지 아니면 그대로 놔둘 것 인지를 결정.

 

* 좌표 검사에서 다음을 만족하는 경우에 해당 좌표(재)를 나무로 변경.
  a.) 주변의 8개 좌표 중에 8개 모두가 물,돌,재 또는 나무의 좌표인 경우 (주위에 자연적인 요소가 많기 때문에 새로운 생명이 자랄 수 있는 환경이 되는 것으로 설정.)

 

* 참고 - 좌표 검사 시, 해당 좌표가 지도(map)의 테두리에 있는 좌표라면 주변의 5개 좌표만을 검사하는데, 이는 테두리에 있는 좌표의 경우 8방향의 좌표에 인접해 있는 것이 아니라, 5개의 좌표만이 인접해있기 때문. 그러한 이유로 지도 테두리에 있는 좌표들은 검사의 조건을 완화.

[ 그림 - 나무의 생성 규칙 ]

 

* 위의 경우에서 가운데에 있는 재의 좌표를 검사한다고 할 때, 주변 모두가 물, 돌, 재 또는 나무(서쪽:재, 북서쪽:재, 북쪽:물, 북동쪽:물, 동쪽:재, 남동쪽:나무, 남쪽:돌, 남서쪽:나무)로만 이루어져 있으므로 다음 턴에서 해당되는 재의 좌표는 나무로 바뀌게 됨.

 

5) 다섯번째 규칙. 물, 돌에 인접한 불의 규칙

* 규칙 - 물과 돌에 인접한 불은 이들의 영향을 받아서 곧 꺼져버리게 됨. 즉, 물과 돌에 인접한 불은 다음 턴에 재로 변하게 됨.

 

6) 여섯번째 규칙. 불의 랜덤 생성 규칙
* 산불이 나게 되면 이미 죽었던 불씨가 종종 살아나게 되는 경우가 있으며, 다른 여러 가지 원인에 의해서 불이 발생하기도 함.

* 참고 - 매 턴마다 지도의 임의의 좌표에 2개의 위치에서 불이 새로 발생. 이는 초기에 입력 받은 불(fire)과 같은 형태이며, 같은 규칙을 따름. 불이 발생하는 임의의 좌표는 가로 5 ~ 95, 세로 5 ~ 45 범위 이내.

 

[프로그램 설명]

1) 실행 전 준비 사항

 * 아래 설명은 LISP 코드의 실행에 대한 설명.

 - 프로그램을 실행하기 위해서는 다음과 같이 설정되어 있어야 합니다.
 - 소스 파일(pl11.lisp)과 데이터 파일(input)이 반드시 ‘c:\\work\\input’ 의 경로에 있어야 합니다. 소스 파일은 다른 곳에 있을 경우 실행가능하지만, 오류가 발생할 가능성이 존재. (소스 파일 내에서 데이터 파일을 불러오는 경로가  ‘c:\\work\\input’로 설정되어 있기 때문인데, 이 부분을 수정한다면 다른 위치에 데이터 파일을 위치시킬 수 있음.)

 

2) 프로그램 실행

 - Allegro Common LISP Console 프로그램 실행
 LISP Console 창에서
    [1] USER(1): (load “c:\\work\\pl11.lisp”) 를 입력한 후, 엔터 키를 입력.
 정상적으로 ‘T’라는 값이 출력되면 정상적으로 LISP프로그램이 로딩된 것이므로 다음과 같이 메인 함수를 호출하여 실행하여 실행.
    [1] USER(2): (pl11 0 5)

3). 프로그램 실행 인자
 * 프로그램을 실행시키기 위해 pl 라는 메인 함수 호출 뒷부분에 추가적으로 2개의 인자가 더 필요함. 프로그램을 실행시키기 위해서는 반드시 2개의 인자를 추가적으로 입력하여야 하며, 각 인자는 다음과 같은 역할을 함.
 a) 첫 번째 인자 : 바람의 방향을 입력. 바람의 방향 값에 대한 설명은 위의 바람 방향에 대한 설명 테이블 참조. 이 값은 반드시 0 ~ 8 사이의 값을 입력해야 하며. 0의 경우는 바람의 영향을 받지 않고, 모든 방향으로 동등하게 불이 번진다는 것을 의미.

 b) 두 번째 인자 : 진행 횟수를 입력. 두 번째 인자로 입력된 수 만큼 프로그램을 진행. 즉, 두 번째 인자 값으로 5를 입력하면 초기 상태로부터 5번의 턴 동안 불이 진행되는 모습을 볼 수 있음.

 

 

[입력 데이터 파일 구성]

* 데이터 파일로부터 입력 받은 내용을 바탕으로 지도(Map)를 생성

* 파일로부터 받는 데이터는 모두 4가지의 문자로 구성되. (데이터 파일은 100 X 50 크기로 이루어진 문자들의 모임이며, 각 문자는 모두 공백 없이 붙어 있고, 라인이 변경될 때만, 캐리지 리턴 값이 포함.)

 

데이터 값	의미
O	물(water)을 의미. 물이 있는 곳은 불이 접근하지 못하며, 불에 타지도 않음.
X	돌(stone)을 의미. 물과 같은 역할.
*	불(fire)을 의미. 불은 주위의 나무를 태우며, 바람의 영향을 받음. 또한, 불이 타고난 다음에는 재가 남음.
-	나무(tree)를 의미. 나무는 불에 의해 타게 되고, 잿더미로 변하게 됨. 잿더미가 모인 곳은 시간이 지난 후, 새로운 나무를 생성시킴.

 

 

[입력 파일 샘플] 

 

 

 

[결과 화면에 대한 화면(문자) 구성]

 

데이터 값	의미
O	물(water)을 의미. 물이 있는 곳은 불이 접근하지 못하며, 불에 타지도 않음.
X	돌(stone)을 의미. 물과 같은 역할.
*	불(fire)을 의미. 불은 주위의 나무를 태우며, 바람의 영향을 받음. 또한, 불이 타고난 다음에는 재가 남음.
-	나무(tree)를 의미. 나무는 불에 의해 타게 되고, 잿더미로 변하게 됨. 잿더미가 모인 곳은 시간이 지난 후, 새로운 나무를 생성시킴.
+	재(ashes)를 의미. 나무가 불에 탄 후, 남기는 것.

 

 

 

 

[프로그램 실행 결과 샘플]

 샘플1)

 조건 : 바람 방향 없음, 진행횟수 50회

 입력 값 : 첨부된 input 파일 참조

 

 

 

 샘플2)

 조건 : 바람 방향 남서풍, 진행횟수 30회

 입력 값 : 첨부된 input 파일 참조

 

 

 

[소스 코드 및 실행 파일]

1) C언어 코드 내려받기

 (CA를 활용한 Forest Fire Modeling 을 구현한 것은 맞으나, LISP과는 조금 다른 조건으로 구현한 코드입니다.)

 

pl_ca_c.zip

 

 

2) LISP언어 코드

 

pl_ca_lisp.zip