L-Systems Considered Harmful

I have no idea what the authors’ intent is. I assume it’s one of the first two, presumably the second. I assume it’s not the third, because the third is a bunch of work, and if you think that’s the way to do it, why wouldn’t you do that work in the paper, rather than make everyone do it themselves?

Of course, a paper can only be so long, and the L-system formulation is small and precise, so maybe you assume #3 but don’t spell it out because that’s busywork that wastes space in the paper. But, I’d argue, at least for the above formula, I don’t think the authors ever spelled it out. In fact, it turns out that the L-system above isn’t even really an L-system at all, as is obvious if you try to reduce it. Maybe implementing it as an L-system made it easier for them to prototype or something, but if there was any value there, it’s gone now.

To demonstrate this, I am going to apply mode #3, and we will see where it takes us. (Or you can skip to the end of this post and see the punchline.)

Let me first rewrite the rules in something a little less compact, more readable, but largely unchanged. I’m going to re-order the production rules and put the most complicated ones last just to make it a tad more readable (since all the production rules are applied in parallel, the order doesn’t matter, but I’ll keep the original numbering for clarity).

Initial state:

[ road(0, ra) query(qa, UNASSIGNED) ]

rules:

1. delete road(x,ra) if x < 0
3. delete road(x,ra) if followed by query(qa, FAILED)
4. decrement x in branch(x, qa, ra) if x > 0
5. replace branch(x,ra,qa) with subtree [road(x, ra) query(qa, UNASSIGNED)] if x == 0
6. delete branch(x,ra,qa) if x < 0
7. delete query(qa,state) if preceded by road(x,ra) and x < 0
9. delete query(qa,state) if state != UNASSIGNED
8. use local constraints(qa) to update query(qa,UNASSIGNED) to query(nqa,state)
2. given road(x,ra) query(qa,SUCCEED):
     run globalGoals(qa,ra) to compute pdel[3], nqa[3], nra[3]
     replace road(x,ra) with:
         segment(ra.angle, ra.length)
         branch(pdel[1], nra[1], nqa[1])
         branch(pdel[2], nra[2], nqa[2])
         road(pdel[0], nra[0])
         query(nqa[0], UNASSIGNED)

3. delete road(x,ra) query(ini_query, FAILED)
2. given road(x,ra) query(qa,SUCCEED):
      run globalGoals(qa,ra) to compute pdel[3], nqa[3], nra[3]
      replace both tokens
          segment(ra.angle, ra.length)
          branch(pdel[1], nra[1], nqa[1])
          branch(pdel[2], nra[2], nqa[2])
          road(pdel[0], nra[0])
          query(nqa[0], UNASSIGNED)

There are similar things that can be done, but we quickly notice now that road&query are always a pair anyway; for example production #1 and production #7 make it look like more flexible updating is happening, but in fact they’re just always updated as a pair. So we replace them with roadq(x,ra,qa,state):

Initial state:

roadq(0, ra, qa, UNASSIGNED)

rules:

1. delete roadq(x,ra,qa,state) if x < 0
3. delete roadq(x,ra,qa,FAILED)
4. decrement x in branch(x, qa, ra) if x > 0
5. replace branch(x,ra,qa) with subtree [roadq(x, ra, qa, UNASSIGNED)] if x == 0
6. delete branch(x,ra,qa) if x < 0
7. [implied by 1]
9. [folded into 2,3]
8. use local constraints(qa) to update roadq(x,ra,qa,UNASSIGNED) to roadq(x,ra,nqa,state)
2. given roadq(x,ra,qa,SUCCEED):
       run globalGoals(qa,ra) to compute pdel[3], nqa[3], nra[3]
       replace roadq(x,ra, qa, SUCCEED) with:
           segment(ra.angle, ra.length)
           branch(pdel[1], nra[1], nqa[1])
           branch(pdel[2], nra[2], nqa[2])
           roadq(pdel[0], nra[0], nqa[0], UNASSIGNED)

Since branch(x,. . .) only decrements x if it’s greater than 0, the only way it can become negative and invoke rule 6 is if it’s created negative. Since it’s never used for context, we delete rule 6 and replace rule 2:

2. given roadq(x,ra,qa,SUCCEED):
       run globalGoals(qa,ra) to compute pdel[3], nqa[3], nra[3]
       replace road(x,ra) with:
           segment(ra.angle, ra.length)
           if (pdel[1] >= 0) branch(pdel[1], nra[1], nqa[1])
           if (pdel[2] >= 0) branch(pdel[2], nra[2], nqa[2])
           roadq(pdel[0], nra[0], nqa[0], UNASSIGNED)

Similarly, the roadq deletion rule in #1 can only occur if the roadq is installed negative. Because we’ll never run branch with a negative, rule #5 will never install a negative roadq, so the only place it can appear is in rule 2, so we remove rule #1 and update the last line of rule 2:

if (pdel[0] >= 0) roadq(pdel[0], nra[0], nqa[0], UNASSIGNED)

Here’s the current rule set:

3. delete roadq(x,ra,qa,FAILED)
4. decrement x in branch(x, qa, ra) if x > 0
5. replace branch(x,ra,qa) with subtree [roadq(x, ra, qa, UNASSIGNED)] if x == 0
8. use local constraints(qa) to update roadq(x,ra,qa,UNASSIGNED) to roadq(x,ra,nqa,state)
2. given roadq(x,ra,qa,SUCCEED):
       run globalGoals(qa,ra) to compute pdel[3], nqa[3], nra[3]
       replace road(x,ra) with:
         segment(ra.angle, ra.length)
         if (pdel[1] >= 0) branch(pdel[1], nra[1], nqa[1])
         if (pdel[2] >= 0) branch(pdel[2], nra[2], nqa[2])
         if (pdel[0] >= 0) insert roadq(pdel[0], nra[0], nqa[0], UNASSIGNED)

8. given roadq(x,ra,qa,UNASSIGNED):
       run localConstraints(ra,qa) to compute nqa,state
       replace roadq(x,ra,qa,UNASSIGNED) with
          if (state != FAILED) roadq(x,ra,nqa,state)

4. decrement x in branch(x, qa, ra) if x > 0
5. replace branch(x,ra,qa) with subtree [roadq(x, ra, qa, UNASSIGNED)] if x == 0
8. given roadq(x,ra,qa,UNASSIGNED), delete it and:
       run localConstraints(ra,qa) to compute nqa,state
          if (state == SUCCEED) 
             { run globalGoals(qa,ra) to compute pdel[3], nqa[3], nra[3]
               insert segment(ra.angle, ra.length)
               if (pdel[1] >= 0) insert branch(pdel[1], nra[1], nqa[1])
               if (pdel[2] >= 0) insert branch(pdel[2], nra[2], nqa[2])
               if (pdel[0] >= 0) insert roadq(pdel[0], nra[0], nqa[0], UNASSIGNED)

Now, if we change from turtle-style motion with nesting at [] (i.e. [] means save/restore a turtle state) to assuming explicit coordinates are stored in the roadq()s and segments(), we can get rid of the [] calls entirely. In that case, we can migrate the decrement from branch to roadq, and get rid of branch().

4. decrement x in roadq(x, qa, ra, state) if x > 0
8. given roadq(x,ra,qa,UNASSIGNED) with x = 0, delete it and:
       run localConstraints(ra,qa) to compute nqa,state
          if (state == SUCCEED) 
             run globalGoals(qa,ra) to compute pdel[3], nqa[3], nra[3]
             insert segment(ra.angle, ra.length)
             if (pdel[1] >= 0) insert roadq(pdel[1], nra[1], nqa[1], UNASSIGNED)
             if (pdel[2] >= 0) insert roadq(pdel[2], nra[2], nqa[2], UNASSIGNED)
             if (pdel[0] >= 0) insert roadq(pdel[0], nra[0], nqa[0], UNASSIGNED)

Now, at this point, we still have an L-system, just one that’s been augmented with this support that when you write out the replacement for an existing module, you can conditionally choose whether certain things are written, and one where we’ve removed the turtle-graphics style information and assumed it’s all tracked explicitly by globalGoals().

But what should be clear is that, by adding these small L-system features and mechanically simplifying the rules, we’ve simplified it down to the point where it’s hardly an L-system at all.

In fact, we can now express it as an actual pseudocode algorithm, rather than an L-system, which has the advantage that it’s clear what exactly it does (rather than the behavior being buried in interactions of productions), and understanding it doesn’t require understanding L-systems.

So here is their actual algorithm:

initialize list of roadqueries L to a single entry:
    roadq(0,ra,qa)

initialize segment list S to empty

until L is empty
   for each entry R = roadq(x,ra,qa) in L
      if x > 0
         decrement x
      else
         L.delete( R )
         compute (nqa,state) = localConstraints(qa)
         if (state == SUCCEED)
            compute (pdel[3],nqa[3],nra[3]) = globalGoals(qa,ra)
            S.add ( segment(ra) );
            if (pdel[1] >= 0) L.add( roadq(pdel[1], nra[1], nqa[1]) )
            if (pdel[2] >= 0) L.add( roadq(pdel[2], nra[2], nqa[2]) )
            if (pdel[0] >= 0) L.add( roadq(pdel[0], nra[0], nqa[0]) )

We can now consider changing the algorithm. It currently spends a lot of time iterating the list and decrementing the x’s without doing any work (depending on the actual values of the xs). We can fix this. It’s possible that computing globalGoals() and localConstraints() will dominate the performance anyway (the list L may stay reasonably small, depending on the pdel values -- the performance of the original system, which left the segments() in the same list, was O(N^2)-ish though) so it doesn’t need fixing. But fixing it lets us express it more simply anyway. What we want to do is go ahead and add a timestep t that we increment every time through the loop, then instead of storing pdel and decrementing it, we store t+pdel and wait until t reaches that value.

Once we’ve got that, we can get rid of incrementing t and just use a priority queue:

initialize priority queue Q with a single entry:
    r(0,ra,qa)

initialize segment list S to empty

until Q is empty
    pop smallest r(t,ra,qa) from Q
    compute (nqa, state) = localConstraints(qa)
    if (state == SUCCEED) {
        add segment(ra) to S
        compute (pdel[3], nqa[3],nra[3]) = globalGoals(qa,ra)
        if (pdel[0] >= 0) add r(t+1+pdel[0], nra[0], nqa[0]) to Q
        if (pdel[1] >= 0) add r(t+1+pdel[1], nra[1], nqa[1]) to Q
        if (pdel[2] >= 0) add r(t+1+pdel[2], nra[2], nqa[2]) to Q

initialize priority queue Q with a single entry:
     r(0,ra,qa)

initialize segment list S to empty

until Q is empty
    pop smallest r(t,ra,qa) from Q
        compute (nqa, state) = localConstraints(qa)
        if (state == SUCCEED) {
            add segment(ra) to S
            addZeroToThreeRoadsUsingGlobalGoals(Q, t+1, qa,ra)

perhaps an inefficient L-system implementation was just fast enough for their purposes, so they stopped thinking about it after they built it?

It shoulld be easy to guess from my last version of the algorithm exactly what they’re doing (they can use the ‘pdel’ field to decide what order to expand roads in, since presumably roads are blocked/stopped by other roads so the order matters).

Also, it turns out that there’s apparently no magic in this L-system addressing the closedness itself, other than by doing that very blocking. None of that is easy to guess in the L-system version.

In fact, let me quote that bit you said above:

perhaps [. . .] they stopped thinking

Maybe they make more sense for plant synthesis. But I have a suspicion that most uses out there would turn out to be using similarly degenerate subsets that would be better expressed in other ways.