Arsitektur Pathfinding Sirkular: Trade-off Grid vs Visibility Graph

Menentukan rute terpendek di sekitar rintangan sirkular (seperti radius tabrakan unit, pilar silindris, atau medan gaya) pada backend simulasi spasial membutuhkan kompromi ketat antara presisi geometris dan anggaran komputasi server. Server deterministik dengan target tick rate tinggi (30–60 Hz) tidak dapat menoleransi lonjakan latensi (frame spikes) akibat kalkulasi graf yang lambat.

Dua paradigma dominan untuk masalah ini adalah Diskritisasi Grid (A*/JPS) dan Tangent Visibility Graph (Continuous Geometric). Masing-masing memiliki karakteristik kompleksitas memori dan CPU yang saling bertolak belakang saat densitas rintangan berubah.

1. Diskritisasi Grid: Rasterisasi Ruang Kontinu

Pendekatan berbasis grid mengonversi koordinat kontinu menjadi matriks sel reguler berukuran $W \times H$. Setiap rintangan sirkular dirasterisasi (stamped) ke dalam grid navigasi sebagai bitmask atau skor bobot keterlewatan (traversability).

Karakteristik Komputasi

• Waktu Lookup Sel: $O(1)$ untuk mendeteksi apakah suatu titik kontinu berada di dalam rintangan.
• Pencarian Jalur: $O(b^d)$ dengan A*, di mana $b$ adalah branching factor (umumnya 4 atau 8 tetangga) dan $d$ adalah kedalaman langkah.
• Dynamic Update: Murah. Jika rintangan bergerak, hanya bitmask sel di sekitar radius bounding box rintangan yang diubah ($O(R^2)$ terhadap radius raster, independen dari total rintangan $N$).

Kelemahan Inheren

Grid memotong koordinat kontinu menjadi diskrit, memicu dua masalah teknis:

1. Path Sub-optimality: Rute menghasilkan pola zig-zag ortogonal/diagonal. Membutuhkan post-processing tambahan seperti Funnel Algorithm atau String Pulling untuk menghaluskan jalur ke ruang kontinu.
2. Memory Bloat: Ruang memori bergantung pada luas area dunia dan resolusi grid ($O(\text{Area} / \text{Resolusi}^2)$), bukan pada jumlah rintangan. Grid beresolusi halus untuk geometri sirkular kecil mengorbankan CPU cache locality saat traversing node A*.

2. Tangent Visibility Graph: Geometri Kontinu Presisi

Berdasarkan formulasi Red Blob Games untuk circular obstacle pathfinding, rute optimal mengitari lingkaran terdiri dari segmen garis lurus yang menyinggung lingkaran (tangent lines) dan busur lingkaran (circular arcs). Titik belok hanya terjadi persis di garis singgung luar (outer bitangents) dan garis singgung dalam (inner bitangents) antar pasangan lingkaran.

Karakteristik Komputasi

• Presisi Matematis: Rute bersifat optimal secara Euclidean tanpa artefak diskritisasi.
• Jejak Memori Statis: Memori tidak bergantung pada luas dunia fisik. Penyimpanan graf proporsional terhadap simpul rintangan ($N$).
• Kompleksitas Pembangunan Graf: Mengidentifikasi garis singgung antar pasangan lingkaran membutuhkan komparasi pasangan $O(N^2)$. Untuk setiap pasang lingkaran, terdapat hingga 4 garis singgung bersama.
• Uji Visibilitas (Raycasting): Setiap segmen garis singgung harus diuji apakah terpotong oleh $N-2$ lingkaran lain, membawa kompleksitas naif pembangunan graf ke $O(N^3)$ tanpa akselerasi spasial.

3. Implementasi Kalkulasi Garis Singgung Antar-Lingkaran

Berikut kalkulasi matematis minimal untuk menentukan sepasang titik singgung luar (external bitangents) antara dua rintangan lingkaran pada ruang 2D kontinu:

import math
from typing import List, Tuple, Optional

Point = Tuple[float, float]
Circle = Tuple[float, float, float]  # x, y, radius

def calculate_external_bitangents(
    c1: Circle, c2: Circle
) -> List[Tuple[Point, Point]]:
    x1, y1, r1 = c1
    x2, y2, r2 = c2
    dx = x2 - x1
    dy = y2 - y1
    d_sq = dx * dx + dy * dy
    d = math.sqrt(d_sq)

    # Rintangan konsentris atau saling bersinggungan di dalam radius
    if d <= abs(r1 - r2) or d == 0.0:
        return []

    base_angle = math.atan2(dy, dx)
    # Sudut offset garis singgung terhadap vektor pusat antar-lingkaran
    cos_alpha = (r1 - r2) / d
    cos_alpha = max(-1.0, min(1.0, cos_alpha))
    alpha = math.acos(cos_alpha)

    tangents = []
    # ponytail: implementasikan internal bitangents jika rute diizinkan melintasi celah antar rintangan
    for sign in (1.0, -1.0):
        theta = base_angle + sign * alpha
        nx = math.cos(theta)
        ny = math.sin(theta)

        p1 = (x1 + r1 * nx, y1 + r1 * ny)
        p2 = (x2 + r2 * nx, y2 + r2 * ny)
        tangents.append((p1, p2))

    return tangents

# Runnable sanity-check
if __name__ == "__main__":
    circ_a = (0.0, 0.0, 10.0)
    circ_b = (50.0, 0.0, 10.0)
    res = calculate_external_bitangents(circ_a, circ_b)
    assert len(res) == 2
    assert abs(res[0][0][1] - 10.0) < 1e-6
    assert abs(res[1][0][1] - (-10.0)) < 1e-6

Catatan arsitektur: Fungsi di atas hanya menghasilkan candidate edges. Segmentasi garis tersebut harus diverifikasi bebas interseksi terhadap rintangan lain menggunakan bounding volume hierarchy (BVH) seperti Dynamic AABB Tree atau R-Tree untuk menekan biaya uji potong dari $O(N)$ ke $O(\log N)$.

4. Komparasi Karakteristik Sistem

5. Panduan Pemilihan Arsitektur

Gunakan acuan keputusan berikut untuk menentukan fondasi sistem pathfinding backend Anda:

Pilih Grid Discretization jika:

• Densitas Obstacle Dinamis Tinggi ($N > 200$): Unit bergerak bebas, sering memblokir jalan, atau memicu mutasi topologi secara konstan setiap tick.
• Waktu CPU per Tick Terbatas: Server menangani ratusan entitas simultan yang memerlukan determinisme alokasi CPU tanpa risiko kalkulasi kombinatorial $O(N^2)$.
• Implementasi Simpel & Maintainable: Kode navigasi grid standar minim resiko floating point precision bug yang umum terjadi pada kalkulasi geometris garis singgung.

Pilih Tangent Visibility Graph jika:

• Rintangan Jarang (Sparse, $N < 80$): Lingkungan terbuka dengan sedikit pilar sirkular besar, struktur menara, atau zona larangan terbang.
• Dunia Luas (Massive Continuous World): Resolusi grid akan memakan memori RAM server terlalu besar jika dipaksakan memetakan seluruh peta ke sel diskrit.
• Akurasi Fisika Kritis: Unit simulasi memiliki radius putar presisi atau kecepatan tinggi di mana deviasi jalur dari diskritisasi grid menyebabkan tabrakan visual atau osilasi kemudi.

Pendekatan Hibrida (Rekomendasi Skala Besar)

Pada arsitektur game server modern, pilihan optimal sering kali menggabungkan keduanya: gunakan Visibility Graph statis di tingkat global untuk rintangan permanen (menara, pulau, pilar), lalu gunakan Local Collision Avoidance berbasis kecepatan diskrit (seperti RVO2 / ORCA) atau grid lokal transien untuk menghindari rintangan dinamis di sekitar entitas.