GPS Pathfinder

1. Project Idea

The GPS Pathfinder project is an intelligent route planning system designed specifically for navigation across Egyptian cities. The system implements the A* (A-Star) search algorithm to find the shortest path between any two cities in Egypt, considering real-world road distances.

Key Features:

Shortest path calculation between 28 Egyptian cities

Interactive graphical user interface (GUI) with map visualization

Real-time path highlighting on the map

Distance calculation and estimated travel time

Coverage of major regions: Delta, Sinai, Upper Egypt, and Western Desert

2. Algorithm Used

A* (A-Star) Search Algorithm

A* is an informed search algorithm that finds the optimal path from a start node to a goal node. It combines the advantages of Dijkstra's algorithm (guarantees shortest path) with the efficiency of Greedy Best-First Search (uses heuristics).

Algorithm Formula:

f(n) = g(n) + h(n)

Where:

f(n) = Total estimated cost of path through node n

g(n) = Actual cost from start to node n (cumulative distance)

h(n) = Heuristic estimated cost from node n to goal (Haversine distance)

Heuristic Function:

The project uses the Haversine formula to calculate the great-circle distance between two points on Earth given their latitude and longitude coordinates. This provides an admissible heuristic that never overestimates the actual distance, ensuring optimal path finding.

3. System Design

Architecture Overview:

The system follows a modular architecture with clear separation of concerns:

Components:

1. Data Layer (map_data.py):

egypt_cities: Graph representation with cities as nodes and roads as weighted edges

city_coords: Geographic coordinates (latitude, longitude) for heuristic calculation

city_positions: Canvas coordinates for GUI visualization

2. Algorithm Layer (astar.py):

heuristic(): Calculates Haversine distance between two cities

astar(): Implements A* search with priority queue (heapq)

3. Presentation Layer (gui.py):

GPSPathfinderApp: Main application class using tkinter

City selection dropdowns

Results display panel

Interactive map canvas with scrolling capability

Data Structures:

Graph: Dictionary of dictionaries (adjacency list representation)

Priority Queue: Python heapq for efficient node selection

Closed Set: Set for O(1) visited node lookup

Path Reconstruction: Dictionary to track parent nodes