Coin-Constrained Path Finder is an interactive GUI application where users select a starting city, a destination, and a total number of available coins. Each path between cities has two associated values: distance and coin cost. We use the A* algorithm to find the shortest feasible path while respecting the coin constraint. The GUI visualizes the algorithm in real time, displays the paths explored, and highlights the optimal route generated by the AI.
- Application entry point that initializes the graph, creates the GUI window, and starts the application.
- Creates the interactive game interface with a dual-panel layout.
- Handles user input, click-to-move gameplay, real-time visualization of the graph, and displays comparisons between user paths and AI-generated optimal solutions.
- Defines the City class representing individual nodes in the graph.
- Each city stores its name, heuristic value, and connections to neighboring cities with their associated distance and coin costs.
- Manages the overall graph structure, storing all cities and their positions.
- Provides methods to add cities, create connections, and includes factory functions to generate pre-configured graph layouts with different strategic trade-offs, taking into consideration distance and coin constraints.
- Implements the A* search algorithm with coin constraints.
- Finds the optimal path between nodes while respecting the coin budget, tracking visited nodes and explored paths for visualization purposes.
- Python
- Tkinter for building the graphical user interface
◌ Graphs (nodes with names, heuristics, and weighted connections)
◌ A* search algorithm adapted with coin constraints
◌ Priority queues (via heapq) for efficient node selection
- Clone the project
git clone https://github.com/jdc88/Coin-Constrained-Path-Finder- Run
python3 main.py⟡ Check Demo here
Developed by Sama Ahmed, Josephine Choi, Karla Ramirez