Skip to content

README.md

Latest commit

 

History

History
72 lines (58 loc) · 3.38 KB

README.md

File metadata and controls

72 lines (58 loc) · 3.38 KB
Raw

Real-World Map Routing Engine

A high-performance backend routing engine built in Node.js that dynamically parses and constructs weighted geographic graphs from real-world OpenStreetMap (OSM) data.

This project was built to explore advanced graph algorithms, spatial data structures, and the complexities of parsing live geographic data streams for real-time pathfinding.

🚀 Key Features

1. Dynamic Graph Construction

  • Overpass API Integration: Dynamically fetches road network geometries directly from the OpenStreetMap Overpass API based on user-defined geographic bounding boxes.
  • Weighted Edges: Constructs an in-memory graph respecting real-world constraints: one-way streets, intersection nodes, and speed-based edge costs mapped across 7 different highway classifications.

2. Pathfinding Algorithms

Implements and benchmarks 5 distinct pathfinding algorithms using a custom Binary MinHeap data structure for O(log n) priority queue operations:

  • Dijkstra's Algorithm: Standard shortest-path traversal.
  • A (A-Star) Search*: Utilizes Haversine geographic distance as a heuristic to prioritize promising nodes, significantly reducing the search space.
  • Bidirectional Dijkstra: Runs simultaneous searches from the origin and destination to drastically reduce explored node counts on long-distance routes.
  • Breadth-First Search (BFS) & Depth-First Search (DFS)

3. Spatial Indexing

  • Grid Index: Implements a 2D spatial grid index (bucket granularity of 0.01°) to map arbitrary GPS coordinates to the nearest valid road network node in amortized O(1) time.
  • Tile Caching: Features a 0.05° tile-based geographic caching system to prevent redundant third-party API calls when users pan across adjacent map areas.

4. Algorithm Benchmarking API

  • Features a side-by-side comparison endpoint (/api/route-compare) that executes two selected algorithms simultaneously on the same graph instance.
  • Returns comprehensive analytics including path distance, execution time, and total explored node count for performance benchmarking.

🛠️ Architecture

├── src/
│   ├── algorithms/
│   │   ├── astar.js            # A* Search with Haversine heuristic
│   │   ├── dijkstra.js         # Standard & Bidirectional Dijkstra
│   │   ├── bfs.js              # Breadth-First Search
│   │   └── dfs.js              # Depth-First Search
│   ├── structures/
│   │   ├── graph.js            # Adjacency list graph implementation
│   │   ├── minheap.js          # Binary MinHeap priority queue
│   │   └── spatialIndex.js     # 2D Grid for coordinate resolution
│   └── overpass.js             # OSM API client and data parser
├── server.js                   # Express.js REST API
└── package.json

💻 Usage

Installation:

npm install

Run the Server:

npm start

Example API Request (Compare Algorithms):

curl -X POST http://localhost:3000/api/route-compare \
  -H "Content-Type: application/json" \
  -d '{
    "startLat": 40.7128,
    "startLon": -74.0060,
    "endLat": 40.7580,
    "endLon": -73.9855,
    "algo1": "astar",
    "algo2": "dijkstra"
  }'

This returns the geometric path alongside benchmark metrics, demonstrating why A* explores significantly fewer nodes than standard Dijkstra for geographic routing.