Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
A Scalability and Performance Evaluation of Precomputed Flow FieldMaps for Multi-Agent Pathfinding
Blekinge Institute of Technology, Faculty of Computing, Department of Computer Science.
Blekinge Institute of Technology, Faculty of Computing, Department of Computer Science.
2022 (English)Independent thesis Basic level (degree of Bachelor), 10 HE creditsStudent thesis
Abstract [en]

Background. The A* algorithm is a well-established pathfinding technique frequently used in video game development. However, a disadvantage of the A* algorithm is that it becomes computationally inefficient and impractical to utilize whenthousands of agents demand an optimal path. A solution to mitigate this issue isthe use of the flow field algorithm. This algorithm employs a goal-based pathfindingstrategy, which allows for the movement of a large number of units through the useof a single direction map (flow field map) that indicates the direction units must take to progress toward their goal.

Objectives. The main objective of this study is to examine the performance and scalability of precomputed flow field maps with regard to execution time and memory utilization, with the objective of determining the feasibility of precomputed maps as an alternative to maps generated at runtime. Furthermore, the study implements and investigates compression techniques to minimize the memory footprint of precomputed flow field maps.

Methods. The study adopts an experimental research design to assess the performance of the two implementations under various conditions of grid size and movement system. Performance evaluation is accomplished through the measurement and comparison of execution time and memory consumption. Additionally, a directional accuracy test is performed to quantify the potential loss of accuracy in the vectors stored in the precomputed flow field maps.

Results. The precomputed flow field maps provide constant access time, with a time complexity of O(1), regardless of the grid size and the type of movement system. The memory usage of these maps increases significantly with the growth of the grid size. A doubling of the grid size leads to a more than fifteen-fold increase in memory usage. The techniques proposed in the study significantly reduced the memory footprint by a factor of thirty-two and by a factor of eight, depending on the selected movement system. The average loss in accuracy was approximately 0.35 degrees for the proposed any-angle compression technique.

Conclusions. The use of precomputed flow field maps has limitations, including being limited to static environments and having high memory requirements. On the other hand, they provide constant access time for pathfinding information, independent of the grid dimensions, movement system, and the number of target nodes. Whether precomputed flow field maps are better than the traditional runtime implementation depends on the intended use.

Place, publisher, year, edition, pages
2022. , p. 38
Keywords [en]
pathfinding, flow field, multi-agent, precomputed, dijkstra maps
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:bth-24302OAI: oai:DiVA.org:bth-24302DiVA, id: diva2:1739049
Subject / course
DV1478 Bachelor Thesis in Computer Science
Educational program
DVGSP Game Programming
Supervisors
Examiners
Available from: 2023-05-03 Created: 2023-02-23 Last updated: 2023-05-03Bibliographically approved

Open Access in DiVA

A Scalability and Performance Evaluation of Precomputed Flow FieldMaps for Multi-Agent Pathfinding(194 kB)115 downloads
File information
File name FULLTEXT02.pdfFile size 194 kBChecksum SHA-512
c5afe63cb3ed35b59980723c142279a50d7025cf8ea4cf0d4a8c37a1342d9fb0f856e716e8d78fd83d6ebee682cd3d54834bf9ddaf80271b187121611cb2c916
Type fulltextMimetype application/pdf

By organisation
Department of Computer Science
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 115 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 340 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf