Need a large scale city generator

[MirceaKitsune]

I've reached a point where I'm stuck and out of ideas with one of my projects. It's part of something meant to be a surprise for Minetest, but seeing I won't be able to do it on my own I'll need help. There will be more to come if this gets solved.

As you probably know, I made the Structure I/O & Mapgen mod. Its aim was not just an easy way of importing and exporting structures (like WorldEdit), but naturally generating towns and cities. Several village mods were created before, so the concept isn't new. My project aimed to take it further and do something on a larger scale, not just spawn small groups of houses. The objective is generating huge complex cities... consisting of large buildings with full indoor detail, interactive items and electronics (such as Technic mod), and roads with interconnected sewers as well as functional transit systems (subway and sky-tram). The cities would stretch over distances of 500 x 500 nodes, some containing skyscrapers hundreds of nodes tall... all with as much of the layout randomized as possible. There's more to the overall plan than that, but this is as far as the spawning system is concerned.

This might sound impossible at a first, but I can say for sure it's not. I stress tested schematics and noticed they can handle buildings this large perfectly well. The problem is that despite the work I put into my mod, I cannot breach the limitations needed to get to this point. It generates roadless villages of respectable size, but that's about it. This is the biggest two towns I got a screenshot of... both of them added barely represent the size a small city is intended to have:

[spoiler][/spoiler]

None of the other village mods seem to work either. There's only one which also generates roads, Nore's Experimental Mapgen. But despite being a mapgen of its own, its roads consist of nodes placed in a straight line.

The streets I want must be structures as well... so they can contain buried sewer systems, street lights, etc. I'll also need houses to spawn right next to roads, so electrical wires touch and power plants can deliver electricity through cables hidden under sidewalks (Technic mod). Cities at surface level are not the only thing I'm aiming for: The system needs the ability to spawn large underground towns (temples) and I'm thinking of sky cities as well. Both buildings and roads must be schematics (mts files) and compatibility is aimed at mapgen v7.

In essence, I'd need a mod capable of spawning different road types (defined as intersection + straight segment + curve), possibly in multiple passes so bridges / sewers / sky-tram lines are layered separately. Then properly jigsawing buildings of various sizes in areas between those roads, placing them at random rotations with all buildings touching each other. Each road and building can be buried by X nodes, so houses can have basements and roads may have tunnels, while their surface level goes where it should.

I'd like to know if anyone is willing to help make this possible. I only need aid with the city generation system, since I can create the structures and new items myself. One can base it off my Structures mod, if the code is clear and can be improved. In either case, please let me know.

[paramat]

I like your ambitious plans. I am intending to tackle massive generative architecture myself using schematics to place multiple copies of apartments or types of rooms ... waiting for 0.4.8 stable for the schematics.
Have you seen Sokomine's village mod? that has roads.
If you need large flat areas for cities this will do it https://forum.minetest.net/viewtopic.php?id=6959 let me know if you need it customised in some way.

[Sokomine]

Your plan is truely ambitious.

There is something which does build this kind of cities...it's called "human beeing" and comes in form of players. Some are good builders, and some even manage to construct large towns, usually in cooperation with other players. For some of us, that is the purpose of the game. Reproducing that with an algorithm may be a very huge challange. I can understand that you find that extremly intresting (it is!) and I'm curious how far you'll get. At least you'll learn more about the concepts behind towns - things that most likely will not be obvious to other players and will give new insight.

Even if you want your town to be automaticly generated from schematics, you'll need plenty of buildings to start with. Your Structures I/O mod comes with far too few buildings. My villages mod has more diffrent types of houses (small and larger farms in this case) - but even that would be nothing close to what you'd need. For a start, join Mauvebics server and talk to LadyMcBeth. She's created buildings for Mauvebics MTCities mod that would fit nicely into some types of town. For a true town, though, her assortment of buildings has too few appartment-houses and other living space.

Types of buildings is another major part of the problem. For my villages mod, life was relatively simple - villages are collections of farms, with a church, a pub/inn/restaurant, and - in historical times - a forge and a mill. There may be variations to that (i.e. a second church, capella, more pubs, shops, today: gas station, for larger ones a school for the first grades), but in general it's simple. Towns are diffrent. They tend to have more structure and buildings devoted to certain activities (town halls, government buildings, police station, fire station, shopping centers, schools, high schools, theaters, cinemas, public transport system, and so on). Some of these buildings occour only once or are spread out and occour once in each segment (Stadtteil) of the town.

My villages mod may create a village of 1000m or longer by changing a single parameter (road length is configurable) - but it will always remain a village, with street structure and structure/distribution of houses beeing that of a (road) village. Even if you where to feed it with houses that fit into a town. Even Nores experimental mapgen creates more complex street structures - but as that mod uses very tiny huts, what it in effect creates are villages that appear archic. Which is not bad - it may very well be perfect for survival and singleplayer maps as a place to distribute mobs without having them stand around in the middle of nowhere.

If you want to be able to spawn a huge town, understand towns. Find out how the road system they have can be generated. While doing research for my villages, some people suggested using L-System for the roads. There was even an article claiming that such a method can create road-systems very similar to that of real towns. The street map may look considerably diffrent depending on the type of towns you base your system on. Most likely you'll prefer the system used in the USA over that of a historically grown european town because the later one will have a more chaotic street system, with roads going crosswise and not fitting well to the cubic style of Minetest.

My villages are planned out before they're spawned. It all starts with a road. Each road consists of three parts: right side (row of houses rotated facing the street), street (consisting of schematics) and left side (more houses, again facing the street, and rotated by 180 degree compared to the other side). Ocasionally it branches off and adds a side-road that's rotated by 90 or 270 degree and planned out the same way as the original road (except that that one's not allowed to branch off). The central village place is a bit more tricky because it has to form a place with the houses at the right distance to the road and facing the right direction. Buildings can be partly buried (cellars/diffrent offsets while saving the building).

Start with the planning of the road system - perhaps output it to a .png file or something - and then proceed to planning the area between the roads. Instead of house rows that where sufficient for my villages, you'll need city blocks. And you need to decide which direction a house at the corner of such a block ought to face.

Also don't forget the option to replace materials in a house to let it look diffrently. My villages mod takes the same set of replacements for all houses in a village, but for a town, each house might be diffrent. Mauvebic was the first to introduce this concept, and PilzAdam added it to the place_schematics code.

[MirceaKitsune]

Didn't know about Sokomine's Villages mod. I cloned the GIT version and looked through the code. No point in considering it however... it's too different from what I need. Mostly because the structures are strongly hard coded (I need something flexible allowing multiple city definitions) and the road pattern is too simple (a main road with others branching to the side).

In all mods and all cases, the primary problem is one: Roads. Generating them properly, then correctly adding structures of different sizes in the spaces between, is a nightmare. It's possible, but would take a genius days to code them correctly. And this is why:

I want each city to have multiple types of roads. Each type would consist of 4 objects: Intersection (X shape), half-intersection (T shape), turn (L shape), segment (I shape). When a city is generated, the code generates an even grid of points, and randomly connect two of them via shortest path multiple times. When 4 roads meet the X shape is used, when 3 meet it's T shape, when 2 meet the L shape... where T and L must be rotated to address the proper connections. Each connection uses a given road type, influenced by its probability value. When different types of roads intersect, the code needs to decide which road's X / T / L shape to use... a priority value would do here. This means that each road's segment must connect to each other road's intersections, and all road objects must be square (X and Z equal)... but that's the artist's concern.

Best bet is adding this to my Structures mod, since the other village mods have too many things which are way different. But I'd suffer a brain attack before even getting close to the formulas needed for roads like this. I know Minetest has experienced programmers however, and maybe one of them would like to see these cities too. If someone could write the theoretical formula for the roads and post the Lua file, I can pipe that to my functions, and we could get started. So again, the question is who's willing.

[MirceaKitsune]

@ Sokomine: That is a correct observation. Such cities would indeed need a lot of different buildings, and several road types too. That's an artistic problem however, and not something I'll have a problem with. The only issue is the code for the road layout and properly spawning structures in place. The buildings don't need to be grouped by any criteria as far as I'm concerned (like schools next to hospitals) as long as they take up the optimal amount of space and are squeezed then rotated correctly. Road patterns can be random maths too.

The purpose is often to build your own places, and that's part of what makes large MineCraft servers fun for years. But I also want to do something else, aimed at a different type of world. And for this I need natural cities and towns.

[Sokomine]

What kind of road layout do you aim for? You need to know that in advance. At least to a degree. If you allow everything (diagonal raods, roads at diffrent angles etc.), then it gets much more complicated. The road system gives your town a structure and helps people finding their way. There may be main roads and sideroads. If it's all one chaotic mass, people will loose orientation very soon.

The buildings don't need to be grouped by any criteria as far as I'm concerned (like schools next to hospitals) as long as they take up the optimal amount of space and are squeezed then rotated correctly.

It's not exactly grouping that counts but more or less amount of buildings of a certain type and to some degree their placement. Imagine a town consisting almost entirely out of schools - with hardly any inhabitants. Or with 5 fire stations clustered at the far end of the town. The sheer size of your town may help a bit here - the amount of buildings may be high enough to rely on random (i.e. probability for spawning a school: 0.01; probability for appartment house: 0.2 and so on).

"The optimal amount of space" - dangerous. That can mean anything from trivial (=all buildings have the same size) to not solvable without a heuristic approach. Again, having lots of buildings to choose from may help. If there's e.g. 5x7 m left at the end of the road, you'd just pick one building out of your large library that has the size of 5x7 - while keeping all the other buildings up to that edge-building mostly random selections. Still requires some assumptions about minimal size for such a house at the corner of two streets. And requires a really huge library of houses.

[jenova99sephiros]

If you think this plan and would be realized one day, I am moving too

[jenova99sephiros]

..!?

[aleksix]

Roads-What about a "plan" for you buildings? It will make intersections easier.Make roads modular and add them after the buildings,searching for additional space. Like this:
BBBB I BBB
BBBB I I I I
BBBB I BBB
I I I I I I I I
I

Where B - building, I-road
As you can see,there are 2 intersections:T junction and X crossing, though computer doesn't know about it.
When you actually start building this,just "look" at the plan. So, if there is a road at the top, make the first section connecting with it. Then,if there is a road to the left,add left curve,etc. This way different parts of the road will overlap and create nice roads.
Sure,this method is slow, but I suppose you don't want to generate lots of giant cities?

BTW,thought about creating something like this too.

[Neon]

Some ideas to get you started in a direction:
- Try googling for "procedural city generator"
- I found this link when following up on my raytracing city-generator days.
- In particular, this technical paper is likely to help you

[jin_xi]

i made a turtle mod which can generate structures you define with algorithms. its good at doing stuff at arbitraty angles, but can do grid aligned stuff too, here is a pic of a generated city block (note that the houses have no interiour walls)



another thing i did is an experimental road generating mod, it uses pathfinding to find nodes, bresenham to fill up the space between nodes and again turtle to finally create the road.

[MirceaKitsune]

Like I said, the mod doesn't need a specific road plan. Roads can be random and go in any direction... as long as their quantity is correct, and the space between two roads is always large enough to fit a few buildings. The city's settings would specify how many roads of each type to generate, and the minimal distance a road should have from another road. But the pattern itself can be any random math that generates a maze.

The links might be useful, I'll look at them if all else fails. It's unlikely they have the specific information I'm looking for however, which I could adapt to Lua and to usage with Minetest schematics.

[jin_xi]

maybe a importer for dwarf fortress worlds would be a solution...

[MirceaKitsune]

Ok. After a few hours of staring at the walls and thinking, and an hour of trying to put the bases in Lua, I might be onto something. I thought of a simpler system for road patterns that could generate a pretty OK road structure:

It starts with a point (tm), randomly placed within the area of the city. That point branches into several other points, which themselves branch further and so on. The number of overall junctions is determined by that road's probability setting. Each point forks into at least 2 directions and at most 3 (since the 4th is where it originated from so it would go back). The length of each fork is random within a minimum and maximum value, but a fork may not be larger than the previous one to avoid self-intersection in case of a + 270* turn.

I haven't scripted it yet, and no doubt it won't be easy... but it's the simplest method I came up with so far. Will see how it goes.

[Nore]

For that, you should look at the mg village generator, and modify it for bigger cities, since it works that way...

EDIT: tweaking some parameters...

[MirceaKitsune]

For that, you should look at the mg village generator, and modify it for bigger cities, since it works that way...

EDIT: tweaking some parameters...
http://nore.mesecons.net/screenshot_2956648574.png

So the roads are minetest schematics too, and you can add X / T / L intersections and joints for each? Are multiple road types supported also, and multiple types of villages too? What about underground and sky towns? Are the cities hard-coded also, or can you define your own towns?

Either way, I'm not sure about using a mapgen for this. Does it have all features in v7, such as biomes defined in Lua? I'll look into it as well.

[Nore]

The roads are schematics, but they are generated on the fly, and only gravel+air above. However, you could change that if you wanted to. As for using the normal mapgen, it doesn't matter since the building generation is completely separated from the spawning, so you could change the spawning code, (it is first chosen which buildings are where, then they are spawned).

[MirceaKitsune]

It's been a full and hard day of coding. But at the end of this day, I can finally post the first screenshots of the road pattern generator, in its primitive and extremely buggy state. At this moment it's simply capable of generating the correct road pattern, and filling it with properly rotated road segments. Next I need to do the intersection corners, and generate bounding boxes for buildings to avoid roads by.

[spoiler]

[/spoiler]

[Neon]

It looks like the cavegen is eating your roads. I suggest a disclaimer to turn those off (unless you can generate the caves *before* you generate your city)

[paramat]

Good work, this must be generated 'on generated chunk'? Cavegen always puts holes through my ongen structures. Perhaps you will be able to combine it with flatten mod.

[MirceaKitsune]

Ah... that's why the holes appear? I thought all mapgen actions are taken before on_generate runs. Any reason why that isn't fixed?

[paramat]

Cavegen ongen griefing occurs mostly in horizontal or vertical slabs near chunk boundaries, it was useful in slabworld mod as it would carve organic looking spacedocks in the walls.

EDIT The devs do know of this bug.

[MirceaKitsune]

Two more days of intensive work on my Structures mod. This time the progress is greater than ever! I entirely rewrote parts of the mapgen system, including the formula used to order and place structures. Roads and buildings may spawn together now, with buildings optimized to use space even more efficiently. Overall, the hard part has been done.

Latest code is still far from usable, and full of bugs which will take more days to solve. Also, despite the functions being relatively simple and optimized, this is pretty slow. A spawning town freezes the server for almost 10 seconds on my machine. It's not the placement of buildings (schematics are almost instant), but the code that calculates where everything goes before the mod edits anything.

The new code can be found on the Structure mod's Github page, under the "roads" branch. DO NOT use it on a world you don't want to break... the mod is currently unpredictable and makes quite a mess. Screenshots of towns with roads:

[spoiler]





[/spoiler]

[rubenwardy]

Nice

Will the building be selected randomly, or will you use a CBD/inner/outer/suburbs format?

[MirceaKitsune]

Nice

Will the building be selected randomly, or will you use a CBD/inner/outer/suburbs format?

Randomly. Maybe sometime I'll make a grouping system, but it's not a priority now.

[paramat]

Good work.

[MirceaKitsune]

The last days since my last post here were dedicated to fixing and perfecting the road and building collision patterns, and all other bugs and bad codes that remained. It was an intensive week, but I'm getting closer to finishing the remaining issues at last.

Roads are finally capable of avoiding self intersection, and buildings do a much better job at fitting between them. I also made changes that should improve performance, although the code will still be a bit slow and require an average machine.

Here's some screenshots from my moments debugging and a few towns at this stage:

[spoiler]







[/spoiler]

[paramat]

Good stuff, what mapgen is that last screenshot, you have a river!

[Neon]

Will you have the ability to customize what the sidewalk and roadbed are made up of? This is for those who don't like cobble or have some mod that has better nodes for those (i.e. streets mod)

[MirceaKitsune]

Alright. I initially thought that after the last fixes are done within, my mod will be capable of spawning huge cities without any problem. Unfortunately, closer calculations and obvious factors indicate that the current system wouldn't be capable of such a thing. There's only one option... and it requires heavily refractoring the base of the mapgen system. Here's the exact story:

The existing system begins with detecting the area of a group (a rectangle), currently about 100 nodes with default town. It analyzes that zone's terrain roughness, height, etc. then clears the space structures will take up while filling the floor down to the lowest node. Separately, calculations take place to determine the road pattern, where each building and road segment goes, etc... and at the end it generates a schematic, in the form of a Lua table. The main function then takes those schematics and imports the actual structures at the positions and rotations stored inside, over the floor and empty space of that area.

This is a decent way and worked acceptably so far. But it has the worst limitation: It cannot spawn large cities. Even a town as big as 200 nodes will barely spawn with it. Namely because the entire area needs to be explored and loaded, and no player has a draw distance that large or the ability to explore such huge locations in a few seconds.

In a discussion on IRC, ShadowNinja lit a spark in my mind: What if we had on_generated only spawn the pieces of city inside its bounds? This would allow cities to be built progressively as the player explores, allowing any size comfortably. But there are several problems with switching to such a structure, and those are the two worst ones:

1 - How do we know the average height, where to clear the area and where to build the floor? Before any node is edited, we need to have a precise list of where each structure goes, since we can't sketch the city as the player explores (especially now with roads). We can however have a list of all structures, and have on_generate place them progressively... but we don't know how the area prior to that.

2 - How do we know where a city should spawn? Currently, on_generated randomly triggers a city, and the area is centered to its middle... eg: (minp.x + maxp.x) / 2. If progressive generation was to exist, we'd need to know the city's "rectangle" before any piece of world generates yet. To make matters worse, I want my mod to keep using the "trigger node" system, which makes cities spawn only where precise nodes exist.

So I need your help and advice on this one. How would I place the rectangular area a city would take up somewhere I haven't explored yet? And how would I know the average height by which to cut and fill if I don't have any clue about the terrain there? If a way is found, I can have on_generate spawn only the structures it addresses from each city.

As for the other posts:

Good stuff, what mapgen is that last screenshot, you have a river!

v7.

Will you have the ability to customize what the sidewalk and roadbed are made up of? This is for those who don't like cobble or have some mod that has better nodes for those (i.e. streets mod)

Each type of street is a series of schematics, so yes... that will be fully possible too.