회사에서 커피 내기로 사다리 게임을 하다가 한번 만들어 보고 싶어서 시작 하게 되었다.

많은 레퍼런스를 찾아보며 내가 기획한 게임 로직은 아래와 같다. (알고리즘과 게임을 위한 로직만 구현하여 디자인은 신경쓰지 못했다...)

  1. 참여인원 수를 입력하면 player 생성
  2. apply시 인원 수 대로 기둥 생성
  3. 기둥과 기둥 사이에 드래그 하여 bridge생성✨
  4. player 클릭 시 해당 경로 추적✨

처음엔 사다리 경로찾는 로직이 재밌을것 같아서 시작했는데
드래그 하여 bridge 그려주는 부분도 재밌었다.

1번은 굳이 설명이 필요 없고,
2번도 canvas를 써보지 않아서 시간이 걸리긴 했지만 어려운 부분은 아니었다.

기둥과 기둥 사이에 드래그 하어 Bridge 생성하기

두 기둥 사이에 수직선을 그릴 때 선분 AB(mousedown-mouseup)가 드래그 하여 그린 선 이다.

여기서 왼쪽의 경우엔 AB의 연장선을 그어 기둥과 교차하는 점을 알아내야 하고, 오른쪽의 경우엔 AB내부의 기둥과 교차하는 점을 알아내어 아래와 같은 선분을 그려야 한다.

각각의 경우를 외분과 내분이라고 한다.


여기서 위와 같이 기둥에 딱 들어 맞는 선을 얻기 위해서는 외분점 및 외분점의 y값을 알아내야 한다.

시작점 A, 끝점 B 의 좌표 찾기

A의 좌표는 <canvas>onMouseDown,
B의 좌표는 <canvas>onMouseUp 에서 알아 낼 수 있다.

// LadderGame.tsx
const startDrawing = ({ nativeEvent }) => {
  const { offsetX, offsetY } = nativeEvent;
};

const finishDrawing = ({ nativeEvent }) => {
  const { offsetX, offsetY } = nativeEvent;
}
return <canvas onMouseDown={startDrawing} onMouseUp={finishDrawing} />

기둥 내부에 선을 그었을 때

외분점 Q의 x값은 기둥의 x와 같다.
A(x,y) = (onMouseDown-offsetX, onMouseDown-offsetY)
B(x,y) = (onMouseUp-offsetX, onMouseUp-offsetY)
Q(x,y) = (기둥의 x, 계산해야 하는 값)

x1: Bx - Ax
x2: Bx - Ax
y1: Qy- By
y2: Ay - By

x2 / x1 = y2 / y1
x2 / x1 : 외분비
y1 = y2 / 외분비
y1 = y2 / (x2/x1) = y2 * x1 / x2

모든 값을 치환 하면
Qy- By = (Ay - By) * (Bx - Ax) / (Bx - Ax)

찾아야 하는 Q의 y값은
Qy = ((Ay - By) * (Bx - Ax) / (Bx - Ax)) + By

기둥을 벗어 났을때

원래라면 AB사이의 교차점을 찾을 때 내분을 이용하는 것이 맞지만 코드를 재사용 하기 위해 외분으로 통일 했다.

외분/내분 둘 중에 어떤 공식을 이용해도 이 문제는 해결이 가능하다.

이렇게 시작점과 끝점에 가까운 두 기둥의 y값들을 알아낸 뒤
(기둥1x, 기둥1y) (기둥2x, 기둥2y) 두 좌표를 이어 선을 그려준다.

(중요) 사다리를 타기 위한 자료구조 만들기

  1. user수와 같은 크기의 배열을 만든다.(각 요소는 기둥을 의미)
    [기둥1, 기둥2, 기둥3, 기둥4, 기둥5]

    예시) 5개(user수)의 기둥

  2. 하나의 기둥은 점(x,y)들의 집합으로 이루어 진다.
    bridge가 하나도 없을 때 기둥의 시작점과 끝점을 추가해준다.

const data = [
  [
    { x: 83.5, y: 0 },
    { x: 83.5, y: 807 },
  ],
  [
    { x: 250.5, y: 0 },
    { x: 250.5, y: 807 },
  ],
  [
    { x: 417.5, y: 0 },
    { x: 417.5, y: 807 },
  ],
  [
    { x: 584.5, y: 0 },
    { x: 584.5, y: 807 },
  ],
  [
    { x: 751.5, y: 0 },
    { x: 751.5, y: 807 },
  ],
];
  1. 두 기둥을 잇는 bridge를 그리게 되면 각 기둥에 점이 추가 된다.
    여기서 bridge는 시작 점과 끝 점으로 나뉜다.
const newBridge = {
  startBridge: {
    targetIndex, // 시작 점이 몇 번째 기둥에 있는지
    x, // bridge 시작점의 x값
    y, // bridge 시작점의 y값
    linkId, // 경로 추적 시 bridge 사용 유무 판별용
    linkIndex // 끝 점이 몇번째 기둥에 있는지
  },
  endBridge: {
    targetIndex, // 끝 점이 몇 번째 기둥에 있는지
    x,
    y,
    linkId,
    linkIndex // 시작 점이 몇 번째 기둥에 있는지
  }
};
  1. 기둥에 bridge point를 추가해주며 각 점의 y값 기준 오름차순으로 정렬해준다.(사다리를 타고 위에서 아래로 내려오기 때문)
const sortedData = [
  ...,
  [
    { x: 584.5, y: 0 },
    {
      targetIndex: 3,
      x: 584.5,
      y: 772.9861111111111,
      linkId: 20142714692.679825,
      linkIndex: 4,
    },
    { x: 584.5, y: 807 },
  ],
  [
    { x: 751.5, y: 0 },
    {
      targetIndex: 4,
      x: 751.5,
      y: 768.3472222222222,
      linkId: 20142714692.679825,
      linkIndex: 3,
    },
    { x: 751.5, y: 807 },
  ],
];

경로를 추적하여 사다리 내려가기(알고리즘)

const tracePath = (idx) => {
  // node : sortedData[currentLine][nodeIdx] 현재 위치한 점
  const path = []; // 선택한 유저의 경로
  let currentLine = idx; // node가 위치한 기둥
  let nodeIdx = 0; // 기둥에서 몇 번째 점인지
  const usedBridge = new Set(); // bridge history

  while (1) {
    if (sortedData[currentLine].length === nodeIdx) break;
    const node = sortedData[currentLine][nodeIdx]; // 현재 위치한 점
    path.push({ i: currentLine, x: node.x, y: node.y });

    if (!node.linkId) {
      // 연결된 점이 없으면 아래로 이동
      nodeIdx++;
    } else if (usedBridge.has(node.linkId)) {
      // 서로 연결 된 두 점
      // A -> B 이동 한 후에
      // B -> A 로 이동을 막고 아래로 이동하기 위함
	  nodeIdx++;
      // 버그 발생 - 아래에서 설명
    } else {
      // 연결된 점이 있으면 연결된 기둥으로 이동하고
      // 연결된 점으로 이동
      currentLine = node.linkIndex;
      nodeIdx = sortedData[currentLine].findIndex((el) => node.linkId === el.linkId);
      usedBridge.add(node.linkId);
    }
  }
};

위에서 작성한 로직을 실행 하면 아래와 같이 1번에서 출발하면 4번에 도달한다.
한번 사용한 bride는 영원히 사용하지 못하게 되어
표시한 두 지점에서 bridge를 무시하고 아래로 이동해 버린다.

버그 수정
const tracePath = (idx) => {
  ...
  while (1) {
    if (sortedData[currentLine].length === nodeIdx) break;
    const node = sortedData[currentLine][nodeIdx]; // 현재 위치한 점
    path.push({ i: currentLine, x: node.x, y: node.y });

    if (!node.linkId) {
      // 연결된 점이 없으면 아래로 이동
      nodeIdx++;
    } else if (usedBridge.has(node.linkId)) {
      const start = path[path.length - 2].i;
      const end = currentLine;
      
      // 현재 node가 어디서 왔는지 체크
      if (start !== end) nodeIdx++; // 옆 기둥에서 왔으면 아래로 이동
      else { // 위에서 내려왔으면 bridge타고 이동
        currentLine = node.linkIndex;
        nodeIdx = sortedData[currentLine].findIndex((el) => node.linkId === el.linkId);
        }
    } else {
      // 연결된 점이 있으면 연결된 기둥으로 이동하고
      // 연결된 점으로 이동
      currentLine = node.linkIndex;
      nodeIdx = sortedData[currentLine].findIndex((el) => node.linkId === el.linkId);
      usedBridge.add(node.linkId);
    }
  }
};

버그가 발생하던 지점에서 정상적으로 연결된 지점으로 이동하여
1번에서 출발하면 3번에 도달한다.

Demo & Code

profile
왜?를 생각하며 개발하기, 다양한 프로젝트를 경험하는 것 또한 중요하지만 내가 사용하는 기술이 어떤 배경과 이유에서 만들어진 건지, 코드를 작성할 때에도 이게 최선의 방법인지를 끊임없이 질문하고 고민하자. 이 과정은 앞으로 개발자로 커리어를 쌓아 나갈 때 중요한 발판이 될 것이다.

1개의 댓글

comment-user-thumbnail
2023년 9월 24일

잘 읽었습니다 😊

답글 달기