Perkembangan video game merupakan salah satu perkembangan teknologi yang paling cepat. Terbukti dengan banyaknya inovasi berkenaan dengan Kecerdasan Buatan, salah satunya adalah penerapan algoritma pathfinding. Pengimplementasian pathfinding biasanya diterapkan pada Non-Player Character (NPC) yang ada pada suatu game.
NPC ialah karakter dalam game yang tak bisa dimainkan dan dikontrol langsung oleh pemain. NPC biasanya akan diprogram melakukan hal tertentu seperti menyediakan informasi sampai bahkan mengikuti si pemain ke mana pun. Meski telah diprogram sedemikian rupa, NPC seringkali membuat kesalahan.
Karena seringnya NPC mengalami eror, penulis mengusulkan untuk mengimplementasikan algoritma pathfinding bertipe Breadth First Search pada NPC di game yang penulis buat, berjudul “DEJAVU”. “DEJAVU” adalah game balapan 2D sederhana yang akan mempertandingkan pemain dan NPC yang sudah diimplementasikan algoritma tertentu secara satu lawan satu. Berdasarkan hasil pengujian yang dilakukan dengan 10 kondisi dan setiap kondisi dilakukan 5 kali, terdapat 6 kondisi yang berhasil.