[게임메이커 강좌-기타][GMS2]그리드 기반의 길찾기-6 A Star 알고리즘

 

 

GAME MAKER 강좌

 

KAYAN

 

 

 

 

 

◈ 그리드 기반의 길찾기(Path finding) A Star 알고리즘

 

 

이번 강좌에서는 mp_grid 기능을 사용하지 않는 길찾기를 만들어 볼 겁니다.

 

강좌에서는 아래와 같은 방식으로 길찾기를 구성할 거에요.

 

(▲ 길찾기)

 

이 방식은 오브젝트가 오브젝트의 중심부로부터 이동할 수 있는 지역을 모두 체크하여 우선 순위를

지정하고, 좌표를 저장해요.

이 우선 순위는 중심부와의 거리에 해당합니다.

예를 들어, 오브젝트 현재 위치는 우선 순위 1부터 시작하고, 1칸 다음은 2, 2칸은 3으로 매깁니다.

 

(▲ 이동 가능 좌표의 우선순위)

 

그리고 이동 가능 지역의 좌표를 모두 저장했다면, 저장한 좌표들을 체크하여 이동할 목표 지점과 일치하는

좌표의 우선 순위를 시작으로 오브젝트 중심부의 우선 순위(1)로 찾아가면 이동 경로가 완성됩니다.

 

(▲ 이동 경로 검색 예시. 4▶3▶2▶1 가까운 우선 순위로 경로 구성)

 

이동 경로가 완성되면 오브젝트를 이동시키는 거죠.

 

(▲ 길찾기)

 

설명을 들어선 난해하죠? ㅠㅠ

물론 사각형 그리드에선 mp_grid 기능을 사용하는 것이 간편하고 효과적입니다.

하지만 HEX 그리드나 아이소메트릭 그리드에서 적용하기에는 매우 어렵죠.

이 방식은 복잡하지만, 다양한 형태의 그리드에 응용하여 적용할 수 있습니다.

 

 

음. 일단 한번 구성해봅시다.

 

먼저 길찾기에 필요한 기능들이 필요합니다.

시스템 오브젝트( obj_system )를 하나 만들고, [Game Start 이벤트]에 기능을 추가합니다.

이동 경로를 구성할 패스, 기본 좌표를 저장할 리스트 데이터 구조체(ds_list), 그리고 좌표의 우선 순위를

저장할 우선 순위 큐(ds_priority)를 사용할 거에요.

우선 순위 큐는 오브젝트의 중심부와의 거리를 체크하기 위해 사용합니다.

 

//● obj_system - Game Start 이벤트            global.grid=32;//그리드 크기 32 x 32        global.move_path=path_add( );//패스    path_set_closed(global.move_path,0);//패스 열림(시작과 끝을 연결하지 않음)        global.move_list_x=ds_list_create( );//이동 가능 지역의 좌표    global.move_list_y=ds_list_create( );        global.move_list_prio=ds_priority_create( );//좌표의 우선순위    global.move_dist_temp=ds_priority_create( );//좌표의 우선순위 체크 전용

 

강좌에서 그리드의 크기는 32 x 32 크기의 정사각형 기준으로 합니다.

 

다음은 [Game End 이벤트]를 추가하고, 이전에 생성했던 패스와 데이터 구조체들을

메모리에서 제거합니다.

 

//● obj_system - Game End 이벤트            path_delete(global.move_path);        ds_list_destroy(global.move_list_x);    ds_list_destroy(global.move_list_y);        ds_priority_destroy(global.move_list_prio);    ds_priority_destroy(global.move_dist_temp);

 

이제 플레이어 오브젝트( obj_player )를 하나 만들고, [Create 이벤트]에 변수를 추가합니다.

 

//● obj_player - Create 이벤트           move_on=0;//이동 스위치        move_point=15;//이동 범위(패스 포인트 제한)        pspeed=2;//이동 속도

 

이동 범위는 현재 위치 기준으로 탐색할 범위(셀)를 말합니다.

더 멀리 탐색하려면 크게 설정하면 되는데, 강좌에선 15 정도로 탐색해 볼거에요.

 

다음은 [Step 이벤트]를 추가하고 본격적으로 이동 설정을 만들거에요.

마우스 좌표를 그리드 중심에 맞추도록 설정합니다.

그리고 이동할 수 있는 지역을 확인해야 이동할 수 있겠죠?

 

//● obj_player - Step 이벤트            var mx,my,mbp_L;    //마우스 좌표    mx=(floor(mouse_x/global.grid)*global.grid)+floor(global.grid/2);    my=(floor(mouse_y/global.grid)*global.grid)+floor(global.grid/2);        mbp_L=mouse_check_button_pressed(mb_left);//마우스 클릭 체크            if move_on==0{    x=(floor(x/global.grid)*global.grid)+floor(global.grid/2);//현재 좌표    y=(floor(y/global.grid)*global.grid)+floor(global.grid/2);        event_user(0);//이동 가능한 좌표 구성        move_on=1;//다음 액션    }

 

이동할 수 있는 지역 확보는 [Step 이벤트]에서 모두 구성하기에는 이벤트가 복잡해질 수

있기 때문에 [사용자 이벤트]에 나눠서 구성할 겁니다.

강좌에서는 [사용자 이벤트 0]에서 이동할 수 있는 지역을 구성해 봅시다.

 

오브젝트에 [사용자 이벤트 0]를 추가합니다.

먼저, 길찾기 기준이 되는 현재 오브젝트의 좌표와 좌표에 해당하는 우선 순위를 데이터 구조체에 저장합니다.

 

(▲ 현재 좌표를 저장)

 

리스트 데이터 구조체에는 이동 좌표를 저장하고, 우선 순위 큐에는 좌표값과 오브젝트 중심부와의

거리를 우선 순위로 저장합니다.

현 오브젝트 중심부 좌표의 우선 순위는 1부터 시작해 멀어질 수록 중심부와의 거리를 칸 수로 지정합니다.

 

//● obj_player - User Defined 0 이벤트            var _x,_y;    _x=(floor(x/global.grid)*global.grid)+floor(global.grid/2);//현재 좌표    _y=(floor(y/global.grid)*global.grid)+floor(global.grid/2);            //데이터 구조체 초기화    ds_list_clear(global.move_list_x);    ds_list_clear(global.move_list_y);    ds_priority_clear(global.move_list_prio);    ds_priority_clear(global.move_dist_temp);        ds_list_add(global.move_list_x,_x);//현재 좌표 저장    ds_list_add(global.move_list_y,_y);    ds_priority_add(global.move_list_prio,string(_x)+","+string(_y),1);//현재 좌표의 우선순위        //다음 회차 때 주변 탐색 기준이 될 임시 우선순위    ds_priority_add(global.move_dist_temp,string(_x)+","+string(_y),1);

 

강좌에서는 우선 순위 큐에 저장하는 좌표를 간편하게 처리하기 위해 아래와 같은 형식의 문자열 형태로 저장할 거에요.

 

   저장값 = "x,y"

 

※ 강좌에서 저장한 좌표를 분리하려면 아래 스크립트가 필요합니다. 이벤트 아무 곳에 추가하면 됩니다만, 스크립트 리소스에서 함수를 정리하면 관리하기 좋습니다.

 

//● 스크립트 함수 - get_pos_str(str)            function get_pos_str(str){    ///get_pos_str(str);    var p;    pos[0]=0;    pos[1]=0;        if string_count(",",str)==1{    p=string_pos(",",str);    if p>1{    pos[0]=real(string_copy(str,1,p-1));    pos[1]=real(string_delete(str,1,p));    }    }    }

 

이제 저장한 좌표를 기준으로 이동 가능 지역을 방향별(강좌에서는 4방향)로 탐색합니다.

 

(▲ 방향별로 이동 가능 지역을 탐색)

 

여기서 지나갈 수 없는 오브젝트(예를 들면 적, 또는, 장애물)가 있는지 체크하고,

이동이 가능하다면 좌표와 우선 순위를 저장하는 것이죠.

 

(▲ 이동 가능 지역)

 

오브젝트 중심부의 우선 순위는 1이니, 중심부 다음 칸인 여기는 2로 저장합니다.

만약 이동할 수 없는 지역이라면 좌표를 저장하지 않는 거에요.

 

방향별로 좌표를 추가했다면, 저장한 두번째 우선 순위의 위치를 기준으로 이동 가능 지역을 또 탐색합니다.

 

(▲ 다음 우선 순위의 좌표 주변 탐색)

 

그리고 이동 가능한 지역이면 좌표를 저장하는 거죠. 만약 이전에 저장한 좌표(중복 위치)인 경우는 제외합니다.

우선 순위 2의 좌표에서 탐색했으니 저장할 우선 순위는 3이 되겠네요.

 

(▲ 좌표를 저장)

 

이와 같은 방식으로 중복되는 위치를 제외한 이동 가능 지역의 좌표를 탐색해 저장합니다.

 

(▲ 우선 순위 좌표를 기준으로 주변 탐색)

 

이동 가능 좌표를 모두 저장했다면, 바로 전에 저장한 우선 순위의 좌표 수만큼 이전에 했던 방식으로

반복하여 이동 가능 지역을 탐색합니다.

이와 같이 했을 때 이동 가능 지역의 우선 순위는 아래와 같은 형태를 띨 거에요.

 

(▲ 이동 가능 좌표의 우선순위)

 

이벤트로 구성하자면 아래와 같습니다. 참고로 강좌에서 장애물은 obj_block 오브젝트입니다.

 

//● obj_player - User Defined 0 이벤트            //------------- ▼ 이어서 추가        var grid_w,grid_h;    grid_w=global.grid;    grid_h=global.grid;        var _d,t;        //이동 범위 설정    var _d,t,i,k,_cell_n,n,_px,_py;;    _cell_n=move_point;            for(i=2;i<=_cell_n+1;i+=1;){    n=ds_priority_size(global.move_dist_temp);//이전에 저장한 우선순위 수        repeat(n){        t=ds_priority_delete_min(global.move_dist_temp);//최근에 저장한 우선순위 좌표    get_pos_str(t);//문자열에서 (x,y)좌표 분리        k=0;repeat(4){    //우선 순위 좌표 주변 탐색    if k==0{_px=pos[0]+grid_w;_py=pos[1];}    if k==1{_px=pos[0];_py=pos[1]-grid_h;}    if k==2{_px=pos[0]-grid_w;_py=pos[1];}    if k==3{_px=pos[0];_py=pos[1]+grid_h;}        //탐색 좌표중 저장한 좌표가 있는지 체크    _d=ds_priority_find_priority(global.move_list_prio,string(_px)+","+string(_py));        if !(_d>0){ //저장한 좌표가 없을 때 좌표를 추가        if _px>0 && _py>0 && _px<room_width && _py<room_height{            if !(position_meeting(_px,_py,obj_block)){ //장애물 체크        ds_list_add(global.move_list_x,_px);//좌표 추가    ds_list_add(global.move_list_y,_py);        ds_priority_add(global.move_list_prio,string(_px)+","+string(_py),i);//우선순위 추가        //다음 회차 때 주변 탐색 기준이 될 임시 우선순위    ds_priority_add(global.move_dist_temp,string(_px)+","+string(_py),i);        }}    }            k+=1;}        }    }        ds_priority_clear(global.move_dist_temp);//임시 우선순위는 클리어 함

 

어우~ 넘 길다... 좀, 복잡해보이죠?

먼저, 임시 우선 순위 큐에 저장한 좌표 주변을 탐색하여, 장애물(블록, 적, 등)을 체크하고 이동 가능한

지역이면 좌표를 저장합니다. 단, 이전에 저장한 좌표는 제외합니다.

이 행동은 탐색할 거리( move point )만큼 반복하는 겁니다.

 

여기까지하면 이동 가능 지역을 이동 포인트만큼 확보하게 됩니다.

 

 

 

이동 범위를 확보했으니 다음은 이동 경로를 구성할 차례입니다.

 

[Step 이벤트]로 돌아가 확보한 좌표를 사용하여 이동할 목표 지점(도착 지점)과 매칭하도록 합니다.

강좌에서 이동할 목표 지점은 마우스 좌표입니다.

 

(▲ 목표 지점)

 

확보한 이동 좌표에 마우스를 클릭하면 그 위치로 플레이어를 이동시키는 것이죠.

이벤트를 구성하자면 아래와 같습니다.

 

//● obj_player - Step 이벤트            //------------- ▼ 이어서 추가        var it,n,i,px,py,_x,_y;;        if move_on==1{    n=ds_list_size(global.move_list_x);//이동 좌표 수 만큼 탐색    px=x;    py=y;        i=0;repeat(n){    _x=ds_list_find_value(global.move_list_x,i);//이동 가능 좌표    _y=ds_list_find_value(global.move_list_y,i);                if mx==_x && my==_y{//마우스 위치와 일치하는지 체크    //action    if !(position_meeting(mx,my,obj_player)) && mbp_L{        //------------- ▼ 패스 구성            //------------- ▲ 패스 구성        move_on=5;//다음 액션        break;}        }    i+=1;}        }

 

이것은 리스트 데이터 구조체에 저장한 좌표를 사용하여 목표 지점과 매칭되는 좌표를 찾는 겁니다.

 

패스 구성은 다른 오브젝트에서도 동일하기 때문에 다른 오브젝트에서도 간편하게 사용할 수 있도록

아래와 같은 스크립트 함수로 추가합니다.

 

//● 스크립트 함수 - grid_set_path(_x,_y)            function grid_set_path(_x,_y){    ///grid_set_path(x,y)    ///@param x    ///@param y    var i,_px,_py,_return,_prio;        path_clear_points(global.move_path);    _return=0;    _prio=ds_priority_find_priority(global.move_list_prio,string(_x)+","+string(_y));        if _prio>0{    path_add_point(global.move_path,_x,_y,100);            _px=_x;    _py=_y;    for(i=_prio;i>1;i-=1;){    if grid_link_prio_pos(_px,_py,i-1){    _px=pos[0];    _py=pos[1];    path_add_point(global.move_path,_px,_py,100);    }    }        path_reverse(global.move_path);        _return=path_get_number(global.move_path);    }    return _return;    }

 

//● 스크립트 함수 - grid_link_prio_pos(x1,y1,_prio)            function grid_link_prio_pos(x1,y1,_prio){    ///grid_link_prio_pos(x1,y1,prio)    ///@param x    ///@param y    ///@param priority        var grid_w,grid_h;    grid_w=global.grid;    grid_h=global.grid;            var _x,_y,k,_px,_py,_d,_return;    _x=(floor(x1/grid_w)*grid_w)+floor(grid_w/2);    _y=(floor(y1/grid_h)*grid_h)+floor(grid_h/2);    pos[0]=_x;    pos[1]=_y;        _return=1;        _px=_x;    _py=_y;        //------    k=0;repeat(4){        if k==0{_px=_x+grid_w;_py=_y;}    if k==1{_px=_x;_py=_y-grid_h;}    if k==2{_px=_x-grid_w;_py=_y;}    if k==3{_px=_x;_py=_y+grid_h;}            if _px>0 && _py>0{    _d=ds_priority_find_priority(global.move_list_prio,string(_px)+","+string(_py));    if _d>0{    if (_d==(_prio)){    pos[0]=_px;    pos[1]=_py;    _return=1;    break;}    }}        k+=1;}    //------    return _return;    }

 

복잡해보이지만, 간단하게 설명하자면 우선 순위 큐에 저장한 우선 순위 좌표를 사용하여 이동할

목표 지점(도착 지점)을 시작으로 오브젝트의 중심 위치까지 탐색하여 이동 경로를 완성시키는 스크립트입니다.

 

예를 들어, 이동할 목표 지점의 우선 순위가 4라면, 그 좌표 주변을 탐색하여 가장 가까운 우선 순위 3을 찾아

이동 경로에 포함합니다.

 

(▲ 이동 경로)

 

그리고 다음은 2, 그리고 우선 순위 1인 오브젝트 중심 위치까지 차례로 추가하는 거죠.

이벤트는 복잡하지만, 원리는 단순합니다.

 

 

추가한 패스 스크립트 함수를 이동 설정 이벤트에 추가하고, 패스를 구성하면 됩니다.

 

//● obj_player - Step 이벤트            var it,n,i,px,py,_x,_y;;        if move_on==1{    n=ds_list_size(global.move_list_x);    px=x;    py=y;        i=0;repeat(n){    _x=ds_list_find_value(global.move_list_x,i);    _y=ds_list_find_value(global.move_list_y,i);                if mx==_x && my==_y{    if !(position_meeting(mx,my,obj_player)) && mbp_L && !(mbp_R){    //------------- ▼ 추가        grid_set_path(_x,_y);    path_start(global.move_path,pspeed,0,1);        move_on=5;//다음 액션        //------------- ▲ 추가    break;}    }    i+=1;}        }

 

마지막으로 패스 이동이 끝났을 때는 데이터 구조체들을 초기화합니다.

 

//● obj_player - Step 이벤트            //------------- ▼ 이어서 추가        if move_on==5{    if path_position==1 || (path_get_number(global.move_path)<2){       path_end( );        ds_list_clear(global.move_list_x);//이동 좌표 초기화    ds_list_clear(global.move_list_y);        ds_priority_clear(global.move_list_prio);//우선순위 초기화    ds_priority_clear(global.move_dist_temp);        path_clear_points(global.move_path);//패스 포인트 초기화        x=(floor(x/global.grid)*global.grid)+floor(global.grid/2);//현재 좌표 갱신    y=(floor(y/global.grid)*global.grid)+floor(global.grid/2);        move_on=0;//다음 액션    }        }

 

강좌에서는 이동이 끝났을 때 처음 이동 구성으로 돌아가게 설정했습니다.

끝났을 때 어떻게 행동시킬 것인지는 여러분이 원하시는대로 구성하시면 될 거에요.

강좌는 여기까지입니다.

이제 잘 되는지 테스트 해봐야겠죠?

 

 

 

 

 

 

◈ 테스트

 

 

테스트하기 전에 이동 범위를 확인해야하니 플레이어보다 아래에 있는 오브젝트( obj_floor )를

하나 만들고, [Draw 이벤트]에 이동 범위를 표시합니다.

 

(▲ 이동 범위 표시)

 

그리고 범위를 표시할 그리드 크기 만큼의 이미지를 추가합니다.

강좌에서는 32 x 32 크기의 흰색 이미지( spr_move_grid 스프라이트 이미지)를 기준으로

표시할 때는 색을 혼합(녹색)하여 표시합니다.

 

//● obj_floor - Draw 이벤트            var n,_x,_y,i;        n=ds_list_size(global.move_list_x);    if !(ds_list_size(global.move_list_y)==n){n=0;}        i=0;repeat(n){    _x=ds_list_find_value(global.move_list_x,i);    _y=ds_list_find_value(global.move_list_y,i);        draw_sprite_ext(spr_move_grid,0,_x,_y,1,1,0,c_green,0.5);//이동 범위에 spr_move_grid 이미지 표시        i+=1;}

 

이것은 이동 범위 설정에서 리스트 데이터 구조체에 저장한 좌표를 사용하여 이동 가능 좌표에 이미지를

표시하는 것입니다.

이 오브젝트를 시스템 오브젝트의 [Room Start 이벤트]에서 생성되도록 합니다.

그러면 따로 배치할 필요 없이 시스템 오브젝트가 배치된 룸에 들어갈 때마다 자동으로 생성되겠죠.

 

//● obj_system - Room Start 이벤트            instance_create_depth(0,0,50,obj_floor);

 

또한, 시스템 오브젝트 [Draw 이벤트]에 패스가 잘 구성되는지 확인할 수 있도록 패스를 화면에 표시해봅시다.

 

//● obj_system - Draw 이벤트           draw_path(global.move_path,0,0,1);

 

 

(▲ 패스 표시)

 

테스트 준비가 끝났네요.

룸에 시스템 오브젝트와 플레이어를 배치하고 잘 작동하는지 테스트해봅시다.

 

 

 

pathfinding_example5_a_star.yyz

0.05MB