How is L-systems for road networks modified?

Question

Greetings each and all!

I'm currently looking into procedural generation of a road network and stumbled upon the L-system algorithm. From what I understand from various scientific papers on the subject, and further papers on the papers on the subject, the algorithm is changed to use "global goals and local constraints", in which the taken path is modified to fit input values such as terrain and population density. Now that part I understand, or atleast the overall concept, but how am I supposed to modify the algorithm?

Right now I have a string which is modified over timesteps according to a set of rules. I then analyze the string and move and turn as I go through the chars, render the result and get beautiful patterns on screen.

Now, to create a network of major roads, should I still use a base axiom with a ruleset and then apply the constraints? And if so, what could a set of good startvalues and rules be?

Or should I rather replace the basic ruleset with the constraints and global goals? And if so, what remains of the original L-system algorithm?

Any help is greatly appreciated, and for the record I'm doing this in C# and XNA, allthough I reccon this is more on a theoretical plane.

Thanks for your time,

Karl

Gushy

Answer 1

So, I've been googling, reading and understanding more the last week and I've found a solution to the problem which I thought I might share. I found this brilliant blog post which basically straightened everything out for me:

http://www.newton64.ca/blog/?p=747#7472

That post is based upon another blog post founded here:

http://mollyrocket.com/forums/viewtopic.php?t=730&sid=a9a2628b059a727cbde67309757ed178

Now, as far as the L-system goes, I'm not quite sure whether this approach really is an L-system anymore. Sure, there are similarities regarding the iterative process of building the network. In L-systems the string grows over iterations and branches are created using "[" or "]" (atleast in the cases I've seen), and in the approach I'm taking now a while-loop and a priority queue does pretty much the same thing.

I also would like to point out that I did not fully understand the papers "describing" how to use an L-system for generating a road network, so my reasoning might be a bit off here. But algorithm naming and boundries aside, I found a solution that works for me, which is good for now.

Happy coding!

Karl

Gushy

Please see this other L-system question: #15152458 – Pino

Both links are sadly now no longer available, but I was able to find the former on the wayback machine if it's of any use to future readers: web.archive.org/web/20130827130016/http://www.newton64.ca/blog/… – Shiller

Update - this could potentially be the missing molly rocket post - nothings.org/gamedev/l_systems.html – Shiller

Answer 2

I'm the author of the above blog post -- glad you found it useful! I never did get around to finishing Spare Parts -- and if nothing else, I'd have to change the name -- but you've got me thinking about it again.

Certainly, the algorithm I described probably isn't much of an L-system anymore; importantly, though, I think it's pretty much functionally equivalent. I'm a positivist when it comes to programming, so if it works, compile it!

EDIT: I've since taken down my old website, but I've recreated the post here. Hope it's still helpful!

Michellemichels

Nice to hear from you. First of all, I suppose I owe you a beer now, and I'll gladly buy you one as your post solved my problem. Secondly, you should really take up Spare Parts (with another name), sounds interesting. I really like your attitude towards coding. I tend to do the same myself. I've been struggling with the global goals and local constraints to make a neat road network, and things are getting there. I really like how a complex problem is broken down into smaller pieces of simple math like this. Thanks again! – Gushy