Pathfinding Simulation
A simple pathfinding simulation utilizing the A* algorithm.
Key Features
- A* pathfinding algorithm
- Probablistic roadmap (PRM)
- 2D collision detection
Description
This was my submission for a class project in CSCI 5611: Animation & Planning in Games. The goal of the project was to create "a simulation of at least one agent navigating through an obstacle filled environment without collision in 2D." I expanded on this by simulating multiple agents at once, and visualizing the simulation in 3D instead of 2D using the Unity game engine.
Discussion
While at first glance the scene appears to be composed of a variety of complex 3D objects, under the hood each of these objects is represented by a basic 2D geometric collision primitive, such as rectangle or a circle. This allows for a simple 2D pathfinding solution to be used to control the motion of the 3D agents (cows).
Note how each piece of geometry appears to have two collision outlines around it: one in red and one in green. The red outlines make up the true 2D collision geometry of the object, while the green outlines make up an approximate Minkowski sum accounting for the cow's collision radius. In this way, cows can be treated as nothing more than points in space when resolving collisions, greatly simplifying pathfinding.
In order to generate walkable paths for the cows to traverse, a probabilistic roadmap (PRM) is generated along with a few hand placed nodes. These nodes are connected to generate a collision-free traversal graph throughout the farm, and then the A* pathfinding algorithm is used to find the shortest path between two points along this graph.
Note that some graph nodes are hand-placed (the blue spheres in the image below) to ensure consistent and interesting pathing through tricky obstacles.
This could have been avoided, however, had a more robust node selection algorithm been used, or had I simply added more points to the PRM.
With collision free paths throughout the farm, the cows are free to wander as they please before they are all called home for the day!
Bonus!
Advanced multi-agent navigation...
Tools Used
Languages: C#
Software: Unity, Blender, Shader Graph