ASCII Hilbert Curve

Question

Given an integer n output the nth iteration of the Hilbert Curve in ASCII using the characters _ and |.

Here are the first 4 iterations:

n=1
 _ 
| |

n=2
 _   _ 
| |_| |
|_   _|
 _| |_

n=3
 _   _   _   _ 
| |_| | | |_| |
|_   _| |_   _|
 _| |_____| |_ 
|  ___   ___  |
|_|  _| |_  |_|
 _  |_   _|  _ 
| |___| |___| |

n=4
 _   _   _   _   _   _   _   _ 
| |_| | | |_| | | |_| | | |_| |
|_   _| |_   _| |_   _| |_   _|
 _| |_____| |_   _| |_____| |_ 
|  ___   ___  | |  ___   ___  |
|_|  _| |_  |_| |_|  _| |_  |_|
 _  |_   _|  _   _  |_   _|  _ 
| |___| |___| |_| |___| |___| |
|_   ___   ___   ___   ___   _|
 _| |_  |_|  _| |_  |_|  _| |_ 
|  _  |  _  |_   _|  _  |  _  |
|_| |_| | |___| |___| | |_| |_|
 _   _  |  ___   ___  |  _   _ 
| |_| | |_|  _| |_  |_| | |_| |
|_   _|  _  |_   _|  _  |_   _|
 _| |___| |___| |___| |___| |_ 

Clarifications

• My question is similar to Draw the Hilbert Curve and Draw the Hilbert curve using slashes.
• The conversion between underscores (_) and vertical bars (|) is u=2*v-1 where u is the number of _s and v is the number of |s.
• To maintain consistency with my original post the curve must start and end at the bottom.
• You can have a full program or a function.
• Output to stdout (or something similar).
• You can have leading or trailing white-spaces, the output just needs to line up so that it looks like the examples.
• This is code-golf so shortest answer in bytes wins.

Answer 1

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.

Answer 2

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.