L-系统森林中的重叠树

Question

我用Python的turtle图形创建了一个程序，模拟森林里树木的生长。有3个随机选择的树型，它们的起始坐标和角度也是随机选择的。我选择了一些看起来很酷的树形，但问题在于许多树木重叠在一起，所以它看起来像一幅糟糕的5岁儿童的画作。

有没有办法使这种重叠较少发生呢？当你观察森林时，有些树木和它们的叶子确实会重叠，但绝对不应该看起来像这样：

因为涉及到大量的随机性，我不确定该如何处理这个问题。

以下是我的代码：

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()

- mdegges

Answer 1

我认为问题更多地在于树木本身特征的规律性，而不是它们本身的位置。

一个可能的解决方案是添加变异。为了全局控制“发育不良”，你可以抑制5%的生产应用程序。这应该会得到更稀疏的树，且更松散地遵循模型。

对于更细致的控制，您可以使用不同的权重来抑制每个生产应用程序。

请查看植物的算法美学第1.7节随机L系统以获取更多信息。他们使用概率来选择单个规则的几种变体。

- luser droog

Answer 2

据我对L系统的理解，整个语法都不是随机选择的。您能详细介绍一下您的语法是如何工作的吗？我想您可以通过创建一个有限的、封闭的产生式集合来在一定程度上限制树木生长的方向，使其不会超过起始角度90度以上的任何地方。

但是您不能完全随机化起始角度...您可能需要在某个范围内随机化它？当然，如果您有一个只生成随机内容的L系统，那么它看起来就像一堆噪音。对于您的初始条件施加限制是有目的的；每个语法都有一个起始符号，您需要利用起始符号生成有意义的东西。我想您希望您的起始符号总是指向上方。

但是我已经很久没有学习L系统了，所以请谨慎对待我的回答。

编辑：

这是一种有趣的限制，因为它听起来像是树木自然而然做的事情。在自然界中，我认为这是因为只有一定量的阳光可以透过给定区域的地面，因此如果一棵树已经在某个地方生长，其他什么也不能生长。

作为一个AI专家，我喜欢将真实世界的解决方案转化为有趣的启发式算法。我们在寻找什么样的启发式算法呢？嗯，在二维坐标系中，“一块地”就是一定范围内的x坐标。也许有些东西会使生长失去动力，如果在生长叶子的某个任意x范围内有太多的物质存在的话？（不是Python xrange，而是x坐标的范围，一些“delta”值，如果您愿意的话。）

- machine yearning

---

我在代码中对所有随机化都进行了范围限制，否则树木将不会真正看起来像树。它们都受到限制，使得树木能够保持站立状态并从画布底部开始。但是我想知道是否有一种方法可以限制可以从相同坐标开始的树木数量...就像有一个检查，如果已经在这里建造了一棵树，再次选择随机坐标，以便树木不会彼此重叠太多。 - mdegges

你懂的！在另一棵树的树干中间长出树木也是不现实的——在自然界中绝对不会发生这种情况。这就是我正在寻找的解决方案——我不太确定如何实现，但我喜欢这个想法。我想要在创建一棵树之后“划掉”它的坐标，这样当另一棵树试图在它的位置上长出时，它将无法生长。它将必须重新随机化，获得新的坐标。 - mdegges

我认为你可以通过保留一个计数器对象（参见collections模块）来实现简化版本，该对象表示您的x范围。这样，您可以为每个x“桶”递增计数器对象，以表示分支进入/穿过的位置。然后，如果达到某个任意的关键x密度（如果任何计数器超过某个特定值），您的L系统可以默认为“死亡”状态。 - machine yearning

谢谢你的建议。我正在研究collections模块，并会随时向你更新。 - mdegges

我最后只是随机改变了一棵树的颜色，并将最大树木数量改为30。为了解决这个问题，我考虑将画布分成一个网格，并在每个区域放置一棵随机的树。但由于迭代是随机的（我将边界从2、6改变了），有些树可能会变得非常大并且长得很高（进入其他网格区域），而有些可能会非常小。所以最后仍然会有很多重叠...或者甚至在某些区域中树木太小，不够密集。 - mdegges