如何递归地检查对象的属性？

Question

如何递归地检查对象的属性？

4

我一直在开发一个电路模拟器，类似于Minecraft的红石，但是是二维的。目前为止，我已经实现了电源和导线。电源会给导线供电，并在后面用于给其他组件供电。但是，我遇到的问题是，当导线与电源断开连接时，它仍然保持通电状态，因为它的所有相邻部分都通电。以下是图片表示这个问题：未连接电源的导线、已连接并通电的导线以及移除电源但导线仍处于活动状态。以下是导线的更新循环：

def update(self):
    self.powered=False
    for b in blocks:
        #Find power sources/powered wires
        if not b.powered:
            continue
        adjacent = False
        if b.rect.collidepoint(self.rect.left,self.rect.top-5):
            adjacent = True
        if b.rect.collidepoint(self.rect.left,self.rect.bottom+5):
            adjacent = True
        if b.rect.collidepoint(self.rect.left-5,self.rect.top):
            adjacent = True
        if b.rect.collidepoint(self.rect.right+5,self.rect.top):
            adjacent = True
        if adjacent:
            self.powered = True
            break
    if not self.powered:
        pygame.draw.rect(screen, (0,0,0), self.rect, 0)
    else:
        pygame.draw.rect(screen, (200,0,0), self.rect, 0)

我希望能通过其他电线为电线提供电力，但前提是它们都连接到一个电源。所以我想，如果每个电线段可以递归地检查它连接到的所有电线，以确保它连接到电源，那么我就可以实现这个目标。但我不确定该怎么做。

我尝试在电线对象内部使用其他变量，比如代表电线是否连接到电源的self.sourced，但结果只能给一根电线供电（即使当电源断开时，电线也会停止工作，所以它还算有效）。无论如何，如果有人知道如何做到这一点，请传授你的知识。

以下是完整的源代码，仅供参考：

import pygame
from pygame.locals import *

pygame.init()

screen=pygame.display.set_mode((640,480))
blocks=[]

class PowerSource(object):
    def __init__(self,pos):
        self.posx=pos[0]
        self.posy=pos[1]
        self.rect=pygame.Rect(self.posx,self.posy,32,32)
        self.powered=True
    def update(self):
        pygame.draw.rect(screen, (255,0,0), self.rect, 0)
    def repos(self):
        pass
class Circuit(object):
    def __init__(self,pos):
        self.powered=False
        self.posx=pos[0]
        self.posy=pos[1]
        self.rect=pygame.Rect(self.posx,self.posy,32,32)
    def update(self):
        self.powered=False
        for b in blocks:
            if not b.powered:
                continue
            adjacent = False
            if b.rect.collidepoint(self.rect.left,self.rect.top-5):
                adjacent = True
            if b.rect.collidepoint(self.rect.left,self.rect.bottom+5):
                adjacent = True
            if b.rect.collidepoint(self.rect.left-5,self.rect.top):
                adjacent = True
            if b.rect.collidepoint(self.rect.right+5,self.rect.top):
                adjacent = True
            if adjacent:
                self.powered = True
                break
        if not self.powered:
            pygame.draw.rect(screen, (0,0,0), self.rect, 0)
        else:
            pygame.draw.rect(screen, (200,0,0), self.rect, 0)
while True:
    place=1
    screen.fill((255,255,255))
    mse=pygame.mouse.get_pos()
    mse=((mse[0]/32)*32,(mse[1]/32)*32)
    pressed=pygame.mouse.get_pressed()
    if pressed==(1,0,0):
        pressed='L'
    elif pressed==(0,0,1):
        pressed='R'
    for b in blocks:
        b.update()
    pygame.draw.rect(screen, (255,0,0), (mse[0],mse[1],32,32), 2)
    for e in pygame.event.get():
        if e.type==QUIT:
            exit()
    key=pygame.key.get_pressed()
    if key[K_SPACE]:
        for b in blocks:
            if b.rect.collidepoint(mse):
                place=0
        if place==1:
            blocks.append(PowerSource(mse))
    if pressed=='L':
        for b in blocks:
            if b.rect.collidepoint(mse):
                place=0
        if place==1:
            blocks.append(Circuit(mse))

    elif pressed=='R':
        for b in blocks:
            if b.rect.collidepoint(mse):
                blocks.remove(b)
    pygame.display.flip()

- Sam Tubb

这并不是你的能力问题，但如果你开始使用更好的数据结构来保存你的块，我认为你会更容易处理一切。一个简单的方法是使用网格（如果空间为空，则让它保持“无”）。或者，如果这有太多的内存开销，你可以使用更聪明的东西，比如四叉树。 - Blckknght

2个回答

2

从我的经验来看，简短的答案是在对象中添加一个标志，指示它们是否已在递归算法中进行过测试。这是因为你可能会遇到循环。因此，在移除电源时，需要调用一个函数来“检查所有它所接触的块是否有电源”。每个块将设置自己的标志，表示“我已经被检查过”，然后查看它是否有邻居作为电源。如果它有一个邻居作为电源，则返回“是的，我有电源”。如果没有，则检查是否有任何邻居拥有电源，但仅当它们尚未被标记为已经被检查过时。然后它会查看任何返回值是否为“是的，我有电源”，如果是，则返回“是”，否则返回“否”并关闭。

- CodeMonkey

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- OEP · Accepted Answer

我认为你遇到了一些问题。

你可能需要一个包含数据结构（另一个类，而不仅仅是列表）来存储你的块，或者让你的块维护一个邻接表。我认为后者对于理解这个问题可能更容易，尽管也许前者对你来说更好，因为你需要能够删除块（邻接表需要大量的簿记）。但由于我觉得邻接表更容易，所以我选择它。 :)

一旦你掌握了这些，你应该编写另一个方法作为递归入口点。它可以非常简单。你可能需要做一些跟踪你所访问的地方的事情；在这里，我将其作为一个集合参数传递给该方法，假设邻接表称为 "neighbors"。

def is_connected_to_powered(self, visited=()):
    if self in visited:
        return False
    visited = set(visited)
    visited.add(self)
    for neighbor in self.neighbors:
        if neighbor.powered or neighbor.is_connected_to_powered(visited):
            return True
    return False

这回答了这个问题，但我可能还考虑从一个共同的基类（如Block）派生电路和电源，因为我怀疑正确的面向对象设计将在未来帮助您。