Dokumentasi akademik dan visualisasi algoritma
Analisis Strategi Algoritma pada Bot Robocode
Implementasi Greedy, BFS, DFS, Route Planning, dan AI Movement pada Bot Battle
Basis analisis
Source Bot yang Dianalisis
Bot 01
SiKicaw: Heuristic Combat Model
SiKicaw memisahkan keputusan menjadi radar, targeting, movement, dan state tracking. Ini cocok dengan gagasan divide and conquer pada modul: masalah battle besar dipecah menjadi sub-masalah yang lebih mudah dioptimasi.
Struktur Bot
- Radar system: full scan, radar lock, dan quick lock target lewat `DoRadar`, `DoSearchRadar`, `QuickLockScannedTarget`.
- Movement: dispatch duel/war, collision escape, anti-gravity, candidate risk search.
- Targeting: memilih power dan prediksi GF/circular/linear berdasarkan data target.
- Enemy tracking: dictionary `enemies`, `EnemyData.FromScan`, scan age, velocity smoothing.
- Wall avoidance: `WallSmooth`, hard wall clamp, penalty jarak dinding.
- Duel/war: `DetermineMode` memilih war saat musuh aktif minimal 2.
- Wave surfing: `waves` dan `WaveDanger` menilai ancaman peluru musuh.
- Guess factor: `gfBins`, `GfPredict`, `UpdateGfWaves` belajar pola lateral target.
Hubungan Modul
Greedy/Best First Search: target dan fire power dipilih dari skor tertinggi. Branch and Bound: kandidat gerak di-prune saat keluar hard wall. Route planning: kandidat posisi dievaluasi sebagai node jalur lokal. Backtracking: simulasi prediksi circular mengulang estimasi waktu sampai konvergen, mirip evaluasi alternatif state.
Target Selection
private EnemyData SelectTarget()
{
EnemyData best = null;
var bestScore = double.NegativeInfinity;
foreach (var e in enemies.Values)
{
if (!IsFresh(e, FreshTurns)) continue;
var score = currentMode == CombatMode.War
? WarTargetScore(e)
: DuelTargetScore(e);
if (score > bestScore) { bestScore = score; best = e; }
}
return best;
}Wave Danger
private double WaveDanger(double x, double y)
{
var danger = 0.0;
foreach (var wave in waves)
{
var radius = wave.Speed * (TurnNumber - wave.FireTurn);
var dist = Dist(x, y, wave.X, wave.Y);
var diff = dist - radius;
if (diff < -50 || diff > wave.Speed * 16) continue;
var angleToPos = AbsBearing(wave.X, wave.Y, x, y);
var spread = Math.Abs(NormRel(angleToPos - wave.Bearing));
danger += Math.Exp(-spread * spread / 2500.0);
}
return danger;
}Bot 02
SiAyam: Greedy Movement Candidate
SiAyam menerapkan local optimization: beberapa kandidat posisi dibangun, lalu skor terbaik dipilih langsung tanpa mengeksplorasi seluruh state space.
Struktur Bot
Radar memakai sweep saat tidak ada target dan lock overshoot saat target ditemukan. Movement memakai empat kandidat: maju, mundur, diagonal kiri, diagonal kanan. Targeting langsung mengarah ke koordinat terakhir musuh dan menembak jika gun heat nol.
Hubungan Modul
Fungsi `MovementScore` adalah Greedy murni: `idealDistanceScore + wallScore`. Route planning muncul dalam bentuk planning lokal satu langkah, bukan BFS/A* penuh. Wall avoidance dilakukan dengan clamp posisi dan skor jarak minimum ke dinding.
Movement Score
private double MovementScore(MovementCandidate candidate, EnemyInfo enemy)
{
var distanceToEnemy = Distance(candidate.X, candidate.Y, enemy.X, enemy.Y);
var idealDistanceScore = 1000 - Math.Abs(distanceToEnemy - IdealDistance);
var wallScore = MinimumWallDistance(candidate.X, candidate.Y);
return idealDistanceScore + wallScore;
}Bot 03
RajaIF: Rule-Based Fire Optimizer
RajaIF adalah baseline yang mudah dibaca: movement periodik, memory target tunggal, radar lock, dan greedy fire-power scoring.
Struktur Bot
`SimpleMovement` membalik arah setiap 35 turn. `CurrentTarget` menyimpan scan selama 30 turn. `ChooseFirePowerByScore` menguji beberapa power lalu memilih nilai tertinggi.
Hubungan Modul
Ini contoh Greedy dan Brute Force kecil: daftar power dicoba satu per satu, lalu keputusan greedy diambil dari skor terbesar. Tidak ada pathfinding global, tetapi ada state-space mini berupa lima pilihan tembakan.
Fire Power Score
var hitChance = 1 / (1 + distance / 400);
var damage = power * 4;
var energyPenalty = power;
var score = damage * hitChance - energyPenalty;Bot 04
RajaIblis: Greedy Multi-Target
RajaIblis menyimpan banyak musuh dalam dictionary, membersihkan data usang, lalu memilih target dengan skor closeness + weakness.
Struktur Bot
Radar sweep digunakan saat target kosong, lock radar saat ada target. Movement sederhana membalik arah setiap 30 turn dan reaktif saat kena peluru, dinding, atau tabrakan bot.
Hubungan Modul
Target selection adalah Greedy Best First sederhana: setiap enemy adalah node kandidat, skor heuristik menentukan prioritas. Cleanup target memory menjaga ruang pencarian tetap kecil.
Target Score
private double TargetScore(EnemyInfo enemy)
{
var distance = DistanceTo(enemy.X, enemy.Y);
var closeness = 1000 / (distance + 1);
var weakness = 100 - enemy.Energy;
return closeness + weakness;
}Pemetaan modul
Algoritma yang Digunakan
| Konsep Modul | Bot | Bukti di Kode | Catatan Akademik |
|---|---|---|---|
| Greedy | Semua | Skor target, skor power, skor movement. | Memilih optimum lokal berdasarkan fungsi evaluasi. |
| Brute Force | RajaIF, SiAyam, SiKicaw | Iterasi daftar power/kandidat. | Jumlah kandidat kecil sehingga layak dicoba semua. |
| DFS/BFS | Visualisasi edukatif | Tidak literal di bot. | Dipakai untuk menjelaskan traversal grid route planning. |
| Branch and Bound | SiKicaw | Kandidat keluar hard wall dilewati. | Cabang invalid tidak dinilai lebih jauh. |
| Route Planning | SiAyam, SiKicaw | Candidate position dan risk scoring. | Planning lokal satu langkah berbasis heuristik. |
| Best First Search | RajaIblis, SiKicaw | Skor tertinggi menjadi target. | Prioritas ditentukan closeness, weakness, data quality. |
Matematika bot
Katalog Rumus dan Penggunaan di Source Bot
Bagian ini merangkum rumus yang benar-benar muncul atau dipakai secara implisit oleh API Robocode/Tank Royale pada source bot. Setiap rumus dihubungkan ke fungsi, tujuan keputusan, contoh angka, serta konsep strategi algoritma.
Kompleksitas
Tabel Kompleksitas Algoritma
| Operasi | Bot | Waktu | Memori | Alasan |
|---|---|---|---|---|
| Pilih target | SiKicaw/RajaIblis | O(n) | O(n) | Scan semua musuh aktif di dictionary. |
| Movement candidate | SiAyam | O(1) | O(1) | Selalu empat kandidat. |
| War risk search | SiKicaw | O(c*n + w) | O(n+w) | c kandidat, n musuh, w wave. |
| Guess factor update | SiKicaw | O(g) | O(s*b) | g wave GF, segment x bin tetap. |
| Fire power scoring | RajaIF/SiKicaw | O(p*k) | O(1) | p power option, k iterasi prediksi. |
Canvas API
Simulasi Visual Interaktif
Radar, Target, Bullet
BFS / DFS / A* / Greedy
Scan musuh
Pilih target
Hitung jarak
Prediksi posisi
Gerakan menghindar
Tembak
Ulangi loop
Evaluasi
Perbandingan Efisiensi Bot
SiKicaw
Efisiensi tinggi untuk battle kompleks, tetapi komputasi paling berat. Movement kuat karena risk scoring, targeting akurat saat data GF cukup.
SiAyam
Ringan dan stabil. Kelemahannya: kandidat sedikit, sehingga dapat gagal menemukan jalur lebih aman yang berada di luar empat arah.
RajaIF
Baseline sederhana dan cepat. Akurasi targeting bergantung pada posisi terakhir target tanpa prediksi velocity.
RajaIblis
Bagus untuk memilih musuh lemah/dekat. Movement masih reaktif dan belum menghitung danger map.
Kesimpulan
Ringkasan Akademik
Keempat bot menunjukkan spektrum strategi dari rule-based sederhana sampai heuristic AI yang lebih adaptif. Secara teori modul strategi algoritma, implementasi paling dominan adalah Greedy, Brute Force terbatas, Route Planning lokal, heuristik Best First, serta pruning ala Branch and Bound. BFS, DFS, UCS, dan A* tidak muncul sebagai implementasi literal pada source, tetapi relevan sebagai pembanding konseptual untuk memahami bagaimana candidate movement bisa dikembangkan menjadi pencarian jalur penuh.