Route
Master
Vehicles finding their way across a real road network, with nothing but the standard library behind it.
- Search
- A* with a straight-line heuristic
- Neighbours
- Spatial hash written from scratch
- Data
- OpenStreetMap road geometry
- Dependencies
- None. Standard library only
Built for college, in Python, with a rule I set myself: no external libraries. Everything runs on the standard library, including the pathfinding, the spatial indexing and the drawing. That is also why it looks the way it does. Tkinter is not going to win any design awards, and I decided early that I would rather have the algorithms be the interesting part than spend the time making it pretty.
Pathfinding across a city is cheap the first time. It gets expensive when hundreds of vehicles each need a fresh route every time something changes, and the plain neighbour search starts eating the whole frame. Bucketing the network into a spatial hash turned that scan into a lookup, which is what made it possible to run the simulation and watch it at the same time.