Advice for designing a logic simulator

A while ago I wrote a logic simulating program in BASIC. You can place sections of wire and logic gates as tiles on a grid, and then start and stop the logic simulation.

The way I designed it is that ‘top level’ items such as switches & clock sources send ‘pulses’ that travel along the wires, one ‘piece’ of wire at a time, until they reach logic gates, where they stay.
The program loops through each pulse moving it to the next piece of wire, until all pulses have reached a logic gate, or until a set number of loop iterations have passed, and then the pulses that had stopped inside logic gates are allowed to continue moving.

Today I tried making a JK flip flop inside my program, and I noticed that it didn’t seem to work unless I put some extra NOT gates inside it in order to add some delay. I recorded a video to demonstrate this problem: https://www.youtube.com/watch?v=CQlVydimwus

This makes me think that my design is very flawed, so I thought I would post here and ask, what would be a more sensible design? Or is there a way I could make my current design better? I want the simulator to be fairly simple, but I also want it to work well enough that you could build a simple computer in it.

Disclaimer: I know sod all about logic simulation… :-)

What seems to be an issue for me, when I think about it, is that the state of the logic circuit is “instantaneous”, that is to say that in reality everything happens at the same time. This can cause problems with a simulation where you are only able to examine one “thing” at a time.

As such – while I may be wrong, I would flag everything with two values – inputsatisfied and outputsatisfied. Then simply step through each element in turn checking its inputs and seeing if this can lead to a valid output. Repeat the entire process over and over until all outputs are satisfied.

Easy example: A piece of wire. Whatever the input is, the output becomes.

Hard example:

       .---
A -----|   \
       |AND |--.e
B -----| 1 /   |  .---
       '---    '--|   \
                  |AND |--- G
       .---    .--| 3 /
C -----|   \   |  '---
       |AND |--'f
D -----| 2 /
       '---

So what we have here are three AND gates. Four inputs (A-D) are ANDed in pairs (A/B and C/D) to create the two outputs e and f, which are ANDed to create the final output G.

Looking at A first, easy. Input = Output. Satisfied. This leads to the AND 1 gate. This does not have inputs satisfied, so ignore it.
Next up is B. Again, a wire, so Input = Output. This leads again to the AND 1 gate, and this time the inputs are satisfied, so we can generate output e.

Depending upon how the elements are stored in memory, we may look at e next, or input C. If e, then input is output as it’s a connection. But AND 3 does not have inputs satisfied so we must skip it. This may take us to C, then AND 2, then D…

See where I’m going here? Initially neither the inputs nor the outputs will be satisfied. So we simply step through looking at the inputs (is there something?) and working out if this means we can determine an output. And just keep iterating through the items over and over until everything has a valid output.
[note: logic gates that use their output as inputs to themselves likely won’t work, though I’m not sure how such a thing could work in reality…]

That’s probably the most asinine thing you’ve ever heard, but, you know, that’s how I’d try approaching it. ;-)

Implementing logic with electronics implies that things take some time to happen. Inductance and capacity of wires and gates, etc. Moreover, with some components (e.g. edge-triggered) timing is important. So probably you really have to include timing.
This is how I would go forward:
With the information from the parts (wires, gates etc) in your grid, and from general knowledge about wires, logic gates etc. fill a database; each database entry is numbered after an input of a something, and knows (from the general information) how long after the input stimulus each of the output(s) (can) change, the other input node numbers, the logic state (0/1) of the node, to which nodes the output(s) are connected (a list of connections), and the logic function that governs it. Perhaps I forgot a few things.
Furthermore there is a red-black tree, each leafnode of which contains a time and a nodenumber.
A red-black tree is a binary tree with some extra magic to keep the tree more or less balanced, at most twice as deep as an optimally balanced one. In this case, the tree should be sorted according to time.
The starting position is, tree is empty.
Fill the tree with the input node where the first external stimulus arrives, and time 0.
Next step: get the lowest-timed node from the tree. Look up the node and see in your database what happens. Remove this leafnode from the tree after each step.
If it is a wire, it will after some delay deliver the signal to the end of the wire that is (hopefully) connected to some input of perhaps a logic gate. Enter the node number of it into the tree, with time=time+delay.
Perhaps if the first signal arrives at two or more inputs, then enter these separate nodes with their respective delaytimes into the tree.
When a logic signal arrives at a function that does nothing, e.g. an ‘1’ to an OR gate where the other input already is ‘1’, then the output of this logic gate does not change and the outputnode does not have to be entered into the tree.
For each next move, look at the treenode with the smallest time. See where it is connected, what logic levels change, and if so, decide which nodes and delayed time have to be added to the tree; remove the node that has just been looked at.
The simulation stops if the whole RB tree gets empty, as this means that a completely stable situation is reached.
When you have a rather limited amount of nodes, a self-balancing tree is not so important, binary insertion alone will do. But with thousands of gates like in a microprocessor, using a self-balancing tree is important, because without the RB magic such a tree degenerates into a linked list that takes ages to traverse.
Caveat: I have not implemented this algorithm design myself yet, so it is possible that is it completely naff.
As a far more better example (becasue it has proven to work), perhaps the source used in www.visual6502.org is available? I don’t know! Anyway, good luck!