Javascript 에서 게임 로그 압축하기

오늘은 기존에 개발했던 게임의 로그 제공을 업데이트하면서 있었던 일을 정리하고자 한다.

배경

https://www.joonas.io/buffalo-chess/

Buffalo Chess

기존에 만든 버팔로 체스는 Replay와 Share Replay 기능을 제공한다.

턴제 게임으로, 각 턴마다 어떤 타일이 움직였는지와 그 상태를 로그로 기록하고 있다. 그리고 replay 기능에서 이를 다시 읽어서 그대로 시뮬레이션한다.

문제는 Share 기능인데, 서버가 없어서 로그를 URL 파라미터로 아래처럼 직접 전달하고 있었다.

https://www.joonas.io/buffalo-chess/?l=m-4-4-3-5-0,m-1-1-2-1-0,m-4-5-4-6-0,m-2-1-3-1-0,m-3-5-3-6-0,m-3-1-4-1-0,m-4-3-4-2-0,m-4-1-5-1-0,e-l

턴 길이만큼 엄청 길어지는데, 이렇게되면 카카오톡 같은 social에서 주소를 공유하기가 어려워진다. 일부 메신저는 URL이 짤려서 링크가 안 되기도 한다.

지금 방식은, 매 턴마다 (event type, x1, y1, x2, y2, boolean)가 한 묶음이고, 파라미터 마지막에 게임의 결과 (win/lose)를 기록한다. 그래서 "m-1-1-5-5-0, ..." 처럼 한 턴마다 11글자를 차지한다.
내 턴이 끝나고 컴퓨터가 움직이는 턴까지 기록하니, 플레이어의 클릭 한 번에 로그는 22자씩 늘어나는 것이다.

 

방법 1

이 방법은 제일 좋다고 생각하는 방법이다.

서버나 remote storage가 있다면, DB에 {"id": "r4Md0mh45H", "log": ....} 처럼 로그를 저장하고 해당 id를 로그 파라미터로 사용하면 될 것이다.

하지만 서버나 remote storage를 제공할 생각은 없고 최대한 로컬에서 해결하고 싶다.

 

방법 2

그럼 파라미터의 길이를 줄여보자.

숫자로만 이루어진 (x1, y1, x2, y2, boolean)은 비트마스킹 기법처럼 하나의 비트로 묶을 수 있다.
등장하는 숫자는 1~7 이므로 길이가 5인 8진법이라고 생각할 수 있다.

가장 작은 경우는 (1, 1, 1, 1, 0) 인 "11110" 이고 이것을 8진법으로 읽어서 36진수로 나타내면 "3m0" 으로 3글자를 만들 수 있다.
가장 큰 경우는 (7, 7, 7, 7, 1) 인 8진법 "77771" 이고, 36진수로 "pa1" 이다.

parseInt(11110, 8).toString(36); // '3m0'
parseInt(77771, 8).toString(36); // 'pa1'

event type은 "move", "end" 이렇게 2개밖에 없는데 "end"는 항상 마지막에 등장하므로, 일정하게 3글자씩 적고 마지막 남은 1글자를 end로 인식할 수 있다.

 

결과

/?l=m-4-4-3-5-0,m-1-1-2-1-0,m-4-5-4-6-0,m-2-1-3-1-0,m-3-5-3-6-0,m-3-1-4-1-0,m-4-3-4-2-0,m-4-1-5-1-0,e-l
/?l=eeg3nseuo6vcbn4a2we1cdagl

위는 기존의 방법, 아래는 방법 2로 압축한 로그이다.

// @parameter events [{type: 'm', r1: 1, c1, 1, r2: 7, c2: 7, kill: false}, ...]
// last event is {type: 'e', value: 'w'|'l'}
History.encode = function (events) {
    const result = [];
    for (const evt of events) {
        if (evt.type === 'e') {
            result.push(evt.value);
        } else if (evt.type === 'm') {
            const hash = evt.r1 * 4096 + evt.c1 * 512 + evt.r2 * 64 +
                evt.c2 * 8 + Number(!!evt.kill);
            result.push(hash.toString(36));
        }
    }
    return result.join('');
};

// @parameter str encode(events)
History.decode = function (str) {
    const evts = str.match(/.{1,3}/g);
    const result = [];
    for (const s of evts) {
    	if (s.length === 1) { // end
            result.push({type: 'e', value: s[1]});
        } else { // move
            const v = [...parseInt(s, 36).toString(8)].map(i => Number(i))
            result.push({
                type: 'm',
                r1: v[0], c1: v[1],
                r2: v[2], c2: v[3],
                kill: !!v[4],
            });
        }
    }
    return result;
};

 

방법 3

방법2도 충분히 좋지만, 게임이 조금 길어지는 경우에는 여전히 로그가 길다.

/?l=m-4-4-3-3-0,m-1-7-2-7-0,m-4-5-4-7-0,m-2-7-3-7-0,m-3-3-3-2-0,m-1-6-2-6-0,m-4-3-4-6-0,m-2-6-3-6-0,m-3-2-3-3-0,m-1-5-2-5-0,m-3-3-3-4-0,m-1-1-2-1-0,m-3-4-2-5-1,m-2-1-3-1-0,m-4-6-4-1-0,m-1-2-2-2-0,m-2-5-3-6-1,m-2-2-3-2-0,m-4-7-4-2-0,m-1-3-2-3-0,m-3-6-3-7-1,m-2-3-3-3-0,m-3-7-4-6-0,m-3-3-4-3-0,m-4-6-4-5-0,m-4-3-5-3-0,e-l
/?l=ee062geuw9a0ats5o0e288vkafs59kau83nsb6x6vcf7s4288hd79sfm84goc1l7o8chcavsf8oe3cel

 

플레이한 턴의 길이를 \(n\) 이라고 하면, 기존에는 \(11n\) 이었다.
그리고 방법 2를 통해 \(3n+1\)로 줄였다.

 

가로 7칸, 세로 5칸이라는 게임의 특성을 이용해 이것을 조금 더 줄일 수 있다.

고정 길이를 위해 1~7을 사용하는 8진법으로 나타내었다. 이 경우는 가장 작을 때와 클 때 모두 3글자이기 때문이다.

 

가로는 7칸이기 때문에 0~6, 세로는 5칸이기 때문에 0~4 로 나타낸다고하면, 진법의 개념을 활용하여 (r1, r2, c1, c2) 를 5와 7을 섞은 진법으로 나타낼 수 있다.

예를 들어, (r1 = 6, r2 = 4, c1 = 0, c2 = 3) 는 \(5 \cdot 7 \cdot 7 \cdot r1 + 7 \cdot 7 \cdot r2 + 7 \cdot c1 + c2\) 와 같은 식으로 압축하는 것이다.

(A, B, C, D) 에서 CD는 00~66 이므로 길이가 2인 7진법으로 처리하고, AB는 길이가 2인 5진법으로 생각하는 것이다.
자리는 중요하지 않아서, \(7 \cdot 5 \cdot 7 \cdot r1 + 5 \cdot 7 \cdot c1 + 7 \cdot r2 + c2\) 가 될 수도 있다.

 

반대로 압축을 해제하는 방법은, 나눗셈과 모듈러를 사용하면 된다. (압축은 곱셈으로 만들었으니 역으로 계산한다.)

// zip
hash =
  (r1-1) * (5*7*7) + // 245
  (r2-1) * (7*7) +   // 49
  (c1-1) * 7 +
  (c2-1)

// unzip
r1: Math.floor(1 + hash / 245)
r2: Math.floor(1 + (hash % 245) / 49)
c1: Math.floor(1 + (hash % 49) / 7)
c2: Math.floor(1 + hash % 7)

 

이렇게 하면 가장 큰 케이스였던 (7, 7, 7, 7, 1)를 36진수 "y0" 인 2글자로 나타낼 수 있다.
나머지 \(n\)개의 boolean들은 2진수 -> 10진수 -> 36진수로 변환하면 된다.

로그의 길이는 \(2n + n/3 + 1\) 가 된다.

 

결과

/?l=ee062geuw9a0ats5o0e288vkafs59kau83nsb6x6vcf7s4288hd79sfm84goc1l7o8chcavsf8oe3cel
/?l=ns2ppgavgr2hp1angl29gt1dfo9jph1lag9rpp1thh9zj0i5plqb-g7uxlqcd-l

위는 방법2, 아래는 방법3 으로 더 줄인 것이다.

총 26턴의 로그이고, 방법 2는 \(3n+1 = 78\), 방법 3은 \(2n + n/3 + 1 = 61\) 로 줄어든 것을 볼 수 있다.

// @parameter events [{type: 'm', r1: 1, c1, 1, r2: 7, c2: 7, kill: false}, ...]
// last event is {type: 'e', value: 'w'|'l'}
History.encode = function (events) {
    const pad = function(str, size) {
        return new Array(size).concat([str]).join('0').slice(-size);
    };
    const rcs = [], ks = [];
    let end = 'i';
    for (const evt of events) {
        if (evt.type === 'e') {
            end = evt.value;
        } else if (evt.type === 'm') {
            rcs.push(pad(
                ((evt.r1-1) * (5*7*7) +
                (evt.r2-1) * (7*7) +
                (evt.c1-1) * 7 +
                (evt.c2-1)).toString(36), 2));
            ks.push(1 + Number(!!evt.kill));
        }
    }
    return [rcs.join(''), parseInt(ks.join(''), 3).toString(36), end].join('-');
};

// @parameter str encode(events)
History.decode = function (str) {
    const [rcs, ks, end] = str.split('-');
    const karr = [...parseInt(ks, 36).toString(3)].map(i => i === '2')
    const result = rcs.match(/.{1,2}/g).map((rc, i) => {
        const v = parseInt(rc, 36);
        return {
            type: 'm',
            r1: Math.floor(1 + v / 245),
            r2: Math.floor(1 + (v % 245) / 49),
            c1: Math.floor(1 + (v % 49) / 7),
            c2: Math.floor(1 + v % 7),
            kill: karr[i],
        }
    }).concat([ { type: 'e', value: end } ]);
    return result;
};