원래 그냥 바로 pathFinder스크립트 만들고 바로 진행하려고 했는데,

생각보다 pathFinder부분이 커서 좀 나누어서 설명하도록하겠습니다.

그래서 이론수업부분이 하나 더 생겼네요.

부록 정도로 생각해주세요.


1. 캐릭터의 움직임.

우리는 w*h 만큼의 4방향 타일맵방식으로 맵을 만들고 상, 하, 좌, 우 로만 움직일수 있도록 할껍니다.

대각선이나 벽을 뛰어넘거나, 통과하는일은 없습니다.

그러니, 길찾기를 할때도 4방향만 신경쓰면 됩니다.


2. 시작점과 목적지


임의로 8*8 짜리 타일맵에 그림과 같이 시작점과 목적지를 표시합니다.

위치는 어디여도 상관없지만, 설명을 위해 맘대로 표시했습니다.


2. 갈수 없는타일 표시


검정색 부분은 벽입니다. 지나갈수 없는 땅이죠..


3. 시작점부터 탐색

제가 길을 찾는방법은 시작점부터 도착점까지 갈수 있는 모든 방향을 하나씩 표시할껍니다.

SearchCount라는 값을 하나 가지고, 한칸씩 움직일때마다 표시를 하는거죠.

우선 S 에서 시작하면 움직일수 있는 방향은 4방향 상,하, 좌,우 모두 움직일수 있습니다.

그럼 아래 그림처럼 상,하,좌,우 칸에 "1" 이라고 표시합니다.


4. 계속 탐색(재귀함수 사용)

이제 "1" 이라고 표시된부분을 기점으로, 3번에서 했던일을 똑같이 합니다.

단 이번엔 "1" 이 아닌 "2" 로 표시하는거죠.

그리고 이미 숫자가 표시된곳은 다시 표지 하지 않습니다.

모두 표시하면 다시 숫자만 하나 올려서 4번의 행동을 또 똑같이 반복합니다.

더이상 표시할수 있는곳이 없거나, "G"에 도착할때까지....계~~속

이번맵에서 탐색을 계속 하면 아래처럼 8번째 탐색에서 목적지까지 검색하게 됩니다.


이 과정으로 S에서 G까지 상하좌우 로만 움직일경우 가장 빨리 도착할수있는 턴은 8 번인걸 알수 있겠네요.


5. 경로 찾기

이제 저 많이 표시된 숫자중에 S->G까지 돌아가지 않고 한번에 가는경로만 찾으면 됩니다.

1,2,3,4,5,6,7,8 순으로 S부터 G까지 따라가면 되겠지만, 중간에 끊길수도 있고, 돌아갈수도 있습니다.

저는 반대로 G부터 S까지 8에서 1씩줄여서 가는방법으로 찾아가도록 하겠습니다.

(이러면 최소한 끊길일은 없습니다.)

지금 표시한 경로 이외에,  위,위,위,위,우,우,우,우 로 가는 루트도 있지만, 둘다 잘못된 길이거나, 최소경로보다 돌아가는건 아니니, 크게 상관 없겠네요.

저 경로는 마지막에 count를 줄여가며 경로를 찾을때 주위타일 검색 순서에따라 틀려지게 됩니다.


이론수업은 이상입니다.

상당히 복잡할꺼같았는데, 그림이랑 같이 설명하니까 금방 끝나네요.




저작자 표시
신고
Posted by andwhy

블로그 이미지
andwhy 개인 블로그.
andwhy

공지사항

Yesterday23
Today8
Total108,450

달력

 « |  » 2017.12
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31            

글 보관함