Optimasi rute menggunakan algoritma A* dan brute force pada game simulasi traveling salesman problem

INDONESIA:

Penelitian ini bertujuan untuk menerapkan Algoritma Brute Force dan A* dalam game CoolCity, sebuah game simulasi edukatif berbasis Travelling Salesman Problem (TSP), guna meningkatkan efisiensi pemain dalam menentukan jalur optimal dalam skenario multi-objektif. Algoritma Brute Force digunakan untuk menentukan urutan kunjungan lokasi dengan jarak total minimum, sedangkan algoritma A* diterapkan untuk mencari jalur terpendek antar lokasi. Hasil pengujian menunjukkan bahwa rute yang dihasilkan Algoritma Brute Force konsisten dengan perhitungan manual dan memberikan hasil optimal dari segi jarak. Sementara itu, pengujian algoritma A* terhadap tiga kali proses pengujian menunjukkan rata-rata selisih waktu tempuh sebesar 0,11 detik pada pengujian tanpa hambatan, 0,22 detik dengan hambatan festival, dan 9.55 detik pada pengujian dengan hambatan tambahan berupa lokasi festival dan lampu merah. Temuan ini menunjukkan bahwa keberadaan hambatan dinamis berdampak signifikan terhadap waktu tempuh aktual, sehingga jalur dengan biaya terendah tidak selalu menghasilkan waktu tercepat. Selain itu, hasil uji usability menggunakan pendekatan GUESS menunjukkan bahwa game memiliki tingkat keterpahaman, kemudahan navigasi, dan kepercayaan diri pengguna yang tinggi, dengan skor rata-rata 5,12 dari skala 7. Hal ini mengindikasikan bahwa game CoolCity berhasil memberikan pengalaman bermain yang baik dan efektif dalam menyampaikan tujuan edukatifnya

ENGLISH:

The purpose of this research is to implement the Brute Force and A* algorithms in CoolCity, an educational simulation game based on the Travelling Salesman Problem (TSP), to enhance players' efficiency in determining the optimal route in multi-objective scenarios. The Brute Force algorithm is employed to determine the optimal sequence of visits with the shortest total distance, while the A* algorithm is used to find the shortest path between locations. Test results indicate that the routes generated by the Brute Force algorithm are consistent with manual calculations and always yield the optimal distance. In contrast, A* algorithm tests across three scenarios show average travel time deviations of 0.11 seconds in the scenario without obstacles, 0.22 seconds in the scenario with static obstacles, and 9.55 seconds in the scenario with dynamic obstacles. These findings highlight that the presence of dynamic obstacles significantly affects actual travel time, indicating that a path with the lowest cost does not always result in the shortest travel time. Furthermore, the usability test using the GUESS method demonstrates that the game has a high level of user understanding, easy navigation, and strong user confidence, with an average score of 5.12 out of 7. These results suggest that CoolCity provides an effective and engaging educational experience.

ARABIC:

على مشكلة البائع المتنقل (TSP)، لتحسين كفاءة اللاعب في تحديد المسار الأمثل في سيناريو متعدد الأهداف. تُستخدم خوارزمية القوة الغاشمة لتحديد تسلسل زيارات المواقع بأقل مسافة إجمالية، بينما يتم تطبيق خوارزمية (A*) لإيجاد أقصر مسار بين المواقع. تُظهر نتائج الاختبار أن المسار الذي تم إنشاؤه بواسطة خوارزمية القوة الغاشمة يتوافق مع الحسابات اليدوية ويوفر النتائج المثلى من حيث المسافة. وفي الوقت نفسه، أظهر اختبار خوارزمية (A*) مقابل ثلاث عمليات اختبارية متوسط فرق في زمن السفر يبلغ ٠.١١ ثانية في الاختبار بدون عوائق، و٠.٢٢ ثانية مع وجود عوائق مهرجانية، و ٩.٥٥ ثانية في الاختبار مع وجود عوائق إضافية على شكل مواقع مهرجانات وإشارات ضوئية حمراء. تُظهر هذه النتيجة أن وجود العوائق الديناميكية له تأثير كبير على وقت السفر الفعلي، وبالتالي فإن المسار الأقل تكلفة لا يؤدي دائماً إلى أسرع وقت. بالإضافة إلى ذلك، أظهرت نتائج اختبار قابلية الاستخدام باستخدام نهج (GUESS) أن اللعبة تتمتع بمستوى عالٍ من قابلية الفهم وسهولة التصفح وثقة المستخدم، بمتوسط ٥.١٢ درجة على مقياس من ٧. وهذا يشير إلى أن لعبة (CoolCity) توفر بنجاح تجربة لعب جيدة وفعالة في تحقيق أهدافها التعليمية.