Overview
This project applies graph algorithms to optimize movement in a spaceship map inspired by Among Us. Using a given set of room coordinates and connectivity rules, we implemented Minimum Spanning Tree (MST) and Traveling Salesperson Problem (TSP) solutions to determine the most efficient routes.
Graph-Based Pathfinding
The problem is modeled as a graph, where rooms are nodes and possible movements are edges. We explored three key pathfinding strategies:
- MST (Minimum Spanning Tree) – Finds the shortest vent network connecting all rooms.
- FASTTSP (Heuristic TSP) – Computes a near-optimal route for a crewmate visiting all rooms.
- OPTTSP (Exact TSP) – Uses Branch & Bound to compute the absolute shortest route.
Algorithmic Implementations
The project required efficient use of graph traversal algorithms, heuristics, and distance calculations to compute paths.
- MST Construction – Implemented using Prim’s and Kruskal’s algorithms, determining the most efficient vent system.
- Heuristic TSP – Applied nearest neighbor heuristics to find fast but approximate routes.
- Optimal TSP – Implemented Branch and Bound for guaranteed shortest routes.
Key Takeaways
- Optimized movement paths using MST and TSP algorithms.
- Explored heuristic vs exact solutions for pathfinding efficiency.
- Balanced speed and accuracy in different routing scenarios.