Pathfinding

This page is part of the Multi Agent System (MAS) documentation.
It contains a documentation of the pathfinding algorithm used in the Multi Agent System.
For an overview of all MAS-related pages, see the MAS main page.

During the simulation each agent receives target coordinates (see at_x and at_y). Each agent must then find a path from its current position to its target using the visibility graph. This is accomplished using the A*-algorithm which is a well-known fast pathfinding algorithm (click ​here for a thorough explanation). For this, the agent's current position and its target are added to the visibility graph, the shortest path between these two points is calculated using A*, the navigation points are shifted outward from the obstacle corner to a random position along a "gate" (see corner_gate_start and corner_gate_width) to avoid collisions with obstacles or other agents, pathfinding is run again with each successive pair of navigation points along the path to avoid intersection of path sections with obstacles resulting from the outward shift, finally, the resulting path is stored in the agent object as a series of intermittent targets. Each agent calculates the direction toward its next intermittent target during each agent time step. It will accelerate toward those coordinates. Once the agent has come close enough (dist_to_int_target) to them, the next intermittent target is chosen. When the final target is reached, the agent is deleted. Recalculation of an agent's path occurs when the agent has deviated too far (max_dist_from_path) from its current path or the path counter has reached its maximum and the target is not yet reached. This can occur because for the purpose of conservation of memory each agent can store a maximum of 15 intermittent targets.