Bottleneck Komputasi Spasial pada Game MMO

Game browser MMO dengan ribuan entitas bergerak bersamaan menuntut kalkulasi Area of Interest (AOI) berulang setiap game-tick (100–200 ms). Server harus mencari seluruh entitas di dalam radius tertentu untuk mengirimkan pembaruan state posisi. Pendekatan naif menggunakan fungsi jarak Euclidean secara langsung pada klausa WHERE:

SELECT id, x, y FROM players
WHERE sqrt(power(x - $1, 2) + power(y - $2, 2)) <= $3;

Query tersebut memicu Full Table Scan (Sequential Scan). PostgreSQL harus menghitung fungsi matematika untuk setiap baris data karena komputasi dilakukan secara dinamis tanpa dukungan indeks skalar B-Tree standar. Saat jumlah entitas aktif meningkat, CPU tersaturasi dan latensi tick melonjak drastis.

Spatial Indexing Menggunakan PostGIS (GiST)

Solusi umum di tingkat basis data adalah ekstensi PostGIS dengan tipe geometri/geografi dan indeks Generalized Search Tree (GiST). GiST memetakan koordinat ke dalam struktur R-Tree menggunakan Bounding Box (kotak pembatas).

Skema Tabel PostGIS

CREATE EXTENSION IF NOT EXISTS postgis;

CREATE TABLE entities_postgis (
    id BIGSERIAL PRIMARY KEY,
    name VARCHAR(32) NOT NULL,
    pos GEOMETRY(Point, 0) NOT NULL
);

CREATE INDEX idx_entities_postgis_pos ON entities_postgis USING GIST (pos);

Query Area-of-Interest (AOI)

Fungsi ST_DWithin memanfaatkan indeks GiST untuk memfilter entitas dalam radius secara efisien:

SELECT id, ST_X(pos) AS x, ST_Y(pos) AS y
FROM entities_postgis
WHERE ST_DWithin(pos, ST_MakePoint($1, $2), $3);

Kelemahan GiST pada Game Real-Time: Struktur R-Tree membutuhkan re-balancing saat nilai baris berubah. Jika ribuan pemain mengirim pembaruan posisi per detik, frekuensi operasi UPDATE menyebabkan lock contention, fragmentasi indeks, dan overhead I/O yang tinggi.

Pendekatan Integer Grid Hashing

Alternatif yang lebih deterministik untuk koordinat kartesius 2D adalah diskretisasi dunia game menjadi grid seragam. Dunia dibagi ke dalam sel-sel berukuran tetap (misal: 100x100 unit dunia). Posisi kontinu (x, y) dipetakan ke ID grid berbasis bilangan bulat (integer).

Skema Tabel Grid Hashing

CREATE TABLE entities_grid (
    id BIGSERIAL PRIMARY KEY,
    name VARCHAR(32) NOT NULL,
    x REAL NOT NULL,
    y REAL NOT NULL,
    cell_id BIGINT NOT NULL
);

-- Indeks B-Tree standar terbukti jauh lebih murah saat UPDATE
CREATE INDEX idx_entities_grid_cell ON entities_grid (cell_id);

Fungsi Konversi Sel di TypeScript

const CELL_SIZE = 100;
const WORLD_WIDTH_CELLS = 1000;

export function getCellId(x: number, y: number): number {
    const cx = Math.floor(x / CELL_SIZE);
    const cy = Math.floor(y / CELL_SIZE);
    return cy * WORLD_WIDTH_CELLS + cx;
}

export function getNeighborCellIds(x: number, y: number): number[] {
    const cx = Math.floor(x / CELL_SIZE);
    const cy = Math.floor(y / CELL_SIZE);
    const cells: number[] = [];

    for (let dx = -1; dx <= 1; dx++) {
        for (let dy = -1; dy <= 1; dy++) {
            cells.push((cy + dy) * WORLD_WIDTH_CELLS + (cx + dx));
        }
    }
    return cells;
}

Query AOI Berbasis Cell-Pruning

-- Mengambil sel target + 8 sel tetangga menggunakan B-Tree Scan,
-- kemudian saring sisa lingkaran presisi hanya pada entitas yang lolos.
SELECT id, x, y
FROM entities_grid
WHERE cell_id = ANY($1::bigint[])
  AND (x - $2)^2 + (y - $3)^2 <= $4^2;

Analisis EXPLAIN ANALYZE: GiST vs Grid Hashing

Pengujian dilakukan pada dataset simulasi 50.000 entitas aktif pada peta 10.000x10.000 unit, mencari radius 100 unit.

1. Hasil PostGIS ST_DWithin (GiST)

Bitmap Heap Scan on entities_postgis  (cost=4.38..45.12 rows=15 width=40) (actual time=0.412..0.890 rows=12 loops=1)
  Recheck Cond: (pos && '...'::geometry)
  Filter: st_dwithin(pos, '...'::geometry, 100::double precision)
  ->  Bitmap Index Scan on idx_entities_postgis_pos  (cost=0.00..4.38 rows=45 width=0) (actual time=0.210..0.210 rows=48 loops=1)
Planning Time: 0.231 ms
Execution Time: 0.945 ms

2. Hasil Integer Grid Hashing (B-Tree)

Index Scan using idx_entities_grid_cell on entities_grid  (cost=0.41..18.25 rows=12 width=40) (actual time=0.045..0.128 rows=12 loops=1)
  Index Cond: (cell_id = ANY ('{10050,10051,...}'::bigint[]))
  Filter: (((x - 500::real)^2 + (y - 500::real)^2) <= 10000::real)
Planning Time: 0.115 ms
Execution Time: 0.162 ms

Grid Hashing menghasilkan eksekusi berkisar 0.1–0.2 ms, memangkas latensi sekitar 5x hingga 8x lipat dibanding GiST pada konfigurasi database yang sama.

Perbandingan Arsitektur

  • Biaya Update (Write Heavy): B-Tree pada Grid Hashing jauh lebih murah dibandingkan re-indexing pohon R-Tree GiST. Update cell_id hanya terjadi ketika entitas melintasi batas sel, bukan setiap piksel pergerakan.
  • Overhead Dependensi: Grid hashing tidak memerlukan ekstensi PostGIS, cukup menggunakan PostgreSQL vanilla dengan indeks B-Tree standar.
  • Akurasi Batas: GiST secara native menangani boundary kompleks. Grid hashing memerlukan penyetelan ukuran sel yang proporsional dengan radius AOI agar sel tetangga tidak mengambil entitas terlalu banyak atau terlalu sedikit.

Rekomendasi Implementasi

Gunakan PostGIS jika dunia game menggunakan sistem GIS riil (garis lintang/bujur geospasial) atau bentuk poligon AOI yang tidak beraturan. Gunakan Grid Hashing pada koordinat kartesius game MMO browser berfrekuensi tinggi untuk menjamin latensi sub-milidetik pada tick rate stabil.