비결정론적인 폴리브릿지

폴리브릿지는 비결정론적(non-deterministic)이다

예전에 폴리브릿지를 하다가 운빨로 스테이지를 넘기고 뿌듯하게 리플레이를 돌려보는데 가끔 실패하는 경우를 발견해서 저장해놨었다가 이에 대해서 정리하려고 방치해뒀던 주제입니다.
쓰다보니 좀 애매하고 범위를 정하기가 어려웠습니다. 물리엔진에서 발생할 수 있는 문제와 원인들에 대해서 대략적으로 알아봅니다.

상황

좌표는 폴리브릿지 4-7

이렇게 성공할 때도 있지만

이렇게 실패할 때도 있습니다.

저렇게 다리가 흔들거리게 만들어두면 어떻게 재생할 때마다 결과가 달라집니다.
이런 상황에 대한 버그리포트는 이미 있지만 좀 더 자세히 알아봅시다.
특히 리더보드에서 순위를 따지는데 저런 상황이 발생하면 엄밀히 말해서 점수가 의미 없는 상황이 되죠(스코어링 곤란해짐)

Bug? Non-deterministic behaviour in jump, jump again (2015.09.28)
https://steamcommunity.com/app/367450/discussions/0/517142892064744193/
Q : 점프를 계속 반복하면 실패할 때가 발생한다, 이거 버그 아니냐?
A : 버그 맞다, 부동소수점 문제일 수도 있지만 근본적인 원인은 런타임에 바디들을 만들어서 발생하는 문제다. Unity, Box2D 구현에선 동일

The physics engine is not deterministic. (2016.06.24)
https://steamcommunity.com/app/367450/discussions/0/351660338688467230/
Q : 나 리더보드에서 순위작 하는데 같은 조건에서도 점수가 계속 다르게 나온다.
A : Box2D는 결정론적 시뮬레이션을 제공한다. 하지만 Unity에 사용할 때 문제가 생겼다. 시뮬레이션(bodies, constraints) 을 만들고 파괴하는 과정에서 객체가 해싱 테이블에 추가되는 순서가 무작위이며 이에 따라서 다른 시뮬레이션 결과가 발생한다. 대신 온라인 갤러리(https://gallery.drycactus.com/)에선 같은 순서를 보장하므로 업로드해서 확인하면 된다.

결정론적, 비결정론적 알고리즘

출처 : 위키피디아

물리엔진에서 결정론적, 비결정론적은 시뮬레이션 결과를 예측할 수 있냐, 재현성이 있느냐라고 이야기할 수 있습니다. 결정론적이라면 동일한 상황에선 언제나 같은 결과가 반복될 것이고, 비결정론적이면 위에 올린 폴리브릿지처럼 같은 상황 같은 조건에서도 다른 결과가 생길 수 있죠.

정보통신기술용어해설 : Deterministic, Nondeterministic   결정론적, 비결정론적
http://www.ktword.co.kr/m/abbr_view.php?m_temp1=4086

Deterministic Algorithm
https://en.wikipedia.org/wiki/Deterministic_algorithm

Nondeterministic Algorithm
https://en.wikipedia.org/wiki/Nondeterministic_algorithm

Stochastic Optimization

https://en.wikipedia.org/wiki/Stochastic_optimization

비결정론적은 확률적과 엄밀히 따지면 다르게 정의됩니다. 이는 맥락에 따라서 조금씩 다르게 사용되는 것에 주의합시다.
https://cstheory.stackexchange.com/questions/632/what-is-the-difference-between-non-determinism-and-randomness

물리엔진

2D와 3D에서 물리엔진

2D에서는 Box2D(https://github.com/erincatto/Box2D)가 대표적입니다. 폴리브릿지 뿐만 아니라 수많은 게임이 Box2D를 물리 시뮬레이션에 사용하고 있죠.
하지만 3D로 넘어가면 차원이 증가함에 따라서 훨씬 더 많은 연산을 필요로 합니다. 그리고 무엇에 중점을 두느냐에 따라, 어떤 환경에서 개발하냐에 따라서 사용하는 물리 엔진의 종류가 달라집니다. 대표적으로 로켓리그라는 게임은 UE4로 개발했지만 물리엔진은 Bullet Phyics를 섞어서 썼다고 합니다.

물리엔진 강체(Rigidbody)와 제약(Constraints)

체인을 만들어봤습니다. 우측이 강체로 엮은 사슬, 좌측은 제약으로 엮은 사슬입니다.
강체(Rigidbody)로 엮은 경우 충돌(Collision)을 바탕으로 각 강체들의 다음 위치를 결정합니다. 반면 제약(Constraints)로 엮은 경우 보이지 않지만 각각 설정된 제약조건에 따라서 다음 위치를 결정합니다. 위치를 결정한다는 의미는 한 스텝(step)에서 다음 스텝으로 넘어갈 때 각 강체에 적용될 힘(F=ma)을 어떻게 주냐로 따질 수 있습니다.

사실 처음 폴리브릿지에서 버그를 봤을 때 여기서 에러가 발생한거 아닌가 의심했었습니다. 다리가 출렁이는 움직임이 매번 달리지기 때문이죠. Bullet Physics와 UE4에선 최적화 조건에 따라서 제약조건을 처리하는 Solver에서 속도 높일려고 랜덤을 박아놓는 경우가 있었습니다. 그래서 폴리브릿지도 마찬가지 아닐까? 생각했지만 2D니까 굳이 이럴 필요가 없었내요.

하지만 강체와 제약조건을 등록하는 해싱 테이블에서 등록하는 순서가 바뀌면 처리 순서가 바뀌고 이게 결국 비결정론적인 물리 시뮬레이션을 만든다는 점에서 결국 랜덤신의 가호가 맞았습니다(?)

조금 더 설명된 자료는 아래 슬라이드, 왠만하면 책을 읽어보시길 바랍니다. 저도 아직 공부를 하는 중이라 어디까지, 어떻게 설명해야할지 모르곘습니다ㅠㅠ
[NDC12] 게임 물리 엔진의 내부 동작 원리 이해

정리하자면...

비결정론적인 이유?

물리엔진은 왜 비결정론적일까? 여러 사례를 살펴보면 주로 처리순서에 따른 문제와 부동소수점에 관한 문제가 있습니다. 특히 게임에 쓰이는 물리엔진의 경우 시뮬레이션 정확도보다 속도를 중요시하기 때문에 꼭 필요한 곳이 아니면 비결정론적으로 구현하는게 도움되는 경우가 많습니다.

대표적으로 오버워치에서 주변 사물과 상호작용을 할 때 공은 모든 사람들이 동일하게 인식하죠, 루시우볼이 특히 이런 경우였습니다. 하지만 단순히 파괴되면 끝나는 물체들은 모든 사람들이 동일한 화면을 볼 필요가 없으니 보는 사람마다 조금씩 다르게 파괴되는 것을 볼 수 있습니다.

결정론적일 때는?

물론 가능합니다. 특히 로보틱스나 강화학습, 게임이 아닌 CG를 만들 땐 속도보다 정확도, 품질이 중요하기 때문에 결정론적인 물리 시뮬레이션을 사용합니다. 어떻게보면 게임 밖에 이렇게 물리시뮬레이션을 하는 사례가 없내요.

파이썬 웹 크롤러 만들기 (Python, Scrapy)

파이썬 웹 크롤러 만들기
(Python, Scrapy, Web Crawler, Crawling)

웹 크롤러는 여러가지 용도로 쓰일 수 있습니다.
자연어 처리를 위한 말뭉치를 모을 때부터 인터넷에 올라온 짤방을 저장할 때 등 여러가지 용도로 사용합니다.
하지만 크롤링을 하기 위해서 여러 URL과 게시판의 페이지를 자동으로 탐색하는건 꽤 귀찮은 작업이죠.

이 글은 Scrapy를 사용해 단 몇 줄로 파이썬 웹 크롤러를 만드는 방법과 필요한 배경지식을 소개합니다.
Beautiful Soup과 request를 쓸 경우 한 게시판에서 대한 URL을 찾고, 여기서 다음 페이지(목록) 찾는 방법을 구하고, 너무 많은 요청을 한 번에 보내지 않게 조절 하면서, 각 페이지에 직접 들어가 파일로 저장하는 것을 동시에 처리하도록 구현해야하는 등, 생각보다 귀찮은 작업이 많습니다.
이에 비해서 Scrapy 프레임워크의 원리만 알고 이용하면 대부분의 귀찮은 작업을 하지 않아도 됩니다.

위 코드는 scrapy runspider <filename> 한 줄로 실행가능합니다.
크롤링하는 대상은 네이버 지식인(http://kin.naver.com/qna/list.nhn) 입니다.

웹 크롤링을 위한 배경 지식

네이버 지식인을 크롤링하는 예제를 바탕으로 필요한 지식으 순서대로 설명합니다.

1. 웹 크롤링이란?

크롤링; (검색 엔진에서) 분산 저장되어 있는 정보를 수집하여 검색 대상으로 복제·보존하는 기술.(네이버 사전)
웹 스파이더(Spider)라는 용어는 인터넷(Internet) 즉 Net을 그물처럼 돌아다니면서 찾느 거미(..)가 어원입니다.
정리하자면 스파이더는 필요한 정보를 자동으로 찾는 것, 크롤링은 데이터를 긁어서(?) 저장하는 것을 의미합니다.

보통 웹 크롤링은 웹사이트에서 우리가 원하는 부분만 자동으로 가공해서 저장하는 작업을 의미합니다.
이 예제에선 네이버 지식인의 질문 목록을 받아오고 자동으로 이동하며(스파이더) 각 질문에 들어가서 본문을 파일로 저장(크롤링)합니다.

2. 웹사이트의 URL 구조

보통 웹 사이트의 블로그나 게시판들의 구조를 생각해봅시다.
지식인은 각 카테고리를 URL(인터넷 주소창) 끝에 ?dirId=(숫자)에 따라서 구분합니다.
즉 이 숫자에 따라서 원하는 카테고리를 선택할 수 있습니다.

보통 다른 게시판도 비슷한 구조로 되어있습니다. 우리가 원하는 게시판과 분류가 어디인지 알아낼 땐 여기를 먼저 조사하면됩니다.
인터넷 주소창에 대한 자세한 내용은 제타위키 GET 요청, POST 요청에 대해서 알아보시면 됩니다.
https://zetawiki.com/wiki/GET_%EB%B0%A9%EC%8B%9D,_POST_%EB%B0%A9%EC%8B%9D

3. robots.txt

robots.txt는 크롤링을 금지한다는 알림입니다. 자세한 내용은 따로 검색해보시면 됩니다. 알아둘 점은 긁지 말라는걸 긁을 경우 저작권에 문제가 생길 수 있습니다.
https://en.wikipedia.org/wiki/Robots_exclusion_standard

아마 Scrapy를 예제처럼 스파이더 따로가 아니라 프레임워크로 구동하면 robots.txt로 금지되어 있다고 경고가 뜰겁니다. 강제성은 없어서 무시할 수 있지만 나중에 문제의 소지가 될 수도 있으니 한 번 찾아보시길 바랍니다. 저는 공부 목적으로 긁었습니다.

4. HTTP

인터넷 통신 프로토콜입니다. 웹 크롤링을 하다보면 200, 301, 302, 404 등 몇 가지 숫자를 볼 텐데 이게 HTTP와 관계있습니다.

출처

자세한 내용은 HTTP에 대해서 따로 찾아보시길 권장합니다. 만약 3XX가 뜨거나 5XX가 뜰 겨우 크롤링을 막아놓은 사이트일 수도 있습니다. 이 경우 웹 브라우저에선 보이는데 왜 크롤링이 안 될까? 궁금하신 분은 이걸 공부하시면 됩니다.

https://ko.wikipedia.org/wiki/HTTP

5. HTML & CSS Selector

HTML은 크롬 개발자도구로 보이는 마크업 언어입니다. 크롤링하고자 하는 대상을 적당히 지정해주면 됩니다.

파이썬 코드에서 뽑기 위해서는 CSS Selector로 해당 위치를 지정해줘야 합니다.
CSS Selector에 대해서는 아래 링크.
https://www.w3schools.com/cssref/css_selectors.asp
직접 테스트해보고 싶다면 아래 링크를 참조해주세요.
https://www.w3schools.com/cssref/trysel.asp

6. Encoding

보통 글씨 깨졌다고 표현하는 현상은  글씨가 깨지는 현상이 발생하면 파이썬 인코딩 등을 찾아보면 됩니다. 반드시 Python 3, UTF-8을 씁시다.

7. Python

프로그래밍 언어입니다. 이제 위에 내용들을 바탕으로 파이썬으로 테스트 해보면 됩니다.
윈도우라면 Anaconda를 사용하면 좋습니다. 아래와 같이 테스트하면 됩니다.

여기서 반드시 알아둘 점이 있습니다. 크롤러를 돌리는 행위는 웹 서비스 제공자에 영향을 줍니다. 짧은 시간내에 많은 요청을 보내기 때문인데, 테스트를 할 때는 크롤링하는 사이트에 부담을 줄 수 있음을 명심하고 너무 무리한 요청을 계속 보내지 않도록 조심합시다. 또 크롤링을 막 돌리면 서버에서 접근이 막힐 수도 있으니 조심합시다.

Scrapy에 관해서

공식 홈페이지 : https://scrapy.org/
홈페이지 첫 페이지에 나와있는 예제를 조금 바꿨을 뿐인데 충분히 훌륭하게 동작합니다.
저건 간단한 예제일 뿐 Scrapy는 프레임워크로써 좀 더 복잡한 사용법이 존재합니다.

제가 공유한 방식은 간단한 하나의 Spider를 수동으로 동작시키는 예제입니다. 목록을 탐색하고 각 게시물을 긁어오는 코드는 공식 튜토리얼을 참조해서 조금 변형했습니다.
https://docs.scrapy.org/en/latest/intro/tutorial.html

일정 시간마다 자동으로 긁어오거나, 만약 트래픽 과다로 차단을 먹거나 일정 시간 지연 기능등을 사용하려면 create a project를 통해서 제대로 만들길 추천드립니다.
https://docs.scrapy.org/en/latest/intro/tutorial.html#creating-a-project

수동으로 돌리실 땐 time()함수나 console창에 출력하는 내용을 잔뜩 만들어서 딜레이를 주는 등으로 하는 방법도 있습니다.