Log Stash

A* 알고리즘은 게임 프로그래밍 해본 사람이라면 꽤나 많이 들어본 길찾기 알고리즘일것이라고 생각한다. 좌표를 이용해서 탐색할 수 있기도 해서 그런건 아닐까. 구현하기도 많이 어려운것도 아니고. 알고리즘에 대한 자세한 설명은 다른 블로그에서도 많이 하니까 넘기고. 간단히 설명하자면 A* 알고리즘에서는 출발좌표에서 시작해서 주변 좌표마다(8방위, 4방위 마음대로) 평가값을 매기고, 가장 작은 평가값을 가진쪽으로 이동하고, 거기에서 또 주변 좌표의 평가값을 매기고... 를 목표 좌표에 닿을때 까지 하는 알고리즘이다. 평가값을 구하는 평가함수를 A*에선 다음과 같은 함수를 사용한다. g(n)은 출발 좌표부터의 현재까지의 거리(비용) h(n)은 현재 좌표에서의 목적지 까지의 예상 거리(비용) 을 나타낸다. 대부분..

유니티에서 지구 텍스쳐가 씌워진 스피어를 주어진 위도 경도를 찾아가도록 회전시켜야 할 일이 있었다. 일단 옛날에 플레이하던 록맨x7 스테이지 셀렉트 장면 가운데에 지구굴러가는 모습이 떠올랐다. 록맨X7의 스테이지 셀렉트씬, 1분17초 부터 지구가 굴러간다. 어차피 2D처럼 화면에 그려지느라 카메라 위치는 고정되어있고, 다른 요인으로 회전값이 바뀌거나 하지 않으니 (뷰 스페이스에서 간섭이 없으니) 그냥 월드 스페이스에서 회전시키기만 하면 됐었다. 그러면 위도, 경도를 이용해서 회전각을 알아내야 하는데, 이것도 중간에 삽질을 많이 해서 그렇지 그렇게 어렵진 않다. 위도, 경도는 구면 좌표계상의 한 점을 표현할때 쓰는 값이니 (고도는 그냥 1로 퉁친다) 이걸 변환 공식을 통해 직교 좌표계로 바꿀 수 있다. 처..

컴파일러가 코드를 해석하는 일을 약간 교과서적인 방법으로 몇가지 뭉텅이로 나눠서 생각해보자. 왠만한 컴파일러 관련 책이라면 이런 그림이 들어가 있을거다. 1.Lexical analysis 하나의 긴 복잡한 문자열이라고 볼 수 있는 코드를 의미있는 토큰 단위로 조각조각내는 단계. 예를들어, begin x := m; y := n; call multiply; end. 위의 코드를 토큰들로 나누면 "begin", "x", ":=", ";", "y", ":=", "n", ";", "call", "multiply", ";", "end", ".' 이런 문자열들이 되겠다. 여기에서 의미 없는 문자열들은 전부 무시한다. 공백, 개행, 주석 처럼. 2. Syntax analysis 문법 오류를 검사하는 단계이다. 토큰을 ..

방향키로 조종하면 왼쪽의 쿼터뷰에 있는 글자가 움직인다. 제목은 길게도 써놨는데 별거 없다. 고1 때였나 아무튼, 저런 쿼터뷰 형식의 게임 맵에서 현재 플레이어가 어느 타일 위치에 있는지를 알아야 했었다.(아마) 그래서 그때 당시에는 모든 마름모의 각 변을 일차 함수로 표현하고 플레이어 좌표가 함수값 위에 있는지 아래에 있는지 검사하는 방법을 썼었다. 타일 갯수만큼 반복문이 들어가기 때문에 당연히 갯수가 많아질수록 점점 느려지더라. 선형대수 시간에 벡터공간 파트에서 기저벡터에 대한 설명을 듣다가 저 문제가 생각났다. (그 때 이후에도 몇번 쿼터뷰에 대한 고찰을 할 기회가 있었지만 그냥 별 생각 안하고 있었다) 평소에 자주 쓰는 직교 좌표계는 (1,0)과 (0,1)을 기저벡터로 삼는 벡터공간이라고 할 수 ..

컴파일러 시간에 첫번째 과제로 제출했던 '재귀 하강 파서(Recursive descent parser)로 PL/0 파싱 및 실행'에 대해 정리해놓으려고 한다. 과제를 진행한 순서로 정리한 글이라 초반에 생각을 잘못해서 나중에 좀 괴랄한 방법으로 구현된 부분도 있고, 함수 이름이 중간에 바뀌기도 하고 그렇다. 과제 후기라고 생각하면 될듯. #PL/0 링크 걸어놓은 위키에서도 설명하고 있지만 PL/0는 2가지 언어를 가리키는데, 그 중 하나는 IBM에서 만든 PL/I 언어의 부분집합이고, 다른 하나는 파스칼 언어에서 몇가지 복잡한 기능을 삭제한 연습용 언어이다. 이 중에서 후자를 파싱해보도록 한다. PL/0은 Algorithms + Data Structures = Programs 라는 책에서 처음으로 소개되..

아마 고2 때였을거다. 당시에는 디씨 프로그래밍갤을 종종 눈팅 하곤 했었다. 당시 자주 돌아다닌 비슷한 떡밥으로는 '1부터 100까지 더하기'나 '별찍기' 따위가 있었는데, 이때 프갤러들은 이런 문제들을 각자 웃기거나, 변태같은 방식으로 풀고 자랑하며 놀곤 했다. (제목을 '1 부터 100까지 더하는 획기적인 알고리즘' 이라고 해놓고 내용에는 printf("5050\n"); 을 적어 놓는다거나 하는) 어느날 프갤에 달팽이 문제 떡밥이 돌아다녔었다. 달팽이 문제도 1-100이나 별찍기와 마찬가지로, 프로그래밍을 처음 배우는 사람이 기초적인 문법까지 보고나서 풀어보는 간단한 응용한 문제중에 하나인데, N by N 2차원 배열에 달팽이 집 모양 처럼 나선 모양대로 정수값을 채워넣는 문제이다. 예를 들면 이런식..

이번엔 '알고스팟 초보용 문제' 카테고리에 있으나 개인적인 두뇌 성능이 좋지 않아 장장 2년 가까운 세월동안 13번의 시도후에 정답 판정을 받아낸 WEIRD 문제에 대해서 이야기를 해보겠다. 문제 링크 : https://algospot.com/judge/problem/read/WEIRD 젠장.. 문제를 한 문장으로 요약하면 'abundant하면서 semiperfect하지 않은 자연수를 이상한 숫자라고 하는데 어떤 숫자가 주어졌을때 이게 이상한 숫자인지 아닌지 판단해내라.' 라고 할 수 있다. 알고스팟 문제도 그렇고 링크 걸어놓은 위키피디아도 죄다 영어라서 읽기 귀찮기 때문에 여기에다 정리한다. 어떤 수가 Abundant 하다는것은 그 수의 진 약수(자기 자신보다 작은 약수)의 합이 그 수보다 큰 경우를 ..

>>2013-10-09에 구글 드라이브에 작성.>>2015-01-13에 에버노트로 이동. 1.이야기회사에서 타일맵 위에서의 A-star 길찾기 알고리즘을 구현할 일이 생겼었다. astar는 고3 때 수능 끝나고 만들던 게임에서 이미 한번 구현 해 봤었고 언어는 java로 회사 엔진에서 쓰는 C++과는 다르지만 그 때의 소스코드도 남아있었기 때문에 그냥 레거시 코드에 맞춰서 적당히 수정해 주면 된다고 생각했었다. 오브젝트가 움직일 수 없는 타일 마스킹 하는 배열 추가, 로직에 맞춰 쓸모없는 코드를 정리해 주기만 하면 문법상 다른 부분만 살짝 고치면 됐으니까. 다른 부분은 다 생각대로 됐었는데 한 가지 문제가 생겼던 부분이 있었다. 예전 자바 코드에는 open list의 container를 F값을 기준으로 ..

군대에 있는 내 친구는 시간날때마다 알고리즘 문제같은걸 몇 가지 알려주곤 한다. 학기중에는 이리저리 바빠서 안 보고, 학기가 끝나서는 귀찮아서 안 보는 중이었는데 끈질기게도 휴가나와서 이런 문제가 있다고 알려주더라. 문제 내용 : https://algospot.com/judge/problem/read/BOGGLE 그림1. 왠지 그냥 허전해서 링크에 있는 이미지를 가져왔다. 개인적으로 알고리즘 문제를 그리 많이 풀어보진 않았지만, 대부분의 문제들은 문제를 읽어보면서 생각나는 가장 간단한 방법의 로직으로 풀려고 하면 대부분 시간 초과에 걸리는 경우가 많았던것 같다. (사실 가장 직관적인 방법으로 풀 수 있으면 아마도 어려운 문제가 아니겠지) 이 문제를 처음 읽으면서, '첫번째 글자를 찾고, 그 주위 8방위로..

게임을 하고 나서 그 느낌을 기록하지 않으면 왠지 그 게임을 하느라 걸린 플레이 타임은 버린 시간이라고 생각하게 되는 것 같다. 따라서 그에 따라 게임을 플레이하면서 느낀점을 간단하게 기록하고자 한다. 그 첫번째 타자는 나를 게임 불감증에서 해소시켜준, 또한 복돌이에서 정돌이로 갈아타게 된 신호탄 격의 게임인 슈퍼 헥사곤이다. #영상에서 간단히 보이는 것 처럼 중앙의 육각형 가장자리에 있는 삼각형을 회전시켜, 다가오는 벽을 피하는 게임이다. opengl로 만들었기 때문인지 ios, android, windows, linux 플랫폼을 지원한다. (맥은 가지고 있질 않아서 잘 모르겠다) 다가오는 벽의 패턴, 속도에 따라 여섯개의 스테이지로 난이도 구분을 해 놓고 있는데 이는 각각 Hexagon, Hexago..