Quick post to let everyone know that with the holidays I don’t expect to get much done over the next two weeks. For the cityscape I have decided to move forward with designing bridges and rivers beginning of next year, but not before I spend just a wee bit of time on some of the aesthetics. This last week I’ve spent an hour or two on minor adjustments including adding just a little splash of color to the sky, adding random clutter to the top of buildings such as radio towers and air conditioning units, and spacing out the buildings a bit to give them more of a chance to stand out.

Anyways, enjoy the holidays and look for a new post probably first week in January.

A major problem with my cityscape is the even monotonous distribution of building heights and sizes across the entire grid.  While this would make sense for a city of infinite size it doesn’t mimic what we see in cities in the real world.   What we typically see instead is a cluster of larger skyscrapers that represent a downtown area and buildings heights getting smaller as you move farther away from this downtown.  You might have other smaller spikes elsewhere in the city, but you usually have one that stands out above the rest.

Now how can I randomly recreate this phenomenon in my cityscape ?  First thing that came to mind is to use the same logic I employ in my Terrain Editor.  Imagine the tops of the buildings with the tallest skyscraper being the peak of a mountain top and the shortest buildings being the valley.  Well creating such a panorama is exactly what my terrain editor is designed for all I need to do is incorporate the same algorithm that generates a random landscape into my code.

Now the terrain editor uses a complex modified version of an algorithm called the Diamond Square Algorithm, but that would be overkill here.  Instead the simple Midpoint Displacement Algorithm should suffice and later on if I need more complexity I can update the code.   This process recursively generates a landscape like a fractal from only the four corner points of the landscape.  To get an idea of how this is possible, lets imagine the same process in in only 2D, first start with a line:

Initial heightmap

Now take the middle of this line and shift it up or down a random amount.  You should now have two lines like so:

Heightmap after 1 recursive iteration

Now take the midpoint of both of these lines and also randomly shift them up or down.  Make the random shift be smaller than the previous iteration.  One of the many possibilities could look like this:

One possible heightmap after 2 recursive iterations

Keep doing this process until you stop noticing any differences, although in theory it can be done infinitely:

One possible heightmap after 4 recursive iterations

Kind of looks like a mountain range doesn’t it?  This can be considered a fractal since each part, no matter how small, resembles the picture as a whole.  A similar process can be done in 3D, and while it does have it’s flaws the results are more than adequate for my cityscape.

One small problem is this algorithm does not guarantee the mountain I need for a proper downtown, so I will need to make a small adjustment to ensure that during one of the iterations at least one of the buildings reaches maximum height.  I will need to do this during an early iteration when most of the heights have not been calculated and giving later points a chance to smooth out, otherwise I’ll end up with a spike which will likely look like a single building all by itself that towers 90 stories over all of it’s neighbors.  On the opposite end I don’t want to do it in the first one or two iterations because I am working with so few points at that time that the downtown area will be too often in the same location, not random enough for me.  I’ll need to play around with this to find the perfect balance of when to force the downtown.

So now my code generates a landscape with the same dimensions as my city complete with peaks and valleys and at least one tall mountain top.  Now before a building is generated it asks what the altitude of this landscape is at that exact same location and translates this into a height.  Here are some screenshots:

First attempt at using heightmap on my Cityscape

Looking better!  Course now it looks a little TOO much like a landscape, unless the city is built on hillsides the buildings don’t increase in height so perfectly like that.  Instead the average is what increases while each individual building can be a certain percentage above or below this average.  What I need now is extra logic that takes the height a building should be at a location, then add or subtract a certain percentage, the lower this percentage the more like the above picture it will look and the higher this percentage the more random it will look.

I think a good reasonable number is 50% to start off, so if the landscape says a building should be 20 stories in actuality it can be anywhere from 10 to 30 stories.  If 100 stories then anywhere from 50 to 150 stories.  Here are the results:

Adding height variance to my heightmap

I think I will make this percentage be random between different instances of the cityscape, initially I assumed anything close to 100% would look awful but after playing around with it the city can look pretty good even as high as 120%.   So far I am pretty happy with how this has turned out, here is a new video flying over the buildings, notice now that I have the option to visually turn on the landscape that dictates the building heights just so you can get an idea of how the underlying code works.

Now I have hit a crossroad concerning what to work on next for my Cityscape and I am not sure which direction I should take.  One direction is to spend a lot of time improving the aesthetics of the buildings themselves.  Another route is to spend time on the streets by adding traffic.  And last is to spend time on an idea I have been bouncing around where I dynamically create rivers and bridges.  Need to ponder upon this one.

Next step, as discussed at the end of my last post, is to add a bit more variety to my buildings by adding the random possibility of a building being rotated.  Currently all buildings have sides that are parallel to one another but many cities don’t have streets that are all perpendicular to one another causing many buildings to be at angles to one another.  I would like to simulate this as well by allowing a building to be rotated anywhere from zero to forty-five degrees.  My guess is that I will need to limit the amount this used to have the greatest visual effect but first I will try with all buildings and an even distribution of angle possibilities.

Rotating is relatively straightforward.  I simply need to take all points of the building and twist around the center point by the number of degrees you plan on rotating.  For example, a block building only has 8 points that need to be moved, the 8 points of the rectangular cube.  Luckily there is an easy formula for rotating around a point:

x’ = xr + (x-xr)Cos(θ) – (y-yr)Sin(θ)

y’ = yr + (x-xr)Sin(θ) + (y-yr)Cos(θ)

where x’ and y’ are the new values, xr and yr are the coordinates for the midpoint of the building, x and y are the coordinates of the point you want to move, and Θ is the angle.

So let’s add this logic to the code and see what happens.  First I will give every building a chance to have anywhere from zero to a forty-five degree rotation, here is the first screenshot:

Utter chaos

As you can see it is utter chaos.   Buildings suddenly look haphazardly placed, often times colliding into one another and/or stretching out into the streets.  Ideally I think the best way to solve this issue is to re-plan the street layout by allowing streets to connect with one another at angles and then filling in the blocks with buildings that would then naturally be angled as well.  However that would require a complete rewrite of my underlying logic since all calculations and data structures are geared for grid-like symmetry.  I’ll have to table that idea for now and come back to it in the future…

So what can I do now to fix this mess other than scrapping the rotation idea all together?  Well for starters I think giving every building a chance to be rotated is a bit unrealistic.  I’ll use the same distribution code that I wrote for the building heights in my last post to decide which buildings get rotated and by how many degrees.  Highest probability will favor not having the building turned at all while the lowest probability will have the building rotated the maximum number of degrees.  Here is a screenshot of the new results:

Better distribution, but building collisions

Ok, looks a little better.  I am starting to have second thoughts though and am leaning more and more towards scrapping this idea all together, at least until I get the logic behind angled streets down.  One major problem is the collision of walls with other walls and/or streets.  The lots the buildings stand on start off as rectangles just barely larger than the building itself, and when twisted the building edges can go over the boundaries of the lot and into its neighbor.  Having lots that aren’t perfect rectangles and aligned with the grid would be a logistical nightmare, so now my only option is to either enlarge the lot or shrink the building when rotating.  The problem with this though is one building might need a much more drastic size reduction compared to another building even if both are rotated the same amount.  For example, a building on a square lot would need to be divided by the square root of 2 (approximately 30% reduction) as seen in this picture:

Square example

A building that has a drastic difference between its width and length could need a much higher reduction in size as evidenced by this picture:

Rectangular example

So now I add in a little bit of extra logic  that shrinks the building size down based on its original length/width ratio and the angle being rotated and get this result:

No collisions

Bit better.  I think I will keep this new feature for now, but still not thrilled with it.  My next post will deal with creating a natural flow of building heights across the entire city resulting in a more realistic skyline complete with a downtown.

For my first task I plan on adding logic to vary the heights of the buildings in my cityscape. Currently each and every building can have a random height between approximately four and seventy stories. This probability is evenly distributed so a building has just as much a likelihood of being short as it being average or tall. The problem is this makes the cityscape very monotonous and gives the illusion of all buildings looking about average. What I want to do is create a way to input a distribution equation that will vary the heights however I want, first entered manually then moving on to having the computer randomly generate one.

To decide what height a building is to be, I randomly generate a number between the minimum height and the maximum height, in this case 4 and 70 respectively. If the random number is 36, then the height of the building will be 36 for example. The distribution graph would look like this:

Even distribution

This is the way my cityscape looks using this logic, notice the boring uniformity of the building heights:

Evenly distributed

Taking a look at some real life skylines, my first impression is that most buildings are around average height and it becomes less and less likely that a building will be really tall or really short. So if I were to generate a random number from one to a thousand, the distribution graph would look something like this:

Uneven distribution

So how do I incorporate this into my code? Well the easiest way I can think of is to translate the graphs into equations, then my code just needs to generate the random number and plug it into the equation to get the building height. The boring equation that I currently employ is simply x=h where x is the random number and h is the height. The second graph you can see that most numbers generate a height hovering around the median and only the extremes result in the tallest skyscrapers or shortest buildings. This can be expressed as the equation Ax^3 = h where the coefficient A dictates the steepness of the curve. For example .0001x^3 will have a very shallow slope while 100x^3 will have a very steep slope.

So lets add this to my program and see the results. First I’ll try a coefficient of .0001, here are the results:

Very flat curve

As you can see this makes it extremely likely that a building will have an average height. Now we try with a coefficient of 100:

X cubed equation

Big improvement! It is kind of hard to tell from a picture but the city looks much better. Tall buildings are much less common now which actually makes them stand out more. Now to try a new equation, instead of x cubed I’ll use x squared, this will be similar to the last version but now the greatest probability will be on the shortest buildings with it becoming less and less likely for medium and tall buildings. Here are the results:

X squared equation

Not sure which one I like more, I’ll have to play around with this just a little bit. Initially I wanted to make another small change, one that adds the possibility of buildings being rotated up to 45 degrees. Currently all buildings are perpendicular to one another which makes sense if it were New York City, but most other skylines have sky scrapers at angles to one another. But the more and more I think about it the more I realize this will take more work than I anticipated. Not only do I need to calculate the new coordinates for each and every point on a building, but I’ll also need to add some logic to shrink building size accordingly so that I don’t get buildings colliding with one another or blocking streets. I still want this to be my next task, but it is no longer an afterthought at the end of this post like I originally intended it to be.

The first project I want to showcase is my program that procedurally generates a cityscape on the fly. I’ve always been highly attracted to procedural concepts in programming, more so than other types of development such as applications or games. In a future post I’ll go into a bit more detail about the definition of procedural, but in a nutshell it means dynamically creating content real-time through algorithms. Apologies to those who have used this example before, but say you want a program that generates a forest tree by tree. One way to write this is to tell the program exactly where to put each and every tree, the height of each tree, the width, the age, color of leaves, and so on. If there are a hundred trees you would need at least a hundred lines of code. A thousand trees, a thousand lines of code, etc. Not the most practical, however the programmer has the most control and can create a beautiful forest similar to an artist drawing a painting. At the other end of the spectrum is creating the forest procedurally using algorithms that logically set parameters of what a forest generally looks like and then lets the program draw something that fits that criteria. The most extreme version of this would be to simply say place a thousand trees of random heights and sizes in a thousand random locations. This version could possibly be written with just a single line of code, and if run would sometimes produce great looking forests and at other times create forests where all one thousand trees were right on top of each other. Unlike the hardcoded version created by the artist in the first example, nothing about this forest actually exists until the program is run and each new running produces a completely new spontaneous forest. The art of procedural content driven programming in my mind is finding the perfect mix of the two where beautiful or interesting content is created with the least amount of code.

The thought of doing a cityscape as one of my first major procedural projects did not start off as my own. Another programming blogger that I follow by the name of Shamus Young (blog can be found here) described a project he had worked on similar to this and it piqued my interest so much that I almost instantly opened up my developing tools to create my own version. I have always been a big fan of skylines, indeed New York City is one of my favorite places to visit for this very reason, so a project where I randomly create my own skyline was a perfect fit.

Here is a video of my cityscape as it now stands. Click full screen and 720HD for best viewing, although you can lower it if your computer/connection can’t handle it. Unfortunately the video editing program I use mucks up the frame rate a little bit so it looks a little choppy, but when run on my less than impressive computer it is silky smooth. The camera can be controlled manually by the user, or the auto camera can be turned on which will do a random fly-by of the city staying at the current altitude.

I won’t go into too much detail about each of the current features, at least not in this post. As I start working on improving and adding new content to the current code I’ll talk more about exact implementation depending on the subject at hand. Some of the features include:

• Four different building types. I talk a little bit about this below.
• Lighting and fog.
• Wireframe mode.
• Randomize the cityscape on the fly.
• Streets in between blocks, although no cars, streetlights or roads yet, but soon!
• Randomly generated window lights on each building including single window rooms and multiple unit offices.
• Camera control, manual and auto.
• And I am proud of this one considering I am also an amateur astronomer, the stars in the sky are an accurate representation of our night sky, all 9000+ visible stars, plus authentic sky rotation. There is an option to produce a random starry night, but personally I prefer the real thing. Kind of hard to see but click here to see a screenshot of Orion and the Winter Triangle as seen in my above my skyline.

So what needs to be done? Well, unfortunately LOTS. If I was to put a percentage on how far along I am I would say maybe 30 to 40 percent. For one, while I am proud that I can generate relatively realistic looking buildings on the fly, they currently are far too simplistic since I wanted to get most of the framework written before I spent too much time improving the aesthetics of the building types. There are a lot of techniques that I plan on implementing to improve the building models, most based around the idea that our eyes fill in spaces that it cannot see – no coincidence that my city can only be seen at night! Another major project is adding street life to the scene, most notably lights imitating cars. This will be an interesting and difficult undertaking as I’m not sure I wrote this program in a way for my code to best understand the concept of roads.  Also adding hundreds of moving objects will likely have an effect on my frame rate meaning time will need to be spent on optimization. Another major improvement that needs to be made is the addition of some logic to vary the skyscraper heights based on location within the city. If you look at most large cities in real life you tend to have one or two locations where the tallest buildings are located and then buildings get smaller the farther away from this “center” you go. Currently all buildings in my program can be any height which creates this monotonous, unrealistic feel. It would be easy to hard code something like this of course, but true to my nature I’d like a way to randomly recreate this phenomenon.

I’ll end this intro post by discussing quickly the four building types found within my city, each style of which loosely resembles a particular generic skyscraper that we see in cities today. I do plan on creating more styles in the future, if you have any types in mind you would like to see let me know!

The first style is the easiest to implement since it is simply a large rectangular box. An example of this style in real life would have been the World Trade Center Towers. This is the most common building type in my program, approximately 50% of the buildings in my city will be of this type. Quick video detailing just this style:

The second style is the cylindrical version, an example in real life would be the Peachtree Building in downtown Atlanta. This is the second most common, set to about 25% in my city. Extra logic was included to add the chance of the sides of the cylinder to be “flattened” to create a more pleasing look and to break up the monotony a bit. Soon I’ll add similar logic to the block buildings to give them the possibility of a more angled appearance. Quick video:

The third style is the tiered version, an example of this is the Empire State Building. These buildings are similar to the block buildings but taper off as you get higher, similar to a traditional wedding cake. I’ve also added a tower to the to make them stand out a little bit more, but I’m not proud of the way they came out since without textures they look like ugly pyramids colored by crayon. That will hopefully be one of the first things that I update. The percentage for these types is around 15%. Quick video:

The last style is what I call a combo building and is a combination of any of the three above into a single building. They compromise the remaining 10% or so. Video:

Next post I will demonstrate another of my procedural content projects, a terrain editor that has a few things in common with this project.