Tree Row Ranges

Counting depth=0 as the N=1 at the origin and depth=1 as the next N=2,3,4,5 generation, the number of cells in a row is

    rowwidth(0) = 1
      then
    rowwidth(depth) = 4 * 3^((count_1_bits(depth) - 1)

So depth=1 has 4*3^0=4 cells, as does depth=2 at N=6,7,8,9. Then depth=3 has 4*3^1=12 cells N=10 to N=21 because depth=3=0b11 has two 1-bits in binary. The N start and end for a row is the cumulative total of those before it,

    Ndepth(depth) = 1 + (rowwidth(0) + ... + rowwidth(depth-1))
    Nend(depth) = rowwidth(0) + ... + rowwidth(depth)

For example depth 3 ends at N=(1+4+4)=9.

    depth    Ndepth   rowwidth     Nend
      0          1         1           1
      1          2         4           5
      2          6         4           9
      3         10        12          21
      4         22         4          25
      5         26        12          37
      6         38        12          49
      7         50        36          85
      8         86         4          89
      9         90        12         101

For a power-of-2 depth the Ndepth is

    Ndepth(2^a) = 2 + 4*(4^a-1)/3

For example depth=4=2^2 starts at N=2+4*(4^2-1)/3=22, or depth=8=2^3 starts N=2+4*(4^3-1)/3=86.

Further bits in the depth value contribute powers-of-4 with a tripling for each bit above. So if the depth number has bits a,b,c,d,etc in descending order,

    depth = 2^a + 2^b + 2^c + 2^d ...       a>b>c>d...
    Ndepth = 2 + 4*(-1
                    +       4^a
                    +   3 * 4^b
                    + 3^2 * 4^c
                    + 3^3 * 4^d + ... ) / 3

For example depth=6 = 2^2+2^1 is Ndepth = 2 + (1+4*(4^2-1)/3) + 4^(1+1) = 38. Or depth=7 = 2^2+2^1+2^0 is Ndepth = 1 + (1+4*(4^2-1)/3) + 4^(1+1) + 3*4^(0+1) = 50.

Self-Similar Replication

The diamond shape depth=1 to depth=2^level-1 repeats three times. For example an "a" part going to the right of the origin "O",

            d
          d d d
    |   a   d   c
  --O a a a * c c c ...
    |   a   b   c
          b b b
            b

The 2x2 diamond shaped "a" repeats pointing up, down and right as "b", "c" and "d". This resulting 4x4 diamond then likewise repeats up, down and right. The same happens in the other quarters of the plane.

The points in the path here are numbered by tree rows rather than in this sort of replication, but the replication helps to see the structure of the pattern.

Half Plane

Option "parts => '2'" confines the pattern to the upper half plane "Y>=0",

    parts => "2"
                      28                           6
                      21                           5
                29 22 16 20 27                     4
                      11                           3
          30       12  6 10       26               2
          23    13     3     9    19               1
    31 24 17 14  7  4  1  2  5  8 15 18 25     <- Y=0
    --------------------------------------
    -6 -5 -4 -3 -2 -1 X=0 1  2  3  4  5  6

Points are still numbered anti-clockwise around so X axis N=1,2,5,8,15,etc is the first of row depth=X. X negative axis N=1,4,7,14,etc is the last of row depth=-X. For depth=0 point N=1 is both the first and last of that row.

Within a row a line from point N to N+1 is always a 45-degree angle. This is true of each 3 direct children, but also across groups of children by symmetry. For this parts=2 the lines from the last of one row to the first of the next are horizontal, making an attractive pattern of diagonals and then across to the next row horizontally. For parts=4 or parts=1 the last to first lines are at various different slopes and so upsets the pattern.

One Quadrant

Option "parts => '1'" confines the pattern to the first quadrant,

    parts => "1"  to depth=14
    14  |  73
    13  |  63
    12  |  53 62 72
    11  |  49
    10  |  39 48       71
     9  |  35    47    61
     8  |  31 34 38 46 52 60 70
     7  |  29    45    59
     6  |  19 28       69          67
     5  |  15    27                57
     4  |  11 14 18 26       68 58 51 56 66
     3  |   9    25    23          43
     2  |   5  8    24 17 22    44 37 42       65
     1  |   3     7    13    21    33    41    55
    Y=0 |   1  2  4  6 10 12 16 20 30 32 36 40 50 54 64
        +-----------------------------------------------
          X=0  1  2  3  4  5  6  7  8  9 10 11 12 13 14

X axis N=1,2,4,6,10,etc is the first of each row X=depth. Y axis N=1,3,5,9,11,etc is the last similarly Y=depth.

In this arrangement horizontal arms have even N and vertical arms have odd N. For example the vertical at X=8 N=30,33,37,etc has N odd from N=33 up and when it turns to horizontal at N=42 or N=56 it switches to N even. The children of N=66 are not shown but the verticals from there are N=79 below and N=81 above and so switch to odd again.

This odd/even pattern is true of N=2 horizontal and N=3 vertical and thereafter is true due to each row having an even number of points and the self-similar replications in the pattern,

    |\          replication
    | \            block 0 to 1 and 3
    |3 \           and block 0 block 2 less sides
    |----
    |\ 2|\
    | \ | \
    |0 \|1 \
    ---------

Block 0 is the base and is replicated as block 1 and in reverse as block 3. Block 2 is a further copy of block 0, but the two halves of block 0 rotated inward 90 degrees, so the X axis of block 0 becomes the vertical of block 2, and the Y axis of block 0 the horizontal of block 2. Those axis parts are dropped since they're already covered by block 1 and 3 and dropping them flips the odd/even parity to match the vertical/horizontal flip due to the 90-degree rotation.

Octant

Option "parts => 'octant'" confines the pattern to the first eighth of the plane 0<=Y<=X.

    parts => "octant"
      7 |                         47     ...
      6 |                      48 36 46
      5 |                   49    31    45
      4 |                50 37 32 27 30 35 44
      3 |             14    51    24    43    41
      2 |          15 10 13    25 20 23    42 34 40
      1 |        5     8    12    18    22    29    39
    Y=0 |  1  2  3  4  6  7  9 11 16 17 19 21 26 28 33 38
        +-------------------------------------------------
         X=0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15

In this arrangement N=1,2,3,4,6,7,etc on the X axis is the first N of each row ("tree_depth_to_n()").

Upper Octant

Option "parts => 'octant_up'" confines the pattern to the upper octant 0<=X<=Y of the first quadrant.

    parts => "octant_up"
      8 | 16 17 19 22 26 29 34 42
      7 | 15    21    28    41
      6 | 10 14    38 33 40
      5 |  8    13    39
      4 |  6  7  9 12
      3 |  5    11
      2 |  3  4
      1 |  2
    Y=0 |  1
        +--------------------------
          X=0 1  2  3  4  5  6  7

In this arrangement N=1,2,3,5,6,8,etc on the Y axis the last N of each row ("tree_depth_to_n_end()").

N Start

The default is to number points starting N=1 as shown above. An optional "n_start" can give a different start, in the same pattern. For example to start at 0,

    n_start => 0
                   29                       5
                30 22 28                    4
                   13                       3
                14  6 12                    2
       31    15     2    11    27           1
    32 23 16  7  3  0  1  5 10 21 26    <- Y=0
       33    17     4     9    25          -1
                18  8 20       37          -2
                   19                      -3
                34 24 36                   -4
                   35                      -5
                    ^
    -5 -4 -3 -2 -1 X=0 1  2  3  4  5

Tree Methods

"@n_children = $path->tree_n_children($n)"

Return the children of $n, or an empty list if $n has no children (including when "$n < 1", ie. before the start of the path).

The children are the cells turned on adjacent to $n at the next row. The way points are numbered means that when there's multiple children they're consecutive N values, for example at N=6 the children are 10,11,12.

Tree Descriptive Methods

"@nums = $path->tree_num_children_list()"

Return a list of the possible number of children in $path. This is the set of possible return values from "tree_n_num_children()". The possible children varies with the "parts",

    parts     tree_num_children_list()
    -----     ------------------------
      4             0, 1,    3, 4        (the default)
      2             0, 1, 2, 3
      1             0, 1, 2, 3
    

parts=4 has 4 children at the origin N=0 and thereafter either 0, 1 or 3.

parts=2 and parts=1 can have 2 children on the boundaries where the 3rd child is chopped off, otherwise 0, 1 or 3.

"$n_parent = $path->tree_n_parent($n)"

Return the parent node of $n, or "undef" if "$n <= 1" (the start of the path).

Level Methods

"($n_lo, $n_hi) = $path->level_to_n_range($level)"

Return "$n_lo = $n_start" and

    parts    $n_hi
    -----    -----
      4      $n_start + (16*4**$level - 4) / 3
      2      $n_start + ( 8*4**$level - 5) / 3  +  2*2**$level
      1      $n_start + ( 4*4**$level - 4) / 3  +  2*2**$level
    

$n_hi is "tree_depth_to_n_end(2**($level+1) - 1".