Back to search

Institutional Repository of Vilnius University

Žemėlapio reprezentacijos įtaka formuotę išlaikančiam agentų judėjimo planavimui /

Abstract

dc:description

This thesis investigates the impact of map representation on formation-preserving path planning for agent groups in real-time strategy (RTS) game environments. The aim of the work is to empirically evaluate and compare three map representations -- a grid with a modified A* algorithm, Theta* search with any-angle motion and a navigation mesh with funnel post-processing -- and to identify the conditions under which each representation provides the best formation integrity and path quality. An experimental system was developed in which all three representations supply a path to a shared formation-control component, ensuring that the different planning methods are evaluated under identical conditions. The A* algorithm was modified to include a formation squeeze cost, a wall-distance estimate and turn penalties; Theta* was extended with a formation-aware line-of-sight check; the navigation mesh was realised in two variants -- a hard clearance buffer and a soft cost penalty. The formation-execution component, consisting of a wedge formation and three squeeze strategies, is shared across all representations. Experiments were carried out on four environments of varying difficulty with 3, 5 and 7 agents and three movement strategies. All representations achieve a high success rate; the hard and soft navigation-mesh variants produce identical paths, and in dense environments the grid with modified A* yields shorter and more reliable paths than the formation-constrained Theta*. The formation safety constraint dominates the path-planning cost model, so the benefit each representation provides for formation-preserving MAPF is smaller than in single-agent pathfinding. The applicability of each representation is shaped by trade-offs between computation cost and path quality, discussed in detail in the work.

Degree

thesis:*
Grantor dc:publisher
Institutional Repository of Vilnius University
Year dc:date
2026

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Zabitis, Gabrielis Vaclovas,

Rights

dc:rights
Statement dc:rights
  • info:eu-repo/semantics/openAccess
Language dc:language
lit

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
Vilnius University
Base URL
epublications.vu.lt/oai
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Zabitis, Gabrielis Vaclovas,. Žemėlapio reprezentacijos įtaka formuotę išlaikančiam agentų judėjimo planavimui /. Institutional Repository of Vilnius University, 2026. https://repository.vu.lt/VU:ELABAETD308339274&prefLang=en_US