Thrive Game Development

Development of the evolution game Thrive.
 
HomeHome  PortalPortal  CalendarCalendar  FAQFAQ  SearchSearch  MemberlistMemberlist  UsergroupsUsergroups  RegisterRegister  Log inLog in  
Welcome new and returning members!
If you're new, read around a bit before you post: the odds are we've already covered your suggestion.
If you want to join the development team, sign up and tell us why.
ADMIN is pleased to note that this marquee has finally been updated.
ADMIN reminds you that the Devblog is REQUIRED reading.
Currently: The Microbe Stage GUI is under heavy development
Log in
Username:
Password:
Log in automatically: 
:: I forgot my password
Quick Links
Website
/r/thrive
GitHub
FAQs
Wiki
New Posts
Search
 
 

Display results as :
 
Rechercher Advanced Search
Statistics
We have 1675 registered users
The newest registered user is dejo123

Our users have posted a total of 30851 messages in 1411 subjects
Who is online?
In total there is 1 user online :: 0 Registered, 0 Hidden and 1 Guest

None

Most users ever online was 443 on Sun Mar 17, 2013 5:41 pm
Latest topics
» THIS FORUM IS NOW OBSOLETE
by NickTheNick Sat Sep 26, 2015 10:26 pm

» To all the people who come here looking for thrive.
by NickTheNick Sat Sep 26, 2015 10:22 pm

» Build Error Code::Blocks / CMake
by crovea Tue Jul 28, 2015 5:28 pm

» Hello! I can translate in japanese
by tjwhale Thu Jul 02, 2015 7:23 pm

» On Leave (Offline thread)
by NickTheNick Wed Jul 01, 2015 12:20 am

» Devblog #14: A Brave New Forum
by NickTheNick Mon Jun 29, 2015 4:49 am

» Application for Programmer
by crovea Fri Jun 26, 2015 11:14 am

» Re-Reapplication
by The Creator Thu Jun 25, 2015 10:57 pm

» Application (programming)
by crovea Tue Jun 23, 2015 8:00 am

» Achieving Sapience
by MitochondriaBox Sun Jun 21, 2015 7:03 pm

» Microbe Stage GDD
by tjwhale Sat Jun 20, 2015 3:44 pm

» Application for Programmer/ Theorist
by tjwhale Wed Jun 17, 2015 9:56 am

» Application for a 3D Modeler.
by Kaiju4u Wed Jun 10, 2015 11:16 am

» Translator to Serbian here
by Simeartherist Sun Jun 07, 2015 6:36 am

» Presentation
by Othithu Tue Jun 02, 2015 10:38 am

» Application of Sorts
by crovea Sun May 31, 2015 5:06 pm

» want to contribute
by Renzope Sun May 31, 2015 12:58 pm

» Music List Thread (Post New Themes Here)
by Oliveriver Thu May 28, 2015 1:06 pm

» Application: English-Spanish translator
by Renzope Tue May 26, 2015 1:53 pm

» Want to be promoter or project manager
by TheBudderBros Sun May 24, 2015 9:00 pm


Share | 
 

 Procedural City Generation

View previous topic View next topic Go down 
AuthorMessage
moopli
Developer


Posts : 318
Reputation : 56
Join date : 2013-09-30
Age : 21
Location : hanging from the chandelier

PostSubject: Procedural City Generation   Sun Jun 08, 2014 10:54 pm

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.


Last edited by moopli on Mon Jun 09, 2014 6:20 pm; edited 1 time in total (Reason for editing : more meat to the conversation)
Back to top Go down
View user profile
TheRabiesGuineaPig
Learner


Posts : 102
Reputation : 10
Join date : 2014-04-22
Age : 15
Location : Somewhere in the World Wide... World

PostSubject: Re: Procedural City Generation   Sun Jun 15, 2014 5:05 am

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.
Back to top Go down
View user profile
moopli
Developer


Posts : 318
Reputation : 56
Join date : 2013-09-30
Age : 21
Location : hanging from the chandelier

PostSubject: Re: Procedural City Generation   Sun Jun 15, 2014 8:06 am

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.
Back to top Go down
View user profile
NickTheNick
Overall Team Co-Lead


Posts : 2312
Reputation : 175
Join date : 2012-07-22
Age : 20
Location : Canada

PostSubject: Re: Procedural City Generation   Sun Jun 15, 2014 2:40 pm

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:
 

_________________
Look at how far we've come when people thought we'd get nowhere. Imagine how far we can go if we try to get somewhere.
Back to top Go down
View user profile
TheRabiesGuineaPig
Learner


Posts : 102
Reputation : 10
Join date : 2014-04-22
Age : 15
Location : Somewhere in the World Wide... World

PostSubject: Re: Procedural City Generation   Sun Jun 15, 2014 2:58 pm

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?
Back to top Go down
View user profile
NickTheNick
Overall Team Co-Lead


Posts : 2312
Reputation : 175
Join date : 2012-07-22
Age : 20
Location : Canada

PostSubject: Re: Procedural City Generation   Sun Jun 15, 2014 3:42 pm

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.

_________________
Look at how far we've come when people thought we'd get nowhere. Imagine how far we can go if we try to get somewhere.
Back to top Go down
View user profile
moopli
Developer


Posts : 318
Reputation : 56
Join date : 2013-09-30
Age : 21
Location : hanging from the chandelier

PostSubject: Re: Procedural City Generation   Sun Jun 15, 2014 4:08 pm

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?
Back to top Go down
View user profile
NickTheNick
Overall Team Co-Lead


Posts : 2312
Reputation : 175
Join date : 2012-07-22
Age : 20
Location : Canada

PostSubject: Re: Procedural City Generation   Sun Jun 15, 2014 4:22 pm

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.

_________________
Look at how far we've come when people thought we'd get nowhere. Imagine how far we can go if we try to get somewhere.
Back to top Go down
View user profile
TheRabiesGuineaPig
Learner


Posts : 102
Reputation : 10
Join date : 2014-04-22
Age : 15
Location : Somewhere in the World Wide... World

PostSubject: Re: Procedural City Generation   Mon Jun 16, 2014 11:15 am

Has it yet been discussed how we are actually supposed to construct buildings? Or is it not priority at the moment.
Back to top Go down
View user profile
moopli
Developer


Posts : 318
Reputation : 56
Join date : 2013-09-30
Age : 21
Location : hanging from the chandelier

PostSubject: Re: Procedural City Generation   Mon Jun 16, 2014 11:39 am

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.
Back to top Go down
View user profile
TheRabiesGuineaPig
Learner


Posts : 102
Reputation : 10
Join date : 2014-04-22
Age : 15
Location : Somewhere in the World Wide... World

PostSubject: Re: Procedural City Generation   Mon Jun 16, 2014 11:47 am

Maybe you should construct the city hall and it will generate the other buildings judging on parts/textures you use.
Back to top Go down
View user profile
moopli
Developer


Posts : 318
Reputation : 56
Join date : 2013-09-30
Age : 21
Location : hanging from the chandelier

PostSubject: Re: Procedural City Generation   Mon Jun 16, 2014 11:52 am

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?
Back to top Go down
View user profile
TheRabiesGuineaPig
Learner


Posts : 102
Reputation : 10
Join date : 2014-04-22
Age : 15
Location : Somewhere in the World Wide... World

PostSubject: Re: Procedural City Generation   Mon Jun 16, 2014 11:53 am

I don't really code so I can't add much to the discussion in that way. Just suggesting really.
Back to top Go down
View user profile
NickTheNick
Overall Team Co-Lead


Posts : 2312
Reputation : 175
Join date : 2012-07-22
Age : 20
Location : Canada

PostSubject: Re: Procedural City Generation   Mon Jun 16, 2014 3:39 pm

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.

_________________
Look at how far we've come when people thought we'd get nowhere. Imagine how far we can go if we try to get somewhere.
Back to top Go down
View user profile
Armok: God of Blood
Newcomer


Posts : 50
Reputation : 2
Join date : 2012-10-20
Age : 19
Location : Either Golarion, Nirn, or Boatmurdered

PostSubject: Re: Procedural City Generation   Tue Jun 17, 2014 5:54 pm

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?
Back to top Go down
View user profile
NickTheNick
Overall Team Co-Lead


Posts : 2312
Reputation : 175
Join date : 2012-07-22
Age : 20
Location : Canada

PostSubject: Re: Procedural City Generation   Tue Jun 17, 2014 6:10 pm

You may, but this thread has been derailed enough.

_________________
Look at how far we've come when people thought we'd get nowhere. Imagine how far we can go if we try to get somewhere.
Back to top Go down
View user profile
moopli
Developer


Posts : 318
Reputation : 56
Join date : 2013-09-30
Age : 21
Location : hanging from the chandelier

PostSubject: Re: Procedural City Generation   Tue Jun 17, 2014 8:02 pm

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.
Back to top Go down
View user profile
tjwhale
Theorist


Posts : 87
Reputation : 26
Join date : 2014-09-07

PostSubject: Some Thoughts   Mon Sep 08, 2014 2:13 pm

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
Back to top Go down
View user profile
NickTheNick
Overall Team Co-Lead


Posts : 2312
Reputation : 175
Join date : 2012-07-22
Age : 20
Location : Canada

PostSubject: Re: Procedural City Generation   Tue Sep 09, 2014 3:22 am

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.

_________________
Look at how far we've come when people thought we'd get nowhere. Imagine how far we can go if we try to get somewhere.
Back to top Go down
View user profile
tjwhale
Theorist


Posts : 87
Reputation : 26
Join date : 2014-09-07

PostSubject: Re: Procedural City Generation   Tue Sep 09, 2014 5:21 am

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.
Back to top Go down
View user profile
NickTheNick
Overall Team Co-Lead


Posts : 2312
Reputation : 175
Join date : 2012-07-22
Age : 20
Location : Canada

PostSubject: Re: Procedural City Generation   Thu Sep 11, 2014 2:12 am

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.

_________________
Look at how far we've come when people thought we'd get nowhere. Imagine how far we can go if we try to get somewhere.
Back to top Go down
View user profile
Sponsored content




PostSubject: Re: Procedural City Generation   Today at 4:47 am

Back to top Go down
 
Procedural City Generation
View previous topic View next topic Back to top 
Page 1 of 1

Permissions in this forum:You cannot reply to topics in this forum
Thrive Game Development :: Development :: Programming :: Technical Discussion-
Jump to: