모든 코스가 통과 가능하다는 보장: 시드 생성기와 층별 BFS 솔버

FOURSTEP의 6개 트랙과 매일 바뀌는 DAILY 코스는 사람이 배치하지 않았습니다. 시드에서 장애물을 생성하고, 솔버가 실제 게임과 같은 물리로 그 코스를 달려 통과 경로를 찾은 경우에만 채택합니다. 이 글은 생성기와 솔버의 구조, 1.1.1에서 넣은 형태별 안전 여유, 실패했을 때 난이도를 낮춰 다시 만드는 규칙, 그리고 현재 코드로 측정한 결과를 다룹니다.

무작위 코스가 가진 문제

장애물을 무작위로 뿌리는 생성기는 금방 만들 수 있지만, 그 결과가 통과 가능한지는 아무도 보장하지 않습니다. 원버튼 러너에서 통과 불가능한 구간은 치명적입니다. 플레이어는 자기 실력이 모자란 것인지 코스가 잘못된 것인지 구분할 수 없고, 수십 번 같은 지점에서 죽다가 게임을 끕니다. 규칙 기반으로 "가시 사이 간격은 최소 몇 칸"을 정하는 방법도 있지만, FOURSTEP은 형태가 넷이고 형태 사이의 경계에서 상태가 이어지기 때문에 규칙만으로는 모든 조합을 막기 어려웠습니다.

그래서 택한 방법은 "만든 다음 직접 풀어 본다"입니다. 생성기는 자유롭게 만들고, 판정은 실제 물리를 돌리는 솔버에게 맡깁니다. 솔버가 쓰는 물리 함수는 게임이 쓰는 stepHero와 같은 함수입니다(이 구조는 변신·물리 글에서 설명했습니다).

생성기: 지형 순서와 패턴

트랙 하나는 시드, BPM, 조, 코드 진행, 마디 수, 지형 계획, 난이도 범위로 정의됩니다. 예를 들어 첫 트랙 SUNRISE HOP은 20마디에 들판·땅굴·들판, 난이도 0.15~0.4입니다. 마디 수를 지형 수로 나눠 각 지형의 길이를 정하고(1마디 = 4박 = 12칸), 난이도는 지형 순서에 따라 범위 안에서 선형으로 올립니다. DAILY는 날짜 문자열로 시드를 만들고 가운데 세 지형의 순서를 섞습니다. 처음과 끝은 항상 들판입니다.

지형 안에서는 패턴을 이어 붙입니다. 들판에는 가시 점프(hops), 구덩이, 터널, 계단, 드럼 패드와 발판, 레이저 패턴이 있고, 난이도가 0.5를 넘으면 절반 확률로 터널·레이저·드럼 쪽 비중이 높은 목록에서 고릅니다. 땅굴은 지표 가시와 지하 바위를 번갈아 놓되 70% 확률로 레인을 바꿉니다. 바다는 위아래로 번갈아 열리는 산호 관문, 위아래로 엇갈린 성게 쌍, 해류 구간을 섞고, 산은 바위 기둥과 매달린 바위를 놓으면서 높은 기둥 앞에는 상승기류를 붙입니다. 장애물 시작 위치는 반 박자 격자에 맞춥니다. 각 지형의 처음 12칸(4박)은 비워 두는 안전 구간입니다.

솔버: 1/8박마다 누를까 말까

솔버는 지형 하나를 단위로 돌아갑니다. 상태 공간은 1/8박마다 "누름" 또는 "안 누름" 두 갈래로 갈라지는 나무입니다. 이것을 그대로 탐색하면 지형 하나(수십 박, 수백 번의 결정)에서 경우의 수가 폭발하므로 너비 우선 탐색을 층별로 진행하면서 같은 상태를 합칩니다.

function key(h){
  const q = h.form==='runner'||h.form==='digger' ? 16 : h.form==='jelly' ? 10 : 8,
        qv = h.form==='runner' ? 4 : 2;
  return h.form+'|'+h.side+'|'+Math.round(h.y*q)+'|'+Math.round(h.vy*qv)+'|'+(h.held?1:0);
}

같은 층(같은 시각)에 있는 상태들은 형태, 접촉면(땅·천장·공중 등), 높이, 세로 속도, 버튼 눌림 여부를 양자화한 키가 같으면 하나로 칩니다. 가로 위치는 시각이 같으면 항상 같으므로 키에 넣을 필요가 없습니다. 이것이 "박자당 3칸 자동 전진"이라는 규칙이 솔버에게 주는 큰 이점입니다. 높이 양자화는 RUNNER·DIGGER가 1/16칸, JELLY가 1/10칸, GLIDER가 1/8칸으로, 움직임이 연속적인 형태일수록 거칠게 잡았습니다. 한 층의 상태는 최대 3,000개로 제한합니다.

각 상태에서 두 행동을 시도해 1/24박 스텝 3번을 진행하고, 살아남은 상태만 다음 층에 넣습니다. 누군가 지형 끝에 닿으면 부모 포인터를 거슬러 올라가 행동 열을 복원합니다. 탐색 순서도 의미가 있습니다. 기본은 "안 누름"을 먼저 시도하지만 GLIDER만은 "누름"을 먼저 시도합니다. 같은 키로 합쳐질 때 먼저 들어온 상태가 남으므로, 활공을 유지하는 완만한 경로가 우선 선택됩니다. 1.1.1 변경 이력의 "솔버가 활공 유지를 우선해 더 완만한 경로를 찾음"이 이 한 줄입니다.

통과 가능과 할 만함은 다르다: MARGIN

1.0.0의 솔버는 정직하게 동작했지만 문제가 있었습니다. 솔버는 1/8박 단위로 정확하게 누르므로, 가시와 몸 사이가 0.01칸만 남아도 "통과 가능"으로 판정합니다. 사람에게 그런 코스는 사실상 불가능합니다. 1.1.1의 변경 이력에서 가장 크게 손본 곳이 바다 구간이라는 점도 이 문제가 어디서 두드러졌는지 보여 줍니다.

1.1.1에서 넣은 해법은 솔버가 풀 때만 장애물을 키우는 것입니다. 형태별 여유는 RUNNER 0.4칸, DIGGER 0.55칸, JELLY와 GLIDER 0.5칸입니다. 솔버가 판정할 때 장애물 충돌 상자를 이만큼 넓히고(자유 이동 형태는 세로로도 절반만큼), 구덩이 양옆도 RUNNER 여유만큼 넓히고, 벽 충돌은 여유의 절반을 씁니다. 박자에 맞춰 깜빡이는 레이저는 켜져 있는 시간을 앞뒤로 여유/속도만큼 늘려서 판정합니다. 박자당 3칸 전진이므로 가로 0.4칸은 약 0.13박, 즉 120 BPM 기준 약 67ms의 타이밍 오차에 해당합니다. 코스 생성이 끝나면 여유는 지우고(L.margin=null) 실제 게임은 원래 크기로 판정합니다.

같은 버전에서 바다의 물리와 생성기도 손봤습니다. 펄스 초속도를 4.5에서 3.4로 낮춰 탭 한 번의 상승을 1.27칸에서 0.81칸으로 줄였고, 산호 통로 폭을 1.9칸에서 2.5칸(난이도에 따라 최대 −0.5)으로 넓혔으며, 해류 세기를 5에서 3으로 낮췄습니다. 들판은 구덩이 폭 상한을 2.5칸에서 2.0칸으로 줄이고 가시 판정 상자를 좁혔습니다. 장애물만 키우면 생성기가 재시도를 거듭하다 난이도가 너무 내려가므로, 물리와 패턴도 함께 조정해 여유를 두고도 풀리는 코스가 제 난이도에서 나오도록 맞춘 것입니다.

실패하면 쉽게 다시, 그리고 이어서 풀기

지형 하나를 생성하고 솔버가 실패하면 그 지형에 추가했던 장애물을 모두 되돌리고 난이도에 0.72를 곱해 다시 생성합니다. 최대 8번까지 시도하고, 그래도 실패하면 그 지형을 장애물 없는 빈 구간으로 남기고 난이도를 0으로 기록합니다. 어떤 시드에서도 트랙이 끝까지 만들어지게 하는 마지막 안전장치입니다. 두 번째 핵심은 지형 사이의 연결입니다. 다음 지형의 솔버는 0초에서 새로 시작하지 않고 앞 지형 해답의 마지막 상태(높이, 속도, 형태, 눌림 여부)에서 출발합니다. 그래서 들판에서 높이 뛴 채로 바다에 들어가는 식의 경계 전이까지 검증 범위에 들어가고, 지형별 해답을 이어 붙이면 트랙 전체의 해답이 됩니다. 이 해답이 타이틀 화면의 자동 플레이와 window.FOURSTEP.setAutoplay(true) 검증에 그대로 쓰입니다.

이 글을 쓰면서 6개 트랙을 생성해 지형별 시도 횟수와 최종 난이도를 뽑아 보았습니다. 생성은 시드 결정적이라 시도 횟수와 난이도는 누가 돌려도 같습니다. 시간은 개발 PC 기준이라 참고용입니다. 왼쪽이 처음 측정한 v1.2.0, 오른쪽이 아래에서 설명할 수정을 넣은 v1.2.1입니다.

v1.2.0 표에서 읽히는 것이 몇 가지 있습니다. 땅굴은 언제나 한 번에 통과하고 솔버 시간도 수 밀리초입니다. 상태가 두 레인뿐이라 탐색이 거의 필요 없기 때문입니다. 반대로 산과 바다는 솔버 시간의 대부분을 차지합니다. 그리고 마지막 들판이 자주 재생성됩니다. MAGMA DRIVE의 마지막 들판은 계획상 난이도 0.8이었지만 네 번째 시도에서 0.8×0.72³ ≈ 0.30으로 내려가서야 통과했습니다. 트랙의 피날레가 설계 의도보다 크게 쉬워지고 있었습니다.

1.2.1에서 고친 것: 마지막 들판은 왜 실패했나

실패한 시도마다 솔버의 마지막 층에서 어떤 장애물에 몇 개의 상태가 죽었는지 기록해 보니, 트랙 끝 처리나 앞 지형에서 이어받은 상태는 원인이 아니었습니다. 죽은 자리는 거의 모두 들판 패턴 안이었고, 그 패턴들은 여유 0.4칸을 둔 RUNNER에게 처음부터 풀 수 없는 모양이었습니다. 난이도가 높을수록 그런 모양이 자주 나오므로, 난이도가 가장 높은 마지막 들판이 가장 많이 걸렸습니다. 원인은 넷이었습니다.

• 점프 정점이 설계보다 낮았습니다. 공중 이동을 "속도를 먼저 줄이고 그 속도로 위치를 옮기는" 방식(반암시적 오일러)으로 1/24박마다 적분하면 정점이 1.6칸이 아니라 약 1.47칸이 됩니다. 몸 윗면이 2.37칸까지만 올라가 2.4칸 터널 천장에 한 번도 닿지 못했습니다. "터널에서 점프하면 매달린다"가 실제로는 일어나지 않았고, 천장으로 피해야 하는 터널 바닥 가시는 통과할 수 없었습니다. 스텝 앞뒤 속도의 평균으로 위치를 옮기도록 바꿔(등가속에서는 정확한 해) 정점 1.6칸, 체공 정확히 1박을 되찾았습니다.
• 2칸 가시는 여유를 두고 넘을 수 없었습니다. 판정 폭 1.64칸에 몸 반폭과 여유를 양쪽에 더하면 3.1칸을 가시보다 높이 지나야 하는데, 점프가 가시 높이 위에 머무는 거리는 약 2.5칸입니다. 그래서 들판의 '이중 가시'는 1칸 가시 둘을 1박(3칸) 간격으로 놓는 "착지 후 바로 다시 점프" 패턴으로 바꿨습니다. 난이도는 그대로 두 번의 정확한 입력을 요구합니다.
• 2.0칸 구덩이는 입력 격자에 걸렸습니다. 점프는 정확히 3칸이고 구덩이는 양옆으로 0.4칸씩 넓혀 판정하므로, 2.0칸 구덩이는 도약 지점이 0.2칸 창 안에 있어야 합니다. 솔버의 결정 간격은 1/8박 = 0.375칸이라 구덩이 위치에 따라 셋 중 둘은 풀 수 없었습니다. 폭 상한을 1.75칸으로 낮췄습니다.
• 낮은 레이저가 0.02칸 차이로 넘을 수 없었습니다. 높이 1.1칸 빔 위를 여유를 두고 넘으려면 1.78칸이 필요한데 점프는 1.76칸을 넘습니다. 히어로는 속도를 바꿀 수 없으니 빔이 켜진 박자에 도착하면 길이 없었습니다. 낮은 빔 높이를 0.9칸으로 줄였습니다.

네 가지 모두 안전 여유와 생성 패턴이 서로 맞지 않던 문제라, 여유 자체는 줄이지 않고 패턴과 물리를 고쳤습니다. 6개 트랙과 DAILY 60일(2026-10-01부터)로 다시 집계하면 다음과 같습니다. "최종/계획"은 최종 난이도를 계획 난이도로 나눈 평균입니다.

66코스의 들판 132개가 모두 계획한 난이도로 한 번에 통과했고, 모든 코스에서 솔버 해답을 실제 판정(여유 없음)으로 다시 돌려 끝까지 완주하는 것을 확인했습니다. 대신 DAILY와 트랙의 코스 배치는 1.2.0과 달라졌습니다. 앞 지형의 시도 횟수가 바뀌면 같은 시드에서 꺼내는 난수 순서도 바뀌기 때문입니다. MAGMA DRIVE의 바다가 1회에서 5회로 늘어난 것도 이 때문인데, 바다와 산은 원래 절반쯤 재생성되고 있었고 그 비율은 이번 수정 전후로 거의 같습니다.

정리

FOURSTEP의 코스 생성은 "자유롭게 만들고 엄격하게 검사한다"는 원칙으로 돌아갑니다. 검사는 게임과 같은 물리 함수를 쓰는 층별 BFS가 맡고, 같은 시각의 상태를 합치는 키 설계 덕분에 1초 안팎에 트랙 하나를 끝냅니다. 1.1.1의 MARGIN은 "풀 수 있다"를 "사람이 풀 만하다"로 바꾼 변화였고, 실패 시 ×0.72 재생성과 이어 풀기는 어떤 시드에서도 트랙이 완성되도록 받쳐 줍니다. 1.2.1에서는 재생성이 몰리던 들판 패턴을 여유와 맞춰 피날레가 계획한 난이도로 끝나게 했습니다. 남은 과제는 여전히 절반가량 재생성되는 바다와 산입니다. 같은 방식으로 실패 지점을 집계해 여유를 두고는 풀 수 없는 모양을 찾아내는 것이 다음 순서입니다.

글: ROGA GAME 개발팀 · 이 글은 실제 개발 기록(설계 문서·변경 이력)을 바탕으로 작성했습니다.