Implementasi algoritma single-objective pso (particle swarm optimation), untuk menentukan rute optimal npc pada game android

ABSTRAK:

Penentuan rute optimal NPC terhadap player merupakan hal yang penting dalam skenario game untuk menambah tingkat kompetitif permainan. Dalam penelitian ini akan menjelaskan tentang pengukuran tingkat keefektifan algoritma optimation dalam mencari rute optimal NPC terhadap player. Salah satu algoritma optimation yang diimplementasikan dalam penelitian ini adalah Single Obejctive Particle Swarm Optimation (PSO). Algoritma PSO merupakan sebuah algoritma yang dapat berguna untuk dalam permasalahan optimisasi yang didasarkan pada simulasi perilaku serangga dan burung yang bergerak dalam sebuah koloni, di mana setiap individu (partikel) dalam koloni mewakili sebuah solusi potensial untuk masalah yang dihadapi. Nantinya PSO akan dibandingkan dengan 2 algoritma yang berbeda yaitu bee colony optimation dan ant colony optimation, dengan mempertimbangkan 3 parameter pengujian yaitu waktu tempuh NPC menemukan rute terhadap player, waktu tempuh NPC menemukan rute ber-obstacle terhadap player, dan Pemilihan rute NPC yang statis (sama) atau dinamis (tidak sama). Didapatkan hasil bahwa algoritma single objective particle swarm optimation mendapatkan hasil paling efektif dibandingkan dengan algoritma bee colony optimation dan ant colony optimation dalam penentuan rute optimal NPC terhadap player

ABSTRACT:

Determining the optimal route for NPCs towards players is crucial in game scenariosto increase the competitiveness of the game. This research will explain the measurement ofthe effectiveness level of optimization algorithms in finding the optimal route for NPCstowards players. One of the optimization algorithms implemented in this study is SingleObjective Particle Swarm Optimization (PSO). The PSO algorithm is used to solveoptimization problems based on simulating the behavior of insects and birds moving in acolony, where each individual (particle) in the colony represents a potential solution to theproblem. PSO will be compared with two different algorithms, namely bee colonyoptimization and ant colony optimization, by considering three testing parameters: the timeit takes for NPCs to find a route towards players, the time it takes for NPCs to find a routewith obstacles towards players, and the selection of static or dynamic NPC route. Theresults show that the single objective particle swarm optimization algorithm is the mosteffective compared to bee colony optimization and ant colony optimization in determiningthe optimal route for NPCs towards players

مستخلص البحث:

هي عنصر مهم يف األلعاب. ميكنأن يلعبNPCدورًا رئيسيًا أو دورًا داعمًاكعدو عادة ً ما يتمتع أو حىت دور املعارض يف اللعبة.NPCبعدة مهام ، ومن بينها البحث عن الالعب ومطاردته. يتطلب البحثعن الالعب ومطاردته خوارزمية حىت يتمكنNPCح قياس مستوى فعامن القيام هبذا األمر. سيتم يف هذا البحث شرلية خوارزميةاألمثلة يف البحث عن املسار املثلى لـNPCجتاه الالعب. أحد خوارزميات األمثلة اليت سيتم تنفيذها يف هذا البحث هوSingleObjective Particle Swarm Optimization (PSO).يعدPSOخوارزمية تستخدم حلل مشاكل األمثلة اليت تعتمدعلى حماكاة سلوك احلشرات والطيور اليت تتحرك يف مستعمرة ، حيث ميثل كل فرد (جسيم) يف املستعمرة حال ً حمتمال ً للمشكلة اليتتواجهها. يف هناية املطاف ، سيتم مقارنةPSOمع خوارزميتني خمتلفتني ومها خوارزميةBee Colony OptimizationوخوارزميةAnt Colony Optimization، بناء ً على ثالثة عوامل اختبارية وهي وقت وصولNPCللعثور على املسار املؤديإىل الالعب ، ووقت وصولNPCللعثور على املسار املؤدي إىل الالعب مع وجود عوائق، واختيارNPCللمسار الثابت (نفسه)أو الديناميكي (غري نفسه.