다음팟 인코더 사용법

다음팟 인코더는 공짜이며, 인코딩만 하지 않고 편집도 가능해서 좋다. 단지 사용법 설명이 좀 부족하다. 이런 분야 프로그램 사용법은 대동소이하다. 가장 골치 아픈 것이 코덱을 선택하는 것이다. 

인코딩 화면은 동영상 파일을 재생 기기와 여러 제약 조건에 맞게 다시 인코딩할 때 사용한다. 그러니까 파일 형식 변환이라고 보면 된다. 여기선 기기와 제약 조건만 선택하면 알아서 코덱과 기타 필요한 설정을 해 준다. 기계의 화면 사이즈 한계가 있고, CPU의 처리 속도, 시스템의 용량 제한, 인터넷의 전송 속도 제한, 시스템에 따라 지원하는 코덱이 다르기 때문에 거기에 맞게 화면 크기와 코덱을 조절해야 한다. 이걸 미리 해 놓았다고 프리셋이라고 부른다. 프리셋을 선택하고 인코딩만 하면 된다.

동영상 편집 화면은 재료 동영상들에서 필요한 부분을 잘라 삽입하여 조립하는 방식과 원본 동영상에서 필요 없는 부분을 잘라 제거하는 방식으로 편집이 가능하다. 하나의 원본을 분할하거나 필요 없는 부분을 잘라 내기 할 때는 코덱을 바꿀 이유가 없기 때문에 Direct Stream Copy로 설정하면 처리 시간이 아주 빠르다. 이건 데이터를 그대로 복사하는 것이다. 그런데 형식이 다른 동영상을 묶어 하나로 만들 때는 화면 크기와 코덱을 하나로 통일 시켜야 하기 때문에 인코딩 설정을 해 주어야 한다. 기타 자막도 넣고(이미지로 박아 넣는다), 로고도 넣고, 오프닝, 엔딩 문구도 넣을 수 있다. 이런 것은 시행착오로 해 보면 되니까.

코덱을 선택하고 옵션을 조절하는 화면이다. 여기선 각 옵션을 다 이해하기 어렵다. 그래서 몇 가지 상식만 설명한다. 

포장형식 = 파일 형식 = 파일 확장자

영상, 소리, 자막(Text) 3가지를 포장하는 형식을 말한다. 코덱은 영상, 소리를 압축하는 방식이기 때문에 포장 형식 안에서 다양하게 선택할 수가 있다. 예를 들어 확장자가 AVI인 포장 형식에서도 비디오 코덱은 MPEG4, DivX, Xvid 등으로 선택할 수가 있다. 오디오 코덱은 비디오 코덱과 별개이다. 

코덱 = 압축 방식

이런저런 놈들이 여러 코덱을 만들어서 어지럽다. 품질과 압축률의 절묘한 조화를 얻기 위해서 많은 사람의 노력이 있었다. 각 코덱에서 상세 옵션을 또 선택할 수가 있다. 이건 코덱에 대한 상세한 지식이 있어야 조절 가능하기 때문에 건드리기 좀 그렇다. 코덱을 바꾸지 않고 원본의 내용을 그대로 잘라 복사하려면 무조건 Direct Stream Copy로 설정한다.

화면의 가로, 세로 크기와 종횡비

기계에 따라 화면의 가로, 세로 크기가 다르고, 또한 화면 종횡비가 다르다. 이 때문에 좌우상하가 잘리기도 하고 억지로 늘려서 퍼져 보이거나 길어 보이기도 한다. 이것을 맞추는 방법이 다양하다. 보통 화면 종횡비는 유지하고 상하, 좌우 중에 어느 하나를 맞춘다. 화면 종횡비는 다음과 같은 것이 많이 쓰인다.

• 4:3 옛날 TV와 모니터
• 16:9 일본 Wide TV, HDTV
• 16:10 = 8:5 황금비 모니터
• 14:10 = 7:5 복사용지 비율

화면 설정(가로 세로 지정)

이 부분 메뉴가 참 이해하기 어렵다. 이걸 이해하는 방법은 2가지 길이 있다.

1. 프로그램이 작업하는 순서를 아는 것.
2. 최종 결과물의 조합을 아는 것.

프로그램이 작업하는 순서는 이렇다.

1. 원본 화면을 잘라내기에서 지정한 비율로 자른다.
2. 원본 화면 비율을 유지할 경우 가로/세로 중 한 쪽 기준으로 결과 화면에 맞춘다.
3. 원본 화면 비율을 무시할 경우 가로/세로 모두 결과 화면에 맞춘다. (디폴트)

나머지 옵션 선택은 무의미하다. 차이를 모르겠다.

최종 결과물의 조합은 위와 같은 경우 외엔 없다. 이걸 왜 깔끔하게 정리하지 못 하지? 최종 화면 크기를 지정하면 디폴트가 거기에 맞게 확대/축소이기 때문에 확대/축소 옵션 선택이 무의미하다. 잘라내기 옵션만 의미가 있는데 잘라낸 후에 어떻게 확대/축소할 것인지는 원본 화면 비율 유지/무시 옵션에 따른다. 보통 잘라내기를 할 경우는 당연히 최종 화면 비율과 자르기 비율을 일치시킨다. (물론 다르게 한 후에 확대/축소할 수도 있다.)

유명한 코덱의 종류(압축률 vs 화질)

대체로 많이 쓰는 코덱이 MPEG4인데 이건 H264와 같은 것이고 AVC라고 이름 붙어도 같은 것이다. 같은 기술에 이름만 다른 것이다. DivX는 유료 코덱이고 이것에 대항한 오픈 소스 무료 코덱이 Xvid이다. 철자 순서도 반대다. 유료 코덱은 안 되는 시스템이 있다는 의미다. 오디오 코덱은 MPEG3, AAC가 유명하겠다. 코덱의 성능을 비교할 정도의 지식이 없으니까 알아서 선택한다.

비트전송률 = 전송속도 → 화질/음질

1초에 몇 비트를 전송하는지에 대한 내용이다. 이건 유선, 무선 전송로의 성능과 CPU등의 성능과 관계 있다. 이건 고정(CBR)과 가변(VBR)이 있다. 장단점이 있다.

CBR : 내용이 많든 적든 1초에 최대 전송 양을 제한 한다. 대신 최종 용량을 예측할 수 있다. CD/DVD에 담아야 한다면 용량 예측이 필요하다. 이건 기존 동영상의 설정 값을 참고하거나 실험을 좀 해 봐야 한다. 화면이 넓고, 화질이 좋으며, 프레임률이 높으면 전송률도 높아야 한다.

VBR : 내용에 따라 많이 보내고 적게 보내기 때문에 효율적이다. 대신 최종 용량을 예측하기 어렵다. 화질 기준으로 정해야 하는데 80%는 되어야 원본과 비슷한 수준을 유지한다. 이 옵션으로 하면 원본과 비슷한 화질에 비슷한 용량으로 인코딩 된다.

※ 최대 전송량 계산
주요 화면에서 색상 깊이 24bit(JPEG YRB 8bit), 25Hz(PAL)에서 압축하지 않을 때

화면	가로	세로	색	Hz	kbps
모니터(4:3)	640	480	24	25	18만4320
HDTV(16:9)	1280	720	24	25	55만2960
HDTV(16:9)	1920	1080	24	25	124만4160

여기에 JPEG 압축률을 곱하거나 원본 영상으로 계산한 압축률을 곱한다.
무손실 압축률 : 약 50%(음악), 그림의 경우는 더 압축률이 높다.
유손실 압축률 : 약 10%(JPEG), 동영상의 경우는 더 압축률이 높다.
※ 받침이 없거나 ㄴ 받침이 있는 명사의 뒤에는 ~율, 그 외는 ~률

프레임률(Frame Rate) → 부드러운 동작

1초에 몇 장의 그림을 보여줄 것인지에 대한 내용이다. 이건 전통적으로 다음과 같은 경우가 많다. 애니메이션이나 영화는 이보다 작은 프레임률이다.

• 25 f/s 유럽 PAL TV
• 30 f/s 미국 NTSC TV
• 60 f/s HDTV

리사이즈(확대/축소) 필터

큰 것을 작게 축소할 때는 뭘 사용하든 문제없다. 작은 것을 크게 확대할 때는 없는 정보를 만들어 넣는 보간법이 필요하다. 이 때 가장 기초적인 bilinear(XY2차원 선형 보간법)이 있는데 하면 안 좋다. 보통 bicubic(XY2차원 3차 다항식)이 적당하다. 아마 Lanczos도 뭔지 잘 모르겠으나 bicubic과 비슷한 수준의 결과를 만들어 낼 것이다.

샘플링 주파수 → 고주파 음질

사람(어린 아이들)은 보통 20~2000Hz를 듣기 때문에 이것의 약 2배인 40000Hz 이상에서 샘플링을 해야 원본 음질을 유지한다. 그래서 보통 44100으로 많이 선택 되어 있을 것이다. 늙은이들은 고음을 못 듣기 때문에 이보다 낮게 설정해도 무난하다. 인간의 육체는 20대부터 낡기 시작한다.

채널 = 스피커의 숫자

오디오의 경우는 모노(1채널), 스테레오(2채널), 기타 여러 채널이 있다. 보통 휴대용 장비나 PC에서 볼 때는 스테레오가 무난하다. 영화 원본의 사운드를 듣고 싶다면 채널 수를 확인해 보기 바란다. 그게 연결할 스피커의 숫자다. 5.1채널까지 있다.

비트 전송률

얼마로 하는 것이 적당한지는 역시 원본을 참고할 수는 있겠으나 원본과 비슷하게 설정하면 이상하게 음질이 떨어진다. 직접 계산을 해 보자.

• 샘플링은 음악의 경우 4만Hz이상을 한다. 뉴스라면 그 절반으로 해도 된다.
• 화면 크기에 해당하는 것이 스피커 수다. 보통 음악은 2채널, 뉴스라면 1채널.
• VBR로 하려면 80%는 되어야 원본과 비슷한 수준이다.

※ 최대 전송량 계산
샘플링 주파수 44100Hz, 샘플링 깊이 16비트(CD), 스테레오(2채널)
압축이 없을 때 44100Hz x 16 x 2채널 = 1411kbps
여기에 MP3의 압축률을 곱하거나 원본의 압축률을 계산해서 곱한다.
원본과 같은 수준 소리 전송률 : 256kbps ~ 320kps
원본과 같은 수준 소리 압축률 : 18% ~ 23% (손실 압축)

키 프레임(Key Frame)

키 프레임이란 온전한 영상이 있는 프레임이다. 키 프레임 사이의 프레임들은 차이점만 저장되어 있다. 다시 인코딩 할 때는 키 프레임 단위로 이동할 필요가 없는데 Direct Stream Copy를 사용할 때는 키 프레임 단위로 잘라야 깔끔하다. 중간에서 자르면 화면이 깨진다. 여기서 주의할 점은 자른 지점에서 보이는 화면은 키 프레임의 화면이란 것이다. 키 프레임은 그 구간의 앞에 있다. 고로 보이는 그 화면에서 잘리지 않는다. 키 프레임으로 이동하고 싶을 때는 마우스로 근처 위치로 간 후에 재생 화면을 선택하여 좌측 방향키(←)로 이동하면 된다. 이상하게 우측 방향키(→)는 먹히지 않는다.

배속 인코딩

너무 느려 처지는 동작이 나오는 화면을 약간 빠르게 (1.1배속 ~ 1.2배속) 하면 경쾌한 느낌을 준다. 이 경우 인코딩 배속을 바꾸면 되는데 Direct Stream Copy에선 안 통하고 인코딩을 다시 해야 한다. 

---

기타 내가 자주 사용하는 프로그램이다.

• 반디캠 : 동영상 캡쳐, 국세충 일베충이 세월호 영상 조작에 사용했던 프로그램.
• 알캡처 : 화면 캡처

국세충 일베충도 세금 받아 처먹고 친일독재잔당의 범죄 덮어주기 힘들 거다. 그러니까 일을 좀 대충, 허접하게 하시라. 자꾸 말썽이 생기도록 실수를 하란 말이지. 거기서 일하는 애들도 젊은 애들 아닌가? 나라 기강을 바로 세우는데 일조를 하란 말이지.

TV 모니터 화면 종횡비 정리

유클리드 기하학(밧줄로 정다각형 작도), 원주율, 황금비, 복사지/복사용지 종횡비

TV 모니터 화면 종횡비 정리

화면 종류	종횡비	정수비		화소수		설명
		가로	세로	가로	세로
DVD video	1.777~	16	9	1280	720	Wide
DVD video	1.777~	16	9	1920	1080	Wide
NTSC video	1.500~	3	2	720	480	NTSC
PAL video	1.250~	5	4	720	576	PAL
HDTV 방송	1.1852	32	27	1280	1080
HDTV 방송	1.333~	4	3	1024	768	TV
HDTV 방송	1.333~	4	3	1440	1080	TV
HDTV 방송	1.777~	16	9	1248	702	Wide
HDTV 방송	1.777~	16	9	1280	720	Wide
HDTV 방송	1.777~	16	9	1888	1062	Wide
HDTV 방송	1.777~	16	9	1920	1080	Wide
HDTV 방송	1.777~	16	9	3840	2160	Wide
HDTV 방송	1.7786	683	384	1366	768	Wide
Monitor	1.0839	168	155	1680	1550
Monitor	1.250~	5	4	720	576	PAL
Monitor	1.250~	5	4	1280	1024	PAL
Monitor	1.333~	4	3	640	480	TV
Monitor	1.333~	4	3	800	600	TV
Monitor	1.333~	4	3	1024	768	TV
Monitor	1.333~	4	3	1152	864	TV
Monitor	1.333~	4	3	1280	960	TV
Monitor	1.500~	3	2	720	480	NTSC
Monitor	1.5625	25	16	1600	1024	NTSC
Monitor	1.600~	8	5	1280	800	황금비
Monitor	1.600~	8	5	1440	900	황금비
Monitor	1.600~	8	5	1680	1050	황금비
Monitor	1.6667	5	3	1280	768	황금비
Monitor	1.7708	85	48	1360	768	Wide
Monitor	1.777~	16	9	1280	720	Wide
Monitor	1.777~	16	9	1600	900	Wide
Monitor	1.7786	683	384	1366	768	Wide

가장 흔한 종횡비는 아래와 같다.

• 4:3 옛날 TV, 옛날 모니터
• 16:9 일본의 Wide TV
• 16:10(8:5) 황금비
• 14:10(7:5) 복사지

자기 모니터의 종횡비 계산이 어려우니까 표로 정리한다. 최소공배수를 구한 후에 가로, 세로를 다시 나눠 주면 종횡비의 정수 비율이 나온다. 같은 종횡비의 내용을 재생하면 늘어나거나 줄어드는 일이 없다.

---

어릴 적에 전두환, 노태우 시절에 부모들은 대학생 자식 보고 데모에 나가지 말라고 했다. 빨갱이 물이 들어서 그렇다고 했다. 허나 진실은 잡혀서 고문 당해 죽는 꼴을 봤으니까 말리는 것이었다. 다행히 80년대 중반 민주화 되면서 더 이상 데모를 할 필요가 없어졌다. 대부분의 대학생들은 빨갱이가 아니었기 때문이다.

그래서 80년대 중반부터 대학생 데모가 거의 사라졌다. 90년대부터 공산주의도 무너졌기 때문에 더 이상 데모는 빨갱이와 관계없어졌다. 그런데 아직도 친일 선동 언론은 빨갱이 선동을 하고 있다. 진실은 좌우 대립이 아니라 선(충신)과 악(간신)의 대립이었다. 정상과 비정상의 대결이었는데 좌우 대립을 핑계로 탄압했던 것이다.

90년대부터 공산주의가 없기 때문에 좌파 사상이 담긴 서적도 자유롭게 읽을 수 있게 되었다. 민주주의 국가에선 사상과 종교의 자유가 있으니까 이제 힘이 없는 좌파 사상도 읽을 수 있게 된 것이다. 그리고 드디어 사람들은 알게 되었다. 왜 빨갱이 물이 들면 개독교인들처럼 신앙이 생기는지. 이론이 아주 단순 명확해서 아이들도 이해할 수 있을 정도의 명명백백한 것이니까. 어릴 적에 듣던 흥부 놀부 이야기의 재탕이다.

좌파 이론이 유치하다면 개독교도 자본주의도 유치한 것이다. 자본주의 때문에 좌파 사상이 생긴 것이니까. 좌파 사상의 씨앗이 개독교에 담겨 있으니까. 좌우 대립이란 결국 인류 문명 이후의 수 천 년 동안의 선악 대결이었다. 강자와 약자의 대결이었고, 부자와 거지의 대결이었고, 지배자와 노예의 대결이었다.

압축, 암호 알고리즘 단순 무식한 이해

압축 암호 알고리즘을 인터넷에서 찾아 봐도 참 설명이 어렵다. 너무 수학적이고 학문적인 표현을 사용한다. 가장 유명하며 그래서 가장 많이 쓰이는 압축 방법 몇 개를 정리해 보겠다. 자기 데이터 압축하거나 암호화할 때 사용하면 되겠다. 압축 방법을 모르면 압축이 암호화 한 것과 다름없다. 

1. 코드(암호) 사전 : 문자/단어 → 숫자

누구에게 편지를 보낸다고 하자. 그런데 그 편지에 사용하는 단어는 99개를 넘지 않는다고 하자. 그럼 모든 단어를 십진수 2개 (00~99)로 나타낼 수 있을 것이다. 예를 들어 우리가 사용하는 단어가 6만 개 미만이라고 할 경우 16비트 정수로 단어를 대신할 수 있다. 그러면 모든 단어는 2바이트만 차지한다. 보통 한글 한 글자는 16비트(완성형, 조합형, 유니코드)로 나타내기 때문에 단어를 문자 하나로 압축한 효과가 있다. 또는 가변 길이를 사용해서 압축할 수도 있다.

• 0xxx.xxxx = 128개의 사용 빈도가 높은 짧은 단어(1 ~ 2 글자 단어)
• 1xxx.xxxx + 0xxx.xxxx = 1만6384개의 중간 길이 단어
• 1xxx.xxxx + 1xxx.xxxx + 0xxx.xxxx = 209만7152개의 긴 단어

이 아이디어는 유니코드 가변 길이(UTF-8)와 비슷하고, 미디 파일에서 음의 길이 표현에서 사용하는 방법과 같다. 여하튼 2바이트만 가지고 거의 모든 단어를 대신할 수 있기 때문에 간단하게 압축이 된다. 문서 압축에 이용해 보시길. 헌데 단어 사전의 양이 너무 방대하다. 이 사전을 미리 상대가 알고 있어야 한다. 우리가 흔히 사용하는 단어는 1만 미만이다. 일상생활에선 몇 천개 수준의 단어만 사용한다.

2. RLE(Run Length Encoding) : 동일 내용 압축

이것은 주로 흑백 이미지나 색상과 명암이 단순한 만화, 문서 이미지 등에서 사용하면 좋다. 이런 자료들은 같은 내용이 반복되는 경우가 많다. 그래서 주행길이코드라고 부르는 것이다. 이 방식은 FAX에 이용하는 방식이다.

AAAAAAABBBBBBCCCCC = A7B6C5

아이디어는 위와 같은데 컴퓨터에선 모든 것을 2진수로 표현하기 때문에 데이터와 길이를 구분하는 표시가 있어야 한다. 그래서 첫 비트로 데이터와 길이를 구분한다고 하면 다음과 같이 된다. 만약 반복이 없는 부분이 나타나면 그대로 표현하는 것이 더 낫다. 그런 경우 첫 비트가 계속 0인 것만 나오겠지?

0xxx.xxxx = 128개의 데이터 구분

1xxx.xxxx = 최대 128까지의 길이

3. 허프만 부호화(Huffman coding) : 빈도 → 길이

이것은 문서나 프로그램에서 단어(코드) 사용 빈도가 높은 것은 짧은 코드로, 빈도가 낮은 것은 긴 코드로 대체하는 것이다. 예를 들어 2진수로는 다음과 같이 코딩할 수 있을 것이다. 마지막 0은 끝을 알리는 구분자이다. 이 방식은 보통 우리가 사용하는 압축 프로그램에서 사용한다. 앞의 코드 사전의 가변 길이와 비슷한 개념이다.

10 = 가장 빈도가 높은 것

110

1110

11110 = 가장 빈도가 낮은 것

이 아이디어는 이미 우리 언어에서 발견할 수 있다. 1~3 글자 단어는 아주 자주 사용하는 문법 단어들이고 4글자 이상은 비교적 자주 사용하지 않는다. GIF, PNG, JPEG 이미지 파일 압축도 이런 방식을 사용한다. 

4. 푸리에 변환 : 패턴/무늬/물결 압축

사진이나 음악처럼 반복 패턴(무늬/물결)이 있는 경우는 어떻게 하지? 예를 들어 다음과 같은 경우 말이다.

ABCABCABCABC = ABC4

반복성을 검사하는 방법은 무식한 비교 외엔 없다. A를 읽고 B와 비교하니 다르다. 그럼 AB를 기억하고 C를 읽어 AB와 비교하니 다르다. 그럼 ABC를 기억하고 다시 A를 읽으니 첫 글자가 같다. 그럼 나머지 BC도 읽어 붙여 비교한다. 그럼 ABC가 일치한다. 1회 반복이 된 것이다. 몇 번 반복 되었는지 계속 비교한다. 이런 짓을 해야 한다.

반복을 인식하려면 과거를 기억해야 하고 과거와 현재를 계속 비교해야 하기 때문에 계산양이 많다. 짧은 반복은 눈에 쉽게 보이는데 아주 긴 천문학적 수준의 반복은 반복인지 느끼지도 못 한다. 큰 반복을 파악하려면 장기간의 과거 기억이 필요하다.

소리나 이미지의 경우 주기적인 특성을 보이는데 이런 주기적 특성을 분석할 때 푸리에 변환을 사용한다. 매우 계산 시간이 많이 소모되는데 주기적인 데이터의 경우 그 주기만 파악하면 압축 효과가 있다. MP3나 JPEG, MPEG 등에서 사용한다. 그런데 우리가 이 짓을 해서 압축할 수준은 아니겠지? 그래도 몇 가지 비슷하게 하는 방법이 있다.

1. 구간 평균을 뺀다.
2. 음수와 양수가 교차하는 지점의 간격을 조사한다. 
3. 주기성이 있다면 특정 간격들에서 빈도가 높게 나타난다.
4. 주기성이 보이는 간격들을 모두 합한 길이가 반복 주기다.

5. 암호화 방법 = 내용 바꾸기 + 위치 바꾸기

압축을 푸는 방법을 알려 주지 않으면 그대로 암호가 된다. 옛날부터 사용하던 암호화 방법이 있다. 문자 하나를 대체하는 방법과 문자들의 자리 바꾸는 방법이다. 이 두 방법을 섞어 사용한다. 자리 바꾸기를 하려면 단위 블록을 정해야 한다.

가나다라마 = ABCDE (문자 바꾸기)

가나다라마 = 다나라가마 (자리 바꾸기)

가나다라마 = CBDAE (문자 바꾸기 + 자리 바꾸기)

위에서 5글자를 블록으로 정해서 문자 바꾸기와 자리 바꾸기를 한 경우이다. 문자 바꾸기는 코드 사전과 비슷한 느낌일 것이다.

6. 대칭 키 암호

문자를 바꾸거나 자리를 바꾸는 방식을 알려주는 정보(숫자)가 키(열쇠)이다. 암호를 만든 쪽과 암호를 푸는 쪽이 같은 키를 사용하면 대칭키 암호이다. 이 암호 키는 당연히 정보를 주고 받을 사람 둘만 알고 있어야 한다. 문제는 10명이 서로가 모르게 암호를 사용해서 통신할 경우 10*10/2-10/2=50개의 키가 있어야 한다는 것이다. 즉, 1명은 나머지 9명과의 암호 키를 가지고 있어야 어느 한 사람과 통신할 때 나머지 8명이 해독할 수 없게 된다. 양쪽이 같은 암호를 알고 있기 때문에 어느 한 쪽이 뚫리면 암호는 깨진다. 상대가 배신하면 내가 당하는 것이다.

7. 공개 키 암호

10명의 사람이 있을 때 각자 자신의 공개 키와 비밀 키 짝을 가지고 있다고 하자. 10명은 각자의 비밀 키만 기억하면 된다. 공개 키는 무두에게 공개한다. 그럼 암호화하는 쪽에선 상대의 공개 키로 암호화해서 보내면 받아 해독하는 쪽에선 자신의 비밀 키를 이용해서 암호를 푼다. 대칭 키와 비교해서 사람의 수에 비례한 공개 키만 알면 되기 때문에 편하다. 10명 모두 10명에 대한 동일한 공개 키를 가지고 있고 오직 1개 자신의 비밀 키만 외우면 된다.

공개 키 : ID, 주민 번호, 계좌 번호 같은 것

비밀 키 : PW, 일반 암호, PIN 번호 같은 것

PIN = Personal Identification Number = 숫자 암호(은행 암호)

일반 암호 : 문자+숫자+기호 조합

공개 키가 편한 점은 공개 키 목록을 잃어 버렸을 때 다른 한 사람에게 공개 키를 물어 볼 수 있다는 점이다. 대칭 키의 경우 자신이 가진 키 목록을 잃어버리면 9명 모두 찾아다니며 키를 수집해야 한다는 것이 불편하다.

공개 키가 가능해진 이유를 보면 큰 소수(prime number)의 곱을 구하기는 쉬워도 그 수를 다시 인수 분해하기는 어렵다는 점을 이용했다고 한다. 그러면 공개 키와 비밀 키는 다음과 같은 관계란 것이다. 공개키로 암호화 하고 공개키로 암호를 풀 수 없는데 비밀 키가 있어야 암호를 풀 수 있는 알고리즘이 있어야 가능한 방법이다. 그러니까 암호화 하는 키와 암호를 푸는 키가 달라야 한다.

1. 공개 키 = 비밀 키1 x 비밀 키2
2. 비밀 키2 = 공개 키 x 비밀 키1
3. 비밀 키1 = 공개 키 x 다른 키2

우리가 구한 소수가 많아야 안전하겠다. 예를 들어 우리가 파악한 소수가 100개라고 한다면 그 조합은 100x100 = 1만개가 나온다. 여하튼 공개 키는 대칭 키보다 암호가 뚫릴 가능성이 더 높다. 공개 키에 비밀 키의 힌트가 담겨 있기 때문이다. 인수 분해만 성공하면 풀린다. 역시 키 자체도 비밀로 하는 것이 안전하다. 이 인수 분해를 하자고 양자 컴퓨터를 개발하고 있다고 하는데 잘 안 되는 거 같다.

---

모두가 가질 수 있고 가져야 하는 것에는 뭐가 있을까?

옷, 식량, 집, 교육, 의료, 에너지, 통신, 대중교통 등이다.

국가는 모든 국민에게 이것을 제공하려고 노력해야 한다. 이건 생존과 관련 있고 삶에 필수적인 것들이다. 그리고 모두에게 나눠 줄 수 있는 것이다. 교육은 지식을 나누는 것이라서 얼마든지 공짜로 나눌 수가 있다. 의료는 병든 사람만 필요한데 병든 사람 중에 부자만 병원에 간다면 의사들도 돈을 못 벌 것이다. 그런 사회에선 의료비는 졸라 비싸면서 혜택 받는 사람은 적어진다. 에너지는 식량과 별로 다를 것이 없다. 모든 활동엔 에너지가 필요하다. 그래서 이 시대 식량처럼 저렴한 것이 에너지다. 통신망과 교통망은 돈이 많이 들어가기 때문에 원래 기업보다 돈이 가장 많은 국가에서 제공해야 한다. 이런 것을 민영화(사유화) 하면 국민만 손해 본다.

모두가 가질 수도 없고 모두가 가지면 문제가 되는 것은?

자동차, 배, 비행기, 황금, 미녀 등이다.

황금, 미녀는 그 수가 적기 때문에 모두가 가질 수 없는 것이다. 그리고 생존에 꼭 필요한 것도 아니다. 자동차, 배, 비행기를 모두가 가진다고 해 보라. 이것들이 할 일 없이 놀 때는 주차난이 발생하고 일 하러 나갈 때는 도로, 바다, 하늘이 막힌다. 그래서 이런 것들은 대중교통으로 제공해야 옳은 것이다. 도시 내부의 순환, 도시 사이의 연결엔 대중 교통이 담당하고, 그 외의 대중교통이 통하지 않는 곳에서 직업적으로 운송을 담당하는 사람들에게만 허용해야 한다. 보통 시골에서 자기 자동차를 소유하고 도시에선 전철, 버스, 택시를 타야 정상인데 거꾸로 된 것 같다.

사유화보다 공유화하는 쪽이 바람직한 것은?

농지, 어장, 광산, 공장, 시장, 은행 등 일터이다.

일터는 사적인 공간이 아니다. 사유물이 될 경우 사회 문제를 발생시킨다. 사장이 돈과 힘을 이용해서 여직원을 강간하는 경우 등, 빈부격차를 심화하고 시장을 어지럽힌다. 운영은 민간에게 맡기더라도 소유는 국가가 해야 바람직하다. 즉, 민간에게 대여하고 대여료를 세금 형식으로 받는 것이다. 이렇게 하면 사유재산이 아니기 때문에 국가가 주도적으로 빈부격차를 해소할 수 있고, 모든 사람이 놀고 먹지 않고 일을 하게 되며, 자본주의 시장 논리에도 부합 된다.

이건 사유재산이 없고 공동 생산, 공동 분배하는 공산주의와 다르다. 사적인 물건과 공간에만 사유재산을 인정하고 공적인 공간과 물건은 국유화 되어 있지만 그 것을 운영함에는 경쟁이 있기 때문에 자본주의와 같다. 공산주의가 무너졌다고 해서 긴장을 풀고 옛날 마르크스 시절의 자본주의로 후퇴하면 경제 불황만 계속 될 것이다. 80년대 자본주의(유럽/미국)가 공산주의(소련)를 이길 수 있었던 이유는 빈부격차가 심하지 않은 건전한 자본주의였기 때문이다. 80년대 한국 경제 성장도 이들 유럽/미국의 경제 성장 때문이지 박정희, 전두환의 공이 아니다.

고교 수학 수준 컴퓨터 게임 인공 지능 길 찾기

인공 지능 하면 인공신경망(대규모 회귀분석), 퍼지논리(애매모호 논리), 유전 알고리즘(진화론 = 시행착오) 등 나올 것 같지만 컴퓨터 게임에선 이런 것 사용하지 않는다. 너무 느리고 어떻게 그렇게 되었는지 파악하기 힘들다. 컴퓨터 게임에서 볼 수 있는 지능은 그냥 따라 하면 되는 알고리즘이다. 간단하게 조건 반응이지.

• 상대 인식(거리 측정)
• 조건에 따른 반응(튜링머신 = 컴퓨터 = 상태변화도/표)
• 길 찾기(path finding) 등

이런 건 반응이 빠르고 왜 그렇게 행동했는지 명확하게 이해할 수 있다.

블로그 날리니 기억이 가물가물하다. 씨발. 참고 했던 글의 링크가 끊어졌다. 

그래서 위키 백과 글을 링크해 두는데 이걸 읽고 이해할 정도면 머리 좋은 거다. ㅋㅋㅋ

• 위키백과 A* 탐색 알고리즘 영문
• 데이크스트라 알고리즘
  

컴퓨터는 1/30초 또는 1/60초(순간/찰나) 동안 다음과 같은 동작을 반복한다.

• 사용자 명령 (키보드, 마우스) 입력
• 물리, 지능 시뮬레이션
• 화면 그리기 (배경, 애니메이션)

인공 지능 시뮬레이션은 다음과 같은 순서이다. 지능 시뮬레이션은 물리 시뮬레이션이나 그림 그리기처럼 단순 반복 작업이 아니기 때문에 단계를 나누어 여러 사이클에 걸쳐 계산할 수도 있다. 즉 한 사이클에는 한 단계의 작업만 하는 것이다.

• 감지 : 주로 거리 계산
• 판단 : 상태 변화 검색, 길 찾기 알고리즘 실행(소모 시간이 가변적)
• 행동 : 간단

물리 시뮬레이션은 그림 그리기보다 더 짧은 빈도로 계산할 수도 있다. 단순 반복 계산이기 때문에 소모 시간이 동일하다. 물리 시뮬레이션이 끝나면 위치 변화가 나타나고 화면에 표시를 해야 한다. 

• 힘 변화 → 가속도 변화
• 가속도 변화 → 속도 변화
• 속도 변화 → 위치 변화
• 위치 변화 → 충돌 확인
• 충돌 계산 → 속도 변화

A. 거리 측정

상대가 근처에 왔는지 확인해야 하겠지? 여러 게임을 보면 정지한 유닛은 거리 계산을 하지 않는다. 스타크래프트 같은 경우를 보면 그렇다. 움직이는 놈이 항상 주변 유닛과의 거리 계산을 한다. 문제는 100개의 유닛이 있을 때 모든 유닛의 거리를 계산하려면 100*100/2 + 100/2 = 5050번의 계산을 해야 하는 것이다. 이 문제 피하기 위해서 지도를 격자로 나누어 거리 계산이 필요한 유닛 주변 3*3 격자 속의 유닛과 거리만 계산한다. 지도를 영역으로 나눠서 같은 영역에 속하는 것들만 거리 계산을 한다는 것이다.

• 총 계산 양 = N*N/2 + N/2 = (N + 1)*N/2

근처에 있는 것을 대충 선택하여 거리 측정을 하고 그 중에서 너무 근접한 것에 대해서 충돌 검사를 하는 것이다. 거리 계산은 피타고라스 정리를 사용한다. 옛날 게임 중엔 단순히 정사각형 안에 들어오면 같은 거리로 취급한 것도 있다. 블리자드에서 만든 워크래프트 같은 것이 그렇다. 대각선 방향을 따지지 않는 것은 도시에서 거리 계산과 비슷하다. 도로를 따라 이동해야 하니 동서남북으로만 이동한다.

B. 조건 반응

상태변화도/표란 어떤 상태에서 외부 조건이 뭔가 더해져서 다음 상태로 변하는 것을 도표로 나타낸 것을 말한다. 상태변화도는 마치 지도를 그린 것과 같다. 예를 들어 지금 A교차로에 있는데 왔던 길을 제외하고 새로운 길이 3개 있어 교차로 B, C, D로 간다고 하면, 외부 조건(주사위 던지기나 신호등)에 따라 각 교차로로 이동하는 식이다. 수식으로 나타내면 다음과 같다.

• 다음 상태 = 대응함수/검색표(현재 상태, 외부 조건 A, B, C...)

이 때 다음 상태로 바뀌면서 거기에 따라 뭔가 행동을 하는 것이다. 예를 들면 다음과 같은 식으로 만들 수 있다.

• if 현재 상태 = 정지 and 외부 조건 = 적 출현 then 다음 상태 = 적에게 이동
• if 현재 상태 = 이동 and 외부 조건 = 적 접촉 then 다음 상태 = 적을 공격
• if 현재 상태 = 공격 and 외부 조건 = 적 사망 then 다음 상태 = 정지
• 기타 기존 상태 유지

그냥 행동 규칙을 나열한 것과 같다. 조건문으로 못 만드는 것은 없다. 이 중에서 가장 구현이 어려운 행동이 이동이다. 길을 찾아야 하기 때문이다. 공격은 대충 뭔가 쏘거나 때리는 시늉만 하면 된다. 외부 환경 인식과 길을 찾는 것이 더 어렵다.

주변의 아군과 적의 비율을 보고 자신이 포위 된 상태인지 판단할 수도 있다. 주변의 적의 수를 비교해야 한다. 장애물을 피해 목표까지 가는 길을 찾는 것은 더 지능적이고 많은 시간이 소모 된다. 분신술을 써서 미리 모든 길을 다녀 봐야 한다.

미사일 요격 게임을 만들 때는 수학이 필요할 것이다. 미사일의 궤적을 예측하여 미리 쏘아야 하기 때문이다. 수학으로 해결 되는 문제는 수학으로 해결하는 것이 깔끔하다.

C. 길 찾기(A* path finding)

A*, A star 알고리즘 간단하게 소개한다. 나도 누군가 알려 줘서 알았다. 유튜브 동영상을 보면 여러 알고리즘이 있다는 걸 알 거다. 여러 갈래 길이 있을 때 어디로 갈 것인지 선택할 때 이 방법을 사용한다. 갈 길을 선택하는 알고리즘과 갈 수 있는 길을 찾는 건 다르다. 갈 수 있는 길이 몇 개 있는지, 여기로 도착하는 길이 몇 개 있는지 확인하는 것이 탐색이고, 그 길 중에서 어떤 길을 먼저 검토할지 결정하는 것이 선택이다.

게임에선 지도를 바둑판처럼 격자로 나누거나 6각형 형태로 나눈다. 이런 것을 타일 맵이라고 한다. 워크래프트가 이 바둑판 스타일이다. 입체감을 주려고 45도 회전한 것도 사용한다. 에이지 오브 엠파이어가 이 스타일이다. 마름모 형태로 된 격자는 레드 얼럿, 스타크래프트 스타일이다. 6각형 형태는 턴 방식 게임인 삼국지, 문명에서 볼 수 있다.

바둑판 형태로 나눈 경우는 한 격자에서 8방향의 길이 있다. 6각형 형태로 나누면 한 방에서 6방향의 길이 있다. 각 방의 좌표를 결정하는 방법은 위의 그림과 같다. 바둑판 형태가 아니면 홀수와 짝수에 따라 엇갈리게 된다. 상세 계산법은 알아서 구할 것. 만약 길 표시가 있는 지도라면 탐색 문제는 더 쉬울 것이다. 길만 따라 가면 되고 교차로에서 길 선택 문제만 있으니까. 자동차 네비게이터가 그러하다. 각 교차로는 연결된 다른 교차로 정보를 가지고 있어야 한다.

마이크로 마우스(로봇)가 미로를 통과하는 경기가 있다. 무조건 빨리 도달하는 게 목표인 게임이다. 여러 차례 도전하기 때문에 길을 암기 할 수도 있고, 카메라를 이용해서 벽 넘어 길을 볼 수도 있다. 날아 가거나 벽을 타 넘지만 않으면 된다. 거기 알고리즘도 매우 비슷하다. 거기서 사용하는 알고리즘은 이렇다.

1. 좌수법/우수법(벽타기) : 벽에 손을 접촉하고 따라가면 미로를 탈출한다. (최초 우승)
2. 깊이 우선 탐색 : 분기점에서 아무 길이나 정하면 무조건 깊게 들어가는 방법
3. 넓이 우선 탐색 : 출발점에 가까운 곳부터 넓게 탐색하는 방법 (그러다 목표에 도달)
4. 전체 지도 탐색 : 모든 길을 다 돌아 다니기 때문에 최적 길을 찾기는 하지만 꼴찌다.
5. 물 채우기 : 분기점에서 목표에 가장 가까운 방향의 길을 선택하는 깊이 우선 탐색.
6. 직진 우선 탐색 : 지도를 알고 있을 때 방향 바꾸는 회수가 가장 적은 길을 선택한다.

여기서 A*는 깊이 우선과 넓이 우선을 조합한 방법이고 물 채우기와 매우 비슷하다. 겉으로 보면 먼저 깊이 우선 탐색을 하다가, 장애물에 막히면 그 때 넓이 우선 탐색을 하는 것처럼 보인다. 가야 할 길을 선택할 때는 물 채우기(glood fill)와 비슷하게 평가 점수가 가장 낮은 쪽 길(목표까지 직선 거리가 가까우며, 출발점에서 거리가 가장 짧은 길)을 선택한다. 마치 물이 중력에 의해 낮은 곳으로 흘러 가는 것처럼. 차이가 있다면 마이크로 마우스는 몸이 있기 때문에 한 번 길을 정하여 갔다가 막히면 다시 원래 분기점으로 돌아 와야 한다. 소프트웨어 길 찾기는 분신술을 써서 동시에 여러 지점에서 탐색한다는 것이다. 순간 점프가 가능하기 때문이다.

여기서 최적의 길은 지도 전체를 탐색했을 때만 얻을 수 있다. 나머지 방법은 최적의 길이 아니다. 지도의 정보가 부족한 상태에서 가장 빨리 도달하는 방법들이다. 만약 벽을 따라 돌았을 때 최적이라 하더라도 전체 지도를 모르면 이를 알 수 없다. 그런 경우 눈에 보이는 정보만 가지고 지도를 대각으로 가로지르면서 복잡하게 이러 저리 돌아서 오히려 시간이 더 소모 될 수도 있다. 컴퓨터 게임에선 시간이 부족하기 때문에 전체 지도 탐색은 할 수 없다. 마이크로 마우스와 비슷한 상황인 것이다. 단지 분신술을 쓰기 때문에 좀 더 최적의 길을 선택한다는 것이다.

마이크로 마우스는 지금 지점에서 다른 지점으로 점프할 수 없다. 그러나 소프트웨어로는 A, B, C 3개 지점에서 동시 탐색이 가능하다. 그래서 여러 갈래의 길을 동시 탐색하다가 가장 먼저 목표 지점에 도달한 길을 선택하는 것이라서, 마이크로 마우스보다는 좀 더 최적의 길을 선택하게 된다. 마이크로 마우스는 물이 흘러 들어갈 거 같은 곳으로 이동하지만, 길 찾기 알고리즘은 진짜 물이 흘러 들어가는 여러 길을 동시에 찾는다. 이 분신술을 멀티태스킹이라고 부른다. A 지점에서 조금 탐색, B 지점에서 조금 탐색, C 지점에서 조금 탐색, 이런 식으로 왔다 갔다 하면서 탐색하기 때문이다.

길 찾기는 대략 다음과 같은 것들이 있다. 깊이 우선 탐색이란 무조건 목표 지점까지 깊게 들어가는 것을 말한다. 최적의 길을 찾는 것보다 길의 유무를 빨리 판단할 때 도움이 된다. 넓이 우선 탐색이란 물결이 퍼지듯이, 점점 부식 되는 것처럼 사방으로 탐색을 하는 것을 말한다. 매우 느리지만 어느 정도 최적의 길을 찾아 준다. 양방향이란 양쪽에서 접근해서 중간에 만나 탐색 시간을 줄이는 방식이다.

• 넓이 우선 탐색 vs 깊이 우선 탐색
• 단방향 탐색 vs 양방향 탐색

물결이 퍼지는 것 같은 넓이 우선 탐색 방법은 도형의 내부를 칠할 때도 유용하다. 중심에서 거리가 같은 곳까지 거품처럼 둥글게 커지는데 이 물결의 경계선까지는 직선 이동이 보장 된다. 장애물을 만나면 마치 물결이 장애물을 돌아가듯이 (회절 현상) 그 모퉁이를 다시 중심 삼아 퍼지게 된다. 이 방식에선 물결의 경계, 거품의 표면에 해당하는 방(교차로)들의 목록을 기억하고 있어야 한다. 그리고 그 목록 중에서 출발점과 목표점으로부터 거리가 가장 짧은 곳을 선택해서 그 지점에서 탐색을 해야 하기 때문에 최소값 고르기를 항상 한다는 것이다. 최소값 결정은 시간이 많이 소모된다.

더 단순한 방법으로는 정사각형을 계속 넓히며 탐색하는 방법이 있다. 8방향 타일에선 바깥 경계선은 항상 정사각형이기 때문에 따로 경계선까지 거리를 비교할 필요가 없다. 경계선 중에 무엇을 먼저 검토할지 결정하기 위해 최소값 결정도 할 필요가 없다. 경계선의 모든 점을 기계적으로 검토할 것이니까. 원형 물결이 아니라 정사각형 물결이란 점이 다르고 결국은 같은 결론에 도달한다. 6각 타일에선 자동으로 원형 물결처럼 된다. 이 방법은 넓이 우선 탐색에 해당한다. 목표를 향해 깊게 돌격하는 게 없다.

다른 방법으로는 벽 타기를 해서 틈을 발견하는 방법이 있다. 최적은 아니지만 길이 있는지 여부는 빨리 판단한다. 벽에서 떨어져야 할 때를 판단해야 한다. 목표 방향으로 장애물이 없다면 벽에서 떨어진다. 만약 장애물이 있다면 자신이 온 길을 기억하고 있어야 하고 벽에 붙어 있어야 한다.

또 다른 방법으로는 돌출 코너만 찾아 직선으로 연결하는 방법이다. 최단 거리는 직선이기 때문이다. 이 방법으로 값 싸게 최적 경로를 구할 수 있다. 여기서 최적이란 지도를 이미 알고 있을 때이고, 지도가 다 밝혀진 게 아니라면 열린 지도 영역에서만 최적이란 의미다.

출발 지점에서 물결이 퍼지고, 도착 지점에서 동시에 물결이 퍼지면 중간 어디에서 만나게 되는데 그 지점이 바로 최적 경로가 된다. 양방향 탐색과 넓이 우선 탐색을 결합하면 적당히 짧은 시간에 최적의 경로를 얻게 된다. 탐색 면적은 탐색 반경의 제곱으로 늘어나기 때문에 양쪽에서 탐색하는 것이 시간 절약이 된다. 그러면서 모든 길을 탐색했기 때문에 가장 최적의 길을 찾게 되는 것이다. 그러나 시간이 너무 많이 소모되어 시간 부족에 시달리는 게임엔 부적합하다. 에이지 오브 엠파이어 게임에선 가장 가까운 나무를 자동으로 찾는 기능이 있는데 이렇게 사방으로 탐색하지 않으면 못 찾는다.

위의 그림이 실제 A* 알고리즘을 적용한 것이다. 내가 만든 건 아니다. 누군가 알려준 글을 통해 얻은 것이다. 녹색은 탐색할 경계, 파랑은 탐색이 끝난 내부, 노랑 사각형은 찾은 길이다. 최적 경로가 아님을 알 수 있을 것이다. 최적 경로는 직선 경로다. 사각형의 좌측 하단엔 실제 이동 거리, 우측 하단엔 목표까지 직선 거리, 좌측 상단엔 평가 점수가 적혀 있다. 화살표는 자신이 어디서 왔는지 나타내는 것이다. 우측 상단이 비었는데 검토한 순서를 적어 놓으면 좋았을 것이다.

• 다익스트라 방식 = 넓이 우선 탐색 + 출발점에 가장 가까운 곳부터 탐색
• A* 알고리즘 = 넓이/깊이 우선 절충 + 목표까지 직선 거리가 가장 짧은 곳(추가)

A*는 깊이 우선 탐색과 넓이 우선 탐색을 결합한 경우이다. 8방향, 6방향 A* 벌판 탐색 방법에 따르면 장애물이 없을 때는 목표까지 계속 직진한다. 장애물을 만나면 그 지점에서 넓게 탐색을 한다. 그러다 틈이 발견 되면 그 쪽으로 빠져나간다. 그림에서 보면 최적의 경로를 찾은 것은 아니다. 품질과 시간 사이에 절충이 있다. A*는 절충 방법이다. 길이 막히면 넓이 우선 탐색(다익스트라 방식처럼)으로 바뀐다. 8방향, 6방향 탐색 A*는 다음 순서로 동작한다.

1. 8방향, 6방향 탐색을 해서 새로운 탐색할 경계 지점을 등록한다.
2. 각 경계 지점에 최소 시간으로 도달할 수 있는 부모 위치를 선택한다. (다익스트라)
3. 각 경계 지점까지 실적 거리와 목표까지 예상 거리(직선)를 구해서 더한다. A*
4. 경계 중에서 가장 좋은 평가 점수인 지점을 하나 선택(최소 최대 구하기)한다. A*
5. 처음으로 돌아가서 반복한다.

어떤 길을 선택할지 평가 하는 기준은 아래와 같다.

• F(평가 기준) = G(출발에서 실적 거리) + H(목표까지 예상 (직선) 거리)
• F가 가장 작은 방향을 선택하여 그 쪽으로 뻗는다. (마치 중력에 끌린 물처럼)
• 예상 거리는 직선/가로/세로/대각 거리 등 지도 형태에 따라 결정 한다.

지도 격자의 각 방은 다음과 같은 정보를 기억해야 한다.

• 부모 위치 (X, Y) : 어디서 왔는지 기억한다.
• 소모 비용 G : 출발점에서 지금까지 온 거리
• 예상 비용 H : 목표까지 직선/가로/세로/대각 거리 계산
• 평가 점수 F = G + H
• 자기 상태 (경계 = 열림 = 검토할 표면, 내부 = 닫힘 = 검토 끝)

8방향 탐색이란 경계 부분의 사각형이 자기 주변 8개 방을 검사해서 내부에 해당하는 것을 찾아 거기서 자기로 오는 경로 중에 가장 짧은 쪽을 선택하는 것이다. 그러니까 누구를 부모로 선택할 건지 결정하는 문제다. 그리고 자신은 주변 8개 방 중에 자식(경계)을 만든다. 경계는 열린 곳인데 아직 자신의 부모가 완전히 정해진 곳은 아니다. 내부/경계는 닫힌 곳인데 자신의 부모가 정해진 곳이다.

8방향, 6방향 탐색에선 임의의 각도로 진행할 수가 없다. 8방향에선 수직, 수평, 대각으로만 진행한다. 그러니까 45도 각도로만 움직인다. 고로 어떤 위치에 있는 목표물에 가더라도 최적의 길은 수직/수평/대각 조합으로만 구해진다. 그 목표까지 평행사변형을 그리면 그게 최적의 길이다. 직선을 쭉 그어서 이동하면 되는데 그렇게는 안 된다. 직선은 오직 수평, 수직, 대각에 있을 때만 가능하다. 6방향 탐색에선 60도 각도로만 움직인다. 여기서도 직선 이동이 가능한 경우는 3축을 따라 이동하는 것뿐이다. 나머지 위치는 톱니처럼 구불구불하게 이동하게 된다.

보면 알겠지만 아주 단순한 장애물을 넘어갈 때는 이 방법이 낭비가 많다. 그냥 벽 타기를 하는 것이 더 경제적이다. 미로에서도 벽 타기를 하면 출구에 도착은 할 수 있다. 왼쪽 또는 오른쪽 벽만 타고 가면 된다. 미로에 넓은 방이 있고 그 속에 목표물이 있을 경우는 벽 타기만으로 힘들다. 벽에서 떨어져야 하기 때문이다. 미로와 같은 복잡한 지형에선 자연스럽게 깊이 우선 탐색에 벽타기가 된다. 미로에선 교차로 지점만 기억하면 된다. 미로는 장애물이 많아서 깊이 우선 탐색으로는 최적 경로 찾기 힘들다. 분신술을 써서 여러 경로를 동시에 탐색하는 넓이 우선 탐색을 해야 한다. 여러 분신 중에서 먼저 도착하는 쪽이 최적 경로로 선택 된다. 

동영상에서 다익스트라 방식(Dijkstra's algorithm)은 사방팔방으로 넓이 우선 탐색을 하고 길을 선택하는 것은 A*와 달리 출발점에서 가장 가까운 곳만 따진다. 목표까지의 거리를 따지는 것만 없다. 물결이 퍼지듯이 탐색하는 것이 다익스트라이다. 다익스트라는 출발점과 가장 가까운 지점을 먼저 선택하기 때문에 최소치 찾기를 해야 한다. A*의 경우는 출발지와 목표지의 거리를 함께 따진다. 고로 역시 최소치 찾기를 해야 한다. 이런 최소치 찾기가 시간 낭비라고 생각하면 가장 겉 표면을 무조건 돌아가면서 탐색하는 방법도 있다. 이 방법은 다익스트라보단 빠를 것이나 엉뚱한 곳도 탐색하기 때문에 그 시간 낭비가 추가 된다. (최소값 정렬을 하는 거나 모두 돌아 보는 거나 그 시간이 그 시간일 걸?)

그 어떤 알고리즘을 사용하더라도 미로에선 성능이 거의 비슷하다. 미로에선 어차피 모든 길을 다 돌아봐야 한다. 알고리즘의 성능 차이는 미로가 아닌 장애물이 단순한 벌판에서 나타난다. 직진을 하면 바로 도달하는 경우 다익스트라처럼 넓이 우선 탐색을 하는 것은 시간 낭비다. 이 경우 A*가 더 유리하다. 더 간단하게 직선을 그어서 장애물이 있는지 검사하는 것이 가장 빠르다. 장애물이 있다면 돌아가는 길을 찾아야 하는데 장애물 상태에 따라 여러 방법 중에 적당한 하나를 선택하는 게 좋다.

대부분의 경우 단순한 장벽이 있어 돌아가야 할 경우 어디로 돌아갈 것인지 빨리 결정하는데서 성능 차이가 난다. 돌아가면 길이 있는지 여부는 벽 타기를 통해서 쉽게 확인 가능하다. 반드시 돌아가야 하는 좁은 길목은 중간 목표지가 된다. 출발 ~ 중간 목표 ~ 최종 목표까지 최단거리를 구해 조립하면 더 빠르다. 이런 지점은 주로 돌출한 모서리 부분으로 반드시 돌아가야 하는 위치다. 이 모서리 부분만 직선으로 이어도 최단 거리가 나온다.

D. 편법

토폴로지(위상학)를 이용하면 고리 형태를 하는 것 외엔 모두 동그란 한 덩어리로 볼 수 있다는 것이지. 이 원리를 이용해서 동서남북 벽에 붙은 장애물의 특징을 정할 수 있지.

• 중앙 홀로 있는 장애물 : 0
• 동쪽 벽에 붙은 장애물 : 1
• 서쪽 벽에 붙은 장애물 : 2
• 남쪽 벽에 붙은 장애물 : 4
• 북쪽 벽에 붙은 장애물 : 8

예를 들어 동과 서에 붙은 장애물은 3 = 2+1이라고 나타낼 수 있다. 이런 특징을 장애물들이 모두 가지고 있다면 그 장애물을 만났을 때 물어 볼 수 있겠지 “너는 어디로 돌아가면 되니?” 거기에 더해서 영역에 ID를 부여할 수 있다. 연결된 영역엔 같은 ID를 부여할 수 있어 ID가 다르다면 통하는 길이 없다는 뜻이다. 목표물이 같은 영역 ID를 가진다면 길이 있다는 의미다. 장애물과 마찬가지로 영역도 동서남북 어느 벽에 붙어 있는지 확인할 수 있다. 

위의 그림에서 물체는 모두 영역 C에 있다. 고로 같은 영역이니까 도달할 수 있다. 그런데 영역 C는 동/남/북 벽에 붙어 있다. 중간에 장애물을 만난다. 이 장애물은 서/남/북에 붙어 있다. 무조건 벽만 따라가면 목표물에 도달할 수 있다. 그럼 어느 쪽 방향으로 벽을 따라 가는 게 좋을까? 목표와 가장 가까운 방향으로 일단 간다. 거기서 벽 타기를 양방향으로 동시에 한다. 벽을 따라 가기 지루하니 반드시 벽을 돌아 가야 하는 모서리(돌출 코너)를 추출해서 가장 가까운 곳으로 직진하는 방법을 겸한다.

벽을 따라 갈 때는 지나온 격자 방에 왔던 방향 표시를 해 두어야 한다. 길이 만나게 되면 거기까지 오는 길 중에 짧은 길을 선택하고 긴 쪽은 무시한다. 목표까지 장애물이 없을 때는 벽에서 떨어져 직진 해도 된다. 그래서 가장 짧은 길을 선택한 다음에 그 길을 단축할 수 있는 방법을 찾는데, 그게 돌출한 모퉁이 위치만 연결하는 법이다. 

지도 생성 때 이미 교차로나 돌출된 코너를 파악할 수 있다. 그리고 이 교차로/코너 사이에 직접 연결 되는 인접한 교차로/코너에 대한 정보를 연결해 둔다. 자동차 네비게이터와 비슷한 방식으로 길을 찾는 것이다. 길 탐색은 연결된 교차로/코너에 대한 탐색이다. 적절한 길 선택은 A* 방식과 비슷하다. 이렇게 여러 가지 방법을 섞어 쓰면 좀 더 빨리 길 탐색을 끝낼 수 있다. 

1. 길이 있는지 없는지 파악
2. 길이 있다면 어느 길로, 어느 방향으로 돌아가는 게 좋은지 파악 (길 선택)
3. 최단 거리 결정 (이건 안 해도 좋다. 길을 헤매는 게 더 그럴 듯하니까)

컴퓨터 게임에서 문제가 아직 지도를 다 열지 않아서 길을 모르는데도 유닛들이 최적의 길을 찾아 간다는 것이다. 유닛이 이동하는 것만 봐도 어디에 장애물이 있는지 추측이 가능하니 실감 나지 않는다. 시야 너머는 보이지 않는다. 지도가 없으면 길을 찾을 수 없다. 고로 유닛은 시야 범위 안에서 무조건 직진을 해야 더 그럴 듯하다. 유닛들도 길을 헤매는 모습을 보여 주는 게 더 그럴 듯하다. 우리도 미로에 들어가면 기억력의 한계 때문에 길을 헤매지 않는가?

E. 배열과 코드

이건 예제 C 코드를 분석한 것인데, 코드는 내 것이 아니라 못 올리겠다. 가장 먼저 데이터 구조를 이해해야 한다. 데이터 구조가 모든 것을 말해 준다. 구조체를 사용하지 않은 이유는 아마도 속도 때문인 것으로 보인다. 가능하면 1차원 배열을 사용해야 속도가 빠르다. 다차원 배열을 사용하면 첨자(index)의 덧셈 시간이 소모되어 속도가 떨어지겠지.  다음과 같은 배열이 필요하다.

지도 2차원 배열

• 지도의 갈 수 있는 곳과 없는 곳이 표시된 2차원 배열
• 지도의 방이 탐색할 경계인지 탐색한 내부인지 표시한 2차원 배열
• 각 방의 부모(출발지)의 x좌표를 저장한 2차원 배열
• 각 방의 부모(출발지)의 y좌표를 저장한 2차원 배열
• 각 방의 G값(거리)을 저장한 2차원 배열이다.

탐색 경계 1차원 배열

• 탐색 경계에 해당하는 방의 아래 정보에 접근할 index를 가진 1차원 배열
• 탐색 경계에 속하는 방의 x좌표를 저장한 1차원 배열
• 탐색 경계에 속하는 방의 y좌표를 저장한 1차원 배열
• 탐색 경계에 속하는 방의 F값(실적 + 예상 거리)을 저장한 1차원 배열
• 탐색 경계에 속하는 방의 H값(예상 거리)을 저장한 1차원 배열

찾은 길을 저장하는 1차원 배열

• 인구수에 해당하는, 그들이 기억할 길의 길이(배열 크기)
• 인구수에 해당하는, 그들이 기억할 길에서 현재 위치
• 인구수에 해당하는, 그들이 기억할 길을 저장한 가변 길이 배열

A* 호출 함수

실제 길을 찾는 함수(누구, 시작 위치, 목표 위치)

좀 더 길 찾기에만 집중하려면 누구인지도 알 필요 없겠지. 여러 유닛이 같은 길을 따라 갈 수도 있으니까.

길 찾기 작업 순서

1단계 : 지도 유닛/목표 좌표 → 격자 좌표 변환 ※ 중요한 부분은 아니다.
2단계 : 출발=도착? or 도착 지점이 갈 수 없는 곳인지 사전 체크
3단계 : 이전 길 찾기 지도에 표기한 내용들 깔끔하게 지우기
4단계 : 시작 위치를 탐색 경계 목록에 넣는다.
5단계 : 길을 찾을 때까지 아래 내용 반복.

5.1단계 : 탐색 경계 목록 중에서 가장 작은 F값인 놈을 하나 취한다.
5.2단계 : 바이너리 힙을 정리하여 다음 최소 F값인 놈을 앞에 둔다.
5.3단계 : 주변 8개 방을 돌며 다음 내용 반복.
※ 바이너리 힙은 최소값을 찾아 제일 앞에 두는 방법이다.

5.3.1단계 : 지도 밖, 탐색 영역 내부(닫힘), 장애물은 검토하지 않고 피한다.
5.3.2단계 : 수직, 수평이 동시에 막혔을 때는 그 방향 대각을 검토하지 않고 피한다.
5.3.3단계 : 새로운 방이면 경계/표면(열림) 목록에 넣는다.
5.3.4단계 : F, G, H값을 계산한다.
5.3.5단계 : 바이너리 힙을 정리하여 최소 F값인 놈을 앞에 둔다.
5,3,6단계 : 이미 경계/표면(열림) 방이면 최적의 부모를 다시 찾는다.
5.3.7단계 : F, G, H값을 계산한다.
5.3.8단계 : 바이너리 힙을 정리하여 최소 F값인 놈을 앞에 둔다.

6단계 : 탐색 경계/표면(열림) 목록에 아무것도 없으면 더 탐색할 길이 없다.
7단계 : 목표에 도달했다면 길이 있다. 길을 거꾸로 밟아 저장한다.

F. 바이너리 힙

이건 최소값, 최대값을 골라내는 방법이다. 반복해서 최소값을 찾아내야 하기 때문에 순서를 미리 정리해 두면 다음에 찾기 편할 것이다. 삽입 정렬이란 것을 사용하면 새로운 것이 추가될 때 이미 정리 해 둔 순서에 삽입해 넣기만 하면 되니까 시간이 절약 된다는 논리다. 하지만 비교와 삽입(이동)에 처리 시간이 많이 소모된다.

바이너리 힙은 토너먼트 방식의 분할 정리 방식이다. 2등 이후부터는 정확한 순서가 중요하지 않고 무조건 1등만 찾아내는 방식이다. 2명씩 대결 해서 이긴 사람끼리 싸움을 붙이는 방식이다. 각 싸움에서 이긴 사람이 높은 자리를 차지하기 때문에 나중에 새로 끼어든 놈은 1등 자리에서 시작하여 아래로 내려오며 싸워 자기 자리를 찾아 간다. 진 놈은 아래로 내려 가고, 이긴 놈은 위로 올라간다.

1등을 제외하면 같은 층에 있다고 해서 같은 실력은 아니다. 좌측이 전반적으로 약골이고 우측이 전반적으로 강골일 수 있으나 같은 층에 배치된다. 4강이라고 해서 같은 실력의 4등 안에 들어가는 것이 아니다. 토너먼트 방식에선 오직 1등만 의미가 있다. (월드컵 4강 신화가 결국 헛것이었다. 결국 우린 항상 16강도 못 되는 실력이었다.)

1차원 배열이 있을 때 첨자 0의 자리는 배열의 길이를 나타내는데 사용한다. 첨자 1은 최소값, 최대값인 1등의 자리다. 나머지 자리는 토너먼트의 각 층과 짝을 나타낸다. 그래서 자기 짝(형제)을 찾는 방법과 부모와 자식을 찾는 방법이 필요할 것이다. 왜냐하면 자식들은 부모와 싸워 자리 바꾸기를 하기 때문이다. 

자세한 동작 순서는 고민해 볼 것. 나도 잘 모르겠다. ㅋㅋㅋㅋ

---

노인들이 박정희 시대를 살았으니 박정희에 대해 잘 안다? 히틀러 시대를 산 독일인들이 히틀러에 대해 잘 알았을까? 그럼 이 시대를 함께 사니 이명박근혜에 대해서도 잘 알겠군? 어떻게 그 시대를 살았다고 그 시대 사건들을 잘 알겠나? 보수우익꼴통들은 말이 안 되는 얘기를 하도 많이 들어서 현실감이 떨어진다.

서울대 빨갱이는 모두 북한에서 돈 받아 공부했다고 하는데 고등학교까지 교육에 얼마 들어가니? 서울대 들어가면 국가에서 돈을 주는데 왜 북한 돈을 받겠냐? 비싼 연고대라도 들어갈 정도로 머리가 나쁘면 모르겠다. 말이 안 되는 소리를 해도 믿으니 꼴통이라고 할 수밖에 없지. 얘들은 가난하기 때문에 자생적으로 빨갱이가 된 것이다. 박정희가 가난으로부터 구해주지 않아서 말이지. 

고교 수학 수준 컴퓨터 게임 물리 시뮬레이션

고등학교 수학 수준의 컴퓨터 게임 물리 시뮬레이션을 만드는 방법이다. 내 대가리가 대학 수준으로 설명할 수준이 안 되고, 옛날 블로그도 다 날려서 공식이 기억도 안 난다. 그래서 아이디어만 정리 해 본다.

1. 에너지 → 힘 → 가속도 → 속도 → 거리

에너지는 자동차 연료통의 크기라고 보면 되고, 힘은 자동차 엔진 크기라고 보면 된다. 큰 힘을 내려면 엔진이 크고 순간 에너지 공급 양이 많아야 한다. 에너지를 소모하면 힘이 나온다. 그런데 같은 힘이라도 무거운 차와 가벼운 차일 때 가속도가 다르다. 이 가속도가 속도의 변화로 이어지고, 속도가 거리 변화로 이어진다. 이를 물리 공식으로 나타내면 아래와 같다.

• e = f * d (에너지 = 힘*거리)
• f = m * a (힘 = 질량*가속도)
• v = a * t (속도 = 가속도*시간)
• d = v * t (거리 = 속도*시간)

컴퓨터 게임에선 Δt (1/30초 또는 1/60초 순간/찰나) 동안 상태가 일정하다고 가정하고 물리 시뮬레이션을 한다. 그럼 다음과 같은 식으로 계산을 할 수 있다.

1. 힘 f = 임의로 정한다. 적당한 연료를 소모했다고 보자.
2. 가속도 a = f/m
3. 속도 변화 Δv = a*Δt
4. 속도 수정 v.new = v.old + Δv
5. 거리 변화 Δd = v.new*Δt
6. 거리 수정 d.new = d.old + Δd

1D에선 방향만 있으니 +/- 구분만 하면 되는데 2D에선 x축, y축이 있으니까 벡터 개념이 나온다. 어렵게 생각할 것 없이 x성분, y성분 각자 계산하면 된다. f, a, v, d 모두 (x, y) 성분으로 분해된다. 3D에선 (x, y, z) 3개 성분으로 계산하면 된다. 여기까진 쉬운 것이다. 여기까지 내용으로 로켓이나 포탄의 비행을 시뮬레이션 할 수 있다.

에너지 vs 운동량(충격량)

힘, 속도, 거리, 시간, 가속도, 질량은 물리 현상 중에 직관적으로 이해하기 쉬운 개념이다. 에너지는 직관적으로 이해하기 어렵다. 물리학자들도 고민을 많이 한 개념이다. 에너지와 운동량의 개념 차이도 상당이 헛갈린다. 그 차이를 간단하게 설명하겠다.

에너지를 이해하려면 도르래를 이해하면 된다. 물체의 무게가 곧 힘이고, 이 물체를 들어 올리는 높이가 거리이다. 에너지란 힘과 거리의 곱이니 무게와 높이의 곱이 된다. 여기까진 이해하기 쉽다. 이 물체를 잡던 줄을 놓으면? 땅에 떨어질 것인데 이게 운동 에너지다. 이 운동 에너지는 높이 있던 물체에 숨어 있었던 것이다. 높은 곳에 있는 물체는 잠재 에너지가 있는 것이다. 떨어지면서 잠재 에너지가 운동 에너지로 바뀌는 것이다.

자 그러면 공중에 정지하고 있을 때 우리가 알 수 있는 정보는 질량, 높이다. 그리고 떨어진 후에 우리가 알 수 있는 정보는 시간, 속력, 중력 가속도이다. 이 정보들로 서로 호환 가능한 잠재 에너지와 운동 에너지를 수학적으로 표현할 수 있을까? 그렇게 해서 찾아낸 것이 에너지와 운동량 공식이다. 그래서 이 둘의 차이가 뭔지 고민했던 것이다.

그러면 이번엔 낙하 시간을 알고 있으니 힘과 시간을 곱할 수도 있을 것이다. 이것이 운동량이다. 이 잠재적인 운동량도 운동으로 바뀌는데 그게 무게와 속력의 곱이 된다. 에너지 개념보다는 더 직관적으로 이해하기 쉽다. 그럼 왜 운동량 대신 에너지를 사용하는 것일까? 열/빛 에너지와 호환이 되는 건 잠재/운동 에너지다. 그럼 운동량은 필요 없는 개념인가? 운동량과 에너지의 차이는 2차원, 3차원 벡터 합성을 할 때 나타난다. 1차원 운동일 때는 둘의 진짜 차이를 알기 어렵다.

• 잠재 에너지 = 힘 * 거리 ☞ 무게 * 높이
• 운동 에너지 = ½ * 질량 * 속력² ☞ ½ * 무게 * 빠르기² ☞ 스칼라
• 운동 에너지 = 잠재 에너지의 변화량
• 운동량 = 질량 * 속도 ☞ 무게 * (빠르기 * 방향) ☞ 벡터 (이동은 방향이 있다)
• 충격량 = 힘 * 시간 = 충격 * 시간 ☞ 벡터 (힘은 방향이 있다)
• 충격량 = 운동량의 변화량

운동 에너지와 헛갈리는 게 하나 있는데 운동량이다. 속력과 속도의 차이이다. 속력은 단순 빠르기(스칼라)만 의미하고, 속도는 방향까지 포함한 빠르기이다. 이런 것을 벡터라 부른다. 단지 잠재 에너지를 속력으로 바꾸어 표현한 것이 운동 에너지이다. 운동량은 벡터인 속도에 스칼라인 질량을 곱해 운동의 세기와 방향을 표현한 것이다. 그러니까 이 둘은 이름이나 공식 속의 변수가 비슷하다. 그래서 헛갈렸던 것이다.

• 벡터 : 힘, 가속도, 속도, 거리, 운동량 (벡터 * 스칼라 = 벡터 = 방향성 계승)
• 스칼라 : 압력, 시간, 질량, 에너지 (벡터 * 벡터 = 스칼라 = 방향성 없음)

잠재 에너지와 헛갈리는 게 하나 있는데 충격량이다. 거리와 시간의 차이이다. 물체를 끌어 올린 거리와 물체를 끌어 올린 시간 차이다. 물체를 너무 빨리 끌어 올리면 충격을 받는다. 즉 짧은 시간에 큰 힘이 가해지면 충격이 크다. 충격량의 원래 뿌리는 운동량이다. 운동하던 물체가 충돌했을 때 저지력(저항력/충격력)과 저지한 거리(에너지), 저지한 시간(충격량)의 차이인 것이다.

파괴력이나 관통력을 계산할 때는 에너지를 이용하고, 벡터 합성 분해를 할 때는 운동량을 이용한다고 생각하면 된다. 즉 X, Y, Z방향 운동량을 벡터 합성하면 총 운동량과 같은데, 각 방향의 에너지를 구한 후에 벡터 합성을 하면 총 에너지와 다르다. 에너지는 따로 계산해서 합성할 수가 없다. 게임에서 운동을 표현할 때는 벡터 합성을 이용하고, 파괴력을 표현할 때는 에너지를 이용한다.

2. 중력과 풍력 추가

앞의 로켓이나 포탄에서 이제 중력과 풍력 등 다른 방향의 힘이 더해진다고 하자. 그럼 벡터 합성이 필요해진다. 에너지는 모두 합성한 후에 최종적으로 계산하는 것이다. 벡터 성분들은 모두 따로 계산해서 합성할 수 있다. 힘, 가속도, 속도, 변위(위치 변화) 모두 벡터라고 했다. 벡터 합성은 쉽다.

포물선은 포탄이 날아가는 곡선을 의미한다. 이 포물선을 계산하려면 단순히 수직, 수평 성분으로 힘을 분해하기만 하면 된다. 수직 성분은 중력 가속도의 영향을 받는다. 3D는 복잡하니까 2D로 가정하자. 수직 방향은 y축, 수평 방향은 x축이라고 놓자. 중력 가속도를 물체의 수직 가속도에 더하기만 하면 된다. 수평 성분은 풍력의 영향을 받는다. 풍력(힘)을 질량으로 나눠 가속도를 구한 후에 수평 가속도에 더하기만 하면 된다. 복잡하게 포물선 계산을 할 필요가 없다. 이렇게 짧은 시간으로 미분(나누기)하여 계산한 후에 적분(누적하기)하면 운동의 묘사가 된다.

가속도 = 엔진 가속도(X, Y) + 중력 가속도(수직) + 풍력 가속도(수평)

3. 인력, 척력, 중력

인력은 당기는 힘, 척력은 미는 힘이다. 중력은 인력에 속하며 보통 2가지로 계산 된다. 땅에 인접한 경우는 땅을 무한 평면으로 보고 중력 가속도 G를 적용한다. 실제 물리에선 9.8이라고 하는데 게임 세계 속에선 임의의 값으로 정한다. 우주로 나가면 그 때는 지구가 작은 공처럼 보이기 때문에 지구 중심에서 거리 제곱에 반비례하는 인력으로 작용한다. 이건 빛이 퍼지는 원리와 같다.

• 무한 평면 중력가속도 = 상수 ☞ 대기권 안에서 작용하는 중력
• 무한 원통 중력가속도 = 기준값/거리 ☞ 원심력을 이용한 중력 발생 우주선
• 원형 지구 중력가속도 = 기준값/거리² ☞ 인공 위성에 작용하는 중력

원심력을 이용한 중력 발생을 하는 우주선의 경우 원심력 = 구심력 = 중력이 된다. 이 경우 구심력 공식(mv²/r)에 의해서 중력은 1/R에 비례하게 된다. 게임에서 쓸 일이 있을까?

표면 장력 같은 인력이나 척력의 경우는 전자기적 힘에 의한 것이기 때문에 거리 제곱(전기장)이나 거리의 3제곱(자기장)과 관련 있다. 그런데 임의로 정해도 된다. 진짜 물리 시뮬레이션은 아니니까.

인력 또는 척력 = 기준값/거리 or 기준값/거리² or 기준값/거리³

4. 마찰력, 저항력, 종단속도

접촉한 물체는 마찰력이 작용하고, 공기 중에선 공기 저항이 작용한다. 잘 생각해 보면 마찰력과 공기저항은 본질적으로 같은 것이다. 그래서 마찰력과 저항력을 구해서 물체의 질량을 나눠 가속도(감속도)를 구한다. 가속도가 음수면 감속도인 것이다. 마찰력과 저항력은 이론적으로 구할 수 있는 값이 아니고 실험적으로 구할 수 있기 때문에 게임에선 마음대로 줘도 된다.

마찰력은 물체의 질량에 비례하고, 방향은 물체의 이동 방향의 반대이다. 저항력은 물체의 속력에 비례하고, 방향은 이동 방향의 반대이다. 물체가 종단 속도에 도달했을 때는 마찰력/저항력과 물체를 가속하는 엔진의 힘/중력과 균형을 이루게 되어 종단 속도를 유지하며 이동한다. 즉, 가속도 0 상태이다.

무거운 것과 가벼운 것은 왜 동시에 떨어질까? 종단속도

• 마찰력 = 질량 * 비례상수 → 비례상수 = 감속도
• 저항력 = 속도 * 비례상수
• 가속도 = 엔진가속도 + 중력가속도 + 풍력가속도 - 마찰감속도 - 저항감속도

5. 강체(고체) 충돌

강체는 고체 중에서 딱딱한 것을 말한다. 쇠사슬 같은 것도 고체에 속하지만 밧줄이나 그물처럼 휜다. 고로 끈이나 천도 고체에 속하지만 강체라고 보긴 어렵겠다. 물렁물렁한 진흙도 고체에 속하지만 강체는 아니다. 강체는 완전탄성충돌을 한다. 완전탄성충돌 공식은 인터넷 검색을 해 보라. 여기에 반발계수(탄성계수)를 적용해서 속도를 약간 감소시키는 방식으로 비탄성충돌을 흉내 낸다. 

충돌을 할 때 충돌면을 계산한다. 이 충돌면에 수직 방향(법선 방향)의 속도만 계산에 동원한다. 수평 방향(접선 방향)은 변화가 없다. 물체 A와 B가 있다. 질량은 Am, Bm이다. 충돌 전 속도는 Av, Bv이다. 충돌 후 속도 Aw, Bw는? 여기서 에너지와 운동량의 협력이 필요하다.

• Am*Av + Bm*Bv = Am*Aw + Bm*Bw (운동량 보존 법칙)
• 충돌 전후의 전체 운동량 변화가 없다.

• Am*Av²+ Bm*Bv²= Am*Aw²+ Bm*Bw² (에너지 보존 법칙)
• 충돌 전후의 전체 에너지 변화가 없다.

이 두 법칙을 이용해서 충돌 후 속도를 구하면 아래와 같다.

• Aw = {(Am - Bm)*Av + 2*Bm*Bv}/(Am + Bm)
• Bw = {(Bm - Am)*Bv + 2*Am*Av}/(Am + Bm)
• 충돌후속도 = {질량차이*충돌전속도 + 2*상대방운동량}/전체질량
• Aw = {(Am*Av + Bm*Bv) + Bm(Bv - Av)}/(Am + Bm)
• Bw = {(Am*Av + Bm*Bv) + Am(Av - Bv)}/(Am + Bm)
• 충돌후속도 = {충돌전 운동량 합 + 상대방질량(충돌전 속도차))/전체질량
• (Aw – Bw) = (Bv – Av) ☞ 충돌 전후의 상대 속도는 같고 방향만 반대
• (Aw + Av) = (Bw + Bv) ☞ 충돌 전후의 속도 합이 같다

여기서 상대 속도에 대해서도 계산이 통하기 때문에 기준 속도를 뺀다고 하면?

• (Am + Bm)Aw = {(Am - Bm)*Av + 2*Bm*Bv} 수식은 다음처럼 변경
• (Am + Bm)(Aw - Av) = 2*Bm(Bv - Av) @ Av = 기준 속도
• (Am + Bm)(Aw - Bv) = (Am - Bm)(Av - Bv) @ Bv = 기준 속도

여기서 기준 질량을 나누어 준다고 하면? 상대 속도, 상대 질량으로 계산 가능

• (1 + R)(Aw - Av) = 2*R(Bv - Av) @ 자기 Av, Am 기준, R = Bm/Am
• (R + 1)(Aw - Bv) = (R - 1)(Av - Bv) @ 상대 Bv, Bm 기준 R = Am/Bm

여기서 상대방 기준으로 계산한 경우 자신의 충돌 전후 상대 속도 변화를 구할 수 있다.

• 상대 Bv, Bm 기준 Rm = Am/Bm, Rv = (Aw-Bv)/(Av-Bv)
• Rv = (Rm-1)/(Rm+1) @ -1 < Rv < 1 
• Rm = (1+Rv)/(1-Rv)
• 질량의 비율이 같다면, 상대 속도의 변화 비율도 같다.

자기 기준일 때는 다음과 같은 꼴이다. (상대가 와서 박을 때)

• 자기 Av, Am 기준 Rm = Bm/Am, Rv = (Aw-Av)/(Bv-Av)
• Rv = 2Rm/(1+Rm) = (Rm+Rm)/(Rm+1) @ 0 < Rv < 2
• Rm = Rv/(2-Rv)
• 상대방 기준의 경우에서 +1을 한 것과 같다.

상대 값으로 계산한 후에 절대 값으로 환산하는 게 쉽다

위의 그래프 해석은 이렇다.

• 상대가 너무 가벼운 경우 나는 속력을 거의 잃지 않고, 상대는 튕겨 나간다. 즉 에너지를 거의 전달하지 못 한다. 더 밀고 싶어도 못 밀어 준다.
• 상대가 너무 무거운 경우 상대는 거의 움직이지 않고, 내가 반대로 튕겨 나간다. 즉 에너지를 거의 전달하지 못 하고 돌려 받는다. 벽과의 충돌에 해당.
• 상대와 내가 비슷한 무게인 경우, 에너지는 그대로 전달 된다. 나는 멈추고, 상대는 그대로 같은 속도로 튕겨 나간다.

여기서 충돌 후 속도를 구한 후에 반발 계수에 따라 속도 감속을 한다.

• e = -(Aw - Bw)/(Av - Bv) = -충돌후속도차/충돌전속도차, 0<e<1
• 반발계수가 1이면 완전탄성충돌, 0이면 떡처럼 붙어 버린 경우

예를 들어 e = 50%라면 충돌후 속도를 50% 줄이면 된다. 이렇게 구한 법선 방향 속도를 접선 방향과 다시 합성한다. 벡터 합성은 서로 직각이니 피타고라스 정리를 사용한다.

자 그러면 법선 방향만 추출하는 방법을 또 알려 달라고 하겠지? 이런 경우 물체의 형상을 단순화시켜야 한다. 형상이 복잡하면 충돌 지점을 계산하기도 힘들고 복잡한 회전도 함께 발생한다. 그래서 원형이 가장 쉬우니 원형이라고 가정한다. 원형이라도 회전은 발생하지만 무시하자. 원과 원의 중심선을 이으면 그게 법선이다. 이것과 수직인 것이 접선이다.

속도/좌표는 이미 (X, Y) 성분으로 분해되어 있을 것이다. 방향 벡터(두 구체의 중심 좌표 차이)를 구하면 그게 바로 법선 벡터이다. 이 법선 벡터의 X, Y 값을 서로 바꾸면 그게 접선 벡터이다. 법선 방향 속도는 법선과 속도의 벡터 내적(스칼라곱/점곱)을 취하면 얻어진다. 공식은 위와 같다. 법선과 접선 벡터는 기준이 되기 때문에 어느 방향이든 상관없으니 하나로 통일하면 된다. 두 물체 중에 어느 하나가 기준이 되면 된다.

접선 방향의 속도 차이가 있게 되면 그게 표면 마찰을 일으켜서 회전력으로 작용한다. 그럼 어느 정도 회전이 발생할까? 이건 계산이 복잡하다. 물체의 이동과 회전 사이의 에너지/운동량 변환이 필요한데 공식을 모르겠다. 회전이 발생한 만큼 이동하는 에너지와 운동량이 줄어야 한다. 원형 물체의 경우 이동에선 모든 질량이 중심에 있다고 가정하고, 회전에선 모든 질량이 표면에 있다고 가정하고 계산한다. 여기까지만...

당구공의 충돌이라고 할 경우 충돌 지점의 접선, 접면을 계산해야 한다. 그래서 법선, 접선 방향을 구분해서 법선 방향에 대해서만 위의 충돌 공식을 적용할 수 있다. 간단하게 이 문제를 이해하려면 당구공과 수직, 수평의 무한 질량을 가진 당구대 벽과의 충돌을 상상하면 된다. 벽이 수직과 수평 방향으로 서 있기 때문에 충돌 지점의 법선과 접선이 수평, 수직 방향으로 단순해진다.

이 경우 법선에 대해서만 위의 공식을 적용하면 되기 때문에 간단하다. 벽의 질량이 무한이고 속도는 0이다. 고등학교 수학을 생각하며 잘 계산해 보면 법선 방향의 속도가 반대가 되어 튕겨 나오는 것을 알 것이다. 그래서 수직, 수평 장벽과 충돌은 의외로 간단하게 계산 된다. x방향, y방향의 속도 중에 하나의 부호만 뒤집으면 된다. 여기까지 내용으로는 당구 게임을 흉내 낼 수 있다. 

6. 액체의 부력, 기체의 양력

액체의 경우는 형상이 없는 점으로 계산한다. 이 점은 인접한 점과의 거리에 따라 인력(표면 장력)이 작용한다. 어느 정도 거리 밖에선 위와 같은 탄성 충돌로 계산하고, 어느 거리 안에선 표면장력이란 것이 작용하기 때문에 약간의 인력을 추가한다. 그리고 어떤 거리 안에선 무한대의 척력을 내서 압축이 되지 않도록 한다. 액체는 고체와 마찬가지로 압축이 안 된다. 액체는 유동적인 고체라고 보면 된다.

중력 구간(원거리) ~ 인력 구간(근거리) ~ 척력 구간(입자 내부)

부력의 경우는 물체가 밀어낸 액체의 양의 무게와 물체 자체의 무게를 비교해서 그 차이만큼 힘이 작용하게 된다. 물체가 표면에 떠 있을 때는 부력이 0이 된 상태이다. 가라앉은 부분만큼의 물의 양이 물체의 무게가 된다. 부력은 중력의 반대 방향이다.

물에 빠지는 순간 물과의 마찰로 에너지/운동량을 잃기 때문에 가라앉았다가 솟아오르기를 무한 반복할 수는 없다. (탄성 충돌 참고) 액체 속에서 이동은 마찰력으로 속도 손실을 가져온다. (종단 속도 참고)

힘과 압력의 차이, 벡터와 스칼라, 삼투현상 & 모세관현상

부력 = (액체 무게 – 물체 무게)

물체와 물의 무게 비교는 비중을 보면 안다. 물은 비중이 1이고 기준이다. 1㎥부피는 1톤, 10㎤=1ℓ 부피는 1kg, 1㎤ 부피는 1g이다. 기체의 경우는 1㎥ 부피에 1g이라고 생각하면 된다. 

7. 기체와 스프링과 와이어

기체의 경우도 형상이 없는 점으로 계산한다. 이 기체의 경우는 스프링처럼 압축이 된다. 그리고 표면장력 같은 점성이 없다. 고로 척력만 있는 경우에 해당하며 완전탄성충돌을 한다. 기체는 중력의 영향을 받지만 일상 생활공간에선 중력의 영향을 받지 않는 것으로 처리한다. 이런 기체를 시뮬레이션 할 경우는 없을 것이다.

코일 스프링은 단순하다. 당기거나 압축시킨 길이에 비례하여 힘이 나온다. 그래서 힘 측정기로 사용하기도 한다. 이런 특징을 선형적이라 한다. 기체의 경우는 압력이 부피에 반비례하기 때문에 비선형적이다. 코일 스프링 시뮬레이션은 쉽다. 판 스프링은? 몰라.

스프링 변형 길이 = 힘

실, 밧줄, 쇠사슬, 그물, 천 같은 것은 고체일까? 고체이다. 작은 고체들이 쇠사슬처럼 엮여 있다고 생각하면 된다. 이런 것들은 점과 점 사이의 직선으로 표현한다. 이 직선이 스프링처럼 탄성이 있으면 고무줄이 된다. 문제는 엮여 있어서 힘이 전파되기 때문에 연쇄반응으로 계산이 많아진다. 이런 거 해 주는 라이브러리(누군가 만들어 제공하는 함수들) 많다.

A를 치면? → B → C → D → ... 계산법은? 몰라

그럼 불은 뭘까? 화학반응이다. 화학 반응을 구현하는 건 내 수준을 넘는다. 화학 반응이란 a와 b가 만나서 하나로 합쳐지면서 열과 빛을 내고 부피가 커지는 반응이다. 그러니까 합성된 기체(CO₂나 H₂O 등)의 운동량이 증가하며 빛과 열을 내며 터진다는 것이지.

8. 회전(토크)

물체는 충돌할 때 회전도 한다. 그럼 에너지, 운동량, 각운동량, 토크 사이의 변환이 필요할 것인데 여기엔 답이 없다. 이걸 제대로 계산하려면 물체 형상에 따라 적당한 미분 적분을 해야 한다. 그럴 시간이 없으니까 물체의 형상을 단순화해야 한다. 원, 공, 정사각형, 정육면체(입방체) 등으로 말이다. 이런 물체는 회전 중심(무게 중심)이 정확하게 가운데 있고 대칭적이다. 충돌 지점도 단순화시키기 위해서 원, 공으로 계산한다.

충돌 순간에 에너지와 운동량의 어느 정도가 회전으로 전환될지 계산이 어려우니 물체의 질량과 크기(반지름)만 가지고 임의로 회전을 주는 방법도 있겠다. 이건 너무 골치 아프다. 회전에선 저울/톱니/바퀴 시뮬레이션도 필요하기 때문에 토크 개념은 알고 있어야 한다.

• t = r*f (토크 = 반지름 * 힘)
• w = r*m*v (각운동량 = 반지름 * 운동량)

위의 공식은 모든 질량이 표면 껍질에 몰려 있고 형상이 원, 공인 경우로 가정한 것이다. 형상이 복잡한 물체는 무게 중심 계산도 힘들다. 예를 들어 무게가 1과 2인 물체를 저울에 올리면 저울의 팔은 반대로 저울 중심(무게 중심)에서 2와 1의 길이가 되어야 한다. 반지름이 1과 2인 톱니가 서로 맞물려 돌아갈 때 회전 속도는 반대로 2대 1이 된다. 도르래도 저울과 원리가 비슷하다. 무게와 길이 사이의 관계이다. 

저울이 중심을 잡기 위해 위아래로 흔들리는 현상을 알 것이다. 이런 원리는 무게 중심의 이동에 있다. 저울의 중심을 잡아주는 접촉점은 이상적인 점이 아니다. 면적이 있는 물체 표면이기 때문에 저울 팔이 기울면서 접촉면도 살짝 이동을 한다. 그래서 무게 중심이 이동하기 때문에 반대로 균형을 잡으려는 힘이 작용하게 되는 것이다. 게임에선 임의의 값으로 지정해 줄 수 있다.

만약 반대 방향으로 회전하는, 무게와 회전 속도가 다른 두 팽이가 충돌하게 되면 어떻게 될까? 회전 방향은 접선 방향이다. 접선 방향의 에너지/운동량을 잃은 만큼 회전이 바뀐다. 그럼 얼마가 이동으로 빠지고, 얼마가 회전으로 빠질까? 계산 공식은 모르겠다. 포기! (대학교 물리학 책을 보면 되잖아? 아니면 라이브러리를 구해서 사용하면 되겠지?) 법선 방향에 작용하는 힘은 마찰력에 비례한다. 이 마찰력에 의해 접선 방향의 속도가 영향을 받는다. 마찰력은 서로가 접촉해서 미는 힘에서 온다.

9. 거리 계산 → 충돌 계산

충돌을 계산하려면 근처에 있는 것인지 아닌지 구분부터 해야 한다. 충돌은 거리와 크기에 관계있기 때문이다. 지구 반대편에 있는 물체와 충돌 검사를 하는 것은 의미 없을 것이다. 100개의 물체 사이의 거리를 계산하려면 약 100²/2 = 5000번의 비교 계산을 해야 한다. 이건 너무 비효율적이다.

게임 공간을 적당히 사각형으로 나눈다. 그 공간에 속하는 물체는 그 공간에 자신을 등록한다. 그래서 그 공간 주변(3x3블록)에 속하는 것들끼리만 거리 계산을 해 보고 충돌 가능성이 있는 것들끼리 충돌 검사를 한다. 즉 멀리 있는 다른 세계의 물체는 충돌 검사가 필요 없다.

이건 물체의 수가 많을 경우에 그렇게 한다는 것이고 물체의 수가 적을 때는 모든 물체끼리 거리 계산을 다 해도 된다. 그리고 충돌 가능성이 있는 것에 대해선 충돌 검사를 한다.

충돌 검사는 형태와 관계있기 때문에 역시 형태를 단순한 원, 공, 정사각형, 입방체로 보는 것이 편하다. 원, 공은 중심 사이의 거리를 계산하면 된다. 3D에서도 계산이 가장 쉽다. 정사각형, 입방체의 경우는 어느 한 개를 기준으로 회전시켜 x, y, z축을 일치시킨 후에 복잡한 계산을 해야 한다. 만약 x, y, z축이 항상 일치하는 경우에는 충돌 검사가 쉽다. 그런 경우가 정사각형, 정마름모이다. 

• 원의 충돌 : dx² + dy² < (Ra + Rb)²
• 정사각형 충돌 : dx and dy < Ra + Rb
• 정마름모 충돌 : dx + dy < Ra + Rb

원의 경우 충돌 계산과 거리 계산 공식이 같다. 그래서 한 번의 계산으로 거리 계산과 충돌 여부 판단이 가능하다. 정사각형이나 정마름모의 경우는 물체의 형상이 원형이 아닌 건물 같은 경우에 적용한다. 먼저 원형으로 보고 거리 계산을 한 후에 충돌 가능한 거리에선 정사각형과 정마름모로 다시 계산을 한다. 그러니까 역시 원형이 가장 기본이 되는군.

같은 형태가 아닌 서로 다른 형태인 원과 정사각형의 충돌을 계산한다고 할 경우 사각형은 4개의 선으로 되어 있으니 원과 4개 직선의 접선, 교점 구하는 문제가 된다. 3D에선 접선이 접면이 되고 교점이 교차선이 된다. 원보다는 사각형을 기준 좌표로 보고 축을 회전하여 x, y에 맞추고 계산하는 것이 더 쉬울 것이다. 원은 회전을 해도 원이기 때문이다.

이렇게 하면 사각형의 모든 직선은 x, y축에 수직이거나 평행하게 된다. 그럼 계산이 쉬워지지. 회전 공식을 알아야 하겠군. 인터넷 검색! 사각형의 꼭짓점이 원과 접촉한 경우는 반대로 원을 중심으로 4개 꼭짓점이 원의 안에 있는지 검사하는 것으로 충돌 검사를 할 수 있다. 

• 2D 선의 공식 → 3D 면의 공식
• 2D 원의 공식 → 3D 구의 공식

2D에서 3가지 형태의 직선 공식 → 3D에서 3가지 형태의 평면 공식

• y = a*x + b → z = a*x + b*y + c
• a*x + b*y = c → a*x + b*y + c*z = d
• x/a + y/b = 1 → x/a + y/b + z/c = 1

위에서 2D에서 선을 표현하는 것은 3D에선 면이 되었다. 그럼 3D에서 선은 어떻게 표현 하냐? x-y, y-z, z-x 사이의 관계 3개를 통해서 표현한다. 다시 말해서 xy, yz, zx 3면에서의 직선 공식으로 3D에서 직선을 표현한다. 보통은 벡터(좌표 A ~ 좌표 B)로 표현하면 쉽다.

3D로 가면 머리가 복잡하고 복잡한 모양의 물체의 충돌과 회전을 처리하기는 힘들다. 여기까지 내용으로는 포탄의 포물선 시뮬레이션이나 원, 공의 충돌 정도만 처리할 수 있을 것이다. 원, 공을 사용하면 일단 회전 문제를 신경 쓰지 않아도 되니 좋다. 더 이상 공부해도 진전이 없는 바보짓이니 여기서 그만 하자.

3D 문제 → 2D 문제 → 1D 문제로 분해하여 푼다.

---

우리 사랑스런 친일독재잔당은 토목공사를 좋아한다. 그래서 강바닥, 길바닥에 돈을 뿌린다. 멀쩡한 강물 막아 오염시키고, 사람이 살지도 않을 곳에 건물을 짓고, 차가 다니지도 않을 곳에 도로를 깐다. 이미 유럽 → 미국 → 일본에서 했던 세금 낭비 정책 아닌가? 그 돈을 복지에 썼더라면 많은 사람이 행복했을 것인데.

거기에 증세 없이 복지 하겠다는 새빨간 거짓말을 하고 (이게 무슨 헛소리인가?) 결국 담배 값 올리고 복지는 없지. 거기에 철도 민영화(사유화)로 교통비만 비싸게 올리려 하고. 이것도 이미 다 유럽 → 미국 → 일본에서 했던 국민 기만 정책 아닌가? (일본에 가니 교통비가 비싸더라, 유럽에 가니 공항료가 너무 비싸더라. 모두 민영화 된 곳이다.)

게임 산업은 핍박을 하지. 그런데 게임이 장기, 바둑, 카지노와 뭐가 다른가? 지역 경제 살리려고 카지노 하는 것이지? 그럼 게임으로 먹고 사는 사람들 밥줄 끊는 짓은 왜? 직업을 만들지 않고 없애는 이유가 뭐냐? 이명박근혜가 이런 수준이면서 왜 그렇게 김대중, 노무현 욕했냐? 말년까지 욕먹을 각오해라.

수 천 년 동안 정부가 해야 할 일은 뻔히 정해져 있었다. 성경, 불경, 유교 경전에 다 나오는 내용이다. 그걸 하면 충신(천사)이고 하지 않으면 간신(악마)이다.