How to map coords (x,y) to a H-tree?

Question

For a mini game I want to have a map resembling the H-Tree Fractal. The line would be road and you can drive around but only on the road. The map is infinite and needs to be generated as you drive around.

So given a coordinate (x,y) how do I decide if it's road or not road?

Lets define some constants:

The length of each cul-de-sac is L. The line segments in each iteration grow by a factor of 1.5, no sqrt(2), to keep everything rational. And a road is any point at a distance <= 1 from the line. max(dx, dy) <= 1 if that is simpler.

The start point is (0,0) and can be any cul-de-sac on the H-tree, your choice.

Answer 1

Signed distance field implemented in Shader Editor for Android from f-Droid:

#version 300 es
#ifdef GL_FRAGMENT_PRECISION_HIGH
precision highp float;
#else
precision mediump float;
#endif

uniform vec2 resolution;

out vec4 outColour;

void main(void)
{
  // p determined by pixel coordinates
  vec2 p = gl_FragCoord.xy - resolution.xy * 0.5;
  p /= 8.0;
  float dL = length(vec4(dFdx(p), dFdy(p)));
  // signed distance to road
  float z = 1.0/0.0;
  // road width (not cul-de-sac length)
  float L = 0.1;
  // inflation factor
  float f = sqrt(2.0);
  // transformation
  mat2 m = mat2(0, 1, -1, 0) * f;
  mat2 m1 = inverse(m);
  vec2 c = vec2(1.0, 0.0);
  // inverse transform to base region
  int maxd = 24; // determines maximum extent
  int D = 0; // count steps
  float fd = 1.0; // for uniform road width
  for (int d = 0; d < maxd; ++d)
  {
    if (abs(p.x) < 1.0 && abs(p.y) < f)
    {
      D = d + 1;
      break;
    }
    p = m1 * (p - c);
    fd /= f;
  }
  // finite tree
  if (D == 0)
  {
    outColour = vec4(1,0,0,1);
    return;
  }
  // add detail
  for (int d = 0; d < D; ++d)
  {
    // two line segments / rectangles
    z = min(z, min(max(abs(p.x/fd) - L, abs(p.y/fd) - 1.0/f/fd),
      max(max(-L - p.x/fd, p.x/fd - (1.0/fd + L)), abs(p.y/fd) - L)));
    // transformation, note abs for symmetry
    p = m * abs(p) + c;
    fd *= f;
  }
  // colouring according to distance: z < 0 means road (white)
  outColour = vec4(vec3(1.0 - smoothstep(max(z, 0.0), 0.0, 0.5*dL)), 1.0);
}

This is using single precision floating point with an approximate $\sqrt{2}$. Other inflation factors don't look so good.

The shader code uses a fixed maximum iteration count because unbounded loops on a GPU can be problematic. Moreover with floating point, rounding errors may accumulate. With exact arithmetic and enough memory, this limit can be increased (each increment of 1 doubles the area covered by the tree) or even removed (risking memory exhaustion from large integer storage at extreme distances from the origin).

There is a way to do exact arithmetic with numbers like $a + b \sqrt{2} \quad a,b \in \mathbb{Q}$:

$$(a + b \sqrt{2}) + (x + y \sqrt{2}) = (a + x) + (b + y) \sqrt{2}$$ $$(a + b \sqrt{2}) - (x + y \sqrt{2}) = (a - x) + (b - y) \sqrt{2}$$ $$(a + b \sqrt{2}) (x + y \sqrt{2}) = (a x + 2 b y) + (a y + b x) \sqrt{2}$$ $$\frac{1}{a + b \sqrt{2}} = \frac{a}{d} - \frac{b}{d} \sqrt{2} \text{ where } d = a^2 - 2 b^2$$ $$a + b \sqrt{2} > 0 \text{ when } a > 0 \wedge b > 0$$ $$a + b \sqrt{2} < 0 \text { when } a < 0 \wedge b < 0$$ $$a + b \sqrt{2} > 0 \equiv a^2 > 2 b^2 \text{ when } a > 0 \wedge b < 0 $$ $$a + b \sqrt{2} > 0 \equiv a^2 < 2 b^2 \text{ when } a < 0 \wedge b > 0 $$

You don't need to evaluate or store the $\sqrt{2}$, it's symbolic.

Make sure to use unbounded integers for the rational numbers (overflow of fixed size integral types is catastrophic here).