Path finding and collision avoidance in a multi-agent system

Abstract

In games where agents navigate through 30 environments scripting is usually used for pre-set movements. However in games coming from the real-time strategy genre, due to the large number of agents present in the virtual world, this would usually be too laborious and generally unsuccessful. In these sort of games, dynamic behaviour, movement in our case, should be carried out at run-time using path finding algorithms. This has already been done and proved to be successful. In this project we plan to make use of these algorithms in scenarios where the maps consist of multiple layers, for example a bridge over a road. Another possible problem could be that of multiple agents navigating through this terrain which need to be aware of their surroundings to have the least possible amount of collisions. Using the navigation mesh as the search space representation, one can abstract such overlapping terrain and avoid using a complex representation. Using the industry standard algorithm for path finding, namely the A* Path Finding algorithm, combined with the aforementioned search space, one can further optimize the path finding algorithm which will lead to an increase in efficiency of the algorithm. On finding a path between two designated positions in the environment, each agent will navigate between such points using Steering Behaviours. These agents will have forces applied to them which will ultimately alter their velocities and heading accordingly, hence allowing them to avoid collisions between each other and keeping away from areas which are not navigable. The main contribution of this project is a system which shows that agents are able to navigate around the area using the least distance possible while using the shortest path extracted from the path finding algorithm, as well as avoiding collisions between neighbouring agents while navigating through the environment. Testing and evaluation of the artefact shows that agents are doing their utmost in a crowded area to push through their neighbouring agents and at the same time trying to evade walls.