카테고리 보관물: Programming

타일맵 길찾기.

원래 블로그에는 평소에 공부했던 걸 저장하고 나중에 찾아서 참고하는 용도로 쓰고 있었는데, 최근 바빠서 그럴 시간이 없었다. 특히 NDC2016 발표를 준비하는 시간은 정말 지옥같았기 때문에(결과값이.. 결과값이 나와야 했다), 발표를 준비하면서 공부했던 내용, 그리고 발표 보충 자료를 올린다고 말해놓고 올리지 않은 채 반 년이 지나버렸다. 최근에 타일 맵을 다시 쓸 일이 생겨서 예전 자료를 참조하다가 NDC2016 발표에 썼던 기법이 기억이 나지 않는 걸 깨닫고, 시간이 나는 김에 하나씩 정리해 놓아야겠다고 생각했다.

타일 맵은 컴퓨터 게임의 초창기부터 지금까지 쓰여온 견고한 기법이다. 보통 균일한 이미지 조각인 타일(Tile) 을 이어붙여서 맵의 형태를 만든다. 보통 이렇게 만든 맵은 보기에 자연스럽고 타일 간의 이음새가 크게 눈에 띄지 않는 것이 좋다. 이렇게 만든 맵은 보통 주인공 캐릭터나 다른 오브젝트들의 활동 무대로 쓰인다.

타일 맵은 RPG Maker 같은 툴에서도 쉽게 찾아볼 수 있다. 타일을 선택하고 색칠하듯 마우스로 드래그하면 맵이 생성된다. 이렇게 생성된 맵은 자연스럽게 보인다. 즉 타일과 타일 간의 이음새가 분리되는 느낌이 아니라 부드럽게 연결된다. 이렇게 만들려면 어떻게 해야 할까?

링크

애초에 이 고민을 했던 것은 고전 게임인 <삼국지 영걸전>의 맵 파일을 누군가 뜯어놓은 것을 살펴볼 때였다. 맵 조각은 아래처럼 구성되어 있었다.

그에 비해 우리가 보통 알고 있는 맵은 아래와 같다.

이미지를 보면 금방 둘의 연관성을 알 수 있다. 실제의 맵을 구성하는 타일 조각의 최소 단위는 보통 플레이어가 “한 칸”이라고 인지하는 유닛이나 성채, 보물창고의 크기에 비해 가로, 세로가 각각 1/2 작은, 1/4 크기였다. 영걸전에서는 한 칸이 32 x 32 픽셀, 타일 하나는 16 x 16 픽셀이다.

예를 들어 위의 맵은 아래처럼 하얀 네모가 하나의 이미지 조각(타일)로, 그것이 모여서 우리가 인지할 수 있는 맵의 형태가 된다.

영걸전에서는 유닛이 이보다 가로 세로 2배 큰 단위로 배치된다. 물론 게임에 따라 맵 타일과 유닛 타일이 같은 단위일수도 있다.

이음새가 자연스럽게 보이기 위해서는 우리가 한 칸의 타일이라고 인식하는 것의 절반 정도의 스케일로 타일을 준비해야 한다. 이 페이지에 따르면 보통 RPG에서 많이 사용되는 타일 종류를 2-corner 타일이라고 부른다. 타일의 corner 부분이 변하기 때문이다. 땅과 물처럼 대비되는 두 가지의 지형이 자연스럽게 이어지도록 하는 것이다.

링크

영걸전에서는 대각선을 연결할 필요가 없었는지 아래 그림에서 빨간 네모로 표시한 이런 타일들은 쓰이지 않았다.

대신에 표현을 풍부하게 하기 위해서인지 연결 타일 일부가 2가지로 쓰였다(이음새와 면적이 차지하는 부분에 차이 있음).
영걸전의 초원 – 물 연결 부분을 정의하는 2-corner 타일은 아래와 같다.

다음 글에서는 내가 RPG 게임의 타일 맵을 어떻게 만들었는지를 보여줄 예정이다.출처:NDC2016 보충자료 – 1. 타일 맵 구현 기본

읽어볼만한 좋은 글
——————
1. http://chulin28ho.egloos.com/5097822 – 워크래프트3에서 사용된 타일 구조 연구

참고자료
——–
2. http://www.codeproject.com/Articles/106884/Implementing-Auto-tiling-Functionality-in-a-Tile-M – 2D 타일 맵의 구현 설명

3. http://s358455341.websitehome.co.uk/stagecast/wang/2corn.html – 보통 RPG 맵을 만들 때 사용하는 2-corner 타일에 대한 설명신고출처:NDC2016 보충자료 – 1. 타일 맵 구현 기본

지난 글에 이에 이번에는 실제 NDC2016 발표에서 타일 맵을 어떻게 구현했는지에 대해서 살펴보겠다. 타일 리소스는 게임업계의 저명한 인사인 Daniel Cook 이 무료로 공개한 타일셋을 가져왔다. 게임에 사용하는 무료 리소스가 올라오는 opengameart.org 에는 이 타일셋을 32 x 32 크기로 수정한 버전이 있는데 이것도 참고했다.

일단 내가 사용할 타일셋을 만들었는데 아래 그림과 같다. 가운데에 있는 벽돌은 이 예제에 사용한 유닛들과 느낌이 어울리지 않아서 결국 사용하지 않았기 때문에 기본 타일 종류는 풀(초원), 길, 물의 3종류다.

풀과 길은 이전 글에서 설명한 2-corner 타일로 서로 경계면이 부드럽게 연결되는 타일 조각들로 이루어져 있다. 하지만 물은 물과 다른 영역의 경계가 투명하게 처리되어 있는데, 이는 먼저 풀과 길을 정리한 다음에 물을 그 위에 덮어씌우기 위해서다. 풀이든 길이든 물을 그 위에 얹으면 자연스럽게 보인다. 3가지 타일이 만나는 경우의 수를 다 계산하는 것보다 이쪽이 간단하고 편하다.

간단히 생성해 본 맵은 아래와 같다.

길을 만드는 과정은 복잡하기 때문에 다음 글에 설명하기로 하고, 여기서는 물을 얹는 방법부터 설명하려고 한다. 맵의 어떤 장소에 물을 배치하기로 결정하면, 상하좌우, 좌상, 좌하, 우상, 우하의 8개 셀에 대해서 랜덤함수를 돌려서 75%의 확률로 물을 배치한다.

물을 배치한 후에는 Cellular Automata 기법을 이용해서 각 셀의 상하좌우 4방향 이웃을 체크, 물의 모양을 자연스럽게 만들어준다.
물 타일이 아닐 경우 상하좌우 이웃에 물 타일이 2개 이상 있으면 물 타일이 된다.

그 다음에는 물의 클러스터가 충분히 가깝지만 이어져 있지 않아서 어색해보이는 경우를 방지하기 위해서 1타일 떨어진 물의 경우 합쳐주는 작업을 한다.

이제 이 맵을 타일맵으로 바꿔줄 때가 왔다. 영역간의 연결을 생각하지 않는다면 아래와 같은 타일맵도 가능할 것이다.

하지만 연결을 생각하면 계산은 조금 복잡해진다. 아까의 타일셋을 살펴보면 각 타일은 4개의 corner에 물타일이 있는 경우와 그렇지 않은 경우로 나눌 수 있다(물 = w, 다른 타일 = o 로 표시).

맵의 타일 결정 방법은, 먼저 물 타일 각각에 대해서 8방향에 어떤 타일이 있는지 검사한다. 그리고 물 타일이 아니면 가중치를 둔다.

타일이 되는 빨간 타일을 확대해서 살펴보면 4개의 corner로 나눌 수 있는데, 어느 한쪽에서 영향을 받으면 인접한 영역에 1을 더해주게 된다.

예를 들어서 왼쪽 상단에 물 타일이 아닌 것이 있으면 왼쪽 위 코너에 1이 더해지고, 오른쪽에 물 타일이 아닌 것이 있으면 오른쪽 상단, 오른쪽 하단 코너에 1을 더한다.

이렇게 계산하면 위 맵의 타일에는 아래처럼 점수가 쌓이고, 그 중 1 이상인 값만 o(other) 타일로 치환하면 알맞은 타일을 찾을 수 있다. 4개의 corner가 모두 o 타일일 때는 이미 물 타일이 아니라고 판단하고 그리지 않는다.

최종적으로는 아래처럼 타일을 찾게 된다. 위와 비교하면 꽤 큰 차이다.

이렇게 타일맵의 실제 구현에 대한 내용을 살펴보았다. 다음 글에서는 위에서 약간 두리뭉실하게 넘어갔던 “어떤 장소에 물을 배치할지” 결정하는 문제에 대한 내용, 즉 맵의 노드와 경로를 정하는 기법에 대해 다룰 예정이다.출처:NDC2016 보충자료 – 2. 타일 맵 구현 실제

이번에는 지난 NDC2016 발표의 “맵 생성 절차”(59~69p.)에 대해서 좀 더 자세한 글을 써보려고 한다. 59페이지를 그대로 가져와보면 다음과 같다.

이 단계들에 대해 차례대로 설명하려고 한다.

1. Poisson Disc Sampling

맵에서 비교적 균일한 간격으로 노드를 선택하기 위한 방법이다. 완전한 랜덤이 아닌 이 방법으로 선택한 노드는 보기에도 좋고 활용도 편리하다. 하나하나의 노드가 도시나 별이라고 하면 서로 너무 멀거나 너무 가깝지 않은 적당한 거리를 유지할 수 있기 때문에 자연스럽기도 하다. 아래 그림에서 가장 오른쪽이 Poisson Disc Sampling 으로 생성한 노드들이다.

이미지 링크

Disc Sampling 이라는 이름대로 이 방법은 대기열에 속한 점(=노드) 주변에 있는 원형(Disc)의 영역에 다른 점을 추가할 수 있는지 검사한다.

새로 추가하는 점 주변에 다른 이웃이 없다면 그 점을 추가하고, 그 점을 대기열에 넣는다.
미리 정해진 tryCount 만큼 탐색하여 점을 여러 개 추가한다. 나는 tryCount를 30으로 설정했다.

tryCount 가 끝나면 대기열에 있던 점을 빼고 새로 추가된 점 중 하나를 대기열에 집어넣고 다음 탐색을 반복한다. 이때 주변에 다른 이웃이 없는지 체크해서 이웃이 있다면 그 점은 추가될 수 없다.

탐색을 빠르게 하기 위해 전체 맵을 그리드로 나누고, 그리드 안에는 하나의 점만 들어갈 수 있도록 제한한다. 따라서 원이 겹치는 영역에 있는 모든 점을 검사할 필요 없이, 원이 걸치는 그리드에 있는 점들만 검사하면 되기 때문에 탐색 시간이 줄어든다.

이해를 돕기 위해 예전에 만들었던 Poisson Disc Sampling 예제 링크를 올린다. 예제에서는 1프레임당 1개의 점을 탐색하도록 했기 때문에 점이 천천히 검색되는 것이지, 실제 검색 속도는 빠르다.

http://wonderfl.net/c/MMGa

2. Minimal Spanning Tree

트리란 두 개의 노드가 하나의 간선(edge)으로만 연결된 그래프를 말한다.

신장 트리(Spanning Tree)는 사이클(루프)가 없이 모든 노드를 연결하는 트리이다. 최소 신장 트리(Minimal Spanning Tree)는 이 중 모든 노드를 연결하면서 경로의 합이 가장 짧은 신장 트리를 말한다.

위에서 만든 노드들을 연결해서 그래프를 만드는데, 복잡한 계산을 줄이기 위해 일정 길이 이하의 간선만 남긴다. 그리고 여기서 최소 신장 트리를 찾는다.

3. 지형 배치

이렇게 최소 신장 트리를 찾은 다음에는 간선 연결이 하나뿐인 터미널 노드(terminal node)를 찾는데, 이곳에 물과 절벽을 배치한다. 터미널 노드에는 물이나 절벽 중 하나를 배치한다.

아래 그림에서 검은색으로 표시된 노드가 터미널 노드이다. 두번째 글에서 설명했던 Cellular Automata 기법으로 인접한 물, 인접한 절벽끼리는 서로 합쳐진 것을 확인할 수 있다.

이제 각 타일이 어느 지형에 속하는지 결정을 해야 한다. 어떤 타일은 풀이 먼저 그려진 다음 위에 물이 그려지고, 또 절벽까지 겹쳐져 있다. 일단 절벽(검은색)을 최우선으로 찾은 다음 물(파란색)을 찾고, 마지막으로 절벽과 물에 속하지 않은 곳을 이동 가능한 타일(하얀색)로 지정한다.

또한 경로에는 랜덤하게 길 타일을 배치해서 사실감을 높인다. 길 타일 역시 Cellular Automata 기법으로 너무 뚜렷하지 않게 자연스러운 모양을 유지하도록 했다.

4. 다시 Poisson Disc Sampling – 메인 경로 추출

지금까지의 작업이 그럴듯해 보이는 지형을 만들기 위한 것이었다면 이번 단계는 유닛들이 이동할 수 있는 메인 경로를 만드는 작업이다. 다시 Poisson Disc Sampling 을 이동 가능한 타일(하얀색)에 대해서만 수행한다. 그리고 경로는 이동 가능한 타일을 지나는 것만 인정하고, 중간에 절벽이나 물과 겹치는 경로는 제외한다.

5. 메인 노드 정하기 & 유닛 배치

그럼 이제 1:1 대결을 상정한 맵이기 때문에 각 팀의 유닛을 배치할 메인 노드를 결정한다. 메인 노드 2개는 서로 연결되어야 하고, 그 거리는 맵의 가로 길이 + 맵의 세로 길이의 40% 에서 100% 사이의 값이 되어야 한다. 적당한 메인 노드 2개를 발견하지 못했을 경우 맵 전체를 다시 생성한다.

메인 노드에는 각 팀이 지켜야 할 타워를 생성하고 그 주위에 유닛을 배치한다. 이제 양 팀은 서로의 타워를 파괴하기 위해 서로 대결을 펼치게 된다. 참고로 타워가 구석에 있을수록 유리한데, 보병과 기병은 인접해야만 타워에 공격이 가능하기 때문이다. 이 맵에서 Blue Team의 승률은 300번의 전투 시뮬레이션을 돌렸을 때 85.0%가 나왔다.

약간 길었지만 발표 중에 가장 정리하고 싶었던 부분인 맵 생성 절차를 정리해 보았다. 다음에는 시간이 된다면 딥러닝 실행 부분을 정리해보려고 한다. 양이 많아서 아마 글 하나로는 안될 것 같다.출처:NDC2016 보충자료 – 3. 맵 생성 절차

Navier-Stokes 방정식

유체방정식인 Navier-Stokes 방정식을 푸는 것이 게임에 구현된 것은 거의 못 본것 같습니다. 아직까지는 단순한 노이즈 기반의 식을 쓰는 것 정도로 충분한것 같고요. 저는 지금까지는 이런 물리식을 게임에 쓰는일은 전혀 안해봤네요. 논문상으로는 파티클을 생성시켜서 물결을 일으키는 수준까지는 있습니다만 대부분 이펙트로 처리하는 것 같습니다.

참고로 Navier-Stokes방정식을 영화 CG쪽에서는 Newtonian 방법이나 Lagrangian 방법으로 나뉘는데 Newtonian은 물의 공간을 표현하는데 좋고 (일반적인 프로그램에서 지원하는 것 같더군요) Lagrangian은 물뿌리는 것에 좋습니다. 점성도 표현 가능하죠. (Realflow라는 프로그램이 많이 쓰입니다.) 다만 실시간이 절대 아니고요 시간이 아주 오래오래 걸려요.

게임쪽에 물리가 들어오기엔 좀 어려워보이는게 아무래도 해외 진출을 해야하는 형편이다보니 저사양을 고려하지 않을수 없어서 물리를 넣기에는 좀 어려울것 같아요.

결국 서버에서 물리를 자세히 하는 것은 오버라고 보고요 잘못된 위치를 보정해주는 정도만 해도 될것 같네요. 이런 일은 클라이언트 프로그래머가 가능한 업무 범위가 아닌가 생각됩니다.

메일 이미지 첨부 보내기

[code language=”csharp”]
public void Sender()
{
MailMessage mail = new MailMessage();
mail.To.Add("yoonhada@gmail.com");
mail.Subject = "Test Mail";
mail.Body = "This is for testing SMTP mail for GMAIL";
//Attachment attachment = new Attachment("d:\\001.jpg");
//mail.Attachments.Add(attachment);

LinkedResource LinkedImage = new LinkedResource(@"d:\\001.jpg");
LinkedImage.ContentId = "MyPic";
AlternateView htmlView = AlternateView.CreateAlternateViewFromString("You should see image next to this line. <img src=cid:MyPic>", null, "text/html");
htmlView.LinkedResources.Add(LinkedImage);
mail.AlternateViews.Add(htmlView);

SmtpClient smtpServer = new SmtpClient("smtp.gmail.com");
smtpServer.Port = 587;
smtpServer.Credentials = new System.Net.NetworkCredential("AAAAAAAAA@gmail.com", "AAAAAAAAAAAAA") as ICredentialsByHost;
smtpServer.EnableSsl = true;
ServicePointManager.ServerCertificateValidationCallback = delegate (object s, X509Certificate certificate, X509Chain chain, SslPolicyErrors sslPolicyErrors)
{ return true; };
smtpServer.Send(mail);
Debug.Log("success");
}
[/code]

Behavior Tree 개념 및 동작

출처: http://lifeisforu.tistory.com/327 [그냥 그런 블로그]

개요


이 문서는 Beahvior Tree( 이하 BT ) 의 세부적인 구현이나 노드들에서 다루기 위해서 작성된 것이 아니라 전반적인 개념 및 흐름을 정리하기 위해서 작성되었습니다. 그러므로 BT 의 세부적인 동작 방식들에 대해 알고 싶으시다면 가마수트라의 [ Behavior trees for AI: How they work ][ 4 ] 를 읽어 보시기 바랍니다

개념


BT 를 이야기하기 위해서는 유한 상태 기계( Finite State Machines, 이하 FSM )에 대해서 언급하지 않고 넘어 갈 수 없습니다.

FSM 은 특정 유형의 로직을 제공합니다. 이는 상태( state )와 전이( transition )으로 구성됩니다. 상태는 동시에 실행되는 행동( action )의 집합입니다. 행동의 예를 들면 애니메이션, 사운드, 특정 시간동안 대기 등을 들 수 있습니다. 전이는 조건( condition )을 포함합니다. 전이의 조건이 충족되면, 상태는 다른 상태로 이동하게 됩니다.

게임에서 이러한 FSM 은 애니메이션 상태를 전환하는 데 많이 사용됩니다. 이러한 FSM 의 한 예는 Unity3D 의 메카님 스테이트 머신( Mechanim State Machine )입니다. 이것을 사용하면 한 애니메이션에서 다른 애니메이션으로 전환되는 로직을 쉽게 작성할 수 있습니다[ 5 ].

출처 : [ 4 ]

게다가 비주얼 디버깅( visual debugging )도 매우 쉽습니다. 현재 상태를 보여주기 때문입니다.

출처 : [ 5 ]

하지만 이러한 상태들이 매우 많아지게 되면 노드가 매우 복잡해집니다.

그렇기 때문에 상태를 계층화( 혹은 그룹화)하는 계층적 유한 상태 기계( Hierarchical Finite State Machines, 이하 HFSM )라는 개념이 등장했습니다[ 3 ].

출처 : [ 3 ]

FSM 은 서로 다른 문맥을 가진 로직을 재사용할 수 있는 방법을 제공하지 않지만, HFSM 은 FSM 들을 그룹화하고 계층화함으로써 특정 문맥을 가진 상태를 재사용할 수 있게 해 줍니다. 그리고 FSM 이 그렇듯이 현재의 문맥( 상위 상태 )을 파악하기도 쉽습니다. 그래서 최근까지 게임 AI 에서 많이 사용되던 방식입니다.

그런데 이 HFSM 도 문제가 있습니다. HFSM 이 어느 정도의 확장성을 가지기는 하지만, ( 하위 ) 상태를 모듈화하는 기능을 제공하지는 않습니다. 예를 들어 같은 상태를 다른 문맥에서 사용할 수는 없습니다. 왜냐하면 특정 상태에서 전이되어야 한다는 조건이 붙어 있기 때문입니다.

좀 더 실용적인 예를 들어 보도록 하겠습니다. 여러분이 “걷기” 상태를 가지고 있다고 합시다. “걷기” 상태는 “전투” 상태의 하위 상태도 될 수 있지만, “추적” 상태의 하위 상태도 될 수 있습니다. 만약 HFSM 을 사용한다면 “전투” 상태에 “걷기” 상태를 추가하고, “추적” 상태에도 “걷기” 상태를 추가해야 합니다. 물론 각 문맥에서의 ( “걷기” 상태로의 ) 전이 조건은 서로 다르겠죠.

그래서 같은 상태를 재작성하지 않고도 다른 목적이나 상황에 따라 상태를 재사용할 수 있도록 하기 위한 목적을 가지고 행동트리( Behavior Tree )라는 것이 생겨났습니다[ 1 ].

BT 는 로직을 캡슐화함으로써 상태의 모듈성을 증가시킵니다. 예를 들면 내포된 상태( 하위 상태 )를 만드는 것이죠. 이는 HFSM 에서도 제공하고 있습니다만, 전이라는 것이 존재하지 않는다는 차이점을 가집니다. 그래서 상태는 그 자체로서 존재할 수 있습니다.

출처 : [ 1 ]

Behaviour Tree 작동 원리


이 부분은 자료구조에 대한 이해가 필요합니다. 일반적으로 BT 를 구현하기 위해서는 스택( Stack )이라는 자료구조를 사용하게 됩니다. 이것은 전형적인 후입선출( Last In First Out ) 방식의 자료구조입니다. 이를 간단하게 도식화하면 다음과 같습니다.

출처 : [ 6 ]

스택에 대해서 언급한 이유는 나중에 언급할 BT 노드들이 동작하는 방식을 이해하는 기반이 되기 때문입니다.

BT 는 태스크( Task ) 집합으로 구성됩니다. FSM 류에서는 행동 집합을 상태라고 하고 상태가 다른 상태로 넘어 갈 수 있는 방향 및 조건을 지정하는 것을 전이라 표현했습니다. 하지만 BT 에서는 모든 것을 노드로 표현합니다.

BT 구현에 따라서 조금씩 다르지만 태스크의 종류는 크게 Composite, Decorator, Condition, Action 으로 나뉩니다. Action 은 단말 태스크로서 FSM 의 행동 집합으로써의 상태에 가깝다고 보시면 됩니다. 보통 태스크와 노드( node )라는 용어를 같은 의미로 사용하는 경우가 많으므로 헷갈리지 않기를 바랍니다.

Action task

Action task 는 실제 행동을 표현하는 단말 노드입니다. 이것은 항상 true 나 false 를 반환하게 되어 있습니다. 일반적으로는 Action.OnStart(), Action.OnUpdate(), Action.OnEnd() 같은 메서드를 가지고 있는데, Action.OnUpdate() 에서 true 나 false 를 반환하면 그 Action 의 작업이 끝납니다. 메서드의 이름은 구현마다 다를 수 있습니다.

스택에 처음 올라갈 때 OnStart() 가 불리고, true 나 false 를 반환하지 않으면 계속해서 OnUpdate() 가 불립니다. 그러다가 true 나 false 가 반환되면 스택에서 빠지면서 OnEnd() 가 불립니다. 어떤 구현들( UE4, ParadoxNotations 의 NodeCanvas 등 )에서는 EndAction() 과 같은 메서드를 명시적으로 호출해서 Action 을 끝내기도 하고, 어떤 구현들( BehaviorDesigner 등 )에서는 true, false, running 과 같은 반환값을 기반으로 Action 이 끝났는지 판단하기도 합니다.

Composite task

Composite task 는 우리말로 하면 복합 태스크입니다. 이것은 말 그대로 ( 하나 이상의 ) 여러 개의 자식으로 구성된 태스크입니다. 자주 사용되는 Composite 으로는 Select, Sequence 등이 있습니다. 이러한 Composite 의 핵심 용도는 node 의 flow 를 제어하는 것입니다.

기본적으로 node 의 실행 순서는 위에서 아래로, 왼쪽에서 오른쪽으로입니다.

Select composite자식 노드가 true 를 반환할 때까지 자식 노드들을 실행합니다. 말 그대로 하나를 선택하는 것이죠. 참고로 스샷은 ParadoxNotations 의 NodeCanvas 의 스샷입니다.

위의 Select 를 스택 구조로 도식화하면 다음과 같습니다. 그림이 복잡해지는 것을 방지하기 위해서, OnStart() 에서 바로 EndAction() 을 호출했다고 가정합니다.

다른 것들도 마찬가지로 동작하므로 스택 구조로 도식화하는 것은 여기까지만 하도록 하겠습니다.

Sequence composite 는 자식 노드가 false 를 반환할 때까지 자식 노드들을 실행합니다. 말 그대로 순차적 실행입니다.

이것들을 잘 조합하면 다양한 로직을 구성할 수 있습니다.

Conditional Aborts

BT 의 단말 노드에 존재하는 Action 이 true 나 false 를 반환하지 않으면 계속해서 그 작업에 머물러 있게 됩니다. 그 Action 의 OnUpdate() 메서드 내부에서 종료 조건을 판단할 수 있으면 좋겠지만 외부에서 강제적으로 그 Action 의 실행을 중단시키고 싶을 수 있습니다.

예를 들어 “추적” 이라는 Action 은 일반적으로 내부에서 추적이 완료되었는지 여부를 판단하고 있을 것입니다. 예외적인 조건 판단까지 그 Action 에 넣어 버리면 너무 복잡해지고, 다른 Action 에 대한 종속성을 가지게 될 것입니다. 이럴 경우에 “추적” Action 을 취소시킬 수 있는 방법이 있다면 좋을 것입니다. 그런 방법을 조건부 취소( Conditional Aborts )라 부릅니다. 어떤 구현에서는 평가를 재활성화한다( Reactive Evaluation )고 합니다.

조건부 취소는 실행 흐름에 영향을 주게 되므로 Composite 에 기능이 내장되어 있습니다. 어떤 변수를 계속 감시하고 있다가 변수의 값이 바뀌게 되면 지금의 실행 흐름을 취소시키고 자신의 노드로부터 재평가를 하는 것입니다.

Conditional Aborts 는 보통 Self, Lower Priority, Both 로 이루어집니다. Self 는 자신의 하위에 있는 태스크를 취소시키는 것이고, Lower Priority 는 자신의 오른쪽에 있는 이웃 노드의 흐름을 취소시키는 것입니다. 그리고 Both 는 Self + Lower Priority 입니다. 여기에서 Lower Priority 라는 의미를 이해하기 힘든 분이 있을 수 있습니다. Lower 라는 이름이 붙은 이유는 BT 의 실행 흐름이 왼쪽에서 오른쪽으로 이어지기 때문입니다.

간단한 예를 들어 보도록 하겠습니다. 일단 NodeCanvas 의 경우에는 Composite 에 Dynamic 이라는 속성이 있습니다. 이것은 Conditional aborts on Self 를 의미합니다. UE4 나 BehaviorDesigner 는 Self, Lower Priority, Both 를 모두 가지고 있습니다. 어쨌든 계속해서 실행되는 어떤 Action 이 있다고 합시다. 아래 BT 에서는 “B” Action 을 실행한 후에 “Run Forever” 라는 Action 으로 제어가 넘어 갔기 때문에, “B” Action 은 앞으로 절대로 평가되지 않습니다.

그런데 특정 조건이 만족되면 다시 Sequece Composite 를 평가하고 싶다면 어떻게 해야 할까요? 이럴 때 Sequencer 노드를 dynamic 으로 변경하고, 하위에 Condition 노드를 추가해 Conditional Aborts 상황을 만들 수 있습니다. 형태는 다음과 같습니다.

이제 Cancel 이라는 변수에 false 를 할당하면, Sequencer 노드가 이를 감시하고 있다가 “Run Forever” Action 을 취소하고 다시 자신의 노드를 평가합니다. 참고로 취소될 때는 “Run Forever” 의 OnEnd() 가 호출됩니다.

여기에서 “Sequencer 가 첫 번째 노드에서 false 를 반환해서 멈춰버리네?” 라는 의문을 가지는 분이 계실 겁니다. 이런 사태에 대비해서 모든 Action.OnEnd() 안에서 Cancel = true 로 만들어 주는 방법이 있고, Condition 앞에서 true 로 만들어 줄 수도 있습니다. 어떤 방법을 선택하느냐는 취향의 문제입니다. 심지어는 Sequencer.OnUpdate() 에서 true 로 만들어 줘도 되겠죠.

그냥 순차적으로 실행되는 것이라고 생각하면 의미가 모호하지만, 이것의 실행 문맥( 스택이 rewind 된 것임 )을 잘 생각하면 문제가 없습니다.

참고로 NodeCanvas 같은 경우에는 Dynamic Composite 을 계층적으로 사용하면 Both 와 같은 Conditional Aborts 를 처리하는 것도 가능합니다. 그냥 Composite 에서 세 종류를 모두 설정할 수 있었으면 좋았겠지만 그 부분이 아쉽습니다.

Decoration task

Decoration task 는 조건을 의미합니다. Decoration 은 하나의 자식만을 가질 수 있는데, 조건을 만족하면 자식을 실행하고, 조건을 만족하지 못하면 false 를 반환합니다. Decoration 이 지정하는 조건을 만족했을 경우의 반환 결과는 자식의 반환 결과에 의존합니다. 자주 사용하는 Decoration 에는 Probability, TimeOut, CheckEvent 등이 있습니다.

예를 들어 “B” Action 과 “C” Action 의 실행 확률을 결정하고 싶다고 합시다. 그러면 Probability task 를 사용해 다음과 같이 할 수 있습니다.

참고


[ 1 ] Understanding Behavior Trees.
[ 2 ] On Finite State Machines and Reusablility.
[ 3 ] The Gist of Hierarchical FSM.
[ 4 ] Behavior trees for AI: How they work.
[ 5 ] 스테이트 머신 기초.
[ 6 ] Stack Data Structures.

The guide to implementing 2D platformers

http://higherorderfun.com/blog/2012/05/20/the-guide-to-implementing-2d-platformers/comment-page-1/#comments

 

Having previously been disappointed by the information available on the topic, this is my attempt at categorizing different ways to implement 2D platform games, list their strengths and weaknesses, and discuss some implementation details.

The long-term goal is to make this an exhaustive and comprehensible guide to the implementation of 2D platform games. If you have any sort of feedback, correction, request, or addition – please leave it in the comments!

Disclaimer: some of the information presented here comes from reverse engineering the behavior of the game, not from its code or programmers. It’s possible that they are not ACTUALLY implemented in this way, and merely behave in an equivalent way. Also note that tile sizes are for the game logic, graphical tiles might be of a different size.

Four Ways of Implementing

I can think of four major ways in which a platform game can be implemented. From simplest to most complicated, they are:

Type #1: Tile-based (pure)

Character movement is limited to tiles, so you can never stand halfway between two tiles. Animations may be used to create the illusion of smooth movement, but as far as the game logic is concerned, the player is always right on top of a specific tile. This is the easiest way to implement a platform game, but it imposes heavy restrictions on the control of character, making it unsuitable for traditional action-based platformers. It is, however, popular with puzzle and “cinematographic” platformers.

Flashback, shown with tile boundaries

Examples: Prince of Persia, Toki Tori, Lode Runner, Flashback

How it works

The map is a grid of tiles, each one storing information such as whether it’s an obstacle or not, what image to use, what kind of footstep sound to use, and so on. The player and other characters are represented by a set of one or more tiles that move together. In Lode Runner, for example, the player is a single tile. In Toki Tori, the player is 2×2 tiles. In Flashback, which is unusual due to the smaller size of its tiles, the player is two tiles wide and five tiles tall (see image above) when standing, but only three tiles tall when crouching.

In this kind of game, the player will rarely – if ever – be moving diagonally, but, if he is, the movement can be decomposed in two separate steps. Likewise, he will likely only move one tile at once, but multi-tile movement can be done as multiple steps of one tile, if needed (in Flashback, you always move two tiles at once). The algorithm is then as follows:

  1. Create a copy of the character where he’d like to move to (e.g., if moving one tile to the right, make a copy where every tile of the character is shifted 1 tile to the right)
  2. Check that copy for intersection with the background and other characters.
  3. If an intersection is found, the character’s movement is blocked. React accordingly.
  4. Otherwise, the path is clear. Move character there, optionally playing an animation so the transition looks smooth.

This kind of movement is very ill-suited for traditional arc-shaped jumps – so games in this genre often have no jump at all (Toki Tori, Lode Runner), or only allow vertical or horizontal jumps (Prince of Persia, Flashback), which are nothing but special cases of linear movement.

Advantages of this system include simplicity and precision. Since the games are more deterministic, glitches are much less likely, and the gameplay experience is more controlled, with less of a need to tweak values depending on circumstances. Implementing certain mechanics (such as grabbing ledges and one-way platforms) becomes a breeze, compared to more complex movement styles – all you have to do is check whether the player tiles and the background tiles are aligned in the one specific way that allows for a given action.

In principle, this system doesn’t allow steps of less than one tile, but that can be mitigated in a few different ways. For example, the tiles can be a bit smaller than the player (say, a player is 2×6 tiles), or you can allow a visual-only movement to take place inside a given tile, without affecting the logic (which is the solution that I believe that “Lode Runner – The Legend Returns” takes).

Type #2: Tile Based (Smooth)

Collision is still determined by a tilemap, but characters can move freely around the world (typically with 1px resolution, aligned to integers, but see the note at the end of article regarding smoothing of movement). This is the most common form of implementing platformers in 8-bit and 16-bit consoles, and remains popular today, as it is still easy to implement and makes level editing simpler than more sophisticated techniques. It also allows for slopes and smooth jump arcs.

If you’re unsure which type of platformer you want to implement, and you want to do an action game, I suggest going for this one. It’s very flexible, relatively easy to implement, and gives you the most control of all four types. It’s no wonder that the majority of the best action platformers of all time are based on this type.

Mega Man X, shown with tile boundaries and player hitbox.

Examples: Super Mario World, Sonic the Hedgehog, Mega Man, Super Metroid, Contra, Metal Slug, and practically every platformer of the 16-bit era

How it works

Map information is stored in the same way as with the pure tile technique, the difference is merely in how the characters interact with the background. The character’s collision hitbox is now an Axis-Aligned Bounding Box (AABB, that is, a rectangle that cannot be rotated), and are typically still an integer multiple of tile size. Common sizes include one tile wide and one (small Mario, morph ball Samus), two (big Mario, Mega Man, crouched Samus) or three (standing Samus) tiles tall. In many cases, the character sprite itself is larger than the logical hitbox, as this makes for a more pleasant visual experience and fairer gameplay (it’s better for the player to avoid getting hit when he should have than for him to get hit when he should not have). In the image above, you can see that the sprite for X is square-ish (in fact, is two tiles wide), but his hitbox is rectangular (one tile wide).

Assuming that there are no slopes and one-way platforms, the algorithm is straightforward:

  1. Decompose movement into X and Y axes, step one at a time. If you’re planning on implementing slopes afterwards, step X first, then Y. Otherwise, the order shouldn’t matter much. Then, for each axis:
  2. Get the coordinate of the forward-facing edge, e.g. : If walking left, the x coordinate of left of bounding box. If walking right, x coordinate of right side. If up, y coordinate of top, etc.
  3. Figure which lines of tiles the bounding box intersects with – this will give you a minimum and maximum tile value on the OPPOSITE axis. For example, if we’re walking left, perhaps the player intersects with horizontal rows 32, 33 and 34 (that is, tiles with y = 32 * TS, y = 33 * TS, and y = 34 * TS, where TS = tile size).
  4. Scan along those lines of tiles and towards the direction of movement until you find the closest static obstacle. Then loop through every moving obstacle, and determine which is the closest obstacle that is actually on your path.
  5. The total movement of the player along that direction is then the minimum between the distance to closest obstacle, and the amount that you wanted to move in the first place.
  6. Move player to the new position. With this new position, step the other coordinate, if still not done.

Slopes

Mega Man X, with slope tile annotations

Slopes (the tiles pointed by green arrows on the image above) can be very tricky, because they are obstacles, and yet still allow the character to move into their tile. They also cause movement along the X axis to adjust position on the Y axis. One way to deal with them is to have the tile store the “floor y” of either side. Assuming a coordinate system where (0, 0) is at top-left, then the tile just left of X (first slope tile) is {0, 3} (left, right), then the one he stands on is {4, 7}, then {8, 11}, then {12, 15}. After that, the tiles repeat, with another {0, 3}, etc, and then we have a steeper slope, composed of two tiles: {0, 7} and {8, 15}.

Detailed View of the {4, 7} tile

The system that I’m going to describe allows arbitrary slopes, though for visual reasons, those two slopes are the most common, and result in a total of 12 tiles (the 6 described previously, and their mirrorings). The collision algorithm changes as follows for horizontal movement:

  • Make sure that you step X position before Y position.
  • During collision detection (4 above), the slope only counts as a collision if its closest edge is the taller (smaller y coordinate) one. This will prevent characters from “popping” through the slope from the opposite side.
  • You might want to forbid slopes to stop “halfway through” (e.g. on a {4, 7} tile). This restriction is adopted by Mega Man X and many other games. If you don’t, you have to deal with the more complicated case of the player attempting to climb from the lower side of the slope tile – one way to deal with this is to pre-process the level, and flag all such offending tiles. Then, on collision detection, also count it as a collision from the lower side if the player’s lowest y coordinate is greater (that is, below) the tile’s offset edge (tile coord * tile size + floor y).
  • A full obstacle tile adjacent to the slope the character is currently on should not be considered for collision if it connects to the slope, that is, if the character (that is, his bottom-center pixel) is on a {0, *} slope, ignore left tile, and, if on a {*, 0} slope, ignore the right tile. You may have to do this for more tiles if your character is wider than two tiles – you might simply skip checking on the entire row if the player is moving towards the upper side of slope. The reason for this is to prevent the character from getting stuck at those tiles (highlighted yellow above) while still climbing the slope, as his foot will still be below the “surface level” by the time he comes into contact with the otherwise solid tile.

And for vertical movement:

  • If you’re letting gravity do its job for downhill movement, make sure that the minimum gravity displacement is compatible with slope and horizontal velocity. For example, on a 4:1 slope (as {4, 7} above), the gravity displacement must be at least 1/4 of the horizontal velocity, rounded up. On a 2:1 slope (such as {0, 7}), at least 1/2. If you don’t ensure this, the player will move horizontally right off the ramp for a while, until gravity catches up and drags him down, making him bounce on the ramp, instead of smoothly descending it.
  • An alternative to using gravity is to compute how many pixels above floor the player was before movement, and how many it is afterwards (using the formula below), and adjust his position so they’re the same.
  • When moving down, instead of considering a slope tile’s top edge as its collision boundary, instead, compute its floor coordinate at the current vertical line, and use that. To do that, find the [0, 1] value which represents the player’s x position on tile (0 = left, 1 = right) and use it to linearly interpolate the floorY values. The code will look something like:
    1
    2
    float t = float(centerX - tileX) / tileSize;
    float floorY = (1-t) * leftFloorY + t * rightFloorY;
  • When moving down, if multiple tiles on the same Y coordinate are obstacle candidates, and the one on the X coordinate of the player’s center is a slope tile, use that one, and ignore the rest – even though the others are technically closer. This ensures proper behaviour around the edges of slopes, with the character actually “sinking” on a completely solid tile because of the adjacent slope.

One-way platforms

Super Mario World, showing Mario falling through (left) and standing on (right) the same one-way platform

One-way platforms are platforms that you can step on, but you can also jump through them. In other words, they count as an obstacle if you’re already on top of them, but are otherwise traversable. That sentence is the key to understanding their behavior. The algorithm changes as follows:

  • On the x axis, the tile is never an obstacle
  • On the y axis, the tile is only an obstacle if, prior to the movement, the player was entirely above it (that is, bottom-most coordinate of player was at least one pixel above top-most coordinate of one-way platform). To check for this, you will probably want to store the original player position before doing any stepping.

It might be tempting to have it act as an obstacle if the player’s y speed is positive (that is, if the player is falling), but this behavior is wrong: it’s possible for the player to jump so he overlaps the platform, but then falls down again without having his feet reach the platform. In that case, he should still fall through.

Some games allow the player to “jump down” from such platforms. There are a few ways to do this, but they are all relatively simple. You could, for example, disable one-way platforms for a single frame and ensure that y speed is at least one (so he’ll be clear of the initial collision condition on the next frame), or you could check if he’s standing exclusively on one-way platforms, and, if so, manually move the player one pixel to the bottom.

Ladders

Mega Man 7, with tile boundaries, highlighted ladder tiles, and player ladder hitbox.

Ladders might seem complicated to implement, but they are simply an alternate state – when you’re in a ladder, you ignore most of the standard collision system, and replace it with a new set of rules. Ladders are typically one tile wide.

You can usually enter the ladder state in two ways:

  • Have your character hitbox overlap with the ladder, either on ground or on air, and hit up (some games also allow you to hit down)
  • Have your character stand on top of a “ladder top” tile (which is often a one-way platform tile as well, so you can walk on top of it), and hit down.

This has the effect of immediately snapping the player’s x coordinate to align with the ladder tiles, and, if going down from the top of ladder, move y coordinate so player is now inside the actual ladder. At this point, some games will use a different hitbox for the purposes of determining whether the player is still on the ladder. Mega Man, for example, seems to use a single tile (equivalent to top tile of the original character, highlighted in red in the image above).

There are a few different ways of LEAVING the ladder:

  • Reaching the top of the ladder. This will usually prompt an animation and move the player several pixels up in y, so he’s now standing on top of the ladder.
  • Reaching the bottom of a hanging ladder. This will cause the player to simply fall, although some games won’t let the player leave the ladder in this way.
  • Moving left or right. If there is no obstacle on that side, the player may be allowed to leave that way.
  • Jumping. Some games allow you to release the ladder by doing this.
While on the ladder, the character’s movement changes so, typically, all he can do is move up and down, and sometimes attack.

Stairs

Castlevania: Dracula X, with tile boundaries

Stairs are a variation of ladders, seen in few games, but notably in the Castlevania series. The actual implementation is very similar to that of ladders, with a few exceptions:

  • The player moves tile by tile or half-tile by half-tile (as in Dracula X)
  • Each “step” causes the player to be shifted simultaneously on X and Y coordinates, by a preset amount.
  • Initial overlapping detection when going up might look on the tile ahead instead of just the current overlap one.
Other games also have stairs that behave like slopes. In that case, they are simply a visual feature.

Moving Platforms

Super Mario World

Moving platforms can seem a little tricky, but are actually fairly simple. Unlike normal platforms, they cannot be represented by fixed tiles (for obvious reasons), and instead should be represented by an AABB, that is, a rectangle that cannot be rotated. It is a normal obstacle for all collision purposes, and if you stop here, you’ll have very slippery moving platforms (that is, they work as intended, except that the character does not move along it on his own).

There are a few different ways to implement that. One algorithm is as follows:

  • Before anything on the scene is stepped, determine whether the character is standing on a moving platform. This can be done by checking, for example, whether his center-bottom pixel is just one pixel above the surface of the platform. If it is, store a handle to the platform and its current position inside the character.
  • Step all moving platforms. Make sure that this happens before you step characters.
  • For every character that’s standing on a moving platform, figure the delta-position of the platform, that is, how much it has moved along each axis. Now, shift the character by the same amount.
  • Step the characters as usual.

Other Features

Sonic the Hedgehog 2

Other games have more complicated and exclusive features. Sonic the Hedgehog series is notable for this. Those are beyond the scope of this article (and my knowledge, for that matter!), but might be subject of a future article.

Type #3: Bitmask

Similar to “Tile Based (Smooth)”, but instead of using large tiles, an image is used to determine collision for each pixel. This allows finer detailing, but significantly increases complexity, memory usage, and requires something akin to an image editor to create levels. It also often implies that tiles won’t be used for visuals, and may therefore require large, individual artwork for each level. Due to those issues, this is a relatively uncommon technique, but can produce higher quality results than tile-based approaches. It is also suitable for dynamic environments – such as the destructible scenarios in Worms – as you can “draw” into the bitmask to change the scenario.

Worms World Party, featuring destructible terrain

Examples: Worms, Talbot’s Odyssey

How it works

The basic idea is very similar to the tile (smooth) algorithm – you can simply consider each pixel to be a tile, and implement the exact same algorithm, and everything will work, with one major exception – slopes. Since slopes are now implicitly defined by the positioning between nearby tiles, the previous technique doesn’t work, and a much more complex algorithm has to be used in its place. Other things, such as ladders, also become trickier.

Slopes

Talbot’s Odyssey, with the collision bitmask overlaid on top of the game.

Slopes are the primary reason why this type of implementation is very hard to get right. Unfortunately, they are also pretty much mandatory, as it’d make no sense to use this implementation without slopes. Often, they’re the reason why you’re even using this system.

This is, roughly, the algorithm used by Talbot’s Odyssey:

  • Integrate acceleration and velocity to compute the desired delta-position vector (how much to move in each axis).
  • Step each axis separately, starting with the one with the largest absolute difference.
  • For the horizontal movement, offset the player AABB by 3 pixels to the top, so he can climb slopes.
  • Scan ahead, by checking against all valid obstacles and the bitmask itself, to determine how many pixels it is able to move before hitting an obstacle. Move to this new position.
  • If this was horizontal movement, move as many pixels up as necessary (which should be up to 3) to make up for slope.
  • If, at the end of the movement, any pixel of the character is overlaping with any obstacle, undo the movement on this axis.
  • Regardless of result of last condition, proceed to do the same for the other axis.
Because this system has no distinction between moving down because you’re going downhill or because you’re falling, you’re likely to need a system counting how many frames it’s been since the character last touched the floor, for purposes of determining whether it can jump and changing animation. For Talbot, this value is 10 frames.
Another trick here is efficiently computing how many pixels it can move before hitting something. There are other possible complicating factors, such as one-way platforms (dealt in the exact same way as for tiled (smooth)) and sliding down steep inclines (which is fairly complex and beyond the scope of the article). In general, this technique requires a lot of fine tuning, and is intrinsically less stable than tile-based approaches. I only recommend it if you absolutely must have detailed terrain.

Type #4: Vectorial

This technique uses vectorial data (lines or polygons) to determine the boundaries of collision areas. Very difficult to implement properly, it is nevertheless increasingly popular due to the ubiquity of physics engines, such as Box2D, which are suitable for implementing this technique. It provides benefits similar to the bitmask technique, but without major memory overhead, and using a very different way of editing levels.

Braid (level editor), with visible layers (top) and the collision polygons (bottom)

Examples: Braid, Limbo

How it works

There are two general ways of approaching this:

  • Resolve movement and collisions yourself, similar to the bitmask method, but using polygon angles to compute deflection and have proper slopes.
  • Use a physics engine (e.g. Box2D)

Obviously, the second is more popular (though I suspect that Braid went for the first), both because it is easier and because it allows you to do many other things with physics in the game. Unfortunately, in my opinion, one has to be very careful when going this route, to avoid making the game feel like a generic, uninteresting physics-platformer.

Compound objects

This approach has its own unique problems. It may suddenly be difficult to tell whether the player is actually standing on the floor (due to rounding errors), or whether it’s hitting a wall or sliding down a steep incline. If using a physics engine, friction can be an issue, as you’ll want friction to be high on the foot, but low on the sides.

There are different ways to deal with those, but a popular solution is to divide the character into several different polygons, each with different roles associated: so you’d (optionally) have the main central body, then a thin rectangle for feet, and two thin rectangles for sides, and another for head or some similar combination. Sometimes they are tapered to avoid getting caught into obstacles. They can have different physics properties, and collision callbacks on those can be used to determine the status of character. For more information, sensors (non-colliding objects that are just used to check for overlap) can be used. Common cases include determinining whether we’re close enough to the floor to perform a jump, or if the character is pushing against a wall, etc.

General Considerations

Regardless of the type of platform movement that you have chosen (except perhaps for type #1), a few general considerations apply.

Acceleration

Super Mario World (low acceleration), Super Metroid (mid acceleration), Mega Man 7 (high acceleration)

One of the factors that affects the feel of a platformer the most is the acceleration of the character. Acceleration is the rate of change in speed. When it is low, the character takes a long time to reach its maximum velocity, or to come to a halt after the player lets go of controls. This makes the character feel “slippery”, and can be hard to master. This movement is most commonly associated with the Super Mario series of games. When the acceleration is high, the character takes very little (or no time) to go from zero to maximum speed and back, resulting in very fast responding, “twitchy” controls, as seen in the Mega Man series (I believe that Mega Man actually employs infinite acceleration, that is, you’re either stopped or on full speed).

Even if a game has no acceleration on its horizontal movement, it is likely to have at least some for the jump arcs – otherwise they will be shaped like triangles.

How it works

Implementing acceleration is actually fairly simple, but there are a few traps to watch out for.

  • Determine xTargetSpeed. This should be 0 if the player is not touching the controls, -maxSpeed if pressing left or +maxSpeed if pressing right.
  • Determine yTargetSpeed. This should be 0 if the player is standing on a platform, +terminalSpeed otherwise.
  • For each axis, accelerate the current speed towards target speed using either weighted averaging or adding acceleration.
The two acceleration methods are as follows:
  • Weighted averaging: acceleration is a number (“a”) from 0 (no change) to 1 (instant acceleration). Use that value to linearly interpolate between target and current speed, and set the result as current speed.
1
2
3
vector2f curSpeed = a * targetSpeed + (1-a) * curSpeed;
if (fabs(curSpeed.x) < threshold) curSpeed.x = 0;
if (fabs(curSpeed.y) < threshold) curSpeed.y = 0;
  • Adding acceleration: We’ll determine which direction to add the acceleration to (using the sign function, which returns 1 for numbers >0 and -1 for <0), then check if we overshot.
1
2
3
4
5
6
7
vector2f direction = vector2f(sign(targetSpeed.x - curSpeed.x),
                              sign(targetSpeed.y - curSpeed.y));
curSpeed += acceleration * direction;
if (sign(targetSpeed.x - curSpeed.x) != direction.x)
    curSpeed.x = targetSpeed.x;
if (sign(targetSpeed.y - curSpeed.y) != direction.y)
    curSpeed.y = targetSpeed.y;
It’s important to integrate the acceleration into the speed before moving the character, otherwise you’ll introduce a one-frame lag into character input.
When the character hits an obstacle, it’s a good idea to zero his speed along that axis.

Jump control

Super Metroid, Samus performing the “Space Jump” (with “Screw Attack” power-up)

Jumping in a platform game can be as simple as checking if the player is on the ground (or, often, whether he was on the ground anytime on the last n frames), and, if so, giving the character an initial negative y speed (in physical terms, an impulse) and letting gravity do the rest.

There are four general ways in which the player can control the jump:

  • Impulse: seen in games such as Super Mario World and Sonic the Hedgehog, the jump preserves the momentum (that is, in implementation terms, the speed) that the character had before the jump. In some games, this is the only way to influence the arc of the jump – just like in real life. There is nothing to implement here – it will be like this unless you do something to stop it!
  • Aerial acceleration: that is, retaining control of horizontal movement while in mid-air. Though this is physically implausible, it is a very popular feature, as it makes the character much more controllable. Almost every platformer game has it, with exceptions for games similar to Prince of Persia. Generally, the airborne acceleration is greatly reduced, so impulse is important, but some games (like Mega Man) give you full air control. This is generally implemented as merely tweaking the acceleration parameter while you’re airborne.
  • Ascent control: another physically implausible action, but very popular, as it gives you much greater control over the character. The longer you hold the jump button, the higher the character jumps. Typically, this is implemented by continuing to add impulse to the character (though this impulse can incrementally decrease) for as long as the button is held, or alternatively by suppressing gravity while the button is held. A time limit is imposed, unless you want the character to be able to jump infinitely.
  • Multiple jumps: once airborne, some games allow the player to jump again, perhaps for an unlimited number of times (as in the Space Jump in Super Metroid or the flight in Talbot’s Odyssey), or for a limited number of jumps before touching the ground (“double jump” being the most common choice). This can be accomplished by keeping a counter that increases for each jump and decreases when you’re on the ground (be careful when you update this, or you might reset it right after the first jump), and only allowing further jumps if the counter is low enough. Sometimes, the second jump is shorter than the initial one. Other restrictions may apply – the Space Jump only triggers if you’re already doing a spin jump and just began to fall.

Animations and leading

Black Thorne, character doing a long animation before shooting backwards (Y button)

In many games, your character will play an animation before actually performing the action you requested. However, on a twitchy action-based game, this will frustrate players – DON’T DO THAT! You should still have leading animations for things such as jumping and running, but if you care about how the game responds, make those cosmetic only, with the action taken immediately regardless of the animation.

Smoother movement

Using integers to represent the position of the characters is wise, as it makes it faster and stable. However, if you use integers for everything, you will end up with some jerky motion. There are multiple solutions to this. These are a few:

  • Use a float for all computations and for storing position, and cast to int whenever you’re rendering or computing collisions. Fast and simple, but it starts losing precision if you move too far away from (0,0). This is probably not relevant unless you have a very large playfield, but it’s something to keep in mind. If it comes to it, you can use a double instead.
  • Use a fixed point number for all computations and position, and again cast to int when you’re rendering or computing collisions. Less precise than float and with a more limited range, but the precision is uniform and can, on some hardware, be faster (notably, floating point processing is slow on many mobile phones).
  • Store position as an integer, but keep a “remainder” stored in a float. When integrating position, compute the delta-movement as a float, add the remainder to the delta-movement, then add the integer part of this value to the position, and the fractional part to the “remainder” field. On the next frame, the remainder will get added back in. The advantage of this method is that you’re using an integer everywhere except for movement, ensuring that you won’t have floating point complications elsewhere, and increasing performance. This technique is also very suitable if you have some framework in which the position of the object has to be an integer, or where it is a float, but that same position is used directly by the rendering system – in that case, you can use the framework-provided float position to store integer values only, to make sure that the rendering is always aligned to pixels.

unity pool script

gameobjectpool

 

[code language=”cpp”]
using System.Collections;
using System.Collections.Generic;
/*
* Usage
*
* CGameObjectPool<GameObject> monster_pool;
* …
*
* // Create monsters.
* this.monster_pool = new CGameObjectPool<GameObject>(5, () =>
{
GameObject obj = new GameObject("monster");
return obj;
});

// Get from pool
GameObject obj = this.monster_pool.pop();

// Return to pool
this.monster_pool.push(obj);
* */

public class CGameObjectPool<T> where T : class
{
// Instance count to create.
short count;
public delegate T Func();
Func create_fn;

// Instances.
Stack<T> objects;

// Construct
public CGameObjectPool(short count, Func fn)
{
this.count = count;
this.create_fn = fn;
this.objects = new Stack<T>(this.count);
allocate();
}

void allocate()
{
for (int i=0; i<this.count; ++i)
{
this.objects.Push(this.create_fn());
}
}

public T pop()
{
if (this.objects.Count <= 0)
{
allocate();
}

return this.objects.Pop();
}

public void push(T obj)
{
this.objects.Push(obj);
}
}
[/code]

Android, MVC, MVVM, MVP

원본링크(Android 와 개발 패턴 1부)

코드를 작성해 가는데 있어서 많은 개발자들은 일관성을 유지하고 유지보수성을 높일 수 있는 많은 개발 모델들을 생각해 왔습니다. 특히나 협업하는 과정에서 로직과 View 를 다루는 코드가 뒤섞이게 되면 작성자뿐만 아니라 동료들조차도 유지보수 하기 힘들어지는 모습을 쉽게 볼 수 있습니다.

이러한 코드 작성때문에 팀단위로, 프로젝트 단위로, 때로는 회사 단위로 여러가지 정책을 가지고 코드와 개발 모델들을 일관되게 하려고 많은 노력을 합니다. 이러한 노력에 개발자들 사이에서 많이 통용되는 개발 패턴들이 나오게 되었습니다.

대표적으로 MVC 모델이라고 할 수 있습니다. 필자가 과거에 했던 웹 프로젝트 중 SpringMVC 프레임워크는 외부로부터의 요청을 처리하는 Controller, 실질적인 비지니스 로직을 수행하는 Model, 그리고 화면 처리를 담당하는 View 를 구분할 수 있도록 지원되어 많은 개발자들에게 사랑받고 있는 프레임워크 중 하나입니다.

차츰 View 자체에서 처리해야하는 로직이 복잡해짐에 따라 MVVM과 MVP 패턴이 나오면서 View 내에서도 Logic과 Presenter 를 구분하려는 노력이 끊임없이 나왔습니다.

이외에도 많은 개발 패턴들이 있지만 가장 많이 통용되는 이야기를 하고자 합니다.

초창기 안드로이드 개발 코드의 모습

안드로이드에서도 초창기 부터 이러한 노력이 끊임없이 나왔습니다. MVC 와 같은 개발 패턴에 익숙해져 있던 많은 개발자들은 안드로이드에도 이와 같은 모습을 적용하려고 노력하였습니다.

다음 코드는 일반적으로 처음 안드로이드를 접하는 사람들이 쓰는 코드들입니다.

[code language=”java”]
public class MainAcivity extends Activity
{

@Override
public void onCreate( Bundle saveInstance )
{
super.onCreate( saveInstance );
setContent( R.layout.main );

TextView textView = ( TextView ) findViewById( R.id.btn_confirm );
textView.setText( "Non-Clicked" );

findViewById( R.id.btn_confirm ).setOnClickListener( new View.OnClickListener()
{

@Override
public void onClick( View view )
{
TextView textView = ( TextView ) findViewById( R.id.btn_confirm );
textView.setText( getClickedText() );
}
} );
}

String getClickedText()
{
return "Clicked!!!";
}

}
[/code]

Activity 내에 이벤트를 핸들링하는 처리나 뷰에 접근하는 코드들이 모두 있습니다.

 

이러한 코드들의 모습은 서버기반 동작시엔 하나의 Activity 내에 네트워크 처리를 위한 쓰레드 처리까지 하게되는 등 코드가 커지면 커질수록 가독성도 떨어지며 유지보수가 힘들어지는 코드로 가기 쉬워집니다.

그래서 기존의 웹에서처럼 좀 더 기능별로 분할하여 코드들을 간결하고 유지보수가 쉬워지도록 하기 위한 방법들이 많이 도입되기 시작하였습니다.

나은 코드들을 위한 패턴들

하지만 화면이 점점 복잡해지게 되고 점점 View 에 의해 제어되는 로직들이 많아짐에 따라 이를 분리하고하는 노력들이 나왔습니다.

다음은 웹 서비스 개발자들에게 가장 쉽게 사용되었던 MVC 패턴을 적용한 코드입니다.

[code language=”java”]
public class MainAcivity extends Activity
{
private MainModel mainModel;

@Override
public void onCreate( Bundle saveInstance )
{
super.onCreate( saveInstance );
setContent( R.layout.main );

mainModel = new MainModel();

TextView textView = ( TextView ) findViewById( R.id.btn_confirm );
textView.setText( "Non-Clicked" );

findViewById( R.id.btn_confirm ).setOnClickListener( new View.OnClickListener()
{

@Override
public void onClick( View view )
{
String text = mainModel.getClickedText();
TextView textView = ( TextView ) findViewById( R.id.btn_confirm );
textView.setText( mainModel.getClickedText() );
}
} );
}
}
[/code]

[code language=”java”]
public class MainModel
{
public String getClickedText()
{
return "Clicked!!!";
}
}
[/code]

View 에 상관없는 로직을 MainModel 로 분리를 하였기 때문에 Activity 는 View 와 Click Event 를 처리하는 모습으로 변화되었습니다.

하지만 Click Event 와 View 에 대한 처리가 함께 있는 것을 유심히 생각해볼 필요가 있습니다. MVC 모델에서 Controller 는 View 에 대한 처리를 직접 하는 것이 아니라 View 에 대한 정보만을 View 에 전달함으로써 화면을 그리는 View 와 동작을 처리하는 로직을 분리하고자 하는데서 시작되었습니다.

헌데 Controller 의 역할을 수행하는 Activity 에서 View 에 대한 직접적인 조작을 수행하는 것은 MVC 모델에 어긋나는 모습을 보여주게 됩니다.

이는 Android 에서 Activity(Fragment) 가 View 와 Controller 두가지의 특성을 모두 가지고 있기 때문에 View 나 Controller 를 한쪽으로 빼게 될 경우 View 에 대한 바인딩이나 처리에서 중복 코드나 일관성을 잃어버리는 코드를 작성할 수 있기 때문입니다. 이를 개선하기 위해서 MVVM 이란 패턴을 적용해봤습니다.

[code language=”java”]
public class MainAcivity extends Activity
{

private MainViewModel mainViewModel;

@Override
public void onCreate( Bundle saveInstance )
{
super.onCreate( saveInstance );
setContent( R.layout.main );

mainViewModel = new MainViewModel( MainActivity.this );

}

}
[/code]

[code language=”java”]
public class MainModel
{

public String getClickedText()
{
return "Clicked!!!";
}

}
[/code]

[code language=”java”]
public class MainViewModel
{

private Activity activity;
private MainModel mainModel;
private TextView textView;

public MainViewModel( Activity activity )
{
this.activity = activity;
this.mainModel = new MainModel();
initView( activity );
}

private void initView( Activity activity )
{

textView = ( TextView ) activity.findViewById( R.id.btn_confirm );
textView.setText( "Non-Clicked" );

activity.findViewById( R.id.btn_confirm ).setOnClickListener( new View.OnClickListener()
{

@Override
public void onClick( View view )
{
String text = mainModel.getClickedText();
textView.setText( text );
}
} );
}

}
[/code]

ViewModel 로 View 에 대한 처리가 분리되었음을 볼 수 있습니다.

하지만 안드로이드에서 MVVM이 가지는 문제점은 View 에 대한 처리가 복잡해질수록 ViewModel 에 거대해지게 되고 상대적으로 Activity 는 아무런 역할도 하지 않는 형태의 클래스로 변모하게 됩니다.

Controller 의 성격을 지닌 Activity 가 실질적으로 아무런 역할을 하지 못하고 ViewModel 에 치중된 모습을 보여줌으로써 다른 형태의 Activity 클래스를 구현한 꼴이 되어버리는 것입니다.

MainViewModel 에 있는 로직을 다시 Activity 로 롤백한다하면 다시 MVC 가 가지고 있는 문제점을 가지게 되는 아이러니한 모습을 가지게 됩니다.

다음은 이러한 View – Model – Controller 의 모습을 명확히 구분하고자 나온 MVP 모델을 보도록 하겠습니다.

[code language=”java”]
public interface MainPresenter
{

void setView( MainPresenter.View view );

void onConfirm();

public interface View
{
void setConfirmText( String text );
}

}
[/code]

[code language=”java”]
public class MainAcivity extends Activity implements MainPresenter.View
{

private MainPresenter mainPresenter;

private Button confirmButton;

@Override
public void onCreate( Bundle saveInstance )
{
super.onCreate( saveInstance );
setContent( R.layout.main );

mainPresenter = new MainPresenterImpl( MainActivity.this );
mainPresenter.setView( this );

confirmButton = ( Button ) findViewById( R.id.btn_confirm );
confirmButton.setOnClickListener( new View.OnClick()
{
@Override
public void onClick( View view )
{
mainPresenter.onConfirm();
}
} );
}

@Override
public void setButtonText( String text )
{
confirmButton.setText( text );
}
}
[/code]

[code language=”java”]
public class MainModel
{

public String getClickedText()
{
return "Clicked!!!";
}

}
[/code]

[code language=”java”]
public class MainPresenterImpl implements MainPresenter
{

private Activity activity;
private MainPresenter.View view;

public MainPresenterImpl( Activity activity )
{
this.activity = activity;
this.mainModel = new MainModel();
}

@Override
public void setView( MainPresenter.View view )
{
this.view = view;
}

@Override
public void onConfirm()
{
if( view != null )
{
view.setConfirmText( mainModel.getClickedText() );
}
}

}
[/code]

MVP 모델의 구분은 다음과 같다.

  1. View 는 실제 view 에 대한 직접적인 접근을 담당한다.
  2. view 에서 발생하는 이벤트는 직접 핸들링하나 Presenter 에 위임하도록 한다.
  3. Presenter 는 실질적인 기능을 제어하는 곳으로써 ViewController 로써 이해하면 쉽다.
  4. Model 은 비지니스 로직을 실질적으로 수행한다.

Presenter : View 는 1:1 로 매칭하며 View Presenter 가 주요 기능을 관장하되 실제 view 에서 발생하는 이벤트는 Presenter (이벤트 : View -> Presenter) 로 전달하여 처리하도록 하고 다시 처리된 결과는 Presenter 가 View 에 전달하도록 하여 처리한다. (처리 결과 표현 : Presenter -> View)

정리

MVC
외부의 모든 이벤트를 Controller(Activity) 에서 처리하되 View 에 관여는 하지 않는 것이 원칙입니다. 하지만 Activity 의 특성상 View 관여하지 않을 수 없습니다. 결국 Android 에서는 MVC 의 구조를 계속적으로 유지하기에는 무리가 있습니다.

MVVM
ViewModel 이 뷰와의 상호작용 및 제어에 집중합니다. ViewModel 에서 직접 뷰의 이벤트를 처리하기 때문에 Controller 의 역할도 함께 수행하게 되어 점점 코드가 집중 되는 구조가 될 수 있습니다. 또한 초기화와 외부 이벤트(뷰에 의한 것이 아닌 이벤트)를 제외 하고는 Activity 의 역할이 모호해지게 됩니다.

MVP
View 에 대한 직접적인 접근이 요구되는 Android 의 Activity 는 직접적인 view 접근은 Activity 가 하도록 하고 이에 대한 제어는 Presenter 가 하도록 하고 있다.

어느 것이 낫다라고 말하기에는 어려운 단계입니다. 하지만 많은 개발자들이 안드로이드에서는 MVC 자체의 모습보다는 MVVM 이나 MVP 가 가장 적합하다는 말을 많이 하고 있습니다. 이는 Activity 가 View 를 포함한 클래스이기 때문에 나타나는 현상이라고 볼 수 있습니다.

참고 블로그

MVC, MVP, MVVM 의 이해 – 이항희

MVC, MVP AND MVVM – tomyrhymond