python - What is a good algorithm for fractal-based procedural city layout?

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.

Answer

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:

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