Overlapping trees in L-system forest

Question

I created an a program using python's turtle graphics that simulates tree growth in a forest. There's 3 tree patterns that are randomly chosen, and their starting coordinates and angles are randomly chosen as well. I chose some cool looking tree patterns, but the problem I'm having is that many of the trees are overlapping, so instead of looking like a forest of trees, it looks like a bad 5 year old's painting.

Is there a way to make this overlapping less common? When you look at a forest, some trees and their leaves do overlap, but it definitely doesn't look like this:

Since there's a lot of randomization involved, I wasn't sure how to deal with this.

Here's my code:

import turtle
import random

stack = []

#max_it = maximum iterations, word = starting axiom such as 'F', proc_rules are the rules that 
#change the elements of word if it's key is found in dictionary notation, x and y are the 
#coordinates, and turn is the starting angle 

def createWord(max_it, word, proc_rules, x, y, turn):

    turtle.up()
    turtle.home()
    turtle.goto(x, y)
    turtle.right(turn)
    turtle.down()

    t = 0
    while t < max_it:
        word = rewrite(word, proc_rules)
        drawit(word, 5, 20)
        t = t+1


def rewrite(word, proc_rules):

   #rewrite changes the word at each iteration depending on proc_rules

    wordList = list(word)

    for i in range(len(wordList)):
        curChar = wordList[i]
        if curChar in proc_rules:
            wordList[i] = proc_rules[curChar]

    return "".join(wordList)


def drawit(newWord, d, angle):

    #drawit 'draws' the words

    newWordLs = list(newWord)
    for i in range(len(newWordLs)):
        cur_Char = newWordLs[i]
        if cur_Char == 'F':
            turtle.forward(d)
        elif cur_Char == '+':
            turtle.right(angle)
        elif cur_Char == '-':
            turtle.left(angle)
        elif cur_Char == '[':
            state_push()
        elif cur_Char == ']':
            state_pop()


def state_push():

    global stack

    stack.append((turtle.position(), turtle.heading()))


def state_pop():

    global stack

    position, heading = stack.pop()

    turtle.up()
    turtle.goto(position)
    turtle.setheading(heading)
    turtle.down()


def randomStart():

    #x can be anywhere from -300 to 300, all across the canvas
    x = random.randint(-300, 300)

    #these are trees, so we need to constrain the 'root' of each
    # to a fairly narrow range from -320 to -280
    y = random.randint(-320, -280)

    #heading (the angle of the 'stalk') will be constrained 
    #from -80 to -100 (10 degrees either side of straight up)
    heading = random.randint(-100, -80)

    return ((x, y), heading)


def main():

    #define the list for rule sets.
    #each set is iteration range [i_range], the axiom and the rule for making a tree.  
    #the randomizer will select one of these for building.

    rule_sets = []
    rule_sets.append(((3, 5), 'F', {'F':'F[+F][-F]F'}))
    rule_sets.append(((4, 6), 'B', {'B':'F[-B][+ B]', 'F':'FF'}))
    rule_sets.append(((2, 4), 'F', {'F':'FF+[+F-F-F]-[-F+F+F]'}))

    #define the number of trees to build
    tree_count = 50

    #speed up the turtle
    turtle.tracer(10, 0)

    #for each tree...
    for x in range(tree_count):

        #pick a random number between 0 and the length
        #of the rule set -1 - this results in selecting
        #a result randomly from the list of possible rules.

        rand_i = random.randint(0, len(rule_sets) - 1)
        selected_ruleset = rule_sets[rand_i]

        #unpack the tuple stored for this ruleset
        i_range, word, rule = selected_ruleset

        #pick a random number inside the given iteration_range to be the 
        #iteration length for this command list.
        low, high = i_range
        i = random.randint(low, high)

        #get a random starting location and heading for the tree
        start_position, start_heading = randomStart()

        #unpack the x & y coordinates from the position
        start_x, start_y = start_position

        #build the current tree
        createWord(i, word, rule, start_x, start_y, start_heading)

if __name__ == '__main__': main()

Answer 1

I think the problem lies more in the regularity of features among the trees themselves, rather than their placement per se.

A possible solution would be to add mutations. For a global control of "stunted growth", you could suppress say 5% of the production applications. This should give sparser trees that follow the model more loosely.

For finer control, you can suppress each production with a different weight.

Check out The Algorithmic Beauty of Plants section 1.7 Stochastic L-systems for more. They use probability to select among several variants of single rule.

Answer 2

From my understanding of an L-system there's a whole grammar that isn't randomly chosen. Could you provide details as to how your grammars work? I would imagine that you can somewhat restrict which directions your trees grow into by making a limited, closed-ended set of productions that go anywhere more than 90 degrees from the starting angle.

But then you can't totally randomize the starting angle... You probably need to just randomize it within a certain range? Of course if you have an L-system that just generates everything randomly, it's just gonna look like a bunch of noise. There's a purpose to putting a restriction on your initial conditions; every grammar has a start symbol, and you need to take advantage of your start symbol to generate stuff that makes sense. I'd imagine that you want your start symbol to always point up.

But I haven't studied L-systems in a long time, so take my answer with a grain of salt.

Edit:

That's an interesting restriction to impose, in that it sound like something that trees do naturally. In nature I think it happens because only a certain amount of sunlight can get through to a given patch of ground, so if a tree is already growing somewhere, nothing else can do so.

Being an AI guy, I love turning real-world solutions into interesting heuristics. What kind of a heuristic are we looking for here? Well, a "patch of ground" in a 2-d coordinate system is just a range of x-coordinates. Maybe have something that makes growth lose impetus if there's too much stuff within some arbitrary x range of a growing leaf? (not a python xrange, but a range of x-coordinates, some "delta" value if you will.)