This is a step in a larger project for detailed city generation within Unreal Engine. It encompasses the generation of road patterns within a boundary following a rule set.
Tiers: Roads are generated in tiers (normally highway, major, minor). The first tier starts at a random position on the boundary. All other tiers use trace seeds generated by the previous tier.
Tracing: The road is generated by greedily tracing the major and minor gradients of a continuous function on the x,y plane describing terrain height. At an interval a road trace marks its current location and places seeds for tracing the gradient (perpendicular to the current road) in either direction. Spacing between roads is managed by casting an intersection test perpendicular to the current trace and aborting the trace if another parallel road is to close. Road traces stop either when intersecting a parallel road (which they then merge with) or after a certain length. In either case a seed is placed at the end to continue the road later.
Hills: If the gradient is over a threshold, it skews the traces so as to create a sweeping hill climbing pattern. It also adjusts the threshold for parallel to maintain clean spacing.
Because the vertex count is so high (hundreds of thousands to millions) it uses several kd-trees with nearest neighbor and range search.
Currently the project takes ~30 seconds to generate a layout. Calculating the complexity of this is hard as its so dependent on spacing rules. The complexity of a trace however is log(n)*k where k is the trace iteration count.
Next in this project is to simplify the graph by merging paths. Then find the borders of all planar regions in the graph. Unless I decide to implement water/bridges… So many options