python - Sierpinski 的三角形 Pygame 递归

Question

因此，对于我目前的大学论文，我们打算创建一个 Sierpinksi 三角形并在其中递归绘制新三角形。

我们得到的原始代码是这样的:

import sys, pygame

# a function that will draw a right-angled triangle of a given size anchored at a given location
def draw_triangle(screen, x, y, size):
        pygame.draw.polygon(screen,white,[[x,y], [x+size,y], [x,y-size]])

############################################################################################# 
# Define a function that will draw Sierpinski's Triangle at a given size anchored at a given location
# You need to update this function 
# currently only one triangle is drawn

def sierpinski(screen, x, y, size):
        draw_triangle(screen, x, y, size)

############################################################################################# 

# Initialize the game engine
pygame.init()

# Define the colors we will use in RGB format
black = [ 0, 0, 0]
white = [255,255,255]
blue = [ 0, 0,255]
green = [ 0,255, 0]
red = [255, 0, 0]

# Set the height and width of the screen
size=[512, 512]
screen=pygame.display.set_mode(size)

# Loop until the user clicks the close button.
done=False
clock = pygame.time.Clock()


while done==False:

    # This limits the while loop to a max of 10 times per second.
    # Leave this out and we will use all CPU we can.
    clock.tick(10)

    for event in pygame.event.get(): # User did something
        if event.type == pygame.QUIT: # If user clicked close
            done=True # Flag that we are done so we exit this loop

    # Clear the screen and set the screen background
    screen.fill(black)

    # Draw Sierpinski's triangle at a given size anchored at a given location

    sierpinski(screen,0, 512, 512)

    # Go ahead and update the screen with what we've drawn.
    # This MUST happen after all the other drawing commands.
    pygame.display.flip()

# Tidy up
pygame.quit ()

好的，我知道这只会创建一个三角形。这是我为使其“有点”工作所做的工作:

我创建了一个新的三角形函数来绘制一个倒三角形:

def draw_upside_down_triangle(screen, x, y, size, color):
        pygame.draw.polygon(screen, color, [[x+size, y+size], [x+size, y], [x, y]])

然后我更新了旧的三角形函数以接受颜色变量:

def draw_triangle(screen, x, y, size, color):
        pygame.draw.polygon(screen, color, [[x, y], [x+size, y], [x, y-size]])

之后我更新了递归绘制三角形的主函数:

def sierpinski(screen, x, y, size):
    if size < 10:
        return False
    else:
        draw_triangle(screen, x, y, size, white)
        draw_upside_down_triangle(screen, x, y/2, size/2, black)
        sierpinski(screen, x+size/2, y+size/2, size/2)
        sierpinski(screen, x, y-size/2, size/2)
        sierpinski(screen, x, y, size/2)
        sierpinski(screen, x, y+size/2, size/2)

我关闭了这个功能

1. 通过添加退出参数(当三角形太小时返回 false)
2. 如果不是太小就用白色画第一个三角形
3. 然后用黑色在相同的 x 位置画一个一半大小但 y 位置一半大小的倒三角形(这会产生 3 个三角形错觉)
4. 在所有这一切之后，我进行了 4 次递归调用，根据实验，我知道这些调用的顺序很重要，因为在更改时输出会发生根本性的变化。

此时当前输出如下:

我不要求任何人完成或更正我的代码，只是为了更好地理解或指出正确的方向。已经与这个问题斗争了几个小时。

谢谢!

Answer 1

查看以下实现 Sierpinski 三角形的链接...

http://interactivepython.org/runestone/static/pythonds/Recursion/graphical.html#sierpinski-triangle

围绕这个问题进行了很多很好的讨论，并编写了 40 多行代码来实现它。

另外，由于 turtle 模块的工作方式，您可以看到每个三角形被一个接一个地绘制。这在您查看代码时非常有帮助，因为您可以直观地看到递归级别及其发生时间。我不知道这在 pygame 中实现起来有多难，但如果你可以放慢三角形的创建速度，那么理解逻辑就会容易得多。

你说你需要基于实验的 4 个递归调用，但你能解释一下它背后的逻辑吗？直觉上这似乎是错误的，因为您只需要三个新三角形加上一个部分覆盖的父三角形就等于四个较小的等边三角形。 (在链接中查看这是如何完成的？)

您能解释一下为什么要使用倒三角法吗？这似乎有点像一个容易出错的解决方法？您应该能够使用正常三角形函数中的负空间绘制倒三角形。在链接中，您会看到作者绘制了一个绿色三角形，它与其他所有东西都朝向相同的方向，但后来用更多三角形覆盖它，直到绿色三角形朝向相反的方向。

总而言之，您看起来很接近。您只需要正确处理最后一段递归逻辑即可。

附言

一个次要的次要风格批评 - 仅因为这是用 python 编写的并且可读性很重要。您可以使用 While True 然后使用 break 来避免额外的变量 done。