Edmonton Route Finder

Crafted by Bob Bu · Winter 2022

This project is a lightweight client/server route finder for Edmonton: a pygame map client lets you pick a start and end point, and a C++ server returns waypoint coordinates for the shortest path on a road graph built from the Edmonton roads dataset.

Map of Edmonton
# edmonton-roads-2.0.1.txt (excerpt)


      ...
      E,30233210,276310831,Connors Road NW
      E,561041104,276310830,Connors Road NW
      E,225520313,299403402,76 Street North-west
      E,251435422,247105314,Kingsway Avenue NW
      E,247105314,251435422,Kingsway Avenue NW
      E,778537675,304465226,160 Avenue NW
      E,304465239,304465240,91 Street NW
      ...

The client and server communicate through a pair of named pipes, so you can inspect exactly what gets sent and received while keeping the system close to a real routing backend.

The server loads edmonton-roads-2.0.1.txt into a weighted directed graph: each road segment becomes a directed edge, and each vertex stores its latitude and longitude as integers in 100,000-ths of a degree.

lat=⌊105⋅latitude⌋,lon=⌊105⋅longitude⌋. \text{lat}=\lfloor 10^5 \cdot \text{latitude} \rfloor, \quad \text{lon}=\lfloor 10^5 \cdot \text{longitude} \rfloor.

Edge weights use Manhattan distance in this scaled coordinate space.

w(u,v)=∣latu−latv∣+∣lonu−lonv∣. w(u,v)=|\text{lat}_u-\text{lat}_v| + |\text{lon}_u-\text{lon}_v|.

When you click on the map, the selected latitude/longitude usually does not land exactly on a graph vertex, so the server snaps the start and end to the nearest vertices before running Dijkstra.

s=arg⁡min⁡v∈V(∣latq−latv∣+∣lonq−lonv∣). s=\arg\min_{v\in V}\left(|\text{lat}_q-\text{lat}_v|+|\text{lon}_q-\text{lon}_v|\right).

Dijkstra's algorithm computes a shortest-path tree from the snapped start vertex by repeatedly relaxing edges.

dist[v]=min⁡(dist[v], dist[u]+w(u,v)). \mathrm{dist}[v] = \min\left(\mathrm{dist}[v],\ \mathrm{dist}[u] + w(u,v)\right).

The protocol is strictly line-based: the client writes exactly two lines to inpipe\texttt{inpipe} (start then end), and the server streams waypoint lines to outpipe\texttt{outpipe}. The final line is a single E\texttt{E} to signal completion. Closing the client sends Q\texttt{Q} to request shutdown.

Pipe protocol


    # client -> inpipe (exactly two lines per request)
    53.530870 -113.532972
    53.530870 -113.514991


    # server -> outpipe (N waypoint lines, then terminator)
    53.53087 -113.53297
    53.51620 -113.53297
    53.51620 -113.51499
    53.53087 -113.51499
    E

The server must read the request exactly as two newline-terminated lines. In earlier iterations, using fixed-size reads could desynchronize the stream under timing/OS buffering, causing occasional “hangs”. Switching to line-based reads (fgets\texttt{fgets} / parsing) makes the server follow the protocol deterministically.

The project also includes a one-command launcher script that builds the server, waits for FIFO pipes to exist, starts the client, and writes separate server/client logs for debugging.

# recommended: run inside WSL/Linux filesystem (FIFO support)
      chmod +x run.sh
      ./run.sh


      # logs
      #   logs/server.log
      #   logs/client.log

This demonstrates a simple navigation loop, starting with clicks of two points, snapping to the nearest vertices, computing the shortest path, and streaming waypoints back to the client for rendering. Code is available on the corresponding GitHub repository.

University of Alberta · Edmonton, AB, Canada