4
\$\begingroup\$

I have made an application which allows the user to place down wires, power sources, and inverters on a virtual circuit board. All connections between tiles are automatic, as shown here:

zero conncetions two conncetions three conncetions four conncetions

As you can see in the last image, the updating of power throughout this grid is not yet functioning. I think I understand how to do this updating conceptually, but getting it to work in my program is appearing to be much more difficult than I first imagined. My source code can be found here.

Getting tiles to pass on power to their neighbors is quite easy, but the tricky part is getting wires to "unpower" after the removal of a power source. The size of the grid is just 18x18, so efficiency really isn't a factor, for those wondering.

If you have any tips as to how to I might approach this task, please let me know.

\$\endgroup\$
  • \$\begingroup\$ Are you trying to achieve any level of accuracy? Or just something that "works"? And please give more detail, how large is the total grid? \$\endgroup\$ – MickLH Jun 5 '14 at 23:35
  • \$\begingroup\$ @MickLH Sorry it was unclear, I've updated the post and hopefully answered all of your questions. \$\endgroup\$ – AJ Weeks Jun 6 '14 at 2:16
  • \$\begingroup\$ Hi, I'm an author of a logic simulator, email me if you want to talk =) \$\endgroup\$ – Jari Komppa Jun 6 '14 at 5:21
  • \$\begingroup\$ @JariKomppa prefarrably answer things here, for the completeness of the site, please. \$\endgroup\$ – Gustavo Maciel Jun 6 '14 at 5:38
  • \$\begingroup\$ @GustavoMaciel I hear you, and for single questions, sure, but circuit simulation is a bit too big topic for a single q/a. \$\endgroup\$ – Jari Komppa Jun 6 '14 at 6:12
6
\$\begingroup\$

The simple solution would be to just discard and recalculate the power distribution in the whole grid whenever you make a change. Considering that your grid is only 18x18, it shouldn't be too computationally intensive to do so.

Inverters might be problematic, though. What do you want to happen when the player connects the output of an inverter to its input? This would lead to a paradoxical situation. In a real-life circuit, the inverter might either oscillate (switch between on- and off as fast as it can) or just short-circuit and break.

When you want to go for the oscillating solution, you should go for a tick-based simulation where a fixed number of updates is calculated each second. In such a simulation, an inverter would not directly forward the state of its input. It would instead be modeled as an object which blocks power-flow, but which is also an independent power-source, just with the difference that the player can not switch it off- and on directly. The update-function which is executed in regular intervals would then look like this in pseudo-code:

 for each source
      if source is inverter
         if input wire is in "on"
             set source to "off"
         else
             set source to "on"

 for each wire
     set wire to "off"

 for each source   
     if source is "on"
         flood-fill wires starting from output-wire and set all found wires to "on"

note that evaluation of the inverter-state and evaluation of the wire-state are two separate steps. That way you will not run into any infinite loops during the update.

When you instead want to go for a "breaking" solution, you would recursively flood-fill from all sources. The status of each wire would start out as "undefined". When you start flood-filling from a souce, you fill with the value "on". When you pass through an inverter, you toggle from "on" to "off" or vice versa and continue flood-filling with the new value. When you ever encounter an "off" wire while flooding with "on" or an "on" wire while flooding with "off", you found a paradoxon in the players circuit, revert the last move and tell the player they can't do that.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the advice, I think I will try to implement the tick-based oscillating method you mentioned. \$\endgroup\$ – AJ Weeks Jun 6 '14 at 16:43
  • \$\begingroup\$ The only problem I'm running into is how to specifically implement the flood-filling of wires when a source is "on". \$\endgroup\$ – AJ Weeks Jun 6 '14 at 17:02
  • 1
    \$\begingroup\$ @AJWeeks FloodFill is a stock algorithm. When you have problems with implementing it you could ask about it on stackoverflow. \$\endgroup\$ – Philipp Jun 6 '14 at 17:29
  • \$\begingroup\$ I've attempted implementing the flood-fill algorithm after reading the WikiPedia page on it, and seem to have run into a problem. As you can see in this picture, the algorithm is only updating tiles which are above the source. I've tried to follow the code line by line using eclipse's debugging tools, but I feel stumped. Any ideas? As mentioned above, the source code can be seen here, if you want to read it, feel free. Thanks again for all the help! \$\endgroup\$ – AJ Weeks Jun 6 '14 at 23:08
  • 1
    \$\begingroup\$ @AJWeeks Because you have a completely new problem (how to implement flood-fill) and this problem is too complex to describe and answer just with comments. So please create a new question where you paste the relevant code-section (not just a link to your git repository) and someone (maybe me) will give you an answer. \$\endgroup\$ – Philipp Jun 6 '14 at 23:19
1
\$\begingroup\$

This sounds strange, and high-level, but I would consider modelling electricity through cellular automata.

Practically, this means modelling electricity as a state (on/off) for each cell, and codifying a set of rules that tell you which states are on or off.

The rules might go something like:

  • For every cell that's a power source, set the state to "on"
  • Notify every adjacent cell that's connected that we're on
  • For each cell which receives notification:
    • Set your state to on
    • Recursively notify all connected neighbours

All you need to worry about is tracking which cells are connected to. The added benefit is if you put a delay before notifying neighbours (eg. 0.25ms), you can "see" the electricity "flowing" from start to finish.

Unplugging would mean turning off the power source, which should work in a similar way, except with setting stuff to "off" instead of "on." Inverters wouldn't be hard to model either.

\$\endgroup\$
  • \$\begingroup\$ So you need to duplicate the set of rules above for when the source is turned off? \$\endgroup\$ – ThorinII Jun 13 '14 at 0:00
  • \$\begingroup\$ @ThorinII no, you don't. You only need the current state of the board to calculate the next state, whether it's on or off; just like Conway's Game of Life. \$\endgroup\$ – ashes999 Jun 13 '14 at 3:10
  • \$\begingroup\$ Sorry, I meant your rules ("The rules might go something like...") don't seem to have any means of setting the states to off... do you imply by ("Unplugging... should work in a similar way except with setting to "off"") that there are more? Ie the rules listed above are just half the needed set? \$\endgroup\$ – ThorinII Jun 13 '14 at 4:46
  • \$\begingroup\$ @ThorinII this is sufficiently the full set of rules you need. If you unplug the charger, that cell turns off, and when you recompute the state of the board, the adjacent cells will cascadingly turn off. There's nothing more that you need. (If you're really confused, try coding the Game of Life, and it'll make sense.) \$\endgroup\$ – ashes999 Jun 13 '14 at 8:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.