Sonntag, 23. September 2012

playing lego

It's done. It's over. I turned in my bachelor thesis. Life has me back. Yea, last post was a month ago. Sorry about that. But between my application for an awesome job in a german games company and my bachelor thesis there was no time for nothing.

Empire State Building - art déco
So let's talk business. Though my bachelor thesis is done my project is not. But I haven't told you about all the features that went into it yet anyway. Last time I really talked about the project I told you about the street  generation system. Then I told you how to find lots in that streetsystem. Today I'm gonna talk about making buildings. And thats really simple. Our buildings will only consist of blocks. Not in the minecraft kind of way tho. For the buildings I chose a very geometric architecture style. The art déco style will serve us just right for
this. Of course to create a foudation for our geometry we will use the L-Systems again. I won't make any friends if I post the definition of the L-System here again. I think most readers will understand it as "cryptic formulas". All you need to know is, that we take the bounding box of a building at the beginning then split it up and shrink parts of it, so it stays in the bounding box. We can use this by utilizing parametric L-Systems that use two vectors as parameters. Those vectors define the minimal and maximal point of a box. In the end we have a long string that is defining a lot of boxes. There also have to be different kinds of boxes. So the L-System knows how it may change them during the generation process... in
Development of a building - types of boxes colored
the picture on the right you can see how the bounding box (green block on the left) gets split up. The different colors mark the different types of blocks. When we parse our string with the instructions for the building we just create geometry data for a lot of boxes. Oh, and don't forget that you should use different textures for the roofs. Just with one type of buildings your end result may already look something along the lines of this:
Bad example
If I think about it, this is a bad example picture because you cannot see any buildings up close. But I'm too lazy to take a new screen now. XD

That's all folks.
Till next time

Mittwoch, 22. August 2012

UrbanGenesis WIP Video Online

Okay guys, I just uploaded the first video of the project to YouTube.
I thought you might wanna check it out:

I'll create a blog post about the techniques to create the buildings in the video very soon, so stay tuned.

Samstag, 18. August 2012

Gamescom 2012

So, this was a pretty busy week for me. I finally finished the coding part in my Bachelor thesis and my personal website went online. Check it out at
And then there was Gamescom! Living only a short 2 hours ride from cologne I sure didn't miss it.

Last year me and my girlfriend went there for two days. First day only for press and business and second day for everyone. This year we decided only to go for the business day.

But, phew, we were busy. Other than checking out the cool new stuff that's getting released or in development I was making sure to leave some job applications at a few developers booths.
That was quite exciting since some of those guys even took the time to talk to me a bit about the culture of their company and how they fared themselves getting into the games industry.
Anyway I had a blast doing this.

Sadly I wasn't as overwhelmed by the entertainment area this year. Somehow I had hoped to get a glimpse of DOTA2 and Guildwars2 before their release. I found a small GW2 booth with no possibility to check out their latest changes to the game. Didn't even find a trace of DOTA2.
Firefall though looked very promising and fun.

Another funny thing is the development of the League of Legends/Riot booth over the last 3 years. In 2010 it was somewhere hidden in the dining hall in a shared booth with some other games. In 2011 they had a pretty crowded normally sized booth directly in front of the entrance to the ESL area. This year they almost had half a hall to themselves it seemed. Great progress guys. Keep it up.

Okay guys, next time I'll write about the creation of some really simple yet cool LOD buildings using L-Systems that need no time to implement.

Dienstag, 7. August 2012

Rome wasn't built in a day...

Well then, last time I wrote about my little procedural project (make a procedural modern day city) I was talking about L-Systems and how they can be manipulated to create a street network for our world.
Now lets say after we got the basics of that down and derived our L-System string a few times we end up with something like this:

Okay. Doesn't look anything close to a street network. Of course nobody with a clear mind would plan to let majority of the streets of his city to end up in a dead end. Every street leads somewhere.
So we tie up our loose ends and come up with this:

Okay, making this possible is not trivial either but I don't want to dive too deep into it. Basically after I read in the string from the L-System (Pic. 1) I have a graph with every node for every bend, intersection or dead end. Now basically there is a simple system to choose a direction to go from the dead end that isn't going into nowhere. There is a lot of intersection tests with the nodes and their edges to finally find the spot where the new street will join into the rest of the street network. Mostly boring.
The really interesting thing comes after the streets are completed. We got a street graph with nodes and edges. One node can have up to four edges (every cardinal direction). How do you find the places where you can put your buildings without putting them onto the streets.
So I needed to find the shortest way from a node to that same node without passing any node twice. Additionally I don't want to have duplicates because they are hard to detect when they have a different start node but describe the same allotment.
It took me a long time to figure this out and I still am not sure if I got a good way to do this.
So we go through every node in the graph and try to get back to the node taking always the edge that leads us counterclockwise. It's a little hard to convey so I made a state machine diagram of it:

So the algorithm tries to follow this state graph. Starting with state S we try to go east. If we cannot, shoot, we failed. But if we can go to the next state and try to go north if it works next state, if not try east, if it works stay, if not we lost again. You get the idea. Once we hit one of the bold states we just keep an eye out for the starting node. Sooner or later it will come around or we run into a position where we cannot go further.
So when can we not go in one of the directions that is leading from our state? This is either the case if there is no edge in this direction (obv.) or the edge has already be used in this direction.
What does that last part mean now?
Well, to avoid any duplicates I made use of the winged edge data structure that is used in graphics programming a lot. Every edge has both directions saved and a bool variable that indicates whether it has been used in that direction already. Once it has it cannot be used in that direction again. But it might be used by the algorithm for a different allotment. Time for some drawing again.......

Now that's beauty. In this example we hit node 1 first and find the red rectangle to use as an allotment. When we visit node 2 we cannot follow the algorithm anymore. If we had found node 2 first we would find the red rectangle as well. And node "3" will find the green rectangle. Note that no other node than those three would deliver anything as a result.
OK. So if you're still following me... Do think this is the best way to do it? Or even a good one? Do you know a better way? Took me some time to figure this out.
Also tried to abuse the A* algorithm but there was no way to efficiently do that that always delivered the right result.

OK, would be nice if you left a comment about this uncommon algorithm i brewed up. Oh, and I'm currently thinking of getting Dragon Age 2 for the 360 since it's now only 20€. Is it worth its money? Looking for a cheap way to pass some time while my gf is gone ;)

So long

P.S.: I hope I can present you a first glance at the city skyline the next time

Mittwoch, 18. Juli 2012

So, it's done. Last exam, ever. A lot of memory management in this exam, did expect more quaternion integration. Whatever! Expect more updates now.

Dienstag, 10. Juli 2012

Today, I won't be writing about procedural content generation. 
Currently I'm preparing for my last exam named "Game programming". It handles topics like nav-graphs, behavior trees, quaternions, resource management and differential equations. So I don't have a lot of time working on my bachelor thesis. But it is almost done anyway. I'm a little behind with my description in my postings.

So for the time after my exam and especially for when I'm finished with my bachelor thesis I am looking for some skilled people for a small game project based on some techniques used in my thesis. I have a very vague idea of the game but I'm very sure it will be done for the PC and the Xbox using XNA.
So, I'm looking mainly for artists. But also if you are a game designer or a programmer that is interested in joining up with me for a small indie title. 
So what will the game be about. It will be a first or maybe third person adventure/puzzle game. When I was little I loved to do those labyrinth puzzles in kids magazines. I want to blow some action into this kind of puzzle game and place a character in a 3D environment in such a labyrinth. Additionally to finding his way out of the maze he also has to evade some kind of monster. He cannot shoot or fight the monster... he can only run away from it and trick its AI (kinda like in Pacman). There could be more gimmicks for the player like marking positions for his orientation or portals through walls.
The labyrinth could rotate sometimes making creating new dead ends and new passage ways. 
Infinite possible mazes could be created by procedural content. 
So again: if you're interested in joining up please message me or write me an email. 

Montag, 25. Juni 2012

Welcome back again. In my last post I wrote about L-Systems and how they can be used to create a street network. Or at least a string of characters that "should" represent such a network.
I give you an example for such an L-System.
Symbols that are terminal are: {'[', ']', '+', '-'}
Symbols that can be derived are: { 'S()' }
I use a parametric L-System which behaves differently for whatever parameters come with the derivable or non-terminal symbols.
As I explained in my last post the axiom with which the system starts to evolve depends on which coordinates the transitions between the CityBlocks have.
You might be thinking "wtf are you talking about, what do those symbols mean, what's an axiom". Yea, I'll explain that now. It's easier than it looks. We got a CityBlock which is just fills some space in our world. A pane with a texture if you want. And we have generated four pairs of coordinates with each of them lying at a different edge of the CityBlock. Now the give those coordinates to our L-System and it creates the following axiom which stands for a street network:
Doesn't look like a street network to you? To me neither. Later interpreted it will look like this:
Basic street network. Arrows hint at the transitions between blocks.
Not quite a street network either but at least some streets.
So what the string means is: Starting at the west entry position go 8 straight, remember the position, turn counter-clockwise, go 33 straight, return to remembered position... and so on.
So S(x) means "Go x units straight".
"[" and "]" will help us create intersections and such. So we can describe what happens after turning some direction and then returning to the point where the intersection was to follow the other paths. If this was a classic "plant"-L-System this is the equivalent to a branch.
And "+" means turn clockwise, while "-" means turn counter-clockwise.
That's all there is to it. 
Note that of course I did make abstractions. Traffic circles do not exist in my world. Also a street always enters another street in a angle of 90°. The bends could still be a little rounder but that's just the set of textures I'm using.

I think that's it for today on logic. Now I have just one last technical thing. In the beginning of my work on this I used distinct textures for all the types of streets I have. I had a texture for a road going straight from north to south, a texture for a t-intersection, a texture for a bend from south to east and so on. To save some time in my draw method I made a texture atlas, so I had all the graphical information I need in one texture.
Now I have just some tiny visible transition between the elements whereas before they were not visible at all. I don't know if they come from some kind of compression XNA uses when it compiles the assets or if I have some error in my code. Maybe you have some knowledge about this? If yes, leave me a comment. 
I'll try to get some code samples of this in my next post.

So long nighttime fellas!