June 4, 2015 By: David Tse
This week I worked on a new road growth system that uses the old road/city system as population maps. This system takes a few source roads usually at city locations and grows them according to a set of rules in two general categories called global goals and local constraints.
The idea of this core system is based on a paper by Parish & Mueller titled “Procedural modelling of cities”. While the core idea of local constraints and global goals is based on the paper, it's somewhat vague on some of the rules they use so I have been writing most of these rules from scratch. As always if you want more frequent updates you can follow me on twitter
were I'm posting what I accomplish every day.
Road Growth - Global Goals
Every new road is always trying to find centers of population. This is the core of what they try to do with their existence. Road segments shoot a series of Rays in possible new directions searching for this population while also constantly evaluating the elevation in the area picking directions that will result in the least amount of elevation change and most population. This least elevation change priority results in roads that try to stay as flat as possible making the inevitable terrain smoothing under buildings and roads easier.
Early test of growth system with only a few source roads. Not all cities are connected, but you get the idea.
In addition to the population and least elevation change the roads will look for water in its nearby area so when their quest for population takes them near the ocean they actively try to stay along the coasts the way highways are like to do. Because they prioritize water once they get close to it they constantly try to create roads in the ocean, when these are rotated and fixed by the local constraints they end up closely bordering the coast. More on local constraints later.
Source population map that roads follow. Generated using the old roads and city locations you saw in the screenshots last week. You can also notice there are some initial test roads following some of the population lines.
One of the most important aspects of the global goals is deciding when and how to split off a new road segment. The primary factor when deciding when there should be a split is if there is population. If there is a large amount of population in an area the probability of splitting a new road goes up dramatically so road growth for these highways generally happens naturally. When a road reaches a city where the population is generally much higher more highways will spawn and connect to other cities.
There are other factors based on type of city being generated (New York block layout, Paris circular layout, ect.) when creating city roads, but when creating these large highways connecting cities there is no concept of a "city shape". City roads will be done in a second pass using the highways as input.
Road Growth - Local Constraints
Once the global goals think that they have a good new segment they add it to a pending list. Before that segment can be added to the world it has to go through a number of tests called local constraints. These are to make sure roads don't go where they are not allowed to go. These constraints will do everything they possibly can to move and rotate around the proposed segments until they can legally fit in the world. If it tries a certain number of times and can't find a valid solution or a way to connect it to existing roads it just deletes it.
Another screenshot of road growth with more cites connected using different parameters. Ocean avoidance is turned off and there are no anti-parallel local constraints meaning roads get way to close. The split rate is also a little too high here creating a few too many roads for high level highways
The primary local constraint is dealing with all the existing roads already in the world. When a new segment is being checked first we see if there is another road or an existing intersection within a certain radius from the new segment's road end. If it finds something it will try to snap to that point. There is also a basic intersection test so if it overlaps another segment it will be trimmed down to create a new intersection.
The final other road based constraint is to test a circle at the tip of the road and not allow roads to be too close together and maintain a certain parallel distance between roads by rotating them. If it can't maintain the separation or correctly connect to the other roads it's dead.
This is a screenshot of these chunks with really large dimensions so you can see them clearly. In reality they are a 100th that size if not smaller.
To do these road to road intersections in any sort of reasonable time every road must be added to a grid of world chunks. The best thing about the regular gird of chunks is that to do intersections I just get the indices for the chunk this road is in and do intersections with the roads in that chunk. This lookup is insanely fast so the dimensions of these chunks can be very very small making these intersections really really fast.
Screenshot from when I was testing a minimum distance allowed before a new split could occur and 100% split rate otherwise. This creates a cool looking grid, but the point is to show the ocean avoidance. Notice how the roads generally follow the coast. It's not perfect because of the chaos and huge number of tiny roads, but you can get the idea.
If a segment survives the perils of road constraints then it has to go through the landscape constraints. We don't want roads climbing up really steep elevations, going into water, or riding on top of mountains. So every segment samples the underlying terrain height data and checks its elevation to see what type of land its on and the change from its previous spot. If it encounters something it doesn't like it will try its hardest to rotate away. It it can't do it after so long it's killed. Like I mentioned before this coupled with the desire to move into the water will result in highways naturally traveling along the coast which you can see in the above screenshot.
There will be many more rules added to these global goals and local constraints to make the roads and cities very robust. This system is easily extensible and I'm really happy with it. It also has the really awesome added benefit of being able to watch these roads grow in real time. When you create a new world in game you will be able to watch the world slowly create itself! I'll probably do a video showing the growth in real time pretty soon because it's so damn cool!
Next week I'll be using this growth system and the highways grown to branch off the smaller city roads based on the population maps. If you have any questions or want any more information on how all this works just let me know and don't forget you can follow me on Twitter
if you want daily updates and screenshots about what I'm working on!