Harsono, IvanAnanda (2015) Implementasi Real-time Pathfinding menggunakan A* dan Reynolds Steering Obstacle Avoidance pada Permainan Komputer. Sarjana thesis, Universitas Brawijaya.
Abstract
Algoritma A* merupakan algoritma tradisional yang sering digunakan untuk menyelesaikan masalah pathfinding. Algoritma long steering tradisional seperti A* tidak mampu untuk dipakai untuk menyelesaikan permasalahan real-time pathfinding. Real-time Pathfinding merupakan permasalahan pathfinding dalam lingkungan real-time dimana terdapat dynamic obstacles yang menambah kompleksitas permasalahan pathfinding. Dengan A* tradisional dalam lingkungan real-time, jika terdapat halangan dinamis akan dilakukan kalkulasi ulang yang akan memakan banyak sumber daya CPU. Salah satu algoritma short steering yang dapat diterapkan untuk menyelesaikan permasalahan real-time pathfinding adalah Reynolds Steering Obstacle Avoidance yang mampu menghindari adanya tabrakan dengan dynamic obstacles. Oleh karena itu, dalam penelitian ini dilakukan implementasi realtime pathfinding dengan mengintegrasikan antara algoritma long steering A* untuk pathfinding dan algoritma short steering Reynolds Steering Obstacle Avoidance untuk menghindari halangan dinamis sehingga tidak perlu dilakukan kalkulasi jalur ulang untuk mengoptimalkan kinerja dari CPU. Implementasi algoritma dilakukan dengan melakukan simulasi pada peta permainan 3D. Representasi ruang pencarian dari peta permainan yang digunakan berupa regular grids berbentuk persegi. Pada peta akan diletakan halangan dinamis dan statis lalu agen akan berjalan dari titik awal ke titik tujuan yang telah di perhitungkan jalurnya dengan menghindari halangan. Simulasi implementasi algoritma dibedakan menjadi 2 skenario. Simulasi dilakukan dengan game engine Unity versi 4.6. Pengujian panjang jalur pada 30 uji coba dalam skenario 1, menunjukkan bahwa implementasi real-time pathfinding dengan A* dan Reynolds Steering Obstacle Avoidance akan menghasilkan jalur yang lebih panjang dibandingkan dengan penghitungan jalur ulang dengan perbandingan 8:7. Sedangkan untuk pengujian FPS pada 30 uji coba dalam skenario 2, menunjukkan bahwa kinerja CPU pada implementasi real-time pathfinding dengan A* dan Reynolds Steering Obstacle Avoidance akan 2 kali optimal dibandingkan dengan menggunakan penghitungan jalur ulang.
English Abstract
A * algorithm is a traditional algorithms that are often used to solve the problem of pathfinding. Traditional long steering algorithms such as A* is not able to be used to solve real-time pathfinding problems. Real-time pathfinding is a pathfinding problems in real-time environment where there is a dynamic obstacle that increase the complexity of pathfinding. With traditional A* in real-time environment, if there is a dynamic obstacle there will be a recalculation path that will take a lot of CPU resources. One of the short steering algorithms that can be applied to solve real-time problems pathfinding is Reynolds Steering Obstacle Avoidance who was able to avoid any collision with dynamic obstacles. Therefore, in this study implemented a real-time pathfinding algorithm that integrates long steering A* algorithm for pathfinding and short steering Reynolds Steering Obstacle Avoidance algorithm to avoid any collision with dynamic obstacles so it does not need to re-calculate path to optimize the performance of the CPU. The algorithm implemented by doing a simulation on a 3D game map. Representation of the search space of a game map is using a square-shaped regular grids. On the map, will be placed some dynamic and static obstacle then there’s will be an agent that will run from the starting point to a destination point on a path that has been calculated and agen will avoid obstacles. Simulation of algorithm implementations will be divided into 2 scenarios. Simulations done with the game engine Unity version 4.6. Testing the path length in 30 trials in scenario 1, shows that the real-time pathfinding implementation using A* and Reynolds Steering Obstacle Avoidance will result in a longer path than path re-calculation with a ratio of 8:7. As for FPS testing on 30 trials in scenario 2, shows that the performance of the CPU in the real-time pathfinding implementation using A* and Reynolds Steering Obstacle Avoidance would be 2 times more optimal than path re-calculation.
| Item Type: | Thesis (Sarjana) |
|---|---|
| Identification Number: | SKR/FTIK/2015/41/051500789 |
| Subjects: | 000 Computer science, information and general works > 005 Computer programming, programs, data |
| Divisions: | Fakultas Ilmu Komputer > Teknik Informatika |
| Depositing User: | Budi Wahyono Wahyono |
| Date Deposited: | 10 Feb 2015 08:39 |
| Last Modified: | 21 Oct 2021 02:16 |
| URI: | http://repository.ub.ac.id/id/eprint/146476 |
Preview |
Text
Implementasi_Realtime_Pathfinding_menggunakan_A-Star_dan_Reynolds_Steering_Obstacle_Avoidance_pada_Permainan_Komputer.pdf Download (3MB) | Preview |
Actions (login required)
 |
View Item |