Institutional Repository of Vilnius University
Žemėlapio reprezentacijos įtaka formuotę išlaikančiam agentų judėjimo planavimui /
Abstract
dc:descriptionThis 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.*- Repository record dc:identifier
- https://repository.vu.lt/VU:ELABAETD308339274&prefLang=en_US