I have been fiddling with procedural generation for a while now, a few months back I was working on a Procedural City Generator in Unity3D and after publishing a video on youtube, a few guys suggested that it would be a good idea to make a tutorial about this. So this is my first tutorial and I will try to explain my method of generating a city.
Basic theory is as follows, roads need to be generated in such a way that they look somewhat realistic and buildings need to be placed besides the roads. I use a subdivision algorithm for road generation, in essence the first few roads are pre-defined, they influence the overall look of the city. All other roads are generated by division of existing roads. For buildings, I just test a position besides the road to see if it already contains a building, if the new building does not collide with an existing one, the spot is taken and the next road-side position is evaluated.
I have just realized that posting all the code here for each class is really not practical, so I will discuss the generation approach rather than explain the code, line by line.
In Unity, there are some logical structures that need to exist in order to render and keep track of everything. The minimum implementation needs a road generation class, a road renderer class and the building placement class.
For the roads I use RoadPoint, RoadSegment and Intersection classes to represent the RoadNetwork of the city. RoadPoint has just a Vector2 position point and a RoadSegment reference of its parent, so it knows who it belongs to. A RoadSegment consists of two RoadPoint, one for each end of the road that it represents and a few helper functions. And finally an Intersection just has a List of RoadPoint that make that intersection, the list is sorted in circular order when the intersection mesh is created.
This is pretty simple, for each RoadSegment two positions on opposite sides perpendicular to the road are evaluated at increments. Each position is checked to see if it can hold a building, in my implementation I adjust the buildings a little, their width and length before moving on to the next road-side position. It is possible to check if an existing building mesh will fit, the buildings need not be simple boxes. A new Building placement needs to check that it does not intersect a RoadSegment and it needs to check that it does not intersect any other Building, if those conditions are met, a building is placed in the allocated position.
For the roads I use RoadPoint, RoadSegment and Intersection classes to represent the RoadNetwork of the city. RoadPoint has just a Vector2 position point and a RoadSegment reference of its parent, so it knows who it belongs to. A RoadSegment consists of two RoadPoint, one for each end of the road that it represents and a few helper functions. And finally an Intersection just has a List of RoadPoint that make that intersection, the list is sorted in circular order when the intersection mesh is created.
RoadRenderer is pretty simple, it just needs to be able to render an Intersection and a RoadSegment. Since we only have 2 points for a RoadSegment and we need to create a road Quad that has width, I take the perpendicular vector at both RoadPoints to get the new RoadSegment Quad. Applying the texture to a RoadSegment can be done in two ways, you can set your texture tiling to repeat and adjust the repeat vlaue of the texture per Quad, according to the length of the RoadSegment or you can split the segment into many Quads and apply the texture to each one.
Intersections are a bit more tricky, in my prototype I only have intersections that are four points or less, I think the method can be used to create intersections with more points, but I have not tested it. First off we need to find the real points of the road that connect to the intersection, same way as when creating RoadSegment Quads. This will result in 8 points or less, 2 per each RoadPoint that is part of the Intersection, to keep things simple and it works well enough, I just sort the points in circular order and create a Intersection Quad/Mesh from those points. The example below is pretty ugly as the roads are coming in at different angles, but it still works. It's also possible to merge the vertices within some threshold to get a clean Quad, but this might affect your road thickness if using a single Quad as the whole RoadSegment.
Road Network Generation
So now that we have the structures required to represent the city road network, it's time to generate that network. General algorithm is pretty simple, we take an existing RoadSegment and split it somewhere around middle, we create an intersection at the splitting point, and now have two road RoadSegment from the existing one and an Intersection. From that new Intersection we extend a new RoadSegment perpendicular to the old segment. Once we have the new segment, we check if that new segment intersects any other existing segment, if it does, we need to create an Intersection for each intersect and split the intersecting segments to reflect the new connections.
So looking at the picture above, we split the Current Segment somewhere between 45-55% of the segment length. Then we added an Intersection that consists of 3 points, 2 points are from the Current Segment and 1 point is from the New Segment. We then found that the New Segment intersects some arbitrary Existing Segment and now we need to create a new Intersection with 4 points and split both the Existing Segment and the New Segment. The new Intersection will have 4 points, 2 from the New Segment and two the Existing Segment.
That is the base, however there are a few other things that are needed to generate a somewhat realistic structure. First off I assign the RoadSegment a level value, so the blueprint roads that are added are level 0, each time a new RoadSegment is spawned from an existing one its level value is increased. This allows you to have a road hierarchy and it can be used to make the lower level roads thicker, buildings that sit on the lower level roads can be bigger and you can split the RoadSegments based on their level. I split level 0, 1 and 2 twice and then level 3 once in my generation prototype.
Also you can decide, based on some probability if you will just add a three-way intersection when you split the segment or a four way intersection. You should have code to add two perpendicular new segments as this is nearly essential for getting the look right.
Building Placement
This is pretty simple, for each RoadSegment two positions on opposite sides perpendicular to the road are evaluated at increments. Each position is checked to see if it can hold a building, in my implementation I adjust the buildings a little, their width and length before moving on to the next road-side position. It is possible to check if an existing building mesh will fit, the buildings need not be simple boxes. A new Building placement needs to check that it does not intersect a RoadSegment and it needs to check that it does not intersect any other Building, if those conditions are met, a building is placed in the allocated position.
Conclusion
I know this is a high level explanation of the method used so I have included below the download to the Unity3D project files. Do note that the source was not meant to be shared, so there might be some unexplained functions and unexplained code. At the time intention was to make a functional prototype.
Current generation algorithm is about 5-10x faster than the one shown in the youtube video below.
