Multi-Target Pathfinding: Evaluating A-star Versus BFS

Sammanfattning

This Bachelor’s thesis provides a comparative analysis of the core algorithms of A-star (A*) and Breadth-First Search (BFS) in multi-target scenarios. Previous research has conducted comparisons of these algorithms in single-target scenarios and improvementst o the algorithms to address their limitations. However, this thesis evaluates the basic versions of A* and BFS for situations where complex implementations are not possible or preferred. The study systematically simulates these algorithms across various scenarios to understand their performance in managing multiple targets. The results show that BFS is generally more effective in scenarios with a small search space and in environments with a higher number of targets due to its ability to locate multiple targets in a single search. Conversely, A* performs better in scenarios where there are fewer targets and the search space is larger, due to its heuristic approach that prioritizes paths which seem more promising. The thesis provides guidelines for developers and researchers to assist in the decision-making process when choosing between these two algorithms depending on specific application requirements.