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 ┘
).
![Level 3 Hilbert Curve showing the reflection across the vertical axis](../../I/static/images/86d04dacd93dc7e245505dc9d4288d8a853fc36a2cb0c4b41483c83ca9daf44e.png)
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 ┘
).
![Level 3 Hilbert Curve showing the reflection across the horizontal axis in the bottom left corner](../../I/static/images/c49711fc11c1af6126bf043098bb7b35fc23c9e491ab34b3512bae368abb6690.png)
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.
![Level 3 Hilbert Curve showing how the top right block of the bottom left corner can be derived](../../I/static/images/99c3e7a6261e444a8810bae2cdf2cb3513aba62a5cf0098e2a78c2116ba0e3dd.png)
And the left hand block can be derived from a vertical reflection of the block in the very top left of the full curve.
![Level 3 Hilbert Curve showing how the top left block of the bottom left corner can be derived](../../I/static/images/968c13e8a67afa52b3c51a2aa953a48d1ec123b5ef930f0b4b9b46cc94696433.png)
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 └
.
![Level 3 Hilbert Curve showing how the top left block of the bottom left corner can be derived](../../I/static/images/4b35b4149471215c3f1881c1706b6f25aad2d04f934027fb11364b3ee26144f0.png)
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 │
.
![Sequence of images showing how the remaining parts of the curve are derived](../../I/static/images/ed30490b3971932e70f9071dfc403675579f19e2a507abe3f7b788155d3c553b.png)
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.
![Level 2 Hilbert Curve rendered as ASCII art and with box characters](../../I/static/images/5ffc94aff1eae485d0a23667a2341375122d77d678fb98ec095cdbfbcf646b43.png)
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.
3Could you please include a definition of the Hilbert Curve in you post, and the exact specifications for how the ASCII version is constructed? – Loovjo – 2016-12-24T11:15:51.993
@Bobas_Pett: Not [tag:kolmogorov-complexity] – shooqie – 2016-12-24T11:20:28.133
@shooqie there's some debate on that on meta
– trichoplax – 2016-12-24T11:25:54.820@Loovjo I added in a point about the lengths of underscores (_) and vertical bars (|) under "Clarifications", if more information or a rigorous definition is still needed please tell me. – Bobas_Pett – 2016-12-24T13:09:27.807
@shooqie i removed the tag – Bobas_Pett – 2016-12-24T13:12:04.260
Your examples show the ends of the hilbert curve at the bottom, but this not specified. Is it a requirement that ends be at the bottom, or can it be rotated 90 / 180 degrees? If variation is allowed, is it acceptable for different values of n to have the ends in different places? – Level River St – 2016-12-25T02:31:33.117
@LevelRiverSt sorry this wasn't specified when i first posted the question I made edit under "Clarifications". – Bobas_Pett – 2016-12-25T05:37:22.017