코딩 어드벤처: 루빅스 큐브

안녕하세요 여러분, 또 다른 코딩 어드벤처에 오신 것을 환영합니다. 의심할 여지 없이 여러분은 이 지독한 작은 물건 중 하나를 전에 접해봤을 겁니다. 즉, 수경(quintillions)의 순열을 가진 당혹스러운 퍼즐로, 루빅스 큐브라고 알려져 있죠. 오늘 우리의 목표는 이것을 풀 수 있는 프로그램을 작성하는 것입니다. 자, 여기 코드로 세 개의 반복문(loop)을 만들어서 각 축을 따라 -1, 0, +1로 설정해 가상 큐브를 만드는 것부터 시작해 봅시다. 이 과정에서 총 26개의 작은 큐브 메쉬가 생성됩니다.

그리고 지금 실행해보니… 이 흥미로운 결과가 나옵니다. 여기에 있는 개별 블록들은 커비(cubies) 또는 큐브릿(cubelets)이라고 알려져 있지만, 우리가 그것들을 구별할 수 있도록 스티커를 붙여야 합니다. 저는 이 스티커들을 코드에서 '페이스렛(facelets)'이라고 부르며, 각 비영(non-zero) 축 방향을 따라 생성합니다. 즉, 모서리 커브릿은 3개, 가장자리 커브릿은 2개, 그리고 중심부는 단지 1개를 갖게 됩니다. 참고로 제가 사용하는 이 페이스렛 함수는 주어진 축에서 큐브릿으로부터 바깥쪽으로 위치를 잡고, 해당 축을 따라 두께 매개변수(thickness parameter)만큼 크기를 조절하여 또 다른 큐브 메쉬를 생성합니다.

마지막으로 이 축은 0부터 5 사이의 인덱스에 매핑되어 각 면에 고유한 색상을 할당할 수 있게 됩니다. 자, 어떻게 되는지 봅시다. 설정을 가져와서 스케일과 두께 값을 저렇게가 아닌 다른 값으로 줄여볼게요. 조금 조정하겠습니다. 좋아, 스케일은 이게 더 보기 좋고, 두께는 좀 더 줄이겠습니다. 오우, 음수가 되게 하고 싶진 않네요. GPU가 그 안에서 흥미로운 추상 미술을 만들고 있네요.

입체파(Cubism)라 할까요... 아무튼, 색깔을 좀 입혀봅시다. 이 첫 번째 면은 초록색으로 하고—이것을 큐브의 앞면이라고 생각합시다. 뒷면은 관례를 따른다면 파란색이어야 합니다. 그리고 그 사이에는 오른쪽에 빨간색 면을 넣고—왼쪽에는 주황색과 짝지어 놓겠습니다. 마지막 조합으로는 윗면을 흰색으로, 아랫면을 노란색으로 남겨두겠습니다. 자, 이렇게 귀여운 작은 큐브가 완성되었네요!

이제 이 큐브가 작동하게 만들 필요가 있습니다. 왼쪽, 오른쪽, 위, 아래, 앞, 뒤 면을 회전시키기 위한 간단한 키보드 제어부터 시작해야 할 것 같습니다. 예를 들어 'L' 문자를 누르면 음의 x축 방향으로 향하는 면을 돌리기 시작하도록 해야 합니다. 그리고 Shift 키를 누르고 있으면 회전 방향이 바뀝니다. 따라서 주어진 축에 대해 모든 면(facelet)을 순회하면서 해당 면이 같은 방향을 가리키는지 테스트할 수 있습니다. 이는 큐브렛(cubelet)이 회전되어야 하는 것과 연결되어 있다는 것을 의미합니다. 그리고 이 정보는 우리가 처리해야 할 애니메이션 대기열(queue of animations)에 입력됩니다.

좋습니다. 그러니 매 프레임마다 그 대기열의 맨 앞에 있는 항목을 가져와서, 해당 항목의 애니메이션 타이머를 증가시키고, 이를 사용하여 현재 각도를 계산합니다. 그런 다음 큐브렛은 이 각도로 회전되고, 마침내 애니메이션이 완료되면 대기열에서 제거됩니다. 자, 한번 해봅시다. 여기 버튼 제어도 설정해 두었습니다—예를 들어 '위' 면을 돌려보는 것을 시도할 수 있습니다. 오, 제가 이것을 제대로 생각하지 못했네요…

하지만 적어도 올바른 큐브렛(cubelets)이 감지되는지는 테스트할 수 있습니다. 그러니 아래 면, 그리고 앞면, 뒷면, 오른쪽 면, 왼쪽 면을 시도해 보겠습니다. 그리고 이것은 아주 잘 작동하고 있습니다. 좋습니다. — 이제 회전 시작 시점의 큐브렛 상태를 가져오도록 코드를 빠르게 수정했습니다. 따라서 회전을 그 상태에 상대적으로 할 수 있게 되었습니다. 그리고 회전이 개별 큐브렛 중심을 기준으로 하는 것이 아니라, 전체 면(face)을 중심으로도 이루어지게 되었습니다.

이것으로 충분할 것입니다. 그래서 '위' 면을 다시 비틀어 보겠습니다. 이것은 이제 아름답게 돌아가고 있습니다. 반대 방향을 시도하기 위해 Shift 키를 누르고 보겠습니다. 이 역시 잘 작동하고 있습니다. 그럼 '오른쪽' 면을 시도해 보겠습니다... 음, 이건 조금 덜 성공적이었습니다. 하지만 쉬운 수정이 되어야 한다고 생각합니다. 제가 어떤 면렛(facelets)이 회전축과 정렬되는지 파악할 때, 물론 그들이 이미 거쳤던 모든 회전을 고려해야 한다는 것을 깜빡했기 때문입니다.

본질적으로는 면렛의 로컬 축을 월드 공간으로 변환하는 것입니다. 이 작은 수정으로 다시 시도해 보겠습니다. 그리고 마침내 작동하는 것 같습니다. 하지만 이것은 다소 투박한 제어 방식이라서, 간단한 마우스 컨트롤도 구현하기 시작했습니다. 그런데 제가 회전에는 정말 서툰 것 같습니다. 인정하고 싶지 않을 정도로 오랜 시간이 걸렸지만, 마침내 작동하게 만들었습니다. 사실 우리가 이걸 컴퓨터가 풀도록 만드는 것이라 제가 왜 애를 썼는지 완전히 확신하지는 못합니다.

제가 좀 흥분했나 봅니다. 어쨌든 컴퓨터는 수백만 개의 움직임을 검색해야 할 것이고, 애니메이션을 건너뛰고 3D 회전만을 직접 적용하는 것조차도 여전히 엄청나게 비효율적일 겁니다. 그래서 이것은 우리가 무슨 일이 일어나고 있는지 볼 수 있는 좋은 그래픽 버전이지만, 컴퓨터가 처리하기 위해서는 더 간결한 표현이 필요합니다. 먼저 이 큐브를 모서리(edges), 구석(corners), 그리고 중심 조각(centre pieces)으로 분리해 봅시다.

하지만 중심 조각은 사실 별로 중요하지 않습니다. 왜냐하면 아무리 돌려도, 그렇게 하는 것은 인접한 두 면을 반대 방향으로 회전시키는 것과 동일하기 때문입니다. 그래서 중심 조각들은 제자리에 고정되어 있다고 가정함으로써 우리의 삶을 어느 정도 단순화할 수 있을 것 같습니다. 좋습니다. 다시 모서리로 돌아가서, 저는 이 각각의 모서리들을 숫자로 식별하고 싶습니다. 예를 들어, 맨 위 층부터 시작하여 원형으로 0, 1, 2, 3으로 진행할 수 있습니다. 그리고 중간 층에는 4, 5, 6, 7이 있고.

마지막으로 아래쪽에는 8, 9, 10, 11이 있습니다. 제가 생각하는 것은 이 12개의 숫자를 다음과 같이 64비트 정수(integer)에 담을 수 있다는 것입니다. 그리고 예를 들어 이렇게 아래 모서리를 회전시키는 것은 단순히 해당 비트들을 재배열하여... 이것처럼 되는 것과 대응됩니다. 하지만 이 그림에는 아직 빠진 것이 하나 있습니다. 바로 모서리들의 방향성입니다. 예를 들어 여기 있는 0번 모서리를 보면, 현재 흰색 면이 위를 향하고 있습니다.

하지만 약간의 조작만으로도 같은 위치에 놓일 수 있지만, 흰 면이 이제 앞을 향하고 있을 뿐입니다. 따라서 우리는 모서리가 두 가지 방향 중 어느 것에 있는지 정의하는 일종의 시스템이 필요합니다. 한 가지 접근 방식은 큐브의 각 면 쌍에 순위를 할당하는 것입니다. 예를 들어, 상단과 하단—또는 흰색과 노란색—을 가장 높은 순위로 지정할 수 있습니다. 그다음으로 전면과 후면 면(우리는 녹색과 파란색으로 만들었지만)이 오고, 좌측과 우측은 당연히 가장 마지막입니다.

이렇게 정의하면 모서리 하나를 살펴볼 수 있습니다. 예를 들어, 왼쪽에는 노란색 면 조각이 있고 전면에는 녹색 면 조각이 있는 이 모서리 같은 경우입니다. 이 두 색상 중에서 우리는 노란색을 녹색보다 높은 순위로 지정했지만, 이 두 면 중에서는 전면을 좌측보다 높게 순위화했습니다. 이는 낮은 녹색이 우월한 배치를 누리고 있다는 의미이며, 이를 비방향성(unoriented) 경우라고 부를 수 있습니다. 하지만 여기 위쪽의 모서리를 보면—파란색이 주황색보다 높은 순위를 가지고 있고, 좌측보다 높은 순위인 상단 면에 놓여 있으므로, 이번에는 계층 구조가 지켜지고 있어 방향성(oriented) 경우입니다.

다시 우리의 큰 이진수로 돌아와서, 각 모서리에 추가 비트를 삽입할 수 있습니다. 이 비트는 모서리가 방향성을 가질 때는 0이고, 그렇지 않을 때는 1이라고 가정합시다. 저는 이것이 큐브를 설명하는 좋은 간결한 방법이라고 생각합니다. 물론 아직 코너(corners)가 빠져 있으니, 그에 대해서도 같은 과정을 빠르게 진행해 보겠습니다. 자, 이제 코너에 대해 같은 과정을 빠르게 진행하겠습니다. 따라서 이들에도 ID 번호를 할당하겠습니다—상단 층에는 0, 1, 2, 3을, 하단 층에는 4, 5, 6, 그리고 7을 하겠습니다.

6은 현재 숨겨져 있지만, 물론 여기 있습니다! 이제 코너는 세 개의 면(facelets)을 가지고 있으므로 방향(orientation)에 대해 다시 생각해야 합니다. 하지만 모든 코너에는 흰색 또는 노란색 중 하나가 있으므로, 그 스티커가 어느 면에 나타나는지에만 집중하면 됩니다. 예를 들어, 여기서는 노란색이 윗면(top side), 즉 가장 높은 순위(highest rank)에 있습니다. 그래서 이 경우를 케이스 0이라고 부를 수 있습니다. 하지만 만약 앞면에 있다면, 그것은 중간 순위(middle)에 속합니다. 이것을 케이스 1이라고 하고, 마지막으로 왼쪽이나 오른쪽에 있다면 케이스 2가 될 것입니다.

따라서 이러한 코너들을 하나의 정수(integer)로도 패킹할 수 있습니다. 비록 이번에는 ID를 위해 3비트만 필요하지만, 방향을 위해서는 2비트가 필요합니다. 코드에서는 에지(edge)와 코너(corner) 값을 저장하기 위한 CubeState 구조체(structure)를 가지고 있습니다. 또한 초기 구성 상태에서 이러한 값들이 무엇일지에 대한 상수(constants)도 만들 수 있으므로, 큐브가 풀렸는지 테스트하는 것은 두 숫자를 비교하는 것만큼 간단합니다. 이제 까다로운 부분, 즉 회전이 발생했을 때 큐브 상태를 업데이트하는 것입니다.

우리가 고려해야 할 총 회전은 18가지입니다. 이는 우리가 논의했던 센터(centres)에 영향을 미치는 소위 슬라이스 회전(slice turns)을 포함하지 않고, 그리고 시계 방향 및 반시계 방향 사분할 회전(quarter-turns)뿐만 아니라 반회전(half-turns)까지 모두 개별적인 움직임으로 계산하는 경우입니다. 우리는 시계 방향 사분할 회전만 존재한다고 단순화하여 말할 수 있습니다. 그러면 반회전을 얻으려면 그것을 두 번 해야 하고, 반시계 방향으로 가려면 세 번 해야 하지만, 그건 저에게 좀 이상하게 느껴집니다.

어쨌든, 나는 이 큐브의 18가지 회전 각각에 대해 간단한 테스트를 설정하여 시각적 검증을 할 수 있게 했습니다. 그리고 궁금하실까 봐 말씀드리자면, 이동 인덱스를 실제 회전을 수행하는 데 필요한 축과 회전 방향으로 변환하고 있습니다. 자, 그럼 한번 실행해 보고 제대로 작동하는지 확인해 봅시다. 좋습니다, 이게 맞네요. 이제 우리가 모서리(edges)와 구석(corners)에 할당했던 ID를 다시 고려해 보면— 이것들을 큐브의 고정된 위치를 설명한다고 생각할 수도 있습니다.

예를 들어, corner 0은 풀렸을 때 위치 0에 있습니다. 하지만 면을 비틀면, 이제 corner 3이 대신 위치 0으로 이동했습니다. 한편 corner 0은 위치 1로 갔고, 이런 식입니다. 따라서 각 회전마다 큐브의 조각들(cubelets)이 어느 위치에서 어디로 운반되는지에 대한 지도가 있으면 유용할 것입니다. 그리고 이 작은 함수가 바로 그 역할을 합니다— 18가지 회전 각각에 대해 무엇이 어디로 가는지 확인하고, 그것을 우리에게 출력해 줄 뿐입니다.

그럼 빠르게 실행해 봅시다… 이제 우리는 각 회전에 대한 시작 및 끝 위치 지도를 갖게 되었습니다. 제가 이 데이터를 출력한 이유는 실제로 시작 시점에 생성하기보다는 원시 데이터(raw data)를 코드에 붙여넣고 싶기 때문입니다. 속도 문제가 아니라, 순수한 큐브 풀이 코드를 모든 지저분한 3D 그래픽 작업으로부터 분리하고 싶어서입니다. 별로 중요하지는 않지만, 그냥 기분이 좋아서요. 좋습니다. 이제 만약 위치 0에 있는 어떤 조각들을 위치 4로 이동하라는 지시를 받으면, 값의 복사본을 가져와서 오른쪽으로 20칸 이동시키면 됩니다.