A look into the experimental redstone changes in 24w33a.

24w33a-redstone-experiments.md

24w33a Redstone Experiments

24w33a introduces new experimental changes to redstone dust, aiming to fix some of the long standing issues with it, like the lag it causes and the unintuitive and unreliable way in which it updates.

The problems with redstone dust

The problems with redstone dust stem from its naive implementation. When a wire is updated, it checks what signal it receives from surrounding blocks. If that is different from its current signal strength, it updates it and then notifies neighboring blocks. This implementation is fine for individual wires, but when multiple wires are connected, its flaws become apparent: the wires power each other, but the signal degrades over distance. Thus when you remove the power source from a line of wires, the signal will die out completely. However, any individual wire does not have this context. It will only decrease its signal strength to match what it receives from neighboring wires, and that will repeat until all wires have depowered completely. This results in lots of unnecessary calculations and updates. For example, depowering a line of 15 wires will result in 64(!) signal strength changes altogether, where 15 should suffice.

Aside from unnecessary calculations, the naive implementation results in copious amounts of unnecessary block updates. With each signal strength change, a wire updates all blocks within a range of 2 blocks of itself, 42 block updates in total. Going back to the example of a line of 15 wires, that is a total of 2688 block updates when the entire line depowers. By comparison, a good implementation would do only 360, and an optimal one 191.

And it gets worse yet. Of the 42 block updates a wire emits, 18 of them completely unnecessary. A block only has 24 neighbors within a range of 2 blocks (6 direct neighbors, 18 neighbors a distance of 2 blocks away), so only 24 block updates need to be emitted. Of the remaining 18, 12 of them are duplicates of the updates to neighboring blocks. Crazier yet, the last 6 block updates are to itself. Not only is that 5 duplicates of a single block update, but they cause the wire to do even more calculations that are completely unnecessary.

Lag is not the only problem, though. Wire blocks do not emit updates in a consistent way. The order of block updates around a wire is dependent on that wire's position in the world. This makes it hard to rely on the update order around an individual wire, but makes it nigh impossible to rely on the update order around a wire network. Each wire in a network updates surrounding blocks in a different order, and that impacts the order in which the wires themselves update as well. So not only can circuits behave differently in different locations, it is nearly impossible to predict how a circuit will behave in a given location.

The new solution in 24w33a

In 24w33a there is an experimental redstone wire evaluator. This engine can handle signal strength changes for entire wire networks at once. This solves the main flaw of the naive implementation, and solves both the performance and the unpredictability of redstone dust in one fell swoop. So how does the experimental evaluator work?

A new evaluator is created every time a wire block is updated. The evaluator will use that wire as the starting wire for its calculations, then works through the following steps.

1. Create a FIFO queue for wires that should decrease in signal strength: wiresToTurnOff.
2. Create a FIFO queue for wires that should increase in signal strength: wiresToTurnOn.
3. Create a linked map to keep track of the wires' new signal strengths: updatedWires.
4. Add the starting wire to the wiresToTurnOff queue.
5. If the wiresToTurnOff queue is empty, proceed to step 7. Otherwise, take out the first wire from the queue, that is the current wire. Find the incoming block signal, power received from neighboring non-wire blocks, and the incoming wire signal, power received from neighboring wire blocks. The highest between these two values is the incoming signal. If the incoming signal is greater than the current wire's signal strength, set its signal strength to the incoming signal. If the incoming signal is less than the current wire's signal strength, set its signal strength to 0, then check the incoming block signal. If that is greater than 0, add the wire to the wiresToTurnOn queue.
6. Compare the current wire's signal strength to that of all wires connected to it. If a connected wire's signal strength is greater than that of the current wire, add the connected wire to the wiresToTurnOff queue. If a connected wire's signal strength is less the current wire's signal strength minus 1, add the connected wire to the wiresToTurnOn queue. Go back to step 5.
7. If the wiresToTurnOn queue is empty, proceed to step 9. Otherwise, take out the first wire from the queue, that is the current wire. Find the incoming signal. If the incoming signal is greater than the current wire's signal strength, set the current wire's signal strength to the incoming signal.
8. Compare current wire's signal strength to that of all wires connected to it. If a connected wire's signal strength is greater than that of the current wire, add the connected wire to the wiresToTurnOff queue. Go back to step 7.
9. For each wire in the updatedWires map, set its signal strength in the world to the new value.
10. For each wire in the updatedWires map, cause block updates to neighboring blocks.

The experimental evaluator also attempts to make the update order of wire networks more consistent and more intuitive. The new algorithm is the first step to achieve that. Since the wiresToTurnOff and wiresToTurnOn queues are ordered FIFO, wires are added to the update queue in a breadth-first manner. Therefore wires are updated in concentric rings going outward from the starting wire. This has the nice result of wires closer to the starting wire updating before wires that are further away. For wires the same distance away, the order is dependent on the order in which wires enqueue their neighbors. This is where another feature of the experimental evaluator comes in. Wires remember which direction they were enqueued from, and change the order in which they enqueue their neighbors accordingly. This results in a completely orientation-independent update order for the entire network.

Except... what about the starting wire? It is not enqueued by another wire, but by a block update. And the order in which it enqueues its neighbors changes the update order of the entire network. Well, they thought of that, too! Most block updates are emitted in the game are dispatched in groups of 6 around some source block. For example, when you place a block, its 6 direct neighbors are updated. The direction from that source block is used by the starting wire to determine the order in which it enqueues its neighbors. There is a catch however. It is not always possible to derive the initial direction from context. If the starting wire was updated from above of below, for example, no horizontal bias is present. In such cases the initial direction is chosen at random.

Apart from the update order, the experimental evaluator also makes changes to how block updates are emitted around redstone wires. A redstone wire now only emits block updates to neighbors that may receive power from the wire. More precisely, it updates direct neighbors in each direction where it has a connection (i.e. it visually points in that direction), and it updates the block below itself. Moreover, it only updates the blocks around a direct neighbor if it may power that neighbor and if that neighbor is a redstone conductor.

Lastly, since the experimental evaluator handles signal strength changes for entire networks at once, redstone wires now ignore block updates from other redstone wires.

The good and the bad

The experimental redstone wire evaluator is fast and compact. It results in deterministic behavior, neither location-dependent nor orientation-dependent, in a majority of cases. These are huge positives and a breath of fresh air when compared to what we had for the past 14 years.

The new update order is intuitive and allows for some neat tricks. Instant dropper lines are the obvious example, but there are others, like a double piston extender controlled from a single redstone line. Unfortunately this is such a fundamental change that it will break some existing redstone builds. Specifically, the previous implementation caused some redstone builds to work only in some locations. With the experimental changes, these builds will work either everywhere, or nowhere (or randomly in some cases). What portion of builds are affected depends a lot on which area of redstone you look at, so it is hard to predict. In my view this new update order is worth the breakages it causes in the long run, as it can undo the bad reputation redstone dust has had. The random aspect of the update order is problematic, but there is a bigger problem that needs to be addressed first.

The changes to how block updates are emitted around wire blocks cause lots of builds to break, more so than the performance improvements and changes to update order, without giving anything in return. As a refresher, block updates are only emitted to neighbors of a wire that may receive power from that wire. This causes two kinds of issues:

1. Blocks that may be powered by the wire through Quasi-Connectivity, i.e. blocks that may be QC-powered, are not updated. For example, a wire placed on a slab can power a piston below or next to the slab, but with the experimental changes, the piston will not be updated. Most breakages will be caused by this change specifically. The previous behavior was widely used as there are often other constraints that force the use of a non-conductive block to place the wire on. For example, here are YouTube videos by MYuen222, Algi, and lum3nd0, showing just how much this change impacts their builds.

2. Blocks that are near the redstone wire but may not receive power from it, are not updated. While a lesser issue compared to the above, this is nonetheless widely relied upon behavior that is removed. Not only that, it is in stark contrast with how every other redstone component operates. I have a hunch why this change was made, which I'll go into now.

The algorithm used by the experimental evaluator is fast and compact, and the from-the-source-outward update order rolls out of it very nicely, but there is a catch. It has been over a decade since redstone dust and pistons were added, and by now there is lots of behavior heavily relied upon in all kinds of areas of redstone. One of the areas that rely heavily on interactions between redstone dust and pistons, is that of 0-tick redstone. Some of the circuitry commonly used in 0-tick builds can easily break if the update order is tampered with too much. In particular, these circuits rely on block updates being emitted at the same time as updating the signal strengths, which leads to blocks around the far end of the wire network being updated before blocks around wires closer to the source. Common 0-tick repeater designs rely on this to avoid a QC-powered piston being updated at the wrong moment.

Let's look at the following implementation detail: after calculating the signal strength changes, the signal strength of all wires is set in the world, and then all updated wires will emit block updates to neighboring blocks. In order words: before a line of wire causes block updates, the new signal strength of all connected wires is set. This, combined with the from-the-source-outward update order, breaks some very common circuitry that relies the behavior described above. So what is to be done?

• One solution is to reverse the update order, update wires furthest away from the source first, and those closest to the source last. But this sacrifices some of the intuitiveness of the new update order, so that is a no-go.
• What appears to be another solution is to emit block updates around a wire immediately after its signal strength is set. However, since 1.19, neighbor updates are no longer instantaneous, and these block updates would be processed only after the evaluator has completed, meaning it would behave no different than the current implementation. For the sake of completeness, however, let's examine this solution for versions prior to 1.19. While it does fix those 0-tick repeaters, it introduces some other quirks that are detrimental to the update order's intuitiveness: it can leave QC-powered blocks in a BUD-ed state, so that is a no-go as well.
• That leaves us with the solution we ended up with: simply remove updates to all blocks not powered by the wire. But as we have seen, that breaks a lot of circuitry, and so should be abandoned as well.

Is there a good solution, then? Of the three we have discussed so far, the first seems the safest bet. It does not break existing builds as much, though it is not as intuitive as we would like. However, there is a variation on the second solution that preserves the from-the-source-outwards update order while also keeping existing builds mostly intact. The idea is to have a single queue for both wires and neighboring blocks to be updated. After signal strength changes have been calculated, the first wire(s) are added to the queue. Then keep polling from the queue, and if it is not a wire, dispatch a block update to that block, but if it is a wire, set its signal strength, enqueue neighboring wires that have not updated yet, and then enqueue neighboring blocks to be updated. This solution has a few advantages. It mimics how redstone behaved before, with block updates emitted during signal strength changes being carried out. It also removes even more duplicate block updates, since the update queue that is used does not allow duplicate entries. And it manages to fix the 0-tick circuitry discussed above without introducing buggy behavior with QC-powered blocks. This is the solution Alternate Current uses.

Finally, the element of randomness. The changelogs mention the following note:

We know that randomness in Redstone is usually unwanted. We've used it here because we've made things deterministic whenever it makes sense, and sometimes it just doesn't make sense - and we don't want some hidden state (like location-based hashes!) determining the order and making machines work differently at different coordinates or in different orientations.

It seems to me that introducing randomness to avoid depending on some arbitrary hidden state does not fix the underlying issue: the game allows such ambiguous cases to occur, and can then behave in different ways. Whether it's location-dependent, direction-dependent, or even randomness, all three make redstone builds broken if you change the context, and debugging that is hard. Randomness has no advantages over the over two, and deprives us of the ability to exploit details within these hidden states that can be relied upon.

Part of what makes people love redstone is its quirks. Little details that were not intended to but have big consequences because they can be exploited in unique ways. The game may not do what you expect, but it does so consistently. With lots of study, this can be exploited, and lead to some truly amazing results. Introducing randomness instead kills that aspect of it.

Great post! I hope Mojang sees this and changes it accordingly.
I just want to add a proposal to minimize dependence on hidden context (orientation, location, time (which is also hidden context, Mojang!)). In some cases we can get rid of it altogether!

Instead of randomness, they should just choose an order like forward-right-left, that way it is not dependent on location, orientation or time. You can easily recognize and remember this order, so it would still be pretty intuitive.

And for when there is no available incoming direction (came from below or above), we can just pretend, that it came from a consistent direction like North. This is only dependent on orientation, which in my opinion is the least unintuitive (while staying useful) of the three. (When you can't get rid of hidden context, make it as simple/usable as possible)

Nice post. I knew that redstone dust was a performance issue, but I didn't think it was that bad.

Your solution is interesting and provides a satisfactory compromise. I would like to add a suggestion: if it is a wire, set its signal strength / if it is not a wire, dispatch a block update to that block / is a air block, don't dispatch a block update to that air. In this way, it will be possible to 'isolate' a piston from a wire that could activate it when you don't want it to do by make a littel air gap, but we can still easily 'connect' it by placing any block instead of the air.

@Aras14HD I really like that proposal. It would be simple for any user to remember, and would make redstone consistent. My biggest problem with the update is introducing inconsistency through randomness.