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:
[attachment=10568:FSM_Grundstucke_small.png]
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 20EUR. Is it worth its money? Looking for a cheap way to pass some time while my gf is gone ;)
So long
ExcelF
P.S.: I hope I can present you a first glance at the city skyline the next time
