• 3D

  • Coding a procedural city generator

I've had a very ambitious idea in mind for some time now. Ambitious enough that I wouldn't fault anyone for saying it's outright impossible, even though I'd disagree with that idea. It will likely be doable in future Godot versions, but since it's a very distant plan we may as well have Godot 4.0 by the time I'd dream of having a demo released.

In a nutshell, what I wish is to create detailed functional cities; Worlds of the depth and quality as those of the Grand Theft Auto >= IV series. Realistic cities full of details and objects, card driving down roads while respecting traffic rules, pedestrians walking on sidewalks and interacting with their surroundings, and much more. My project actually plans to go further than the detail any GTA game has ever offered: It would allow boarding and walking inside subway / skytram trains, entering random people's apartments, exploring full sewer systems located under roads, etc. Different presets of cities, people, vehicles, items, etc would be defined and possible to mix (present day, futuristic, etc).

There is however a catch... and this is where the crazy part comes in: I also want all this to be procedurally generated, not designed by the mapper as in other games that have this level of detail. When starting a new world, a script will draw the roads, manage the terrain, place the buildings... all using a selection of objects and road segments defining that world. The plan is for cities and characters to always be unique, with players being able to save and share cites by copying the generated file containing them (likely in json format). To add insult to injury, I'm not planning to settle for making those cities flat either: I'll want not only roads that go up and down, but tunnels and bridges that traverse bumpy terrain as well. Crazy I know :)

I already have some ideas in mind about how I'm going to achieve this, based on a similar city generator I once created for the Minetest project (a Minecraft clone). The system would rely on using a 3D gridmap, which by default will be empty and is filled by the script itself... the tiles contain terrain and road pieces, on top of which buildings and other objects would be placed. The rough idea of how this would work is something among the following lines:

  • The script starts drawing the roads in 2D space, each road defined as a multitude of cubic segments: The straight I segment, an L segment to steer the road, an X intersection segment, a T intersection segment, a dead end segment, as well as conversion segments to connect different types of road to one another... for height there will be a special straight segment which goes up or down. The script simply starts from one point then draws a random number of segments in a given direction, before deciding whether to steer the road or fork it into an intersection. I don't know if 45* segments could also be supported, as this would add far too much complexity to both the pathing algorithm and the number of road segments needed overall.
  • Once a flat version of the road system has been drawn, the system needs to determine the height of each segment. Some straight segments are next converted into the sloped segments mentioned above, which connect upper and lower segments on the grid. Roads will ideally take one of two choices when faced with a height difference: Either go up or down, either continue forward as a tunnel or a bridge. Terrain segments surrounding roads will also have to respect this height, spawning flat planes or slopes or corners accordingly. I imagine the most reliable way is using a perlin noise map but that remains to be seen.
  • Now that we have a 3D road and terrain tilemap, we need to know which spaces are free in between roads and what buildings we can spawn there. In every empty patch of terrain, we place a randomly rotated building that can properly fit in between the roads. We also need to place misc objects on road segments themselves, such as street lights and trash cans not to mention vehicle / pedestrian spawners... this will be done by assigning a list of items with probabilities to each segment.

I don't yet know how far this idea can get me. I have alternatively thought of using the new terrain node once it's finally in (I hear Godot 3.2 is the next target) then seeing if I can simply generate the road system in 2D and somehow project it across the terrain surface vertically. What I want is still pushing the limits by far however... namely since cars and peds must know how to navigate those road systems too (trains will need a curve straight out). Performance would be managed by using a smart draw distance limit mixed with model LOD, parts of the world can be (de)spawned in grid chunks similarly to Minecraft.

I'm posting this thread as a discussion rather than a question, since there are a ton of parallel questions that emerge for an idea as big as this one. For the scope of this topic, the primary one remains how I can (ab)use Godot to generate procedural cities using road segments in the most efficient way. I'd like to know if there are any base suggestions on how I'd get started on such a thing, perhaps even some existing demos if anyone has made any! What are your thoughts on this?

Procedural cities are indeed doable in Godot if these videos are to go by.

The buildings can be generated too

The author didn't provide any links to his code though (and this doesn't cover traffic, pedestrians, and more organic layouts), but it would be a start.

That's very useful, thank you! Indeed it's a shame they didn't provide the code, it could have been useful if I was able to understand it. Even so it looks like it only covered half of the story, since it generates one type of road across a flat plane... multiple roads that can also go up and down without causing gaps in the ground will be a far more complex issue.

Generating building structures is not something I plan to do, especially since some of them will have an explorable interior plus other model and texture details placed across it. But it was interesting to see how that was achieved too.

Cars and pedestrians will be their own concern once automatic placement of roads and buildings are in order: They're objects / scenes that will have their own scripts and detect other items spawned in the world to interact with. The only thing the generated city needs to make sure of is that both collisions as well as navmeshes connect properly between tiles, so that every moving item can navigate between various segments unhindered. Trains will be the only issue I can see, as they'll have to follow a fixed path across rails on the segments... I'm not sure to what extent a thin navmesh can convince them to use a straight line without any wobble being noticeable.

@MirceaKitsune, take a look at my Free Roam Racer project. My idea is very much like yours, and I have straight roads and corners and T-intersections already (including sloped straights).

@Zireael said: @MirceaKitsune, take a look at my Free Roam Racer project. My idea is very much like yours, and I have straight roads and corners and T-intersections already (including sloped straights).

That's a great example and very promising project you did there, nice work! I tried it briefly but the map seems to be the same whenever I load up the game, thus I assume procedural city generation isn't there just yet.

I did a lot of city generation for last years. Your ideas are mostly correct. First you generate your terrain heightmap. Next you generate population density map based on your terrain and some basic rules. Next you generate roadmap starting from density map local maximums. Also you can generate supplemental maps for growth rules and generate full road map based on growth rules and density map. Also it is useful to build probability map for growth depending on location. Having full road graph you generate lots from it (closed polygons). Using density map and probability map you build lots split rules map. Having polygon list you split it according to generated rules split map. Generate building size map based on density map and growth probability map. Using split contours you generate buildings, using building size map. To prevent repeatition of buildings, generate variation maps to make sure there is no similar buildings too close. Using generated building model, generate each building interior.

On any stage use optimization, so to not generate forever. It is possible to generate city parts and then reuse them in combinations.

Read Parish & Mueller for fundamentals, and articles on building facade generation and building interior generation.

However as you generate visuals you will end up with navigation problems, as Godot navigation is not mature enough for such project. So you will need to add changes to C++ code to add needed functions, like runtime navmesh generation

For roads it is possible to use CSG polygon swept over a Path. Also other city stuff can be generated this way.

@slapin said: For roads it is possible to use CSG polygon swept over a Path. Also other city stuff can be generated this way.

I thought about using a curve to draw the roads, which I understand becomes possible in Godot 3.1 and would be far easier from some perspectives. But there are quite a few issues with that approach which render it almost impossible:

  • First of all, how do I even spawn a series of bezier curves that generate full circuits resembling a road system? Roads are typically straight and only steer occasionally, so I'd need a smart algorithm to know how to generate realistic patterns.
  • How do you create intersections? The curve can loop one road segment, but how will it seamlessly create a cross segment where two or more roads meet? Will there be a polygon blending mechanism smart enough to do that? Remember roads also have sidewalks, while some will also have green spaces dividing them in the middle.
  • Generic objects will also need to be placed at each intersection, including stop signs and pedestrian crossings. I'd also need the system to loop other items across road curve, such as fence railings that cars can bump out of the ground.
  • How do you project the road onto a terrain without parts of it either floating of being buried into the ground? I understand the terrain node may finally be coming in Godot 3.2, but no news of a way to project curves on its surface.
  • For things like tunnels and subway stations, the system will also need to know how to cut holes in the terrain (including collisions and navmesh) while the navigation system must allow characters to know how to travel inside. In fact how do I even generate occasional gaps across a curve based tunnel, that can spawn sewer manholes or subway entrances in alignment with terrain at the surface? Also how would I make a surface road occasionally go in and out of the terrain and switch between road and tunnel, ideally where it detects that terrain is not leveled?
  • Once the road system was generated, how would the code know to automatically place buildings in areas not touched by roads? It would need to detect all empty patches left across the terrain surface and calculate what fits inside.
  1. it is road map generation logic. I explained it in my above post. You need probability map for your road. Your probabilities define the road patterns. Like p_turn - probability of turn, etc. You define the set of probabilities which define your road and use that to generate all roadmap nodes. The algorithm would be simple.
    • a) define a set of points which are considered "axiom". They are connected by road segments already. This defines the start.
    • b) for each of this point, according to your density map and probability map you grow additional points according to growth rules. You need to define your max and min distance. You pass through your existing road segments and according to growth probability which you calculate using density map and growth probability map, you add new segment.
    • basically you need to write function which makes new points from existing point then discard bad ones,. Maintain your segments - if segment intersects another road segment, add the point at intersection. If new point gets too close to another road segment, add intersection. I suggest maintaining grid alignment with road point coordinates. Check your angles and discard new segments which produce bad intersection angles.
  2. Depends on your fantasy. I did generate mesh intersections using 2D roadmap. It is not hard. I think curent CSG tools in Godot might make the process easier, too. Your problems are valid, but solvable. Just draw on paper and see. You need to generate a set of contours then "extrude" them and generate lots of triangles. If you need help with that I have some Urho3D-based C++ code for that.
  3. Objec placement can be done using curves, maps and good old random with subsequent consttraint check.
  4. You can use heightmap height values. You can construct your terrain node even now, use height map and splat mapping. You can get your height from height map.
  5. Navigation system needs to know about offmesh connections and allow to add them. I'd look at Detour for that. Basically Navigation is only serious Godot limitation here now. Everything else can be done now with stock stuff and GDScript. Maybe a bit slow (could require adding KDTree and Octree custom C++ code for faster processing with geometry). For tunnels - use texture hole mask for your terrain, just pass your road through the hole and build mesh tube alongside road curve for tunnel, checking heightmap height above/below road. Very easy.
  6. As I explained above, you need to build lots from roads. Read Parish & Mueller, also you can use some of shortcut approaches. Actually this is very easy part. The problem is that some roads will not produce closed polygons, so you need to find how to close them manually. For later you can use some heuristics. The grid alignment should help to make it faster.

Hope you don't mind that I tweaked the structure of your post a bit.

No, I don't mind, that looks better.

An example of how to close polygons for all roads is to create convex hull for your entire road map and connect all your points with exactly 1 segment to the closest segment of the hull (if new segment crosses some other segments, add intersections). For growth rules selection it is easy to use texture atlases. And for other maps too.

The issue with intersections is whether Godot knows how to amalgamate a 2D polygonal blueprint as a curve divides or crosses over itself or another curve. For any serious detail to be possible, sidewalks must be put into the geometry of the road so that they bump upward on the sides... same for the division in the middle. When an intersection is formed, the sidewalks must melt into each other in a round pattern... meanwhile the road divider (middle sidewalk) must stop. There needs to be some rule to tell Godot how to combine polygons when two curves meet... to my knowledge this is not a planned feature, and I'm not sure how important it to convince the developers to put it on their list for Godot >= 3.2.

Keep in mind that I actually don't want all curves to be closed polygons: City roads often have dead ends, thus I'm okay with some roads ending abruptly as long as it's not too frequent. The only issue here is I once again want a different pattern at the curve end, so the road mesh doesn't just stop there but you have the sidewalk loop around the end.

As far as mapping the road to the terrain goes, that might not be hard to script an accurate approximation: For each point of the curve, detect the closest vertice on the terrain horizontally (X and Z axes), then copy its vertical position (Y axis).

As for navigation, that would be the second part that comes later. As far as the generator is concerned, roads and terrain just need a consistent navmesh that objects can understand how to navigate across. Programming the AI to actually use it properly will be where the nightmare begins, as I have no idea yet how to teach cars to drive on the correct side of the road let alone respect traffic lanes and only cross from one line to the other occasionally.

I hacked-up simple PoC generator. https://github.com/slapin/godot-city-roadmap

What is missing: 1. Intersection checks. 2. Probability maps. Density map is aded as function though. 3. Convex hull generation 4. Lot generation

Will add this in following days. Will need to add some spatial partitioning structures to make it work faster though.

Updated, now looks better:

only "grid" growth rule is implemented, will add other rules and rule map later.

About your doubts about intersection meshes - please add some pictures, I don't understand them. You just generate separate intersection mesh with whatever geometry you like.

All roads being closed polygons helps a lot. You can have fake "roads" which you do not turn into actual roads, but these help with lot generation.

Currently only proper navigation option for this scenario is DetourCrowd, for both cars and people.

That's pretty neat! Though it doesn't seem to generate any round roads, for mine I'd like to have occasional roundness in places... also more diagonal roads and uneven spaces, no city is made of fixed squares like that. This does however show how easily this part can be achieved which helps a lot!

And my question is how I generate that intersection mesh. Godot 3.1 will have a system to define a 2D pattern which is extruded along a curve node. But how does the curve first detect when it intersects with either itself or another curve, then second know how to melt that 2D pattern into a "T" or "X" intersection (respecting both geometry and texturing)?