Real-world navigation based on open source spatial data and pathfinding algorithms.

• Description
• Features
• Presentation
• Architecture
• Technology Stack
• Prerequisites
• Setup
• License

The project provides the graphical interface to visualize and simulate the execution process of various pathfinding algorithms on a street map. To ensure the most accurate and up-to-date results, it operates on spatial data provided by the OpenStreetMap community. The use of microservice architecture enables the entire application to be scalable, reliable and fault-tolerant.

• OSM file parser
• OSM street network graph
• Implementation and visualization of the following single-source shortest path (SSSP) algorithms:
  • BFS
  • Bidirectional BFS
  • Bellman-Ford
  • Dijkstra
  • Bidirectional Dijkstra
  • A*
  • Bidirectional A*
• Implementation and visualization of the following pathfinding algorithms (their results might be suboptimal):
  • DFS
  • Greedy Best First Search
  • Bidirectional Greedy Best First Search
• Geocoding - converting addresses to coordinates
• Reverse Geocoding - converting coordinates to addresses
• Data distribution pipeline in a microservice architecture
• Interactive visualization on street and satellite maps

In the process of designing the separation of responsibility, a strategic pattern proposed by Eric Evans in the DDD methodology called Bounded Context was used. Contexts divide a complex domain into smaller subdomains while encapsulating internal models and business logic. The application was divided into the following contexts (represented as services)

• Geocoding - converts addresses to coordinates
• Reverse Geocoding - converts coordinates to addresses
• Pathfinding - generates summary statistics and data to visualize the execution of pathfinding algorithms
• OSM Data Processor - parses and loads the OSM data

The services are deployed as independent docker containers. Their API is provided to customers through the Spring Cloud Gateway.

By combining the Producer API and the Kafka Connect API, Kafka can propagate data across a distributed system. Each service has a separate Kafka Connect API configuration, responsible for adapting data to internal schemas and data persistence.

The project consists of two main modules - services and libraries. Libraries offer universal functionality decoupled from services and infrastructure. The pathfinder library provide pathfinding, convex hull and edge weight calculation algorithms, and the implementation of graph data structure. On the other hand, the parser library exports API to load and extract data from OSM files.

One of the goals of separating domain components into separate libraries (based on interfaces) was to simplify their testability. Using interfaces instead of classes allows providing particular implementations for testing purposes (e.g. an in-memory version of an exporter) , thus reducing the need to create mocks and stubs for specific test scenarios.

• Typescript
• React
• Leaflet
• React Query
• Material-UI
• React Testing Library
• Jest
• React Hook Form

• Java
• Spring
• Hibernate
• Groovy
• Spock
• Testcontainers
• Gradle

• Docker
• Kafka
• Kafka Connect
• MongoDB
• Elasticsearch

• Github Actions
• Codecov

Install jdk16 and gradle.

You should be able to run the following commands:

Install docker and docker-compose.

You should be able to run the following commands:

Install node, npm and yarn.

You should be able to run the following commands:

Visit geofabrik website and download any .osm.bzip file. Rename the downloaded file to osm-data.osm.bz2 and move it to the data directory.

Wait for the export process to finish (osm-data-processor should shut itself down). This process should take approximately 3-5 min per 100Mb of compressed map data.

Open localhost in your browser.

This project is licensed under the MIT License - see the LICENSE.md file for details.