Procedural City Generation

A while ago I posted some interesting papers about procedural city generation on my intro-thread. Now that this forum exists, this is a better place for them.

I'll get the ball rolling:
The second paper offers what I consider a more compelling model for city generation -- it works at a higher level, caring less about the exact placement of specific buildings and more about the patterns in land use. We could give the cities of different civilizations some real character by changing up the generation rules a bit to reflect their culture/whatever. Different researches could create noticeable long-term change to the patterns of growth of cities, as they do in the real world. And most importantly, the changes wouldn't have to be aesthetic either.

What else could we do? How could we do it?
Discuss.

Maybe the buildings should generate on a hexagonal grid and bigger buildings would use more hexes. It would make sense therefore that the bigger buildings would generate more rarely. Also, in terms of buildings, will they be random or picked from a library of models. Maybe we could pull a spore and use user-created buildings? I unfortunately can't view the links for whatever reason but I will keep the ball rolling nonetheless.

That's certainly one easy way to limit large buildings, but since it won't be enough on its own, we can use some of the techniques in the second paper to generate a realistic distribution of building types, and then we populate each area with buildings of various sizes, there being fewer with large footprints by random chance, as you say.

About the grid: the modern city (and many city-building games) rely on a a rectilinear grid (or many at different angles over different sections of the city), since right-angle intersections are the best balance between being able to go straight and seeing the traffic on either side of you. Changing the underlying topology will result in some interesting effects on the structure of the city. For example, a hex grid using edges as roads will have a lot of turns, 3-way intersections, and roundabouts; and building shapes are probably much more likely to be organic, since having a hexagon-based footprint means you can make smooth curves while wasting much less ground space. Using strings of hexes as the roads would make it easier to apply some grids every now and then (good, because it doesn't force you to use grids, but doesn't prevent them either), but would still afford organic shape very easily.

So, with those thoughts I think I agree with using hex grids.

As for building generation; I hope we'll be able to make them procedurally (and indeed, once we have procedural organism generation I think a lot of the technical details can be transferred). How we'll do it is an open question though.

Oh shoot they might be behind a paywall -- no wait that can't be right, I can access them from home.

I don't know about using a hex grid, because you would not have any straight roads (past one hex) and no right angle intersections, such as T-intersections and 4-ways.

Is it not possible to have the procedural city generation create cities in an open method, such as the picture below:

Spoiler:

Wow, Nick. That would make for amazing looking cities! But how would this fit with the 'customization' feel of the game? Wouldn't it be hard for you to edit and arrange roads/buildings with such a complicated layout as this?

I assume this is for generating cities for the AI, or for when you automate your cities to build things themselves. Of course when you take control there will not be any procedural mechanics needed, because it will play like a city-builder at that point.

I'd prefer the procedural city planner always be available to do the grunt work of road placement and so on; leaving you to designate new districts, which then slowly get developed, and to plop your own buildings down on auto-generated lots whenever you want a particular building somewhere instead of what the generator will place. The algorithms used in the papers I referenced (the second of which, I think, is used in your picture, Nick) both allow you to place landmarks (ie, your own buildings) and plan out roads, leaving the generator to fill the gaps in between.

You have a good point on hex grids though -- it would be most flexible not to use grid alignments at all, but to work with raw geometry. However, I'm not sure what the best way to store all that data would be. We couldn't just store generator metadata and regenerate the city on the fly, as the stuff the player builds could have major effects on the development direction the city takes. At worst, though, it would just be a mass of oriented points for buildings and a network for the roads. Cities might get pretty big, however. 

Nick, it seems RabiesPig can't read any of the papers I'm linking, can you?

I'm not sure I like the idea of semi-automation for city building. The plan is that players either automate the city, so that it builds things on its own, or they control it entirely, because they an still afford to do so and want to be able to meticulously control what goes where, basically like one of the Anno Games, or Grand Ages Rome.

Example:

However, as there civilization increases in size, and their cities become larger, the incentive will be to automate cities, or simply queue buildings for the city to build but the city chooses how and where to build them. In this way it starts to play our more like a game of Civilization.

Example:

So basically there will be a gradual transition from a directly controlled city-builder, to more automated, computer controlled with player supervision city building.

I've been able to read all the papers you have linked to so far.

Has it yet been discussed how we are actually supposed to construct buildings? Or is it not priority at the moment.

Oh oops, I thought I opened that question on here already, guess I didn't. I'd certainly be interested in talking about procedurally generating buildings.

Maybe you should construct the city hall and it will generate the other buildings judging on parts/textures you use.

Good idea. How? The how is what this discussion's about, if all we were talking about is what we should do then this thread would be in game design and also not exist.

When in doubt I usually look towards machine learning methods, despite all their difficulties. Is there anything better we could use to pattern-match?

I don't really code so I can't add much to the discussion in that way. Just suggesting really.

The Tech Editor is used to design buildings, and unless we find a fancy way of making the AI design their own buildings or procedurally generate them, they will just use presets.

NickTheNick wrote:

I don't know about using a hex grid, because you would not have any straight roads (past one hex) and no right angle intersections, such as T-intersections and 4-ways.

Is it not possible to have the procedural city generation create cities in an open method, such as the picture below:

Spoiler:

May I just say that program is beautiful?

You may, but this thread has been derailed enough.

Yesh, shadly thish forum doeshn't have nearly enough technical people, so any technical thread ish likely to get derailed into nontechnical dishcushion; cuz otherwishe there wouldn't be any dishcushion going on.

Ok so I've got some thoughts on city generation, hope they are helpful. I had a quick look at the papers you posted, they were interesting.


First it might be wise to establish size classes for the buildings. So taking a base unit (meter, foot, whatever).

Small: 10-25 Square units.
Medium: 25-50 Square units
Large: 50-150 Square units
Gigantic: 150-300 Square units.


Ok so to go through the algorithm.

1. Designate central vertex
2. create 4 city blocks around it
3. start filling these blocks with buildings (and subdividing as necessary)
4. if there isn't enough room to add the next building create a new block

only display roads that are touching occupied buildings.

So to unpack this a bit.

1. The city centre is a point on the map, every building wants to be close to this center.

2. a city block is 4 vertices which are points connected by main road. This will make a tetrahedron. The first 4 blocks will have the center vertex as one of their corners.

3. If you put a gigantic building in a block it fills it, if you put a large one in the block is cut in two and there is room for another large building. If you put a medium in you need half of a half. And a small one needs half of that.

So a block can have 8 small, 4 medium, 2 large or 1 gigantic. Or any reasonable combination. So 1 large, 1 medium and 2 small. Or 4 small and 2 medium. etc.

4. When trying to add a building if there is no room the game designates a new block (as close to the center as it can) and puts your building in there.


Bonus extra! Buildings could have their effectiveness decrease the further they are from the center. So you have to choose which buildings you want to be the most important. Do you want a cathedral right in the middle or a spaceport?

If you want to overwrite a current block you can force purchase what is there and put your new building in. Then all the old buildings you built over get rebuilt by the algorithm above. Of course you have to pay for this rebuilding.

.

what do you think?

.


Here are some illustrative images. This is what the computer would have designated.



This is what the player would see



As you can tell I am no graphic designer

tjwhale wrote:

First it might be wise to establish size classes for the buildings. So taking a base unit (meter, foot, whatever).

Small: 10-25 Square units.
Medium: 25-50 Square units
Large: 50-150 Square units
Gigantic: 150-300 Square units.

We might need to raise the bar for large buildings to account for more size, if the AI builds especially large airports, seaports, spaceports, or other buildings that just take more space.

tjwhale wrote:

Ok so to go through the algorithm.

1. Designate central vertex
2. create 4 city blocks around it
3. start filling these blocks with buildings (and subdividing as necessary)
4. if there isn't enough room to add the next building create a new block

only display roads that are touching occupied buildings.

So to unpack this a bit.

1. The city centre is a point on the map, every building wants to be close to this center.

2. a city block is 4 vertices which are points connected by main road. This will make a tetrahedron. The first 4 blocks will have the center vertex as one of their corners.

3. If you put a gigantic building in a block it fills it, if you put a large one in the block is cut in two and there is room for another large building. If you put a medium in you need half of a half. And a small one needs half of that.

So a block can have 8 small, 4 medium, 2 large or 1 gigantic. Or any reasonable combination. So 1 large, 1 medium and 2 small. Or 4 small and 2 medium. etc.

4. When trying to add a building if there is no room the game designates a new block (as close to the center as it can) and puts your building in there.

We would have to factor in some exceptions though. For example, early cities would obviously not be an orderly grid of buildings but more of just a cluster of huts. Also, even in more modern, grid-based cities, the outskirts of the city are not grid based, such as mines, mills, farms, villages. It's primarily the core of the city that follows this pattern.

tjwhale wrote:

Bonus extra! Buildings could have their effectiveness decrease the further they are from the center. So you have to choose which buildings you want to be the most important. Do you want a cathedral right in the middle or a spaceport?

Right idea, but we don't need to represent the decrease in effectiveness with some approximation because the specific interactions between the people and buildings will be simulated. For example, a blacksmith would be much more productive if placed near a warehouse that stores ores, since it would be less distance to travel to pick up materials, or a hospital would have greater effect when placed near more people. This encourages the player to specialize parts of their city, like say a residential area with schools and hospitals, and an industrial area with factories and warehouses.

NickTheNick wrote:

We might need to raise the bar for large buildings to account for more size, if the AI builds especially large airports, seaports, spaceports, or other buildings that just take more space.

Sure, the categories I suggest are just examples. I suppose under the above system you could also modify it to have buildings covering double or triple blocks. It's about having the right numbers of roads to make it look good.

NickTheNick wrote:

We would have to factor in some exceptions though. For example, early cities would obviously not be an orderly grid of buildings but more of just a cluster of huts. Also, even in more modern, grid-based cities, the outskirts of the city are not grid based, such as mines, mills, farms, villages. It's primarily the core of the city that follows this pattern.

One thing about mines and farms is they are sat on top of resources. So if these resources are designated in the game then you'll just put those buildings there.

The thing about even iron age settlements is the buildings want to be as close together as possible while there is still reasonable room to move inbetween them so the system I propose is reasonable. Though it is definitely not without it's limitations.

NickTheNick wrote:

Right idea, but we don't need to represent the decrease in effectiveness with some approximation because the specific interactions between the people and buildings will be simulated. For example, a blacksmith would be much more productive if placed near a warehouse that stores ores, since it would be less distance to travel to pick up materials, or a hospital would have greater effect when placed near more people. This encourages the player to specialize parts of their city, like say a residential area with schools and hospitals, and an industrial area with factories and warehouses.

It's an important design decision to pick the level of abstraction in the city design stage. For example do you build an individual house for every worker? (Think age of empires or tropico) Do you designate large areas for thousands of people (sim city) or do you just choose to build "a city" which has room for millions (civilisation)? These are very different approaches.

Managing the placement of individual buildings is attractive when you have 1-2 cities but if you will have 20-30 or even 300 on different planets this will become impossible.

Overall good points, thanks for the response.

Actually, all of those levels of abstraction will be in the game. You start the game building each individual building, but with the City Planning research you can zone areas for different types of buildings (i.e. residential, commercial, industrial, etc.) You can also at any time queue up buildings for a city to build and the city will decide where to build it.

Ideally this will cover the transition from small tribes into large empires.