19
\$\begingroup\$

Background

I run a minecraft server where I'm going to design a starter city of fairly large scale. I have a series of things, like rule signs and mob cages, I would like to put in buildings there. The city itself will be extremely large and spread out, preferably up to 1000 by 1000 blocks in size.

The buildings themselves will be have cube or rectangular footprints that are based on a certain base cube, like all multiples of 3 blocks. The streets and distance between the buildings will be preferably 5-11 blocks wide, depending on the importance of the street.

When I begin the plan for the city, I will know exactly how big I want the buildings to be and how many there will be.

The Problem

The problem is designing the layout for the city. Obviously with something of such a scale, and me coming from a programming background rather than an urban planner background, it's quite challenging to even begin to wrap my head around the problem.

The problem specifically is that I want the city to look as natural as possible. Of course this would be fairly easy to build on a simple grid pattern, but I want to avoid a grid, or anything that looks like a grid, as much as possible.

The Question

What algorithms might I be able to pursue to be able to help me design it using code? I was thinking that it would look most natural if I used fractals in some way, as minecraft uses fractals already in its terrain generation, and a city seems to grow in a fractal pattern naturally.

I think it's similar in some ways to a tetris playing algorithm, so if anybody has solutions that exist down that direction then it would help also. I'm picturing something where I'll be able to define the shapes that I want to use, and the software then iterates until it finds the most "optimal" solution for even distribution of buildings. Does something already exist to help me solve this problem using python, preferably in a visual way using pygame?

Naturally this also has interesting implications for city generation in general in game design, so I'm very excited to see what the best solution is.

edit To be clear, I'm just looking for the layout at this point as the buildings will be designed and built in game.

Improve this question
\$\endgroup\$
5
  • 3
    \$\begingroup\$ Minecraft uses fractals? I was under the impression it just uses continuous noise functions (Perlin or Simplex, I believe). \$\endgroup\$
    – Martin Sojka
    Oct 21, 2011 at 7:00
  • \$\begingroup\$ @Martin Sojka Perlin noise is actually a fractal, so there. \$\endgroup\$
    – Nevermind
    Oct 21, 2011 at 10:34
  • 1
    \$\begingroup\$ @Nevermind: The defining characteristic of a fractal is self-similarity: If you pick a part of it and scale it to the size of the original, it will be "similar" (have the same structure). In particular, the frequency spectrum of a fractal signal is invariant to the scale. If you do that with Perlin noise, all you'll get is a scaled-up area of a Perlin noise; the frequency spectrum will shift as well. \$\endgroup\$
    – Martin Sojka
    Oct 21, 2011 at 10:38
  • \$\begingroup\$ @Nevermind Perlin noise actually isn't a fractal, however Brownian motion (which is a technique that can use Perlin noise) is a fractal and is commonly referred to as Perlin noise. \$\endgroup\$
    – Elva
    Oct 21, 2011 at 12:32
  • \$\begingroup\$ Yeah, sorry, I always correct people when they confuse Perlin noise and pink noise, but here I am making the same mistake myself. My only defense is that Minecraft actually uses pink (brownian motion) noise too, IIRC. \$\endgroup\$
    – Nevermind
    Oct 21, 2011 at 13:48

3 Answers 3

Reset to default
20
\$\begingroup\$

I've recently implemented an algorithm for a procedural city layout. It's still very much a work in progress, but seems promising to me. Take a look:

procedural city example

The algorithm used to create this layout is loosely based on L-Systems. I have a base Element class, that has a rectangle marking its place on map and a method Grow, which creates other Elements inside the rectangle, and/or spawns some objects on map. Then there are actual elements, inherited from this base class: City, Street, Building etc.

The generation starts with a number of "seed" objects (in my case, just a single City element randomly placed on the map). Then the system iterates over all elements, calling Grow, until all elements become inactive (Grow returns false), or some large number of iteration passes.

The city in the picture is built using only a few simple rules:

  • City becomes a Street element splitting the area someplace.
  • All Streets grow 0-3 side streets, further splitting the area.
  • Also, Streets continuously try to fit a random-sized Building at the side.

The result is not terribly interesting, but not bad either. The system can be extended easily, and is simple enough to understand what's going on (-8

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Love the simplicity. Cities are, I guess, actually organic because they are controlled by an organic entity - which seeks to create perfection as its mind's eye sees it - making L-Systems probably the best approximation of this process. \$\endgroup\$
    – Jonathan Dickinson
    Oct 21, 2011 at 13:31
  • \$\begingroup\$ I like it. =) Now to implement in pygame... \$\endgroup\$
    – Ken
    Oct 21, 2011 at 16:17
8
\$\begingroup\$

There's this GDC talk on procedural building generation from a couple of years ago. It's for creating individual buildings based on a set of templates, but not for creating whole cities (laying out streets and so forth). There isn't any free code to go with it, unfortunately. The system described in the talk is implemented in Unreal although I'm not clear whether it's in the free version of UDK or not. In any case, you could use some of the same ideas to build your own system.

Googling "procedural buildings" or "procedural city" will also give you quite a few other papers and articles on the topic.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

I ran across a very good/detailed tutorial for creating procedural cities a while back. There is a video @ http://www.youtube.com/watch?v=-d2-PtK4F6Y The tutorial is on the author's blog: http://www.shamusyoung.com/twentysidedtale/?p=2940 Hope this helps amb

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ Looks like a great tutorial from what I skimmed over, and it will have some great pointers if I decide to generate cities later. =) \$\endgroup\$
    – Ken
    Oct 24, 2011 at 17:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .