Relativistic automata continued II

In a previous blog I outlined roughly how you can add velocity symmetry neatly into fractal automata (from now on called Lorentz automata). Here are some implementation descriptions.

Minkowski lattice

The data structure for cellular automata is the (n dimensional) grid, for fractal automata it is a grid-tree, otherwise known as a quad-tree and oct-tree in two and three dimensions respectively. For Lorentz automata I use what I call a Minkowski lattice (or M lattice). Similar to a grid tree, but each grid has several children of different elongations, as such two parents can have the same child, which makes this structure a lattice:

The data structure is therefore the set of grids with resolutions (2^w, 2^h) for all w,h between 1 and the highest resolution depth. The non-square grids represent non-zero velocity frames.

Lattice update order

Assuming we have such grids available for accessing and setting the bit value at any point on the grid, the challenge is then to find the correct order at which each cell of each grid is updated. For the 1+1 Minkowski space-time the update order can be seen as follows:

The image shows the high resolution grid on the left and two lower resolution grids as examples. The red/green arrows indicate the local coordinate origin for each grid. If a single frame step is defined as one quarter the diagonal length of the highest resolution grid then the centre of the grid cells and all lower resolution grid cells always pass through one of these frame times (shown as blue line).
We want each cell to be updated when the frame time hits the centre of that cell, so the simplest algorithm is to iterate through all the grids and update all the cells that touch the line.

In 2+1 space-time the frame-time represents a plane which the 3d grid cell centres sit on. The direction of time is along the long-diagonal of the grid coordinates. To update the cells correctly you need to define a resolution for the plane, e.g. 256x256, then for each grid it must find cell centres that lie on and in this clipped plane:

for (i = 1; i<=resolution; i*=2)
  for (j = 1; j<=resolution; j*=2)
    for (k = 1; k<=resolution; k*=2)
      for (x = centre.x-resolution; x++)
        if ((x&(2*i-1)) != i)
          continue;
        for (y = centre.y-resolution; y++)
          if ((y&(2*j-1)) != j)
            continue;
          z = frame - x - y;
          if ((z&(2*k-1)) != k)
            continue;
          updateCell(x/(2*i), y/(2*j), k/(2*k)); 

Interestingly the update of the lattice has an exactly constant number of updateCell calls per frame, which is useful for real-time use. The number of updateCell calls approaches 4 times the number of pixels, so the cost of adding velocity symmetry using these Lorentz transforms is finite and small, unlike with Galilean transforms.

Cell update 

With the fractal cellular automata the half-resolution parent cell is located at (frame - 1)>>1. For these Lorentz automata it is simply this for each axis, e.g. (x-1)>>1 on each axis that is half-resolution. This therefore applies to elongated grids too. The purpose of this is that you only retrieve data from neighbour cells that are prior in time.

Conversely, the double-resolution children cells are located at x << 1 and ( x << 1 ) - 1 again ensuring that these neighbours are prior in time so have already been set.

Results

Due to the large search space, I start with a hand-built automata rule:

This diagram shows a very simple Lorentz automaton, there are just four points with zero velocity, each with scale twice the previous. The larger scale points (set in the larger voxel grid) are interpreted by the successively higher resolution grids such that the resulting shape is a high resolution hexagon in this case. A different rule could generate any shape like those seen in the static fractal automata.

Additionally there are seven clones of these 4 points which have successively larger upwards velocities (velocity 1), and also 7 clones with successively larger diagonal velocities (velocity 2 in the diagram).

The picture was taken after a few seconds, so the points have moved from their initial positions. You can see most clearly the tiny points in the bottom right area, notice that the points are not evenly spaced along the velocity, even though they each have the same difference in speed. This is because we are using a relativistic velocity. The points get closer together towards the top, this is the equivalent of approaching the speed of light.

Looking at the top left section of large hexagons, it looks a bit like a grid of points, this is because there are points for each non-uniform power of two scale, which give the different point directions, velocities and scales. The middle points seem flattened in the direction of movement, this is mainly because the three prime motion directions are elongated in this model and the three secondary motion directions are flattened. But additionally there is some flattening due to time dilation.

Notice that the decimation (from low res to high res) keeps smoothly shaped hexagons even when they are distorted by their velocity.

Base tiling

While most cellular automata use a square grid, these automata are a bit different. The long-diagonal projection of each cube through time gives a variable shape, but we can make the grid constant by viewing the last three frames rather than just the last frame. This gives us a base hexagonal tiling, which is nice since it has 6 rotational symmetries compared with 4 for a square, plus it is a 'stable' tiling in that it is the most efficient filling of the space. This also extends into 3d (where time is the long diagonal of a 4d 'hyper'cube)... the base tiling becomes a rhombic dodecahedron, with 12 rotational symmetries compared to 6 for the cube. Equally, the honeycomb of rhombic dodecahedrons are the most space efficient way to tile 3d space. 

This also makes the 'diagonal time axis' method an attractive method for normal fractal automata, not just for Lorentz automata.