3D FX-Finder

(3D Fire&Exit Finder)

제1절 프로젝트 개요

9.11테러, 대구지하철 참사에 인명피해가 많이 발생했던 이유는 무엇이며 사람들은 어떠한 방식으로 피난을 했을까? 이 물음에 답을 구하기 위해 기존 분석 시스템은 사람들의 이야기를 종합하고 피난경로 및 상황을 수동으로 유추 한 후 피난정보를 산출하였다. 그러나 이와 같은 방식은 사람들의 실제 행동을 반영하지 않으므로 정확한 분석결과라 보기 어려웠다.

그리하여 우리는 보다 정확한 정보를 추출할 수 있는 FX-Finder를 개발하게 되였다. Fx-Finder는 건물의 도면 CAD파일을 이용하여 공간을 자동으로 시각화 시켜준 뒤, 피난자들의 특성(속도, 성별, 건물이해도 등)에 따라 각각의 피난시간을 고려하여 피난정보를 산출하게 된다.

1.1개발 배경 및 목적

화재 피난 프로그램을 개발을 시작 하게 된 것은 두 가지 동기에 의해서 였다. 첫번째로 대전 소방본부 에서 Pyrosim이라는 화재 분석 시뮬레이션 도입하였다는 뉴스를 접한 후 였다. 그러나 우리나라에서는 이 같은 프로그램을 개발하는 곳이 없어 비싼 로열티를 들여 기업 및 공공기관에서 프로그램을 구매하여 사용한다는 것이였다. 안타까워 하던 중 문득 이런 생각이 들었다.“화재가 났을 때 건물 내 화재 정보뿐 아니라 사람이 피난하는 모습까지 시뮬레이팅 할 수 있는 프로그램을 만들어 보면 어떨까?”라는 생각이 들었다.

두번째로 도심의 인구가 증가하고 건축기술이 발전함에 따라 면적당 최대 수용인원을 늘리기 위하여 건물들이 초고층화 되어가고 있다. 초고층 건물에서 화재 등의 위급상황이 발생할 경우, 건물의 특성상 피난시간이 오래 걸리게 된다. 사전에 계획된 피난 시나리오가 없다면 많은 인명피해가 예상 되어 진다. 그렇다면 “건물을 짓기 전에 피난 문제를 분석할 수 있는 도구를 만들면 어떨까?” 라는 생각을 가지게 되었다. 그리하여 시뮬레이팅 프로그램 개발을 시작하게 되었다. 그렇다면 선진국에서는 피난시뮬레이션 프로그램이 어느정도 개발이 되어 있을까?

  인명피해를 사고 이전에 계산할 수 있다는 장점을 가진 공간 및 피난 분석 프로그램들을 선진국에서는 1990년대 중반부터 개발하기 시작하였다. 그리하여 각 국가 연구소에서는 피난 분석 프로그램을 만들어 실제 현장에서 사용되고 있는 반면, 국내에서는 아직 시작단계로, 많이 뒤쳐져 있는 상황이다. 이와 같은 문제를 인지하여 본 프로그램을 개발하게 되었고, 이것을 통하여 인명피해의 결과를 계산하여 피해를 최소화 할 수 있도록 도와주는 프로그램을 제작 하게 되었다.

1.2추진체계 및 일정

기간 :4월5째주`~7월4째주(14주)+a
   팀장 : 나

팀원 : 6명

-       분석, 설계, 검증 : 나

-       제작 : 2명

-       3D그래픽, 테스트: 2명

-       WPF UI: 1명

<표1.2.1> 프로젝트 일정표

1.3부분 별 수행 업무 수행 및 담당자

<표1.3.1> 프로젝트 업무수행 및 담당자

1.4 프로젝트 개발 범위

본 프로젝트는 한국에서 개발된 피난 시뮬레이션들과 다른 알고리즘을 가진 모델로 개발하고자 하였다. 인간의 시각적 인지를 이용한 서울대의 프로그램이 독자화 되서 사용되어왔던 것을 계기로, 우리프로그램만의 특별한 알고리즘 계산법을 적용 시키고 싶었다. 그리고 피난 프로그램중 가장 유명한 Simulex 및 PathFinder를 롤 모델로 삼았다. 그 이유는 이미 검증된 피난 프로그램으로, 우리가 제작한 프로그램과의 결과값 비교시 유사한 값이 나오도록 하기 위해서 였다. 그리하여 각각의 프로그램의 장점을 파악하여, 우리 프로그램에 적용하였다.

엔진의 경우 인천대에서 개발된 프로그램 및 미국 Thunder 사에서 개발된 PathFinder의 경우 둘다 A* 알고리즘을 적용하였는데, 우리 프로젝트의 경우 그와 유사한 Static Floor Field 알고리즘을 적용하였다. 왜냐하면 개미의 페로몬 현상을 응용한 위급상황시 군집하게되는 현상을 적용하기 위해서 A*알고리즘 보다는 Static Floor Field가 적합하다고 생각하기 때문이다. 그러나 피난자들이 군집하게 되면서 서로 밀고 밀리는 Push Force현상은 적용하지 않았다.

그래픽의 경우 CAD파일을 정보화 시켜 2D및 3D화 시켜주는데 초점을 맞추었다. 화려한 디자인과 실제 피난자 케릭터가 이동하려는 모습을 구현하려 하였으나, WPF3D폼에 엔진과 연동하여 움직이게 하는데에 충분한 학습시간이 부족하여 구현하지 못하였다.

화제관련하여, 기본적으로 화제모델을 설정할줄 알아야 화제에 대한 정보를 적용시킬수 있기 때문에 FDS(화제시뮬레이션) Output 파일의 경우, 사용자를 FDS를 사용할수 있는 사용자로 제한하였다.  보통 FDS 시뮬레이팅 후 2차 검증과정으로 피난 시뮬레이션을 하는 것을 보며 FDS사용자에게 잘 맞는 피난 시뮬레이션이라고 생각 하였다.

제5절 결론 및 개선방향

5.1 결론 및 기대효과

FX-Finder를 통하여 얻을 수 있는 효과는 다음과 같다. 건물의 정보가 있는 CAD파일만 가지고 있다면 화재나 위급상황의 발생전에 위험을 미리 평가하고 위험에 대처할 수 있다. 또한 방송영상 자료나 안전도 검증자료로도 다양하게 활용될 수 있다.

피난프로그램의 대부분을 수입에 의존하는 국내 상황에서 FX-Finder는 국내 재난프로그램에 많은 변화와 발전을 가져오는 계기가 될 것이다.

테스트시 비교군으로 썼던 Thunderhead사의 PathFinder의 경우는 약 1000만원 정도 하는 고가의 프로그램이다. 그러나 이 프로그램 조차도 시뮬레이션 프로그램중에는 저가에 속한다. 1억원이 넘는 피난프로그램이 있을 정도로 대부분의 피난 프로그램들의 단가가 높은데, 국내기술로 피난프로그램을 개발한다면 외화 절감에도 상당한 효과를 가져올 수 있다.

5.2 테스트 및 검증

5.2.1 국내외 시뮬레이션 프로그램 비교

우리가 만든 FX-Finder와 Thunderhead사에서 만든 Pathfiner를 같은 조건하에 비교 실험 해 보았다. 실험 모델은 선문대학교 신축 기숙사를 선정하였고, 11가지 상황을 3번씩, 총 33번의 테스트를 해 보았다. 다음은 실험에 대한 결과이다.

5.2.2 대학 신축기숙사 테스트 결과(피난시간)

5.2.3 대학 신축기숙사 테스트 결과(오차범위)

실험결과 대량의 군집현상을 제외하고는 비교군인 Pathfinder와 유사한 결과가 나오는 것을 볼 수 있다. 각기 다른 알고리즘을 사용하였지만, 사람의 행동특성을 반영한 알고리즘이라는 유사성 때문에 비슷한 결과가 나올수 있었다. 

자세한 프로필 및 연락 주실 분들은
amhoya@hanmail.net
으로 메일 주세요. 

gem1-astar1.ppt

AStar.zip

당신이 쉽게 A* 알고리즘을 이해할 때, 이 A*알고리즘은 초보자에게는 복잡하게 느껴질수도 있습니다. A*알고리즘을 해석한 논설들이 웹상에 많이 존재합니다. 그러나 그 글들의 대부분은 이미 기본적인 것을 이해한 사람들을 위해 쓰여진 글들이지만. 그와 달리 이 글은 진정 초보자들을 위한 것입니다.

이 논설은 A* 길찾기 알고리즘의 주제를 완벽히 보여주도록 노력하지는 않습니다. 그보다는 당신이 앞으로 관련된 다른 좀더 구체적인 글들을 읽고 이해하는데 필요한 A*길찾기 알고리즘의 원리와 기본적인 것들을 설명하고 있습니다. 나중에 여러분들이 읽을수 있도록 최고의 몇몇 웹사이트 링크를 마지막 부분에 제공합니다.

마지막으로, 이 논설은 어느한쪽으로 특유화된 프로그램이 아닙니다. 나는 이 논설의 마지막 부분에 C++과 Blitz Basic 두가지 버전의 샘플프로그램 패키지의 링크를 넣어 놓았지만 당신은 어떤 컴퓨터 언어로든 A*알고리즘을 적용하는 것이 가능할 것입니다.

샘플프로그램에는 당신이 A*가 동작하는 것을 볼수있도록 실행파일도 포함시켜 놓았습니다.

• AStar.zip

자~ 처음부터 시작해 보자... 우리스스로 헤처나가 보자 ~Let's Go(^^b)

도입: 범위 찾기(The Search Area)

자~ 가정해 보자 누군가가 A지점에서 B지점으로 가기를 원한다. 그리고 벽이 이 두 지점을 분리시켜놓고 있다. 이것에 대한 그림이 아래에 있다. 녹색은 출발지점A, 빨간 것은 도착지점B, 그리고 파란색으로 채워진 사각형은 양쪽사이에 있는 벽이다.

먼저 알수 있는 것은 우리의 검색지역이 사각형 격자들(Grid) 로 나누어져 있다는 것이다. 우리는 이 단순화된 검색지역 사용한다. 우리가 첫 단계로 할 것은 길 찾기이다(당근이쥐!). (격자들로 지역을 단순화시킨) 이런 특별한 방법은 우리의 검색지역을 단순한 2차원배열로 만들어준다. 각각의 아이템(시작지점,도착지점,벽,길 등등)은 사각형 격자위에 하나의 2차원배열로 묘사된다. 그리고 이것은 ‘갈수 있는곳’, ‘갈수없는곳‘ 이런식으로 상태가 기록된다. 우리가 A에서 B로 갈 수 있는 길은 어떠한 사각형들의 모양으로 나타난다. 사각형의 중앙에서 다음 사각형의 중앙으로의 이동을 목표에 도착할때까지 하면서 길이 찾아진다.

이 중심점들을 노드 라고 부른다. 당신이 다른곳에서 길찾기에 대해 들을때, 사람들이 노드에 대해 토론하는 것을 종종 볼수 있을것이다(그런사람 없는데ㅡㅡ;). 왜 그것들을 사각형으로 사용하지 않지?(사각형을 사용하지 않는 사람들도 있나보다.) 왜냐하면 사각형보다 좀더 다른 것으로 검색지역을 나누는 것이 가능하기 때문이지. 그들은 직사각형, 육각형 또는 어떤모양이든 할수 있어~, 진짜루-. 그리고 노드는 그 형태 안에서 중심, 외각선사이 또는 다른 어디이든 위치할수 있어. 우리는 이 방식을 사용할거야 왜냐면 이것이 가장 단순한 방식이니까!(사각형을 쓰는것이? 아니면 A*길찾기 방식이? 이 방식이란 뭘 말하는것일까^^)

다음의 순서들을 실행 하므로써 우리는 길 찾기를 한다.

1. 지점A로부터 충분히 검토된 사각형을 열린목록(open list)에 추가한다. 열린목록은 쇼핑목록과 비슷하다. 지금은 목록상에 아이템이 하나이지만 나중에 좀더 갖게 될 것이다. 이것은 당신이 갖기를 원하는 길을  따라 저장 할 수도 있다. 그러나 그럴 수는 없다. 기본적으로 이사각형들의 목록은 검사가 필요하기 때문이다.

2. 시작점 근처에 붙어있고 지나갈 수 있는 모든 사각형들을 보아라. 벽, 물 또는 다른 잘못된 지역들은 무시해라. 그리고 그것들(정상적인 사각형) 역시 열린목록에 추가해라. 각각의 그 사각형들에게 지점A를 저장하라 ‘부모사각형’이라고~. 이 ‘부모사각형’은 우리의 길을 거슬러 올러갈 때 아주 중요하다. 좀더 후에 이것에 대해 확실하게 알게 될 것이다.

3. 시작사각형 A를 열린목록에서 빼고, 이것을 다시는 볼 필요가 없는 사각형들의 목록인 닫힌목록(closed list)에 추가해라

이 시점에서, 당신은 다음과 같은 그림을 얻을수 있다. 이 그림에서 중심에 어두운 녹색 사각형은 출발사각형이다. 이것은 밝은파란 외곽선으로 되어있고 이것은 닫힌목록에 추가되었음을 의미한다. 그리고 인접한 모든 사각형들은 검사되어진후 열린목록에 들어가 있다. 그리고 그것들은 밝은녹색 외곽으로 되어있다. 각각은 회색의 포인터를 가지고 있고 이것은 부모사각형인 시작점을 가리키고 있다.

다음으로, 우리는 열린목록에 있는 인접한 사각형중에 하나를 선택하고 앞에서 했던 처리를 아래에 설명된 방법으로 반복한다.  좀더 많이 할 수도 있고 덜 할 수도 있다. 그런데 어떤 사각형을 선택해야 할까? 그것은 바로 가장 작은 F비용을 가진 것을 선택한다.

(F비용이 무엇 일까요?? ^^ 아래를 보면 알게 된다구요.~)

 길 기록(Path Scoring)

길을 찾아내야 할 때 사용할 사각형을 선택하는 방법은 바로 다음 방정식이다.

F = G + H

G, H 요것들이 무엇이냐 하 믄~

? G = 출발점 A로부터 얻어진 새로운 사각형까지의 이동비용이다. 길을 찾아가면서 생성되게 된다.

? H = 얻어진 사각형으로부터 최종목적지점 B까지의 예상이동비용이다. 이것은 매번 조회될때마다 발견된다. 이것은 좀 당황스러울수 있다. 왜냐면 예상이동비용라고 불리듯이 이값은 추측이기 때문이다. 우리는 완전한 길을 찾을때까지 정확한 거리를 알수 없다. 왜냐하면 모든성격의 것들(물,벽,기타등등 갈수없는사각형)이 길위에 있기 때문이다. 당신은 H를 계산하는 한가지 방법을 연습을 통해 알게 될것이다. 그리고 H를 계산하는 방법은 웹상에 다른 많은 방법이 존재한다.

우리의 길은 열린목록과 F비용이 작은 사각형을 선택하는것의 반복을 통해서 얻어진다. 이 반복처리는 앞으로 이 논술 안에서 좀더 자세히 설명 될 것이다. 일단 우리가 어떻게 이 방정식을 계산하는지 세심히 보자.

위에 설명된 것처럼, G는 출발점으로부터 길을 만들기 위해 얻게 되는 사각형으로 이동하는데 드는 이동비용이다. 이 예제에서 우리는 세로 또는 가로로 이동하는데 각각 10의 비용을 할당 할 것이다 그리고 대각선이동에 대해서는 14의비용을 할당 할 것이다. 우리는 이 숫자들을 사용할것이다. 왜냐하면 대각선으로 이동하는 비용은 2의 루트이고 또는 대충 가로또는 세로로 이동하는거의 1.414배이기 때문이다. 단순하게 하기위해 우리는 10과 14를 사용한다. 비율은 거의 맞다. 그러므로써 우리는 루트 계산과 10진법을 피한다. 이것은 우리가 벙어리이거나 수학을 싫어하기 때문이 아니다. 그와 같은 숫자들을 사용하는 것은 컴퓨터에서도 역시 매우 빠르기 때문이다. 그것들과 같이 단순화 시킨 숫자들을 사용하지 않는다면 길찾기가 매우 느려진다는 것을 당신은 금방 알게 될 것이다.

우리는 얻어지는 사각형의 일정한 길을 따라 G 비용을 계산하기 때문에, 사각형의 G비용을 알아내는 방법은 그 부모로부터 G비용을 가져와서 부모로부터 직각으로 움직였냐 대각선으로 움직였냐에 따라서 10또는 14를 추가해 주는것이다. 이 방법이 좀더 명확하게 되도록 하기위해서 이 예제상에서 좀더 멀리까지 해볼 필요가 있다. 그래서 우리는 시작점으로부터 떨어져 있는 하나 이상의 사각형을 얻는다.

H 는 길들의 변화 안에서 어림잡아 예측될 수 있다. 우리가 사용하는 이 방법을 맨하탄방식(Manhattan method)이라고 부른다. 당신은 현재사각형에서 목표사각형에 도달하기 까지의 대각선이동을 제외한 가로 또는 세로로 이동한 총숫자를 계산할수 있다. 그리고 거기에 10을 곱한다. 이것이 바로 맨하탄방식인데 이것은 도시에 한쪽에서 다른 한쪽까지의 블록을 계산하는것과 같은 방식이기 때문이다. 여기서 당신은 대각선으로 블록을 가로질러 자를수는 없다. 중요하게도, H비용을 계산할 때 우리는 어떤 끼여드는 방해물도 무시한다. H비용은 단지 남은거리에 대한 어림잡은 추측일 뿐이다. 진짜 거리가 아니다. 또한 발견적방식이라고 불리는 이유이기도하다. 좀더 알기를 원하는가? 당신은 발견적방식상의 방정식들과 추가적인 사항들을 여기(http://www.policyalmanac.org/games/heuristics.htm)에서 발견할수 있을 것이다.

G 와 H를 더하므로써 F 가 계산된다.우리의 검색의 첫단계의 결과를 아래 그림에서 볼수있다. F,G,H 비용이 각각의 사각형에 표시되어 있다. 시작사각형에 오른쪽에 있는 사각형안에 표시된것처럼, F는 좌상단에, G는 좌하단에, 그리고 H는 우하단에 표시되어 있다.

그럼, 저 사각형들을 살펴보자. 글자와 같이 있는 사각형을 보면, G비용이 10이다. 이것은 시작 사각형으로부터 수평방향으로 위치한 사각형이기 때문이다. 즉, 시작사각형으로부터 위, 아래, 왼쪽, 오른쪽에 있는 모든사각형들은 모두 똑같이 G비용이 10이다. 대각선으로 위치한 사각형들은 14의 G비용을 갖는다.

그리서 보다 몇몇의 그 사각형들을. 사각형 안에 그것들 안에있는 문자안에, G=10, 이것은 왜냐면 이것은 단지 한 사각형이다. 출발사각형으로부터의 가로 방향. 사각형들은 즉시 상하 하지 않는다. 그리고 왼쪽으로의 출발사각으로부터 것드은 모두 똑같이 갖는다 G점수가 10을. 대각선 사각형은 G점수가 14를 갖는다.

H 비용은 맨하탄 방식으로 빨간 목적지 사각형까지의 거리를 추측하여 계산된다. 가로, 세로 방향으로만 움직이고 길위에 있는 장애물들은 그냥 무시된다. 이 방식대로 한번 해보자, 시작사각형에 오른쪽에 있는 사각형은 목표사각형으로부터 3개의 사각형만큼의 거리에 있으므로 H비용은 30이다. 이사각형에 위에 있는 사각형은 4개의 사각형만큼 떨어져 있으므로 H비용이 40이다(가로,세로 로만 움직인다는 것을 명심해라). 이제 당신도 다른 사각형들의 H비용을 어떻게 계산해야 할지 느낌이 올것이다.

이제 F비용은 단순히 H 와 G 값을 더하면 되는것이다.

찾기 계속하기(Continuing the Search)

계속 찾기를 해 나가기위해서 우리는 단순히 열린목록에 있는 사각형들 중에서 가장 작은 F비용을 가지고 있는 사각형을 선택하고 그 선택된 사각형으로 다음의 과정을 하면 된다.

4. 이것을 열림목록에서 빼고 단힌목록에 추가한다.

5. 인접한 모든 사각형을 검사해서 닫힌목록에 있거나 갈수없는것(벽,물,그밖에 장애물)들을 제외하고 나머지중에서 열린목록에 들어가 있지 않은것들을 열린목록에 추가한다. 선택되었던 사각형을 새로운 사각형들의 부모로 만든다.(선택되었던 사각형이란 4.에서 단힌목록에 추가된 그 사각형을 말한다. 새로운 사각형이란 5.에서 열린목록에 새롭게 추가된 사각형을 말한다.)

6. 만약 인접한 사각형중에 이미 열린목록에 있는 사각형이 있다면 이사각형으로 가는길이 더 좋은 길인지 확인해 봐라. 다시 말하면, 우리가 현재 선택된 사각형보다 G비용이 더 작은지를 검사해 봐라. 만약 아니라면 아무것도 할 필요가 없다. 그러나 새로운 길이 G비용이 더 작다면 선택되었던 사각형의 인접사각형들의 부모를 새로운 사각형으로 바꿔라(위쪽 그림에서 보면, 선택된 사각형으로 향하는 포인터들의 방향을 바꾸는 것을 말한다.). 마지막으로, 그 사각형의 F와 G를 다시 계산해라. 이것이 좀 복잡하게 느껴진다면, 아래 그림을 보아라.

좋았어~, 이제 이작업들을 직접해보자. 최초에 9개의 사각형중에 우리는 시작사각형을 닫힌목록에 넣은후 열린목록에 8개의 사각형을 가지고 있다. 이들중에서 F비용이 가장작은 것은 시작사각형에 오른쪽에 있는 사각형 하나이다. 이사각형은 다음 그림에서 파란색 안에 강조되어 있다.(사실 뭐 강조되어 있지는 않다. 그냥 하늘색 외곽선에 쌓여 있을뿐^^)

제일 먼저 할 것은, 이것을 열린목록에서 빼는것이다.. 그리고 닫힌목록에 넣는다. (이것이 바로 지금 저 사각형이 파란색 외관선으로 강조된 이유이다). 그리고 우리는 인접한 사각형들을 검사한다. 오른쪽에 있는 사각형은 벽이다. 그래서 이것들은 무시한다. 왼쪽에 있는 것은 시작사각형이고 이것은 닫힌목록에 있다. 그래서 이것역시 무시한다.

다른 4 개의 사각형들은 이미 열린목록에 있다. 그래서 우리는 그것들을 이용한 길 중에 현재 이사각형을 이용하는 것 보다 좋은 것이 있는지 G비용을 이용한 검사가 필요한다. 우상단의 사각형을 보자. 이것의 G비용은 14이다. 만약 우리가 선택된 사각형을 거쳐서 그곳으로 이동한다고 하면 G비용은 20과 같을것이다(현재사각형이 G비용이 10이고 이것에서 수직으로 위쪽으로 한번 이동하였으므로 10을 더한다.). G비용 20은 14보다 크다. 그래서 이것은 좋은 길이 아니다. 그림을 보면 좀더 알기쉬울것이다. 단순히 시작사각형에서 대각선으로 1번 움직이는 것이 가로로 한번 세로로 한번 이렇게 움직이는거 보다 더 직접적이다.

우리가 열린목록상에 이미 있는 4 개의 인접한 사각형에 대한 처리를 할때, 현재의 사각형으로는 더 이상 길을 개선할 수 없다는 것을 알게 된다. 그래서 우리는 아무것도 변경하지 않고 이제는 인접한 사각형들에 주목하자. 이제 우리는 이것을 가지고 처리 할 것이고, 다음 사각형으로 이동할 준비를 할 것이다.

그럼 열린목록에 있는 사각형은 7 개로 줄었다. 그중에 가장 작은 F비용을 가지고 있는 것을 하나 고르자. 흥미롭게도 이 경우 두개의 사각형이 54의 F비용을 가지고 있다. 어떤 것을 사용할까? 이건 사실 별로 중요한 문제는 아니다. 속도상의 목적으로는 둘중 열린목록에 더 늦게 추가된 것을 선택하는 것이 속도상 빠르다. 이것은 그냥 단지 하나의 성향인데 당신이 목표에 다가갈 때 검색상에서 더 늦게 발견된 사각형들을 선호하는 검색성향일 뿐이다. (각각 다른 두개의 A* 버전을 만들더라도 길이가 같은 각각 두개의 길을 찾게 될 것이기 때문에 F점수가 둘 다 같더라도 서로 다르게 처리해도 상관없다.)

그래서, 우리는 그냥 단지 아래쪽에 있는 것을 선택하자, 그리고 다음 그림에 보여지는 시작사각형의 오른편을 보자

이제, 우리는 인접한 사각형들을 검사할 때 바로 오른쪽에 사각형이 벽이라는 것을 발견하게 된다. 그래서 우리는 이것을 무시한다. 그 바로위도 똑같이 벽이기 때문에 이것도 역시 무시한다. 그리고 우리는 벽 바로 아래 사각형도 무시한다. 왜그럴까? 왜냐하면 당신은 벽의 모서리 부분을 자르지 않고는 그 사각형으로 바로 갈수가 없기 때문이다.(뽀쪽한게 막구있잖아요~). 당신은 일단 밑으로 내려가서 그다음 그사각형을 거쳐서 지나간다. 이 처리에서는 이렇게 코너를 돌아서 이동한다. (노트: 코너를 자르는 규칙은 옵션이다. 당신의 노드를 어떻게 위치시키느냐에 따라서 사용된다.)

이렇게 5 개의 사각형이 계산에서 빠진다. 현재사각형 아래에 있는 2개의 사각형은 열린목록에 없는것이다. 그래서 우리는 이것들을 추가한다. 그리고 현재 사각형은 이것들의 부모가 된다. 다른 3개의 사각형중 2개는 이미 닫힌목록(시작사각형과 현재사각형위에있는 사각형, 둘다 파란색 외관선안에 있다)상에 있다. 그래서 우리는 이것들을 무시한다. 그리고 바로 왼쪽에 있는 마지막 사각형은 현재사각형을 통해서 가는것보다 G비용이 적은지 검사를 해보자. 아니군~, 그래서 이제 다 했고 열린목록에서 다음으로 이동할 사각형을 검사해보자

우리는 목표사각형을 열린목록에 추가 할때까지 이 처리를 계속 반복한다. 이것에 대해 정리된 그림을 아래에서 볼수 있다.

시작사각형으로부터 2 개의 사각형만큼 밑에 있는 사각형의 부모사각형이 이전 그림에서 변경되었다는 것을 주목하라. 전에 이것은 G비용이 28이었고 오른쪽위에 사각형을 가리키고 있었다. 지금은 G비용은 20이고 위쪽 사각형을 가리키고 있다. 이 일은 우리가 길찾기를 처리해 나가면서 어디선가에서 일어난 것이다. 어딘가에서 G비용을 검사했고 여기서 더 비용이 적게드는 길을 찾아냈다 그러므로써 부모가 바뀌것이고 G, F비용이 다시 계산되어진것이다. 이변화가 일어나는 동안에 예제에서 아주 중요하다고 보이는 것은 없는 것 같다.

가능성이 많은 장소들에서 이 검사는 목표지점으로 가는 가장 좋은 길을 찾아가면서 모든 것들을 다르게 만들것이다.(모든것들이란~ 더 빨리 갈 수 있는 곳을 말하는듯~-_- 그러니까 좀더 좋은 길은 G,F 값이 전하고 다른게 바뀐다. 이런 뜻인 것 같다.)

그래 그러면 이제 어떻게 최종적인 진짜 길을 찾아내지? 단순히, 단지 빨간 목표지점에서 시작해서 화살표를 따라서 부모사각형으로 한걸음씩 거슬러 올라가면 된다. 이렇게하면 결국 시작사각형까지 되돌아 가게된다. 그리고 그것이 당신의 최종적인 길이다. 이것은 다음의 그림에서 볼수있다. 시작지점 A에서 목표지점 B까지 이동하는 것은 단순히 길을 따라있는 각각의 사각형의 중심(노드)에서 다음사각형의 중심으로 이동하면 된다. 당신이 목표지점에 도달할때까지~ 쉽지~ㅋ

 A* 방식의 요약(Summary of the A* Method)

좋다. 지금시점에서 이제 당신은 설명을 통해서 했던 것 들은 까먹었을 것이다. 차례차례 이 A* 방식을 여기에서 정리해보자.

1. 시작사각형을 열린목록에서 넣는다.

2. 다음의 과정들을 반복한다.

a) 열린목록에서 가장 낮은 F 비용을 찾는다. 그리고 우리는 이것을 현재사각형으로 선택한다.

b) 이것을 닫힌목록으로 바꾼다.

c) 현재 사각형에 인접한 8 개의 사각형에 대해?

● 만약 인접한사각형이 갈수없는 것 이거나 그것이 닫힌목록상에 있다면 이것은 무시한다. 그렇지 않은것은 다음을 계속한다.

● 만약이것이 열린목록에 있지 않다면, 이것을 열린목록에 추가한다. 이사각형의 부모를 현재 사각형으로 만든다. 사각형의 F,G,H 비용을 기록한다.

●  만약 이것이 이미 열린목록에 있다면, 사각형 G비용을 이용하여 이사각형이 더 나은가 알아본다. 그것의 G비용이 더 작으면 그것이 더 나은 길이라는 것을 의미한다. 만약 그렇다면, 부모 사각형을 그 (G비용이 더 작은)사각형으로 바꾸어라, 그리고 그 사각형의 G,F비용을 다시 계산해라. 만약 당신이 당신의 열린목록을 F비용으로 정렬하고 있다면 바뀐것에 따라서 열린목록을 다시 정렬해야한다.

d) 그만할 때

● 길을 찾다는 중 목표사각형을 열린목록에 추가하였을때,

● 열린목록이 비어있게 될 경우 이때는 목표사각형을 찾는데 실패한것인데 이 경우 길이 없는경우다.

탈출하는 부분이 잘 표현 되어있다.
특히 3D로 자연스럽게 표현하였음.

모델로 사용한 것은
In his 1987 paper, Flocks, Herds, and Schools: A distributed Behavioral Model, Craig Reynolds introduced the concept of steering behaviors He showed that by combining three behaviors (collision avoidance, velocity matching, and flock centering) it was possible to efficiently simulate the movement of a flock of birds in real time - a feat that was otherwise computationally unmanageable.

워킹 스피드 값도 조절가능함


문의 위치를 입력 해야함

Quickly sketch geometry ->도면을 스캔한 이미지를 불러와서
쉽게 다시 도면파일로 그려줄수 있게 하였음.
특정 선택한 대피자들을 특정한 문으로 탈출할수 있도록 고려함

복층건물에서도 계단을 통해 대피하는 시뮬레이션 을 제공함
Number of occupant in seleted room 같은 도표를 제공함으로써
방에서 사람들이 얼마나 점거하고있는지 한눈에 보이게 하였다.

Flow rates for seleted doors
->view door flow rate, original or averaged
간단한 리뷰.끝

더 참고하거나 다운로드시 아래의 사이트를 방문하세요.
http://www.thunderheadeng.com/pathfinder/index.html