Večagentno iskanje poti v strateških igrah

MIHEVC, SIMON (author), 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.

• Language: Slovenian
• Keywords: 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
• Work type: Undergraduate thesis
• Organization: FRI - Faculty of Computer and Information Science
• Year: 2015
• PID: 20.500.12556/RUL-30651
• Publication date in RUL: 19.03.2015

Secondary language

• Language: English
• Title: Multiagent path-finding in strategic games

Abstract

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.

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