Večagentno iskanje poti v strateških igrah

MIHEVC, SIMON (avtor), Bratko, Ivan (mentor)

V tej diplomski nalogi sem se ukvarjal z izdelavo, primerjavo in izboljšanjem algoritmov za večagentno iskanje poti na domeni, ki je tipična za realno časovne strateške igre. Implementiral in primerjal sem algoritma Večagentno iskanje poti z uporabo hodnika in Večagentno iskanje poti z detekcijo neodvisnosti in dekompozicijo operatorjev. Algoritma nista ohranjala enotnosti skupine in sta potrebovala preveč časa za iskanje poti. Pomanjkljivosti algoritmov sem v precejšnji meri odpravil.

• Jezik: Slovenski jezik
• Ključne besede: Večagentno iskanje poti, realno časovne strateške igre, algoritem A*, večagentno iskanje poti z uporabo hodnika, večagentno iskanje poti z detekcijo neodvisnosti in dekompozicijo operatorjev
• Vrsta gradiva: Diplomsko delo
• Organizacija: FRI - Fakulteta za računalništvo in informatiko
• Leto izida: 2015
• PID: 20.500.12556/RUL-30651
• Datum objave v RUL: 19.03.2015

Sekundarni jezik

• Jezik: Angleški jezik
• Naslov: Multiagent path-finding in strategic games

Izvleček

In this thesis I worked on creating, comparing and improving algorithms for multi-agent path planning on a domain typical for real-time strategy games. I implemented and compared Multiagent pathfinding using clearance and Multiagent pathfinding using independence detection and operator decomposition. I discovered that they had problems maintaining group compactness and took too long to calculate the path. I considerably improved the efficiency of both algorithms.

• Ključne besede: Multi-agent pathfinding, real-time strategy gamess, A* algorithm, multi-agent pathfinding using clearance, multi-agent pathfinding using independence detection and operator decomposition