Saturday, March 19, 2011

Writing Architecture

If you were the last person in the world, would you build a parser?

It is only me using this engine at this point. There is no UI for any of the things you can define for the virtual world. Not even configuration files, XML, INI, etc. It is all a  big soup of C++ code. To me it is the same to change a value in a C++ file than to edit a configuration file.

Then I started working on the architecture L-System. Soon I realized that writing grammars in C++ was not very good. They were extremely verbose and hard to read. It would be better if the grammar was written in a language designed just for that. For the first time in this project, I started considering parsing from an external file.

Luckily I remembered an old trick. I saw it long time it in ancient UI systems to define menu structures. The trick is to define functions that always return the state you are building, so you can chain their calls.

For instance, you can have a construct like:

begin("house").
divide_y("80% 20%", "living_area roof").
end();

It is really three functions being chained one after the other, but it looks like an structured construct. The "begin" function returns a new rule object with the specified name, in this case "house". Then the "divide_y" function is called in the rule to specify a house will be divided in two spaces, the living area and the roof. The function also returns the rule, so if we wanted to add more instructions we could do it right there. Then the "end" function returns the grammar object so a new rule can begin.

It is quite simple to use, the grammars are easy to read and you get all the help from the C++ compiler. Even the intellisense kicks in and gives you hints about function signatures. Also it allows to move into a different format in the future, even a dynamic UI. What changes is how the grammar objects are created, nothing more.

Just so you get a feeling of the written grammars, I leave you with the rules that define the church of my earlier screenshots. This is just the main module for the church. It references other modules that I did not include here. In a future post I will explain what these functions actually do.


begin("church").


// main space
push().
occludes().
center().
scale("90%", "100%", "70%").
box().
select("face_x", "nave_walls").
select("face_z", "nave_facade").
push().
move("0", "100%", "0").
loft_box("80%", "100%", "0%").
select("face_x", "thin_wall").
pop().
pop().


// transept
push().
move("10%", "0", "0").
push().
occludes().
center().
rotate_y("90").
scale("70%", "100%", "50%").
box().
select("face_x", "transept_walls").
select("face_z", "transept_facade").
push().
move("0", "100%", "0").
loft_box("80%", "100%", "0%").
select("sides", "thin_wall").
select("prism_sides", "prism_cap").
pop().
pop().
pop().


// towers
push().
move("0", "0", "100%").
push().
scale("tower_width", "300%", "tower_depth").
move("0", "0", "-50%").
module("tower").
pop().
pop().


push().
push().
scale("tower_width", "300%", "tower_depth").
module("left_tower").
move("0", "0", "-50%").
pop().
pop().


// apse
push().
move("20%", "0", "0").
push().
occludes().
center().
scale("130%", "100%", "130%").
ngon("18").
select("sides", "nave_wall").
push().
occludes().
move("0", "100%", "0").
move("0", "0.5", "0").
loft_ngon("18", "100%", "0%").
select("sides", "thin_wall").
select("prism_sides", "prism_cap").
pop().
pop().
pop().
end().

15 comments:

  1. I was curious about the double push() calls, like on the tower for example, does that embody some sort of hidden state in your interpreter?

    It occurs to me that now that you have an engine driven by these chained calls, it should now be trivial to write either a small language to drive the underlying machinery, especially since it looks like your system doesn't support expressions like move(sin(t) + x, 0, 0) directly - it would have to be contrived with string conversions :)

    I think the main advantage you would have with an interpreter is that you could keep your main application running, and as you tweak your grammar, you could just hit a refresh key - that's go to be more productive than the compile, link, run cycle once your architecture gets as busy as this very nice looking church has got.

    ReplyDelete
  2. When can I start using this new language? :-D
    Seriously, I have some great practical applications that could use a programming language in this way of writing, which isn't possible with other languages. This is some serious stuff.

    ReplyDelete
  3. @Nick: The push() and pop() map directly to commands for the L-System execution machine. At any time the machine holds a state called the current "scope". This is little more than a volume definition with its own coordinate system. Pushing will save the current state so further transformations will be reverted once the matching pop() is executed. If you are familiar with the OpenGL state machine, it is similar to pushing and popping OpenGL states.

    As you pointed out, this format does not allow for complex expressions. I could start parsing them, but that defeats the point. I think you can go very far with just external variables, like "tower_width", and clever use of percentages. So I'm trying to stay out of complex expressions for now and see if I can pull it off.

    I also agree with your last point. For someone working on the grammars it would be easier to just reload a text file and see the results without having to restart the program. But then again, it is only me for now. It does not really make a difference. I just edit one file and press F5 (compile and run) and see the results. Anyway the entire building has to be re-created, so time-wise there is no much difference. Also it is nicer to have the aid of intellisense.

    So I will probably skip the part using my own syntax in an external file. If anyone ever needs to use this system, I would create a WYSIWYG editor where the grammar can be defined. Then it could be saved even in binary, no need for any syntax.

    ReplyDelete
  4. In the past, I've taken this one step further:

    drawText("Hello world!").at(100,100).color(1,0,0).align(ALIGN_LEFT);

    drawText returns (by value) a drawTextSettings structure with fields for all the settings you'll want to set. The other functions all simply modify it in place, and return it by reference.

    And the magic part: its destructor actually does the drawing command!

    ReplyDelete
  5. i've used this technique before in production enviroment (a wii game). a little advice: if you write too much code structures like that you will be running out of heap/stack allocation anytime soon. if you plan to code *a lot* of l-systems you will have to move the declarations to external files at some point. anyways, great blog; i will be following you :)

    ReplyDelete
  6. @rlyeh: I have used this in production too, and when stack sizes were tiny a fraction of what they can be today. Yes, I'm that old.

    I have no worries about the stack. To make sure it won't ever become a problem I keep the chains to a single module. That means the entire set of grammars is not into a single chain. So you do see a ";" from once in a while.

    For heap this approach makes no difference, even if it was parsed you need to keep the internal form in the heap for execution later.

    As long as I continue working alone I still don't see a need for a parser. If I ever need to bring artists into the workflow I don't want them to be crippled by learning a syntax and having to write code. I would build a visual editor for the rules so they can do what they do best.

    Odds are I won't be needing a parser after all, but time will tell.

    ReplyDelete
  7. This is called a "fluent interface". It's akin to writing a DSL, but you do it entirely within the construct of your API, in your language.

    ReplyDelete
  8. @Wouter: That's correct. If you want to know more about this trick check out the comments it generated at Reddit, there are some nice points there (as usual with Reddit just ignore the ones about zombies): http://www.reddit.com/r/programming/comments/g732e/if_you_were_the_last_person_in_the_world_would/

    ReplyDelete
  9. Your work is really inspiring. Before finding your blog I'd been reading the some of the papers on the topic (Muller in particular), and it's great to see you putting it into practice.

    Been attempting to make little villages with bridges etc, but being primarily an artist, I've been struggling to put into practice, so your posts have been very helpful. :]

    I was just wondering, what does your function 'occlude' do, does it replace the current element? Are you just moving around scopes, and then replacing them with objects at a later part of the program (not shown here)?

    ReplyDelete
  10. @Brendan: A call to "occludes()" means the current scope will occlude other scopes. A rule may then have the "if_occluded()" clause, which will make the rule be selected if the scope intersect with any of the occluding scopes.

    As you noticed, the snippet in this post only moves scopes, it does not instance any particular geometry. This happens in other rules for the grammar. But yes, this is pretty much what I do, define scopes and use replace them by object geometry.

    I will come back to the topic of architecture soon, hopefully then you will get more details on this implementation.

    ReplyDelete
  11. Awesome. So I'm guessing that'd be like a boolean value in the scope.

    You mentioned in another post that you were interested in doing interiors. Did you see Jess Martin's thesis on generating building interiors? It might help.

    ReplyDelete
  12. So I'm guessing "church" is your axiom.

    Are you making a collection of scopes, or are they nested within each one? How do you know when you're at a terminal symbol? Would your terminal symbols be the final a geometric shapes?

    I feel like I'm quizzing you for all your trade secrets. :P

    ReplyDelete
  13. @Brendan: Yes "occludes" just sets a boolean flag for the scope. This is a simple way I found to control which scopes really occlude other scopes. It also helps speed up scope intersection tests, since you only need to test against the occluders.

    The link you posted does not work. Can you repost it please?

    As you noticed, "church" is the axiom for the church screenshots I have posted.

    I am making a tree-like hierarchy of scopes. In most cases the final nodes will be a call to the "instance" method, which brings actual geometry into the scope. Sometimes an end node does nothing, this is often needed to leave holes in the resulting structure.

    ReplyDelete
  14. Neat idea with the occlusion.

    Been attempting to do abit of reverse engineering today based on this post, I hope you don't mind! I did some searching and found it was called a 'Fluent Interface': http://hilloldebnath.byethost3.com/2009/08/20/implementing-the-fluent-interface-approach-in-java/

    So now basically each scope contains a list of more scopes. We'll see how that goes.

    Sorry about the link! https://github.com/jessmartin/writings/raw/master/pcg_paper/generative.pdf

    It's really interesting. The whole idea of using graphs sparks my thinking about my elevated village. I really want to find a way to make a sort of 'networked' L-system that can interconnect so that I can crazy networks of bridges, ladders and treehouses. Most of the stuff I've seen in terms of shape grammar is all about subdivision, which is fine for stand-alone buildings, but I don't know if it's possible to do what I'm wanting with that alone...

    You mentioned you felt like you had a brick and were trying to get us to imagine the house. I feel like I have a little glob of clay and want you to imagine the brick.

    ReplyDelete
  15. My last comment didn't seem to have shown up, so sorry if this is a double post.

    Yeah, Muller mentioned the empty nodes, which is a neat idea.

    I've been attempting to do some reverse-engineering of your code snippets today, I hope you don't mind. The way I was going was to give each scope a label, a bounding box, and a list of child scopes. Dunno if that's the best way. I'm struggling on the push and pops, but I think a good nights sleep might help there.

    I guess innovation requires a bit of appropriation, so I'm grateful for your blog posts.

    I did some googling on the chained calls, and apparently it's referred to as a 'fluent interface': http://hilloldebnath.byethost3.com/2009/08/20/implementing-the-fluent-interface-approach-in-java/

    Here's the link: https://github.com/jessmartin/writings/raw/master/pcg_paper/generative.pdf I think it might be helpful to you.

    His graph idea is kind of neat. I'm thinking it might help with the elevated village thing I'm working on. Loads of the shape grammar stuff is all todo with subdivision, but I'm not sure it'd work so well for complex network of bridges, ladders and houses I want. I think what I'm after is some sort of networked l-system. I dunno. At least my stuff is in 2D so it's a little easier.

    You mentioned you feel like your showing off a brick and expecting us to imagine the house. If that's true, I feel like I'm showing off a tiny ball of clay.

    ReplyDelete