Algoritma Pada Dota

Defense of the Ancients (atau disingkat DotA) adalah sebuah custom map (peta buatan) untuk permainan komputer buatan Blizzard berjudul Warcraft III:Frozen Throne, yang dibuat berdasarkan map "Aeon of Strife" dari permainan Blizzard lainnya, StarCraft. Tujuan utama permainan ini adalah untuk menghancurkan "Ancient" musuh, sebuah struktur yang dijaga ketat di pojok kiri bawah atau kanan atas (yang satu untuk sisi sendiri dan yang satu lagi untuk sisi musuh). Kedua sisi yang bertarung adalah The Sentinel (pasukan penjaga) dan The Scourge (pasukan pembinasa). The Sentinel menjagaAncient bernama Tree of the World (pohon dunia) di pojok kiri bawah, sedangkan The Scourge menjaga Ancient bernama Frozen Throne (tahta yang membeku) di pojok kanan atas. Untuk membuat Ai dalam game dota ini bisa mengejar kita atau pun bergerak mencari kita maka kita akan menggunakan algoritma Pathfinding algorithm. Pathfinding algoritm berdasarkan pada Diijkstra algorithm dimana algoritma ini digunakan untuk memecahkan masalah dengan cara yang paling cepat, jadi dengan menggunakan algoritma pathfinding maka Ai akan dapat menemukan kita dengan rute tercepat. Berikut ini adalah contoh sederhana dari algoritma pathfinding. Pertama-tama siapkan Peta, lalu tentukan koordinat mulainya dan koordinat akhirnya. Tanda X adalah sebuah tembok, S adalah koordinat awal dan 0 adalah koordinat akhirnya. X X X X X X X X X X X _ _ _ X X _ X _ X X _ X _ _ X _ _ _ X X S X X _ _ _ X _ X X _ X _ _ X _ _ _ X X _ _ _ X X _ X _ X X _ X _ _ X _ X _ X X _ X X _ _ _ X _ X X _ _ 0 _ X _ _ _ X X X X X X X X X X X Pertama-tama kita buat daftar dari koordinatnya, dimana kita akan gunakan sebagai antrian. Antrian akan diinisialisasi dengan satu koordinat, akhir dari koordinat.Masing-masing koordinat juga akan memiliki variable counter terlampir. Maka antrian kita mulai dari ((3,8,0)) Kemudian pergi melalui setiap elemen yang ada dalam antrian,termasuk elemen yang ditambahkan ke akhir dalam algoritma, dan untuk setiap elemen lakukan berikut: 1.Buat daftar dari empat sel yang bersebelahan dengan variabel variabel counter elemen saat ini +1 (dalam contoh kita , empat sel adalah ((281)),((371)),((481)), ((391)) 2.Periksa semua sel dalam setiap daftar untuk dua kondisi berikut 1.jika sel itu adalah dinding,hapus dari daftar 2.jika ada unur dalam daftar utama dengan koordinat yang sama atau lebih rendah maka hapus dari daftar. 3.Tambahkan semua sell yang tersisa dalam daftar ke akhir daftar utama 4. Pergi ke elemen selanjutnya dalam daftar Maka setelah satu putaran ,dafatar dari elemen akan menjadi seperti ini ((380)),((281)),((481)) Setelah 2 putaran ((3,8,0),(2,8,1),(4,8,1),(1,8,2),(4,7,2)) Setelah 3 putaran (...(1,7,3),(4,6,3),(5,7,3)) Setelah 4 putaran (...(1,6,4),(3,6,4),(6,7,4)) Setelah 5 putaran (...(1,5,5),(3,5,5),(6,6,5),(6,8,5)) Setelah 6 putaran (...(1,4,6),(2,5,6),(3,4,6),(6,5,6),(7,8,6)) Setelah 7 putaran ((1,3,7)) Sekarang petanya akan terlihat seperti ini: X X X X X X X X X X X _ _ _ X X _ X _ X X _ X _ _ X _ _ _ X X S X X _ _ _ X _ X X 6 X 6 _ X _ _ _ X X 5 6 5 X X 6 X _ X X 4 X 4 3 X 5 X _ X X 3 X X 2 3 4 X _ X X 2 1 0 1 X 5 6 _ X X X X X X X X X X X Sekarang mulai dari S(7)dan pergi ke sel terdekatnya dengan angka terandah (sel yg dicentang tidak dapat di pindahkan). Jalan yang di telusuri adalah (137) > (146) > (155) > (164) > (173) > (182) > (281) > (380).Dalam hal dua nomor sama-sama rendah misalnya, jika S adalah (2,5), memilih arah acak, maka panjangnya akan sama. Dan Algoritma pun selesai.