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

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, računalništvo, univerzitetni študij, diplomske naloge
• Work type: Undergraduate thesis
• Typology: 2.11 - Undergraduate Thesis
• Organization: FRI - Faculty of Computer and Information Science
• Publisher: S. Mihevc
• Year: 2015
• Number of pages: 46 f.
• PID: 20.500.12556/RUL-30651
• ISSN: 1536203715
• COBISS.SI-ID: 1536203715
• 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, computer science, diploma