Python을 이용한 시각적 A* 경로 탐색 및 미로 생성

이 프로젝트는 A* ("A-Star") 경로 탐색 알고리즘(Andrew Kravchuck의 이 Lisp 구현체 기반)의 고성능 구현과 함께, 이 알고리즘이 어떻게 작동하는지 보여주기 위한 다양한 미로 생성 기술 및 이러한 미로에서의 경로 탐색에 대한 고급 애니메이션 시각화(Visualization)를 제공합니다. 미로는 매우 다양한 접근 방식을 사용하여 생성되며, 각 방식은 서로 다른 시각적 느낌을 제공할 뿐만 아니라 경로 탐색 알고리즘에 잠재적인 도전 과제를 부여합니다. A* 알고리즘은 다양한 휴리스틱 함수(Heuristic functions)와 이웃 열거자(Neighbor enumerators)를 고려하여 이러한 미로에서 최단 경로를 효율적으로 찾도록 설계되었습니다.

주요 기능

• 최적화된 A 경로 탐색*: 정수 및 부동 소수점 좌표 모두를 위한 커스텀 우선순위 큐(Priority queue) 및 효율적인 상태 처리(State handling)를 포함합니다.
• 다양한 미로 생성: 확산 제한 응집 (Diffusion-Limited Aggregation, DLA), 생명 게임 (Game of Life), 1차원 오토마타 (One-Dimensional Automata), Langton's Ant, 보로노이 다이어그램 (Voronoi Diagrams), 프랙탈 분할 (Fractal Division), 파동 함수 붕괴 (Wave Function Collapse), 성장 트리 (Growing Tree), 지형 기반 (Terrain-Based), 음악화 (Musicalized), 양자 영감 (Quantum-Inspired), 예술적 (Artistic), 셀룰러 오토마타 (Cellular Automaton), 푸리에 기반 (Fourier-Based), 반응-확산 (Reaction-Diffusion)을 포함하여 복잡하고 다양한 미로를 생성하기 위한 여러 알고리즘을 제공합니다.
• 고급 시각화: 탐색 및 경로 발견의 애니메이션을 포함하여 미로 생성과 경로 탐색에 대한 상세한 시각적 표현을 제공합니다.

<div align="center"> <a href="https://www.youtube.com/watch?v=iA6XJRE6CTM"> <img src="https://img.youtube.com/vi/iA6XJRE6CTM/0.jpg" alt="Demo of it in Action"> </a> <br> <em>작동 데모 (YouTube 영상을 보려면 썸네일을 클릭하세요!)</em> </div>

경로 탐색 구현

설계 철학 및 성능

A* 알고리즘 구현은 효율성과 확장성(Scalability)에 초점을 맞춥니다. 주요 측면은 다음과 같습니다:

1. 커스텀 우선순위 큐 (Custom Priority Queue): 우선순위 큐 (Priority Queue)는 A* 알고리즘의 핵심 구성 요소로, 탐색할 노드들의 열린 집합 (Open Set, Frontier)을 관리하는 데 사용됩니다. 본 구현에서 우선순위 큐는 목표 지점까지의 예상 총 비용(이동 거리 + 휴리스틱 (Heuristic))을 나타내는 우선순위 값을 기반으로 요소의 빠른 삽입 및 추출이 가능하도록 최적화되었습니다. 이를 통해 알고리즘은 가장 유망한 노드에 빠르게 집중할 수 있습니다.

2. 좌표 인코딩 (Coordinate Encoding): 시스템은 정수 및 부동 소수점 (Float) 좌표를 모두 지원하며, 메모리 사용량과 계산을 최적화하기 위해 이를 효율적으로 인코딩합니다. 이 인코딩 과정은 부동 소수점 좌표를 고유한 정수 표현으로 변환하여 정확하고 빠른 디코딩 (Decoding)을 보장합니다. 인코딩 방식은 광범위한 값을 지원하여 세밀한 정밀도와 대규모 지도 모두를 수용할 수 있습니다.

3. 휴리스틱 함수 (Heuristic Functions): 맨해튼 (Manhattan), 옥타일 (Octile), 유클리드 (Euclidean) 거리 휴리스틱을 포함한 다양한 휴리스틱 함수를 사용할 수 있습니다. 각 휴리스틱은 주어진 노드에서 목표에 도달하는 비용을 추정하는 서로 다른 방식을 제공하며, 정확도와 계산 효율성 사이의 균형을 맞춥니다. 휴리스틱의 선택은 A* 알고리즘의 성능에 상당한 영향을 미칠 수 있으며, 일반적으로 더 정확한 휴리스틱은 추가적인 계산 비용을 대가로 더 빠른 경로 탐색 (Pathfinding)을 가능하게 합니다.

4. 이웃 열거 (Neighbor Enumeration): 알고리즘은 경로 탐색 과정에서 이웃 노드를 고려하는 방식을 정의하는 사용자 정의 가능한 이웃 열거기 (Neighbor Enumerators)를 제공합니다. 옵션에는 4방향, 8방향 및 더 복잡한 이동 패턴이 포함됩니다. 이러한 유연성을 통해 알고 la즘은 대각선 이동이 직교 이동보다 비용이 더 많이 드는 것과 같은 다양한 유형의 지형 및 이동 비용을 처리할 수 있습니다.

정확한 비용 함수 및 휴리스틱 비용 함수 (Exact and Heuristic Cost Functions)

• 정확한 비용 (Exact Cost): 이 함수는 한 노드에서 다른 노드로 이동하는 실제 비용을 계산합니다. 노드 간의 거리나 특정 유형의 지형 또는 이동과 관련된 페널티 등 다양한 요소를 고려할 수 있습니다. 예를 들어, 대각선 이동은 수직 또는 수평 이동보다 더 높은 비용이 발생할 수 있습니다.
• 휴리스틱 비용 (Heuristic Cost): 휴리스틱 비용은 주어진 노드에서 목표(goal)에 도달하는 데 드는 비용의 추정치입니다. 이는 A* 알고리즘의 가이드 역할을 하며, 목표에 더 가까울 가능성이 높은 노드에 우선순위를 두도록 돕습니다. 휴리스틱의 정확도와 계산 비용은 다양할 수 있습니다. 더 정확한 휴리스틱은 더 나은 가이드를 제공할 수 있지만 더 많은 계산을 필요로 할 수 있습니다.

미로 생성 방법 (Maze Generation Methods)

이 프로젝트에는 각각 고유한 패턴과 도전 과제를 생성하는 매우 다양한 미로 생성 알고리즘이 포함되어 있습니다. 각 방법에 대한 자세한 설명은 다음과 같습니다:

1. 확산 제한 응집 (Diffusion-Limited Aggregation, DLA):

   • 설명: DLA는 입자가 표면이나 서로에게 달라붙어 응집체(aggregates)를 형성할 때까지 매질 내에서 입자의 무작위 운동을 시뮬레이션하는 과정입니다. 이 알고리즘에서 입자는 무작위 위치에서 시작하여 기존 구조에 달라붙거나 정의된 공간의 경계 밖으로 떨어질 때까지 무작위로 이동합니다.
   • 메커니즘: 알고리즘은 그리드 위의 몇몇 시드(seed) 입자로 초기화됩니다. 새로운 입자들이 무작위 위치에 도입되어 무작위 보행 (random walk)을 수행합니다. 입자가 점유된 셀(다른 입자)과 마주치면 그곳에 달라붙어 응집 구조를 성장시킵니다. 이 과정은 눈송이나 광물 퇴적물과 같은 자연 형성물과 유사한 복잡한 나무 모양의 패턴을 만들어냅니다.

2. Game of Life (라이프 게임):

   • 설명 (Description): Conway의 Game of Life를 기반으로 하는 이 방법은 셀룰러 오토마타 (Cellular Automata) 규칙을 사용하여 살아있거나 죽어있는 상태를 가질 수 있는 셀 격자 (Grid)를 진화시킵니다. 각 셀의 다음 상태는 현재 상태와 살아있는 이웃 셀의 수에 의해 결정됩니다.
   • 메커니즘 (Mechanism): 격자는 살아있는(1) 셀과 죽어있는(0) 셀의 무작위 구성으로 초기화됩니다. 다음 세대의 각 셀 상태는 살아있는 이웃의 수를 세어 결정됩니다. 정확히 3개의 살아있는 이웃을 가진 셀은 살아나고, 살아있는 이웃이 2개 미만이거나 3개를 초과하는 셀은 죽습니다. 이러한 진화는 역동적이고 예측 불가능한 패턴을 생성하며, 종종 복잡한 통로와 막다른 길이 있는 미로 같은 구조를 만들어냅니다.

3. One-Dimensional Automata (1차원 오토마타):

   • 설명 (Description): 이 방법은 단일 행의 셀 (1D)에 적용되는 단순한 규칙을 사용하여 시간이 지남에 따라 2D 미로 패턴을 형성하도록 진화시키는 과정을 포함합니다. 종종 이진수로 표현되는 규칙 세트는 이웃의 상태를 기반으로 셀의 상태를 규정합니다.
   • 메커니즘 (Mechanism): 셀의 한 행이 무작위로 초기화됩니다. 다음 행의 각 셀 상태는 특정 규칙 세트(예: Rule 30, Rule 110)에 따라 현재 상태와 인접한 이웃의 상태에 의해 결정됩니다. 이 과정은 새로운 행을 반복적으로 생성하며, 사용된 규칙에 따라 단순한 형태부터 매우 혼돈스러운 형태에 이르기까지 복잡한 패턴을 만들어냅니다.

4. Langton's Ant (랭턴의 개미):

   • 설명 (Description): 흑백 셀로 이루어진 격자 위를 움직이는 단순한 튜링 머신 (Turing machine)으로, 만나는 셀의 색상에 따라 이동 규칙이 결정됩니다.
   • 메커니즘 (Mechanism): 개미는 일련의 규칙을 따릅니다. 흰색 셀을 만나면 오른쪽으로 회전하고, 해당 셀의 색상을 검은색으로 바꾼 뒤 앞으로 이동합니다. 검은색 셀을 만나면 왼쪽으로 회전하고, 셀의 색상을 흰색으로 바꾼 뒤 앞으로 이동합니다. 이러한 단순함에도 불구하고, 이 시스템은 고속도로 (highways)와 혼돈 영역 (chaotic regions)의 형성을 유도하는 복잡한 동작을 보여줍니다. 시간이 지남에 따라 개미의 경로는 복잡하고 예측 불가능한 패턴을 생성할 수 있습니다.

5. Voronoi Diagram (보로노이 다이어그램):

   • 설명 (Description): 이 방법은 일련의 시드 포인트 (seed points)와의 거리를 기반으로 공간을 영역으로 나눕니다. 각 영역은 다른 어떤 시드 포인트보다 특정 시드 포인트에 더 가까운 모든 점을 포함합니다.
   • 메커니즘 (Mechanism): 격자 위에 무작위 점들을 배치하고, 각 격자 셀에 대해 가장 가까운 시드 포인트를 결정함으로써 보로노이 다이어그램을 계산합니다. 서로 다른 영역 사이의 경계선은 벽으로 취급되어, 다각형 셀로 이루어진 미로가 만들어집니다. 이후 셀 사이의 경계선을 다듬어 통로를 형성하며, 이는 종종 미로 구조에 자연스럽고 유기적인 느낌을 부여합니다.

6. Fractal Division (프랙탈 분할):

   • 설명 (Description): 분할선을 따라 벽을 도입하여 격자를 더 작은 영역으로 나누는 재귀적 분할 (recursive subdivision) 방법입니다.
   • 메커니즘 (Mechanism): 알고리즘은 격자를 수평 또는 수직 벽으로 나누는 것으로 시작하며, 그 후 벽에 개구부 (opening)를 추가합니다. 이 과정은 생성된 하위 영역에서 재귀적으로 반복됩니다. 재귀적 분할 알고리즘 (recursive division algorithm)으로도 알려진 이 방법은 매우 대칭적이고 자기 유사성 (self-similar)을 가진 패턴을 생성할 수 있으며, 작은 규모의 레이아웃이 전체 구조와 닮은 형태를 띠게 됩니다.

7. Wave Function Collapse (파동 함수 붕괴):

   • 설명 (Description): 양자 역학 (quantum mechanics) 개념에서 영감을 받은 이 방법은 제약 기반 접근 방식 (constraint-based approach)을 사용하여 인접한 셀을 바탕으로 각 셀의 상태를 결정합니다.
   • 메커니즘 (Mechanism): 알고리즘은 각 셀이 잠재적으로 여러 상태를 가질 수 있는 미결정 그리드 (undecided grid)에서 시작합니다. 그런 다음 인접한 셀로부터의 제약 조건에 따라 각 셀의 가능성을 붕괴 (collapse)시켜, 패턴이 일관성을 유지하고 모순되지 않도록 보장합니다. 이 방법은 구조가 사전 정의된 규칙 및 패턴과 일치하며, 매우 상세하고 미적으로 즐거움을 주는 미로를 생성합니다.

8. Growing Tree (성장 트리):

   • 설명 (Description): 시작점에서 경로를 확장하여 미로를 생성하는 절차적 방법으로, 어떤 경계 셀 (frontier cell)로부터 확장할지 결정하기 위해 선택 전략 (selection strategy)을 사용합니다.
   • 메커니즘 (Mechanism): 알고리즘은 단일 셀에서 시작하여 미로에 인접한 셀들을 반복적으로 추가합니다. 선택 전략은 다양할 수 있으며 (예: 무작위 (random), 후입선출 (LIFO), 선입선출 (FIFO)), 이는 전체적인 구조에 영향을 미칩니다. Growing Tree 방법은 유연하며 긴 복도부터 밀집된 네트워크에 이르기까지 다양한 외형의 미로를 생성할 수 있습니다.

9. Terrain-Based (지형 기반):

   • 설명 (Description): 이 접근 방식은 Perlin noise (펄린 노이즈)를 사용하여 지형과 같은 높이맵 (heightmap)을 생성한 다음, 임계값 처리 (thresholding)를 통해 미로로 변환합니다.
   • 메커니즘 (Mechanism): 그래디언트 노이즈 (gradient noise)의 일종인 Perlin noise를 사용하여 부드럽고 연속적인 지형 높이맵을 생성합니다. 그런 다음 임계값 (threshold value)을 기준으로 그리드를 통과 가능한 영역과 통과 불가능한 영역으로 나눕니다. 이 방법은 언덕과 계곡이 있는 자연 경관을 닮은 미로를 생성하며, 자연스러운 장애물과 함께 색다른 도전 과제를 제공합니다.

10. Musicalized (음악적 방식):

    • 설명 (Description): 음악적 구성에서 영감을 받은 이 방식은 화성 함수 (harmonic functions)와 파동 (waves)을 해석하여 미로를 생성합니다.
    • 메커니즘 (Mechanism): 알고리즘은 각 셀의 값이 서로 다른 주파수 (frequencies)와 진폭 (amplitudes)을 가진 여러 사인파 (sine waves)의 합으로 결정되는 그리드 (grid)를 생성합니다. 결과적으로 나타나는 파동 패턴은 임계값 처리 (thresholded)를 거쳐 벽과 경로를 생성하며, 이는 리듬감 있고 파동 같은 구조를 닮게 됩니다. 이 방식은 음악의 주기적인 특성을 반영하여 독특한 미적 감각을 제공합니다.

11. Quantum-Inspired (양자 영감 방식):

    • 설명 (Description): 파동 함수 (wave functions)를 중첩시켜 복잡한 간섭 패턴 (interference patterns)을 생성함으로써 양자 간섭 패턴을 모방합니다.
    • 메커니즘 (Mechanism): 알고리즘은 파동 함수의 조합을 사용하여 확률 밀도장 (probability density field)을 생성합니다. 이 장에 임계값 처리를 함으로써 미로의 벽이 결정됩니다. 결과로 나타나는 패턴은 정교하고 섬세하며, 종종 양자 물리학 실험에서 볼 수 있는 복잡한 간섭 패턴과 유사합니다. 이 방식은 높은 수준의 대칭성과 복잡성을 가진 시각적으로 놀라운 미로를 제공합니다.

12. Artistic (예술적 방식):

    • 설명 (Description): 붓 터치 (brush strokes) 및 튐 효과 (splatter effects)와 같은 예술적 기법을 활용하여 추상적인 미로 패턴을 생성합니다.
    • 메커니즘 (Mechanism): 알고리즘은 캔버스 위에 붓 터치와 튐 효과를 무작위로 배치하며, 각 터치는 그리드의 여러 셀에 영향을 미칩니다. 터치의 배치와 방향은 무작위로 결정되어 독특하고 추상적인 패턴을 만들어냅니다. 이러한 예술적 접근 방식은 다양한 예술 스타일을 모방하는 미로를 결과물로 내놓으며, 시각적으로 차별화된 경험을 제공합니다.

13. Cellular Automaton (세포 자동자):

    • 설명 (Description): 각 셀 (Cell)의 상태가 주변 이웃 셀의 영향을 받아 격자 형태의 셀들을 진화시키는 사용자 정의 규칙을 사용합니다.
    • 메커니즘 (Mechanism): 격자는 무작위 상태로 초기화됩니다. 일련의 규칙 세트가 이웃 셀들의 상태를 기반으로 각 셀의 다음 상태를 결정합니다. 이 과정은 여러 번 반복되며, 특정 규칙과 반복 횟수가 최종 패턴에 영향을 미칩니다. 이 방법은 선택된 규칙 세트에 따라 매우 질서 정연한 구조부터 혼돈 상태에 이르기까지 광범위한 구조를 생성할 수 있습니다.