Here's how to add the main component of special relativity to these fractal automata.
Now consider the black square in the centre of the diagram above. An equivalent square directly below it would just touch the axis origin so be visible at time zero. This below square has the black square as its neighbour, and so if its update rule turns the square on when its neighbour is on then this piece of space will continue to propagate through time.
The diagonal rectangles represent squares that have a velocity. Each one has the same volume and each one's diagonal point the the origin, so they are all objects that will hit distance 0 at time 0. The way to represent these in the cellular automata is to have separate grids for each power of two on each axis. The cellular automata rules can then act on neighbouring velocities as well squares in neighbouring space.
If we draw a grid of the possible scales then we can see that, in addition to its spatial neighbours, each pixel has several scale neighbours:
The mapping applied to each rectangle must be the same at every position on this grid.
The neighbours seen as black arrows are squares that have a velocity, and the neighbours in green are smaller and larger scale versions of the square. In other words, we already use the uniformly scaled neighbours, that is what makes it fractal automata rather than normal cellular automata, we are now just incorporating non-uniform neighbours.
Amazingly this is all that is needed to allow for special relativity's space-time geometry, time dilation etc, and it allows cellular automata to act on objects with a velocity, without any particular privaleged velocity. The rules are velocity independent. Though I can't show an example as I haven't built any yet.
In 2 dimensions things get trickier. We can't just rotate our grid by 45 degrees. There may be other solutions but my solution is to use a 3d grid and have the time axis as the long diagonal. Squares can then be elongated along three different axes, which equates to different diagonal motions of the object when the axes are different, and it equates to different size objects when they are the same.
This is an extension of the 2d approximation, you use a 4d grid and have time as the long diagonal. The expanding light sphere is approximated by an expanding tetrahedron.