2D Physics and Pathfinding

Solo 8 weeks C++ (Custom Engine)

Assignment

This project was a school assignment focused on two core topics: AI pathfinding and 2D physics. We were provided with a custom engine that handled rendering, but had to build everything else from scratch. The main requirements were to construct 3D meshes from 2D point data, generate a navigation mesh, create a graph structure from the navmesh, implement A* pathfinding, and develop a 2D physics system. The goal was to combine both systems into a cohesive demo.

Pathfinding

For the pathfinding implementation, I started by generating a navigation mesh from 2D points that were provided, while clipping the navmesh with the 2d geometry that was provided. Once I had the navmesh, I created a graph representation where each node corresponded to a navigable region.

I implemented the A* algorithm to find optimal paths through this graph. The challenge was making the pathfinding work smoothly with the physics system, as agents needed to both follow paths and respond to physical collisions with each other and the environment. When implementing the agents I also implemented The funnel algorithm for the pathfinding and a clipping offset for going around corners smoothly.

Physics

The physics system was built from the ground up. I implemented collision detection for both circles and polygons, using a grid-based spatial partitioning structure to accelerate broad-phase collision detection. This optimization was crucial for handling scenes with many objects efficiently. For the narrow-phase, I implemented circle-to-circle and polygon-to-polygon collision detection and resolution. The polygon collision system wasn’t perfect, but it was functional enough for the project’s needs.

Result

The final demo brings both systems together. Agents use A* pathfinding to navigate toward the player from a semi-top-down perspective while simultaneously responding to physics collisions. When agents encounter each other or walls, the physics system takes over, creating realistic interactions while they continue trying to follow their paths. This combination of pathfinding and physics creates emergent behavior where agents must navigate around both static obstacles and other moving agents.