How to recursively check for attributes in an object?

Question

I've been working a circuit simulator, kind of like Minecraft's red-stone, but in 2d.

So far, I have power sources and wires. The power sources give power to the wire, which will later be used to power other components.

The problem I am facing is when the wire is disconnected from the source, it stays powered, because all of it's neighbors are powered.

Here is the issue represented in images:

Wire not connected to power

Wire is connected, and powered

Power removed, but wire is still active

Here is the update loop from the wire showing this:

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)

I need the wires to be powered by other wires, but only if they are all connected to a source.. so I figured, if I can have each wire segment recursively check all the ones that it is connected to, to make sure it is connected to a power source, then I could achieve this. But I am not sure how to do this.

I tried using other variables inside of the wire object like self.sourced which represented if the wire was connected to a power source, but this resulted in only being able top power one wire. (even though when the power source was broken, the wire deactivated, so it kind of worked..)

Anyways, if anyone has know how to do this, please lend me your knowledge.

Here is the full source-code for reference:

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

Answer 1

I think you're having trouble because of a few things.

You're probably going to want to have some sort of containing data structure (another class, not just a list) for your blocks, or have your blocks maintain an adjacency list. I think the latter is probably easier for understanding this question, though maybe the former is better for you since you need to be able to delete blocks (adjacency lists have a lot of bookkeeping). It's up to you, but I'm choosing adjacency lists since it's easier for me. :)

Once you have that down, you should write another method which serves as your recursive entry point. It can be pretty simple. You'll probably need to do something which keeps up with where you've visited; here I've done it as a set which is a parameter to the method, assuming an adjacency list called 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

That answers this question, but I might also consider deriving Circuit and PowerSource from a common base class (Block?) since I suspect having proper OO will help you down the line.

Answer 2

The short answer, from my experience, is to add a flag to the objects indicating whether or not they have been tested in the recursive algorithm. This is because you can have loops. So when you remove the power source, have it call a function to "check for source" for all blocks it is touching. Each block will set it's own flag stating "I've been checked" just prior to looking to see if it has a source as a neighbor. If it has a source as a neighbor it returns "yes I have a source". If not, then it checks to see if any neighbors have a source but only if they have not yet been flagged as having been checked. It will then see if any of the return values are "yes I have a source" and, if so, return "yes" If not, it returns "no" and shuts off.