ASCII Hilbert Curve

Befunge, 444 368 323 bytes

&1>\1-:v
0v^*2\<_$00p>
_>:10p\:20pv^_@#-*2g00:+1,+55$
^!-<v*2g000<>$#<0>>-\:v
g2*^>>10g20g+v \ ^*84g_$:88+g,89+g,\1+:00
v#*!-1g02!g01_4^2_
>::00g2*-!\1-:10g-\20g-++>v
87+#^\#p01#<<v!`g01/2\+76:_
vv1-^#1-g01:\_$:2/20g`!
_ 2/^>:10g#vv#`g02/4*3:\+77
v>0p^^/2:/2_
<^2-1-g02</2`#*3:
0g+10p2*:^*3_1
! "#%$
%$"#!
 !!##%
|||_
 _ __

Try it online!

The typical approach to drawing the Hilbert Curve is to follow the path as a series of strokes and turns, rendering the result into a bitmap or some area of memory, and then writing out that rendering when the path is complete. This is just not feasible in Befunge when we only have 2000 bytes of memory to work with, and that includes the source of the program itself.

So the approach we've taken here is to come up with a formula that tells us exactly which character to output for a given x,y coordinate. To understand how this works, it's easiest to ignore the ASCII rendering to start with, and just think of the curve as made up of box characters: ┌, ┐, └, ┘, │, and ─.

When we look at the curve like that, we can immediately see that right hand side is an exact mirror of the left hand side. Characters on the right can simply be determined by looking up their partner on the left, and reflecting it horizontally (i.e. occurrences of ┌ and ┐ are swapped, as are └ and ┘).

Then looking at the bottom left corner, again we can see that the lower half is a reflection of the top half. Thus the characters on the bottom are simply determined by looking up their partner above, and reflecting it vertically (i.e. occurrences of ┌ and └ are swapped, as are ┐ and ┘).

The remaining half of this corner is a little less obvious. The right hand block can be derived from a vertical reflection of the block diagonally adjacent to it.

And the left hand block can be derived from a vertical reflection of the block in the very top left of the full curve.

At this point, all we're left with is the top left corner, which is just another Hilbert Curve one iteration lower. In theory, we should now just need to repeat the process again, but there's a bit of a catch - at this level, the left and right halves of the block aren't exact mirrors of each other.

So at anything other than the top level, the bottom corner characters need to be handled as a special case, where the ┌ character is reflected as ─, and the │ character is reflected as └.

But other than that, we really can just repeat this process recursively. At the last level we hardcode the top left character as ┌, and the character below it as │.

Now that we have a way to determine the shape of the curve at a particular x,y coordinate, how do we translate that into the ASCII rendering? It's actually just a simple mapping that translates each possible tile into two ASCII characters.

• ┌ becomes  _ (space plus underscore)
• ┐ becomes    (two spaces)
• └ becomes |_ (vertical bar plus underscore)
• ┘ becomes |  (vertical bar plus space)
• │ becomes |  (again a vertical bar plus space)
• ─ becomes __ (two underscores)

This mapping isn't intuitive at first, but you can see how it works when looking at two corresponding renderings side by side.

And that's basically all there is to it. Actually implementing this algorithm in Befunge is another problem altogether, but I'll leave that explanation for another time.

C, 267 bytes

const n=4,s=1<<n,a[]={1,-s,-1,s};l,p,q;
t(d){d&=3;p-q||printf("%.2s",&"__|      _|       |___ _|_| | | "[l*8+d*2]);p+=a[l=d];}
h(d,r,n){n--&&(h(d+r,-r,n),t(d+r),h(d,r,n),t(d),h(d,r,n),t(d-r),h(d-r,-r,n));}
main(){for(;p=s*s-s,l=1,q<s*s;++q%s||putchar(10))h(0,1,n),t(3);}

Try it online!

h() uses recursion to generate the strokes of hlibert curve. t() only prints out the stroke character if the pen position p is equal to the current output position q.

This is inefficient but simple.

If the curve starts at top-left, the code can be reduced to 256 bytes.