Building PathCraft: An Open-Source Routing Engine in Go

Source: Dev.to

Introduction

When I started building PathCraft, I had a simple goal: create a routing engine that I could actually understand, extend, and deploy without vendor lock‑in. What began as an experimental side project has evolved into a modular, multimodal routing engine that handles everything from pedestrian navigation to public‑transit routing.

In this post, I’ll share the journey of building PathCraft—architectural decisions, the algorithms powering it, and the lessons learned along the way.

What is PathCraft?

PathCraft is an experimental walking and transit routing engine written in Go. It’s designed to be:

• A reusable Go library (SDK) that developers can embed in their applications
• A CLI application for quick routing queries
• An HTTP server for production deployments
• An embeddable engine for integration into larger systems

The core philosophy? Correctness first, performance second. Too many routing engines sacrifice readability and maintainability for marginal performance gains. PathCraft takes a different approach.

Why Go?

Architecture

One of the most important decisions was the architecture. I initially considered a Hexagonal (Ports and Adapters) architecture, but ultimately chose a Modular Monolith approach.

• For a project focused on algorithmic correctness and rapid iteration, Hexagonal architecture introduces unnecessary overhead.
• The indirection layers and abstraction boundaries, while valuable for large enterprise systems, would slow down development without providing proportional benefits.

Module Layout

/internal                → Private core logic
  /graph                → Graph data structures
  /geo                  → Geographic calculations
  /routing              → A*, RAPTOR algorithms
  /osm                  → OpenStreetMap parsing
  /gtfs                 → Transit data parsing

/pkg/pathcraft/engine   → Public API (the only thing users import)
/cmd/pathcraft          → CLI entrypoint
/web                    → Visualization tools

This structure maintains low coupling and high cohesion while keeping the system easy to reason about. The dependency flow is strict: core logic never depends on infrastructure (HTTP, CLI, file I/O).

Walking Router – A*

At the heart of PathCraft’s walking router is the A* algorithm. Here’s a simplified view of how it works:

• A* combines the best of Dijkstra’s algorithm (guaranteed shortest path) with heuristic‑guided search (faster exploration).
• For each node we calculate

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

• g(n) – actual cost from start to node n

• h(n) – estimated cost from n to the goal (our heuristic)

• For geographic routing we use the Haversine formula to compute the great‑circle distance between two points on Earth. This gives an admissible heuristic—it never overestimates the actual distance, guaranteeing optimality.

The algorithm maintains an open set as a priority queue, always exploring the most promising node first. Go’s container/heap package provides the foundation, with a custom pqItem struct tracking node IDs and priorities.

Transit Router – RAPTOR

For public transit we implemented the RAPTOR (Round‑Based Public Transit Optimized Router) algorithm. Unlike traditional graph‑based approaches, RAPTOR works directly on timetable data.

• Rounds – each round represents one additional transit leg (transfer)
• Route Scanning – for each marked stop, scan all routes serving that stop
• Transfer Processing – after route scanning, process foot‑path transfers
• Pareto Optimality – track both arrival time and number of transfers

Why RAPTOR?

Public API

The Engine struct in /pkg/pathcraft/engine serves as the public API—the only package external users should import.

type Engine struct {
    graph     *graph.Graph
    gtfsIndex *gtfs.StopTimeIndex
}

// Core methods
func (e *Engine) Route(req RouteRequest) (RouteResult, error)
func (e *Engine) LoadOSM(path string) error
func (e *Engine) LoadGTFS(stopTimesPath, tripsPath string) error

The engine orchestrates; it doesn’t compute. This separation keeps HTTP/CLI concerns from leaking into the algorithms.

Handling GTFS Time Formats

A tricky challenge was dealing with GTFS times that exceed 24:00:00 to represent service past midnight. For example, a trip departing at 25:30:00 means 1:30 AM the next day.

We built a custom time package in /internal/time that handles this edge case transparently, keeping the rest of the codebase clean.

Development Principles

1. Pure Functions – Routing algorithms are pure. Given the same graph and query, they always produce the same result (no hidden state, randomness, or side effects).
2. Comprehensive Tests – Every routing algorithm has thorough tests, especially for edge cases. Bugs in routing logic can be subtle and hard to detect.
3. Interface Discipline – Introduce interfaces only when there’s a concrete need, not based on hypothetical future requirements.
4. Self‑Documenting Code – Code should explain what it does; comments are reserved for why certain decisions were made.

OSM Parsing and Graph Construction

(The original content was truncated here; the following is a brief placeholder to indicate the next section.)

OSM parsing converts raw OpenStreetMap data into a walkable graph, handling node deduplication, edge creation, and attribute extraction (e.g., footway tags, surface types). The resulting graph feeds directly into the A* router, enabling fast, accurate pedestrian routing.

Quick Start

• A* routing for walking
• CLI interface
• GeoJSON export
• HTTP server mode with /route and /health endpoints
• GTFS ingestion
• RAPTOR algorithm implementation
• Basic map visualization
• Walk + Transit integration
• Time‑dependent routing
• Performance benchmarking
• Graph contraction for faster queries
• Caching strategies
• WASM/JavaScript bindings
• gRPC API
• Plugin system

The first version of PathCraft was embarrassingly simple. That was intentional – get something working, then improve it.

A good Makefile, consistent formatting, and automated testing pay dividends. Every hour spent on tooling saves days of debugging later.

Writing documentation forces you to think through your design. If you can’t explain it simply, you probably don’t understand it.