Excalidraw에서 Elbow 화살표 만들기 (파트 2)

발행: 1개월 전 (2025년 12월 19일 오후 09:55 GMT+9)

23 분 소요

Source: Dev.to

이전에 Building Elbow Arrows…

1부에서는 설계 목표(최단 경로, 최소 세그먼트, 올바른 화살표 방향 및 형태 회피)를 식별했지만, 알고리즘에 대한 우리의 순진하고 탐욕스러운 첫 접근 방식은 여러 면에서 부적절한 것으로 드러났습니다. 따라서 이 접근 방식은 다른 알고리즘으로 대체됩니다.

구조를 위한 게임

디자인 목표는 비디오 게임에서의 경로 찾기 문제와 놀라울 정도로 유사했으며, 이는 흔하고 연구가 많이 된 문제입니다. 이 게임의 캐릭터들은 종종 장애물에 막히지 않으면서 게임 맵에서 A 지점에서 B 지점으로 이동해야 하며, 최단 경로를 사용합니다. 또한 그 경로가 인간이 선택할 것처럼 보여야 하므로 몰입감을 깨뜨리지 않아야 합니다. 따라서 우리는 A* 탐색 알고리즘에 주목합니다.

기초 다지기

A* 경로 탐색을 이해하려면 그 배경과, 그것이 기반하고 개선된 다른 그래프 탐색 알고리즘들, 그리고 이들이 우리의 문제 해결에 어떻게 도움이 되는지를 알아야 합니다.

A*가 어디서 왔는가 – 이것은 그래프 탐색을 위한 알고리즘군의 일부로, 모두 노드와 엣지로 연결된 그래프에서 최단 경로를 찾는 것을 목표로 합니다. 이러한 알고리즘은 게임을 넘어 다양한 분야에서 유용하지만, 여기서는 2D 그리드(즉, 캔버스)상의 경로 탐색에 초점을 맞춥니다.
캔버스를 그래프로 변환하기 – 캔버스를 2D 그리드로 나누면(극단적인 경우, 각 픽셀이 하나의 셀) 각 셀 쌍의 인접(공통) 면을 그래프의 엣지로 표현할 수 있으며, 노드는 바로 그 셀 자체가 됩니다.

Nodes to grids

이 노드 엣지(그리드 셀)들을 따라 원래 제약을 만족하는 경로를 찾을 수 있다면, 우리는 그 엘보우 화살표 자체를 간단히 그릴 수 있습니다!

너비 우선 탐색

무가중 그래프에서 최단 경로를 보장하는 간단한 그래프 탐색 알고리즘 중 하나는 겸손한 **Breadth‑First Search (BFS)**이며, 여기서 탐색을 시작합니다.

BFS는 각 반복에서 이미 방문한 노드(시작 셀부터 시작)로부터 직접 연결된 방문하지 않은 모든 노드를 방문합니다.
종료 지점을 포함하는 셀이 방문될 때까지 계속됩니다.
탐색하면서, 방문한 각 노드에 대해 어디서 왔는지 인접 노드를 기록하여 시작 노드로 돌아가는 연결 리스트를 형성합니다.
종료 지점에 도달하면(경로가 최적이므로 조기에 종료할 수 있음), 그 리스트를 역추적하여 최단 경로를 얻습니다.

NOTE: BFS, DFS, 그리고 A*가 어떻게 동작하는지 더 깊이 파고들고 싶다면, 이 article, which dives deeper into these algorithms and offers interactive visualizations를 추천합니다. 이 가이드는 최종 팔꿈치 화살표 구현에 필요한 핵심 통찰만 다룹니다.

다익스트라 알고리즘

BFS는 최단 경로를 제공하고 장애물을 피하지만, 여전히 팔꿈치 화살표에 필요한 직교 굽힘을 만들지는 못합니다. 알고리즘이 원하는 형태를 취하도록 유도하기 위해 다익스트라 알고리즘을 사용합니다.

다익스트라는 가중치가 있는 그래프 간선을 사용하며, 가중치를 이웃을 방문하는 비용으로 활용합니다.
캔버스에 세 번째 “깊이” 차원이 있다고 상상해 보세요: 올바른 팔꿈치‑화살표 경로에 놓인 셀은 평평하고, 그 외의 모든 셀은 가파른 “벽”입니다.
우리의 “미로 생성기”는 설계 목표를 만족하는 셀에 낮은 비용(계곡)을, 그 외 모든 셀에 높은(또는 금지된) 비용을 할당할 수 있습니다.

Excalidraw 캔버스는 사실상 무한하므로 전체 지형을 미리 계산할 수 없습니다. 대신 알고리즘은 임의의 셀에 대해 어느 이웃 셀이 방문하기에 저렴하고 어느 셀이 비싼지를 조회할 수 있어야 합니다.

Source: …

거리 함수

지형을 형성하는 핵심은 잘 선택된 거리 함수입니다. 엣지 가중치는 끝 셀을 향해 자연스럽게 감소하여 하강 “경사”(음의 기울기)를 만들고, 잘못된 선택은 비용이 많이 들게 해야 합니다.

유클리드 거리 – 두 점 사이의 직선 거리.
맨해튼(택시) 거리 – 우리 직교 화살표 경로에 더 적합합니다. 좌표의 절대 차이를 더해 계산합니다:

[ \text{Manhattan}(p_1, p_2) = |x_1 - x_2| + |y_1 - y_2| ]

예를 들어, ([5, 12])와 ([10, -3]) 사이의 거리는 (|5-10| + |12-(-3)| = 5 + 15 = 20) 입니다.

아래 그림은 유클리드(녹색) 선과 길이가 같은 세 개의 맨해튼 경로(빨강, 파랑, 노랑)를 보여줍니다.

Manhattan distance illustration

A*의 휴리스틱(또는 다익스트라의 가중치 함수)으로 맨해튼 거리를 사용하면 알고리즘이 직교 이동을 선호하게 되어, 우리가 원하는 특징적인 팔꿈치‑화살표 모양을 얻을 수 있습니다.

추가 휴리스틱

다익스트라 알고리즘에서 방문하고자 하는 모든 셀에 대해 맨해튼 거리를 조회하면 미로를 생성할 수 있는 메트릭을 얻지만, 동일한 가중치를 가진 여러 경로가 존재하고 우리는 가장 짧은 직교 굽힘 수를 가진 경로를 선택해야 합니다.

미로 생성기에 추가 항을 도입합니다: 이웃 셀의 끝 셀까지의 맨해튼 거리뿐만 아니라, 그 셀로 이동했을 때 경로에 굽힘이 생기면 비용을 증가시킵니다.

탐색 메트릭:

Manhattan distance + bend count

이 가중치 함수와 다익스트라 알고리즘을 결합하면 장애물이 없을 때 올바르고 시각적으로도 깔끔한 팔꿈치 화살표를 생성할 수 있습니다.

Exclusion Zones

형상 회피를 지원하기 위해서는 일부 셀을 비활성화해야 합니다. 이 셀들은 우리 미로에서 무한히 높은 벽처럼 동작하므로 그래프 탐색 알고리즘이 절대 방문하지 않게 됩니다. 이는 각 셀에 플래그를 추가하고, 형상을 해당 셀에 매핑한 뒤, 형상에 의해 덮인 셀들을 비활성화하는 것으로 쉽게 구현할 수 있습니다.

하지만 수정된 거리 계산과 결합되면, 알고리즘이 형상 주위에서 최적이 아닌 경로를 선택하기 시작합니다. 그 이유는 전체 “지도”(즉, 격자)를 한눈에 볼 수 없기 때문이며, 마치 전쟁의 안개가 매 탐색 반복마다 조금씩 밝혀지는 것과 같습니다. 미리 피해야 할 장애물이 너무 늦게 “보여”서 최적의 경로를 놓칠 수 있습니다.

이를 해결하기 위한 실용적인 방법 중 하나는 되돌아가는(back‑tracking) 과정을 도입하는 것이지만, 계산량이 감당하기 어려울 수 있습니다. 불필요한 탐색 단계를 줄이고 우리의 휴리스틱을 적용하기 위해 A* 알고리즘이 최적의 선택처럼 보였습니다.

A*는 다익스트라 알고리즘과 유사합니다—그래프 간선의 가중치를 고려하지만—목표에 더 가까워질 가능성이 높은 인접 노드(또는 셀)를 우선 탐색함으로써 낭비되는 계산을 방지합니다. 또한 메모리 효율적인 단일 패스 해결책을 제공한다는 장점이 있습니다.

Source:

A*란 무엇인가?

A*의 핵심 통찰은 각 셀(노드)에 대해 두 가지 요소를 균형 있게 고려한다는 점이다:

g(n) – 시작점에서 해당 노드에 도달하는 실제 비용(우리의 굽힘 횟수와 이후 추가될 수 있는 휴리스틱).
h(n) – 해당 노드에서 목표에 도달하는 데 필요한 추정 비용(맨해튼 거리 + 격자 제외 + 기타 추가 휴리스틱 함수).
f(n) = g(n) + h(n) – 그 노드를 통과하는 경로의 전체 추정 비용.

알고리즘은 두 개의 노드 집합을 유지한다:

Open set – 평가할 노드들.
Closed set – 이미 평가된 노드들.

과정

시작 노드를 Open set에 추가한다.
Open set이 비어 있을 때까지 반복한다:
- f(n) 점수가 가장 낮은 노드를 선택한다.
- 그 노드가 목표라면 경로를 재구성하고 반환한다.
- 노드를 Closed set으로 이동한다.
- 각 이웃에 대해:
  - 잠정적인 g 점수를 계산한다.
  - 이웃이 Closed set에 있고 새로운 g 점수가 더 나쁘면 건너뛴다.
  - 이웃이 Open set에 없거나 새로운 g 점수가 더 좋다면:
    - 이웃의 점수를 업데이트한다.
    - 현재 노드를 이웃의 부모로 설정한다.
    - 이웃을 Open set에 추가한다.
목표를 찾지 못하고 Open set이 비게 되면 경로가 존재하지 않는다.

항상 f(n) 값이 가장 낮은 노드를 탐색함으로써, A*는 모든 가능성을 전부 탐색하지 않고도 최적 경로를 효율적으로 찾는다—우리가 원하는 바로 그 방식이다. 현재 구현은 대부분 기대대로 동작했지만, 인간이 기대하는 다른 라우팅 선택이 나타나는 엣지 케이스가 계속 발생했고, 성능 문제도 여전히 남아 있었다.

Performance Optimizations

동작은 근접했지만, 성능이 곧 병목 현상이 되었습니다. 특히 매 프레임마다 여러 개의 팔꿈치‑화살표 경로를 계산해야 할 때 더욱 그렇습니다. 120 Hz 이상의 부드러운 렌더링을 목표로, 매 프레임마다 ~50개의 팔꿈치 화살표를 재라우팅하는 것은 높은 목표이지만 달성 가능한 목표였습니다.

Binary Heap Optimization

가장 손쉽게 개선할 수 있는 부분은 열린 노드 집합(셀)입니다. 매 반복마다 열린 노드를 선형 탐색하는 것은 비효율적입니다. 명백한 해결책은 열린 집합을 binary heap에 저장하는 것으로, 삽입 및 제거를 O(log n) 시간에 수행할 수 있게 해 주며 O(n)보다 훨씬 빠릅니다.

Non‑Uniform Grid

픽셀‑그리드(픽셀당 하나의 노드) 위에서 작업하면 불필요한 A* 반복이 대량으로 발생합니다(종종 > 99 %). 몇 픽셀만 차지하는 셀을 사용하더라도 많은 작업이 낭비되고, 픽셀‑정밀한 결과를 얻기 어렵습니다.

해결책은 non‑uniform grid를 그려서 잠재적인 굴곡이 발생할 수 있는 위치에만 노드를 배치하는 것입니다. 미적으로 보기 좋은 팔꿈치 화살표는 항상 다음 지점에서 꺾입니다:

도형의 모서리,
시작점 및 끝점의 방향,
피해야 할 도형 사이의 중간점(선택적 패딩 포함).

알고리즘이 그래프 노드 위에서 동작하기 때문에, 균일한 크기의 그리드를 사용할 필요가 없습니다. A*와 Manhattan‑distance 계산에 필요한 유일한 조건은 인접 셀들이 연속적인 데카르트 좌표를 가져야 한다는 점입니다.

Non‑uniform grid sources and placement

적응형 그리드 (미리보기)

이 기사는 현재 도형 레이아웃을 기반으로 비균일 그리드를 동적으로 생성하고 적응하는 방법을 탐구하는 내용을 계속하지만, 발췌는 여기서 끝납니다.

이미지 출처: Wikipedia (via dev.to)

Manhattan 거리와 A*를 활용한 미적이고 성능 좋은 엘보우 화살표

미적 휴리스틱

기본 A* 구현이 BFS 접근법보다 더 나은 결과를 제공했지만, 과도한 굽힘 수를 넘어서도 부자연스러운 경로가 생성되는 경우가 있었습니다. 추가적인 휴리스틱을 신중히 구성함으로써 이러한 문제를 해결할 수 있었습니다. 그러나 A* 메트릭에 대한 변경은 모든 엣지 케이스에 영향을 미치므로, 최종 솔루션에 도달하기 위해 테스트와 미세 조정을 수동으로 진행했습니다.

1. 역방향 방문 방지

화살표 세그먼트는 대체 경로가 없을 때 역방향(즉, 이전 세그먼트와 겹치는) 이동이 금지됩니다. 이는 스파이크와 같은 경로(완전히 뒤집힌 세그먼트)를 방지할 뿐만 아니라, 거의 완전히 U자형 화살표 구성을 요구하는 경로도 차단합니다.

작동 방식
- 방문 방향을 추적합니다.
- 문제되는 구성을 감지하기 위해 한 단계 뒤와 한 단계 앞을 살펴봅니다.
- 이와 매우 구체적인 그리드 선택을 결합하여, 문제가 발생할 수 있는 엣지 케이스를 방지합니다.

Note: 이는 최대 두 개의 축 정렬된 폐쇄 경계 상자(형태)를 피해야 하는 상황에서만 작동합니다. 장애물이 더 많아지면 문제가 다시 나타날 수 있습니다.

2. 세그먼트 길이 고려

맨해튼 거리가 A* 경로 탐색의 주요 메트릭이지만, 유클리드 거리 기준으로 더 긴 직선 세그먼트를 여러 짧은 세그먼트보다 선호합니다. 일부 엣지 케이스에서는 비균일 그리드가 생성된 경로가 최단이라고 가정하지만, 픽셀 그리드에 투영될 때 존재해서는 안 되는 짧은 스텝 패턴을 만들 수 있습니다—특히 연결된 형태가 멀리 떨어져 있을 때 그렇습니다.

3. 형태‑측면 인식

장애물을 좌측이나 우측으로 우회할지를 선택할 때 알고리즘은 다음을 고려합니다:

장애물 측면의 길이.
시작점과 끝점의 방향(이 시리즈 1부의 “heading” 참고) 상대 위치.
화살표와 형태의 경계 상자 측면 사이의 평행 또는 직교 관계.

4. 짧은 화살표 처리

시작점과 끝점이 매우 가까운 경우를 위한 특수 로직이 포함됩니다. 이는 과도한 우회와 루프를 방지합니다. 연결된 형태가 거의 겹치는 상황에서는 일반 알고리즘으로는 기대되는 경로가 나오지 않기 때문에, 하드코딩된 단순 직접 경로가 사용됩니다.

5. 겹침 관리

구현은 형태가 시작점 및/또는 끝점을 덮는 경우를 명시적으로 감지합니다. 연결된 형태나 점이 겹칠 때는 하나의 형태 또는 두 형태에 대한 회피를 선택적으로 비활성화하여, 회피 구역이 차단하더라도 유효한 경로가 존재하도록 합니다.

기타 솔루션

Manhattan 거리를 사용한 A*가 직교(엘보우) 화살표를 얻는 유일한 방법은 아닙니다. 아래는 검토했지만 최종적으로 채택하지 않은 연구 논문들입니다:

Gladisch, V., Weigandt, H., Schumann, C., & Tominski, C.
Orthogonal Edge Routing for the EditLens – arXiv:1612.05064
Wybrow, M., Marriott, K., & Stuckey, P. J.
Orthogonal Connector Routing – Springer PDF

결론

단순한 기능 요청—“팔꿈치 화살표 추가”—에서 시작된 것이 정교한 경로 탐색 과제로 발전했습니다. 다음을 결합함으로써:

고전 알고리즘 (A*),
도메인 특화 최적화 (비균일 그리드, 피해야 할 두 가지 형태 등), 그리고
신중하게 조정된 휴리스틱 (미적 가중치),

Excalidraw의 팔꿈치 화살표는 다이어그램 작성 속도를 크게 높이고 손으로 그리거나 관리하던 화살표의 필요성을 없앴습니다.

이러한 개선 덕분에 키보드 단축키 흐름도 생성(데모 보기)과 같은 강력한 기능도 가능해졌으며, 이는 진지한 다이어그램 작업이 필요한 Excalidraw 사용자들에게 더욱 큰 힘을 실어줍니다.

다음 단계: 팔꿈치 화살표 시리즈의 세 번째이자 마지막 파트에 함께 참여하세요. 여기서는 화살표 세그먼트를 제어하고 고정함으로써 파워 유저가 예측하기 어려운 경로를 구현할 수 있게 하는 방법을 안내합니다!