사과 게임 헬퍼 만들어보기

게임

https://www.gamesaien.com/game/fruit_box_a/

無料ゲーム「フルーツボックス」

요약

예전에 참 재밌게 했었던 게임인데, 오랜만에 다시 하려니 심신이 피로하고 무척 귀찮아서 차라리 사각형을 보여주는 걸 코딩해보면 재밌겠다는 생각이 들었다.

플래시 게임 수준의 1인용 로컬 게임이기도 하니, 핵이나 매크로를 만든다고 해서 피해가 생기진 않을테고...
어디서 사용한다고 쳐도 너무 눈에 띄는 수준이라 만들고 공개도 해볼만하다고 생각해서 진행했다.

---

구현

게임 동작 방식

가로로 17개, 세로로 10개의 사과가 있고, 각 사과에는 1부터 9 까지의 숫자가 적혀있다.
아래와 같이 숫자의 합이 10이 되는 사각형을 찾아서 드래그하면 점수를 얻는다.

사과의 숫자 인식

게임은 워낙 간단한 방식이니 이해했고, 그럼 코드로 풀어보려면 숫자부터 인식해야한다.

게임판에서 적당히 20x20 크기로 잘라낸 숫자들

다행히도 HTML5 canvas 기반이라서 쉽게 이미지를 가져올 수 있었다. 적당히 기준점을 (75, 80) 위치로 잡고 33 x 33 크기로 잘라봤는데 모든 사과들의 위치가 규칙적이라, 이미지를 얻는 데 큰 문제는 없었다.

const getImageData = (x, y) => {
  return ctx.getImageData(75 + x * 33, 80 + y * 33, 20, 20);
};

진지하게 숫자 인식을 사용해볼까하다가 tensorflow.js 같은 외부 라이브러리를 쓰는 수고가 더 들 것 같았다.
어차피 재미로 짜보는 코드인데, 완성도는 나중에 생각하고 로직을 먼저 완성해보는 것이 맞아보인다.

대충 모든 숫자를 겹쳐 본 모습

어차피 9개의 숫자가 서로 구분만 되면 되니까, 숫자별로 위치가 다르게 나올 수 밖에 없는 조합을 골라서 해싱으로 비교했다.

노란색 박스 안에서 적당히 6개의 픽셀 선정

자세한 설명은 생략한다.

// 20x20 pixels => 6 pixels X 3(rgb) => 18개
const pca = ({data}) => {
  const loc = (x, y) => 4 * (y * 20 + x);
  const rgb = (x, y) => {
    const i = loc(x, y);
    const s = data.slice(i, i + 4);
    return [s[0], s[1], s[2]];
  };
  return [rgb(5, 5), rgb(12, 5), rgb(5, 9), rgb(12, 9), rgb(5, 13), rgb(12, 13)];
};
const hash = (imgData) => pca(imgData).flat().reduce((a, c) => (a * 256 + c) % 213, 0);
const answers = [37, 48, 145, 205, 175, 146, 59, 139, 70];
const getNumber = (imgData) => answers.indexOf(hash(imgData)) + 1;

아무튼 규칙적인 위치에 적당히 점을 뽑아서 패턴에 맞게 숫자들을 분류하면 아래와 같이 숫자를 인식할 수 있다.

첫 번째 스크린샷과 비교하면 성공적으로 숫자 인식됨

물론 캔버스의 크기나 주변 픽셀 등의 영향으로 rgb 색상이 조금이라도 바뀐다면 동작하지 않는 코드지만, 아래의 짤로 마무리하겠다.

합이 10인 사각형 찾기

사과 게임 이미지로부터 숫자를 해석하고 이제 처리할 준비는 되었는데, 어떤 알고리즘으로 사각형을 찾아줄 것인지 고민할 차례이다.

2차원 배열에서 합이 10이 되는 사각형을 찾는 알고리즘은, prefix sum(누적 합)으로 계산할 수 있다. 적절한 연습 문제로는 BOJ 2167 - 2차원 배열의 합이 있다.

물론 모든 경우의 수를 탐색하면서 하나씩 전부 찾아도 되긴 하지만, 시간복잡도가 $O(n^6)$ 이다. 물론 $n \le 17$  이라서 허용할 수 있는 정도지만.. 일단 이런 naive한 방식의 구현은 아래와 같다.

아래 코드는 사각형의 네 꼭짓점을 찾고, 네 꼭짓점 안에 존재하는 모든 숫자를 더하는 방법이다.

function getSum(g, sx, sy, ex, ey) {
  let sum = 0;
  for (let i = sx; i <= ex; i++)
    for (let j = sy; j <= ey; j++)
      sum += g[i][j];
  return sum;
}

function getBoxes() {
  const g = getGrid();
  const boxes = [];
  // O(n^6)
  for (let sy = 0; sy < ROWS; sy++)
    for (let sx = 0; sx < COLS; sx++)
      for (let ey = sy; ey < ROWS; ey++)
        for (let ex = sx; ex < COLS; ex++)
          if (getSum(g, sx, sy, ex, ey) === 10)
            boxes.push({sx, sy, ex, ey});
  return boxes;
}

약간 최적화

다음은 누적합 배열을 두어서, $O(n^2)$ 시간에 미리 초기화를 해두고, 어떤 사각형을 만드는 네 꼭짓점이 주어지면 $O(1)$ 시간에 사각형 내부의 합계를 알 수 있다.

// O(1)
function getPrefixSum(sum, sx, sy, ex, ey) {
  return sum[ey+1][ex+1] - sum[ey+1][sx] - sum[sy][ex+1] + sum[sy][sx];
}

function getBoxes() {
  const g = getGrid();
  const boxes = [];
  const sum = Array.from({length: ROWS + 1}, () => Array(COLS + 1).fill(0));
  
  // O(n^2); init prefix sum array
  for (let y = 1; y <= ROWS; ++y)
    for (let x = 1; x <= COLS; ++x)
      sum[y][x] = g[y-1][x-1] + sum[y-1][x] + sum[y][x-1] - sum[y-1][x-1];
  
  // O(n^4)
  for (let sy = 0; sy < ROWS; sy++)
    for (let sx = 0; sx < COLS; sx++)
      for (let ey = sy; ey < ROWS; ey++)
        for (let ex = sx; ex < COLS; ex++)
          if (getPrefixSum(sum, sx, sy, ex, ey) === 10)
            boxes.push({sx, sy, ex, ey});
  return boxes;
}

별거 아닌 것 같지만, 가로 17, 세로 10인 이 게임의 경우에는 위 코드보다 170배 빠르게 계산하는 코드이다.

---

결과

실제 게임 캔버스 위에 가상의 투명 캔버스를 올리고, 마우스 이벤트가 무시되도록 설정하고, 사각형을 "잘" 그리는 등의 설명은 생략되었지만 중요한 내용은 다 짚었으므로 생략한다.

잘 나온다

---

전체 코드

Fruit box game visualizer