Belajar BFS dengan Bubble Shooter: Detektif Gelembung untuk Pemula

 

sumber : www.juangtechno.my.id

Hai, coder pemula! Ingin tahu cara algoritma Breadth-First Search (BFS) membuat game Bubble Shooter jadi seru? Yuk, kita jadi detektif gelembung dan ungkap rahasia grid dengan bahasa sederhana!

Apa Itu BFS?

Bayangkan kamu mencari teman di pesta: kamu cek orang di dekatmu dulu, baru ke lingkaran berikutnya. Itulah BFS! Ia menjelajahi "tetangga" terdekat dari titik awal (seperti gelembung di grid) sebelum melangkah lebih jauh, seperti gelombang air yang menyebar.

Dalam Bubble Shooter, BFS membantu menemukan:

1. Kelompok gelembung dengan warna sama yang harus pecah.
2. Gelembung "mengambang" yang tidak terhubung ke atas dan harus jatuh.

Misi 1: Pecahkan Gelembung Sama Warna

Saat gelembung baru menempel, BFS mencari kelompok gelembung dengan warna yang sama menggunakan fungsi find_connected_group(). Berikut kode ringkasnya:

def find_connected_group(grid, start_r, start_c, target_color):
    if grid[start_r][start_c] is None or grid[start_r][start_c].color != target_color:
        return set()
    q = [(start_r, start_c)]  # Antrean detektif
    visited = {(start_r, start_c)}  # Buku catatan detektif
    group = {(start_r, start_c)}  # Tas detektif
    neighbors_offsets = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    while q:
        r, c = q.pop(0)
        for dr, dc in neighbors_offsets:
            nr, nc = r + dr, c + dc
            if 0 <= nr < GRID_ROWS and 0 <= nc < GRID_COLS:
                if (nr, nc) not in visited and grid[nr][nc] is not None and grid[nr][nc].color == target_color:
                    visited.add((nr, nc))
                    q.append((nr, nc))
                    group.add((nr, nc))
    return group

Cara Kerja:

• Detektif BFS mulai dari gelembung baru, memeriksa tetangga (atas, bawah, kiri, kanan).
• Gelembung dengan warna sama dikumpulkan. Jika ada tiga atau lebih, mereka pecah!

Misi 2: Jatuhkan Gelembung Mengambang

Setelah beberapa gelembung pecah, BFS mencari gelembung yang "mengambang" (tidak terhubung ke atas) dengan find_floating_bubbles():

def find_floating_bubbles(grid):
    reachable_from_top = set()
    q = []
    for c in range(GRID_COLS):
        if grid[0][c] is not None:
            q.append((0, c))
            reachable_from_top.add((0, c))
    neighbors_offsets = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    while q:
        r, c = q.pop(0)
        for dr, dc in neighbors_offsets:
            nr, nc = r + dr, c + dc
            if 0 <= nr < GRID_ROWS and 0 <= nc < GRID_COLS:
                if (nr, nc) not in reachable_from_top and grid[nr][nc] is not None:
                    reachable_from_top.add((nr, nc))
                    q.append((nr, nc))
    floating_bubbles = set()
    for r in range(GRID_ROWS):
        for c in range(GRID_COLS):
            if grid[r][c] is not None and (r, c) not in reachable_from_top:
                floating_bubbles.add((r, c))
    return floating_bubbles

Cara Kerja:

• BFS mulai dari gelembung di baris atas, menandai semua yang terhubung.
• Gelembung yang tidak ditemukan dianggap mengambang dan dijatuhkan.

BFS dalam Aksi

Dalam game loop, setelah gelembung menempel:

if attached_r is not None and attached_c is not None:
    group_to_pop = find_connected_group(game_grid, attached_r, attached_c, game_grid[attached_r][attached_c].color)
    pop_bubbles(game_grid, group_to_pop)  # Pecahkan jika grup >= 3
    floating_group = find_floating_bubbles(game_grid)
    drop_floating_bubbles(game_grid, floating_group)  # Jatuhkan gelembung

Kenapa BFS Keren?

• Efisien: Memeriksa semua gelembung secara sistematis.
• Sederhana: Antrean membuatnya mudah dipahami.
• Fleksibel: Bisa digunakan untuk labirin, peta, dan lainnya!

Ingin Petualangan Coding Lebih Seru?

Artikel ini hanya cuplikan dari kehebatan BFS di Bubble Shooter. Untuk penjelasan lengkap dan petualangan coding lainnya, dapatkan buku Petualangan Pythonku! di lynk.id.(segera menysusul) Tembak gelembung, pelajari algoritma, dan jadilah coder hebat!