Večagentno iskanje poti v strateških igrah : diplomsko delo

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, računalništvo, univerzitetni študij, diplomske naloge
• Vrsta gradiva: Diplomsko delo
• Tipologija: 2.11 - Diplomsko delo
• Organizacija: FRI - Fakulteta za računalništvo in informatiko
• Založnik: [S. Mihevc]
• Leto izida: 2014
• Št. strani: 46 f.
• PID: 20.500.12556/RUL-69916
• UDK: 004.8(043.2)
• COBISS.SI-ID: 1536203715
• Datum objave v RUL: 10.07.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 games, A* algorithm, multi-agent pathfinding using independence detection and operator decomposition, computer science, diploma