Bagian 4: Pengujian Jalur

Pada bagian terakhir ini, kita menguji pathfinder pada beberapa skenario edge: grid kosong tanpa rintangan, grid dengan banyak jalur alternatif, dan grid di mana goal tidak terjangkau (dead end). Setiap skenario menyingkap aspek berbeda dari algoritma Dijkstra — dari best-case yang seharusnya cepat hingga kasus di mana algoritma harus melaporkan kegagalan dengan sopan.

Skenario Pengujian #

Empat skenario yang akan dijalankan:

#	Skenario	Yang Diuji
1	Grid kosong 5×5	Best case: jalur lurus, banyak alternatif
2	Grid dengan rintangan	Dijkstra menghindari `#`
3	Dead end (goal terkurung `#`)	Deteksi ketiadaan jalur
4	Start = goal	Edge case: panjang 0

Program Pengujian Lengkap #

Berikut program yang menjalankan keempat skenario. Fungsi dijkstra dan reconstructPath diambil dari Bagian 3.

cpp
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>

struct Cell {
    int row, col;
    bool operator==(const Cell& o) const { return row == o.row && col == o.col; }
    bool operator<(const Cell& o) const {
        return row != o.row ? row < o.row : col < o.col;
    }
};

struct Grid {
    std::vector<std::string> cells;
    int rows, cols;
    Grid(std::vector<std::string> g) : cells(std::move(g)) {
        rows = (int)cells.size();
        cols = rows > 0 ? (int)cells[0].size() : 0;
    }
    bool inBounds(int r, int c) const { return r >= 0 && r < rows && c >= 0 && c < cols; }
    bool walkable(int r, int c) const {
        if (!inBounds(r, c)) return false;
        return cells[r][c] != '#';
    }
};

std::vector<Cell> neighbors(const Grid& g, const Cell& c) {
    static const int dr[] = {-1, 1, 0, 0};
    static const int dc[] = {0, 0, -1, 1};
    std::vector<Cell> result;
    for (int i = 0; i < 4; ++i) {
        int nr = c.row + dr[i], nc = c.col + dc[i];
        if (g.walkable(nr, nc)) result.push_back({nr, nc});
    }
    return result;
}

const int INF = 1'000'000'000;

std::vector<std::vector<int>> dijkstra(
        const Grid& g, const Cell& start,
        std::vector<std::vector<Cell>>& parent) {
    std::vector<std::vector<int>> dist(g.rows, std::vector<int>(g.cols, INF));
    parent.assign(g.rows, std::vector<Cell>(g.cols, {-1, -1}));
    using State = std::pair<int, Cell>;
    std::priority_queue<State, std::vector<State>, std::greater<State>> pq;
    dist[start.row][start.col] = 0;
    pq.push({0, start});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u.row][u.col]) continue;
        for (const auto& nb : neighbors(g, u)) {
            int nd = d + 1;
            if (nd < dist[nb.row][nb.col]) {
                dist[nb.row][nb.col] = nd;
                parent[nb.row][nb.col] = u;
                pq.push({nd, nb});
            }
        }
    }
    return dist;
}

std::vector<Cell> reconstructPath(
        const std::vector<std::vector<Cell>>& parent,
        const Cell& start, const Cell& goal) {
    std::vector<Cell> path;
    Cell cur = goal;
    while (!(cur == start)) {
        path.push_back(cur);
        cur = parent[cur.row][cur.col];
        if (cur.row == -1) return {};
    }
    path.push_back(start);
    std::reverse(path.begin(), path.end());
    return path;
}

void printPath(const Grid& g, const std::vector<Cell>& path) {
    if (path.empty()) {
        std::cout << "  Tidak ada jalur dari start ke goal.\n";
        return;
    }
    std::vector<std::string> output = g.cells;
    for (size_t i = 1; i + 1 < path.size(); ++i) {
        output[path[i].row][path[i].col] = '*';
    }
    std::cout << "  Panjang=" << path.size() - 1 << "\n";
    for (const auto& row : output) std::cout << "  " << row << "\n";
}

void runScenario(const std::string& name,
        const std::vector<std::string>& gridData,
        const Cell& start, const Cell& goal) {
    std::cout << "=== " << name << " ===\n";
    Grid g(gridData);
    std::vector<std::vector<Cell>> parent;
    dijkstra(g, start, parent);
    auto path = reconstructPath(parent, start, goal);
    printPath(g, path);
    std::cout << "\n";
}

int main() {
    runScenario("Test 1: Grid kosong 5x5",
        {
            ".....",
            ".....",
            ".S...",
            ".....",
            "....G"
        },
        {2, 1}, {4, 4});

    runScenario("Test 2: Dengan rintangan",
        {
            ".....",
            ".###.",
            ".S.#.",
            "...#.",
            "...G."
        },
        {2, 1}, {4, 3});

    runScenario("Test 3: Dead end (goal terkurung)",
        {
            ".....",
            ".S...",
            ".....",
            ".###.",
            ".#G#."
        },
        {1, 1}, {4, 2});

    runScenario("Test 4: Start = goal",
        {
            ".....",
            ".S...",
            ".....",
            ".....",
            "....G"
        },
        {1, 1}, {1, 1});
    return 0;
}

Output yang Dihasilkan:

text
=== Test 1: Grid kosong 5x5 ===
  Panjang=5
  .....
  .....
  .S***
  ....*
  ....G

=== Test 2: Dengan rintangan ===
  Panjang=4
  .....
  .###.
  .S*#.
  ..*#.
  ..*G.

=== Test 3: Dead end (goal terkurung) ===
  Tidak ada jalur dari start ke goal.

=== Test 4: Start = goal ===
  Panjang=0
  .....
  .S...
  .....
  .....
  ....G

Bedah Hasil Pengujian #

Test 1 — Grid kosong: Dijkstra menemukan jalur (2,1) → (2,2) → (2,3) → (2,4) → (3,4) → (4,4) sepanjang 5 langkah. Banyak jalur lain juga berpanjang 5 — algoritma memilih satu berdasarkan urutan neighbor (atas-bawah-kiri-kanan) dan tie-breaker pada operator< Cell.
Test 2 — Dengan rintangan: jalur tetap ditemukan dengan panjang 4. Dijkstra menghindari # secara otomatis karena neighbors() tidak mengembalikan sel rintangan.
Test 3 — Dead end: goal (4,2) diapit # di tiga sisi (atas, kiri, kanan). Tidak ada sel tetangga goal yang walkable, sehingga dist[goal] tetap INF dan parent tetap (-1, -1). Rekonstruksi jalur mendeteksi cur.row == -1 dan mengembalikan vector kosong — pesan “tidak ada jalur” dicetak.
Test 4 — Start = goal: loop backtrack while (!(cur == start)) langsung keluar karena cur == start sejak awal. Path berisi hanya start ({start}), panjang path.size() - 1 = 0. Tidak ada sel yang ditandai * karena loop for (i = 1; i + 1 < path.size()) tidak dieksekusi (size=1, jadi 1 + 1 < 1 false).

Optimasi: Early Exit saat Goal Pop #

Pada implementasi di atas, Dijkstra berjalan sampai queue kosong meskipun goal sudah ditemukan. Optimasi yang umum: hentikan loop begitu goal di-pop dari queue (saat d == dist[goal]). Pada grid besar, ini bisa menghemat waktu signifikan.

cpp
while (!pq.empty()) {
    auto [d, u] = pq.top(); pq.pop();
    if (d > dist[u.row][u.col]) continue;
    if (u == goal) break;   // early exit
    // ... relaksasi neighbors
}

Trade-off: bila kita butuh jarak ke semua sel (misal untuk visualisasi peta dist), early exit tidak bisa dipakai. Untuk pathfinding murni (hanya butuh jalur start→goal), early exit memberi speedup 2–5× pada grid besar.

Ringkasan Proyek #

Kita telah membangun pathfinder Dijkstra lengkap: pemodelan grid sebagai graph berbobot (Bagian 1), algoritma Dijkstra dengan priority queue (Bagian 2), rekonstruksi jalur via parent array (Bagian 3), dan pengujian pada berbagai skenario edge (Bagian 4). Konsep kunci yang harus diingat: lazy deletion tetap efisien pada std::priority_queue, parent array cukup untuk rekonstruksi jalur, dan guard (-1, -1) memberi deteksi ketiadaan jalur yang jelas.

Kompilasi dan Pengujian #

bash
g++ -std=c++17 -O2 -Wall -Wextra -o test_jalur.bin test_jalur.cpp
./test_jalur.bin

Coba modifikasi grid pada Test 3 untuk membuat jalur alternatif, atau tambahkan goal kedua untuk menguji perilaku Dijkstra pada multi-goal.