From 8e36b81714320657b7d06973daa4e769bb17de46 Mon Sep 17 00:00:00 2001 From: Jedidiah Barber Date: Sun, 27 Nov 2022 01:21:53 +1300 Subject: Added ASCII fluid simulator article --- project/templates/fluidsim.xhtml | 537 +++++++++++++++++++++ project/templates/tags/physics.xhtml | 10 + project/templates/vidframe/base_preview.xhtml | 60 +++ project/templates/vidframe/base_video.xhtml | 26 + project/templates/vidframe/base_vidframe.xhtml | 17 + .../templates/vidframe/endoh1_column_preview.xhtml | 9 + .../templates/vidframe/endoh1_column_video.xhtml | 11 + .../templates/vidframe/fluid_tanada_preview.xhtml | 9 + .../templates/vidframe/fluid_tanada_video.xhtml | 11 + 9 files changed, 690 insertions(+) create mode 100644 project/templates/fluidsim.xhtml create mode 100644 project/templates/tags/physics.xhtml create mode 100644 project/templates/vidframe/base_preview.xhtml create mode 100644 project/templates/vidframe/base_video.xhtml create mode 100644 project/templates/vidframe/base_vidframe.xhtml create mode 100644 project/templates/vidframe/endoh1_column_preview.xhtml create mode 100644 project/templates/vidframe/endoh1_column_video.xhtml create mode 100644 project/templates/vidframe/fluid_tanada_preview.xhtml create mode 100644 project/templates/vidframe/fluid_tanada_video.xhtml (limited to 'project/templates') diff --git a/project/templates/fluidsim.xhtml b/project/templates/fluidsim.xhtml new file mode 100644 index 0000000..5537712 --- /dev/null +++ b/project/templates/fluidsim.xhtml @@ -0,0 +1,537 @@ + +{%- extends "base_math.xhtml" -%} + + + +{%- block title -%}ASCII Fluid Simulator{%- endblock -%} + + + +{%- block footer -%}{{ math_footer ("fluidsim.xhtml") }}{%- endblock -%} + + + +{%- block content %} +

ASCII Fluid Simulator

+ +

Git repository: Link
+Yusuke Endoh's original: +IOCCC +Invidious Youtube

+ +

26/11/2022

+ + +

Overview

+ +

One of the submissions for the 2012 International Obfuscated C Code Contest was +a 23, 30, or 31 line piece of seeming +nonsense code that did... something. When fed appropriately sized text as +input, all characters except for instances of '#' would melt and flow as if liquid. It was a fluid +simulator that worked with ASCII text in the terminal.

+ +

While it didn't win, it did receive an honorable mention and has also attracted the occasional +article over the years since then. Often with commenters in awe of how it +does what it does. Because it is damned cool.

+ +

Endoh's fluid simulator with input column.txt, monochrome version

+ +

So it's doing some sort of black magic to accomplish this, right? Well, yes, but also no. +Condensing and obfuscating the code to fit in 23 lines as in the original monochrome version is +definitely some impressive magic. But actually simulating a fluid in textual form is surprisingly +easy. What's going on is it's running a simplified version of + +smoothed-particle hydrodynamics which involves nothing more complicated than addition, +subtraction, multiplication, division, exponentiation, and square roots. And technically also +complex numbers, because they tend to be the most accessible way to deal with two dimensional +values. Nothing too difficult.

+ +

To prove how easy it is, the rest of this article is going to detail what you need to know so +that you too can write your very own comprehensible knockoff version.

+ + +

Reading Input

+ +

First thing to note is what we are dealing with. Every particle is stored as a structure +containing five values:

+ +

Position, a two dimensional quantity, typically a complex number.
Is_Wall, a flag denoting whether or not that particle is a solid wall or not.
Density, a one dimensional real valued quantity.
Acceleration, another complex number.
Velocity, yet another complex number.

+ +

These particles can be stored in whatever convenient data structure you like. The most natural is +probably a vector since the program isn't sure how much input it is going to be given, but an array +can also be made to work.

+ +

Reading in the input is just done with standard text I/O functions. But here is a very important +detail to note: Each character of ASCII input actually denotes two particles, one just above the +other in position. That is, while the input is usually a textfile with no more than 25 rows, once it +is read into the program you will have double the number of particles spread across an 80x50 field. +The display algorithm will scale it back to 25 later on.

+ +

If you do not double up the input like this, your simulator will still work, but it won't look +quite right. Details like how high particles bounce will be off.

+ +

Also note that by typical terminal conventions, coordinates (1,1) are at the top left corner and +numbers increase as you go down and right. Following this convention will make reading in input +easier, but will have some implications for gravity.

+ + +

Various Constants

+ +

Before going into the physics calculations, there are a handful of useful constants that are +going to be needed:

+ +

$R$ , a radius distance from a + given particle, set here to be 2
$m$ , the mass of a given + particle, set as 1
$+ +_{ρ + 0 +} +$ , a density constant used in calculating interaction forces, set as 1.5
$G$ , the gravitational + constant, which will be set to a magnitude of 1
$P$ , the pressure parameter, + which will be set to 4
$μ$ , the + viscosity parameter, which will be set to 8

+ +

Note that while the gravitational constant magnitude is set to 1, care still has to be taken to +make sure the value is oriented in the correct direction. If terminal conventions are being followed +for axis orientation then the value will actually be the complex number + $+ + 0 + + + i + +$ . Endoh avoids this issue by switching the axes.

+ +

Also note that while the documentation for Endoh's simulator claims the gravitational, pressure, +and viscosity parameters are set to 1, 4, 8 as they are here, there is actually an error in his +makefile. As a result the viscosity constant is set equal to the pressure constant, causing them +to take on values of 1, 4, 4 by default instead.

+ + +

Calculating Density

+ +

The density of each particle can be calculated by:

+ +

+ +_{ρ + i +} + = + + \underset{\sum}{+} + +_{m + j +} + W + (+ | + +_{r + i +} + - + +_{r + j +} + | +) + +

+ where

+

+ ρ +

+ is particle density
+

+ r +

+ is particle position
+

+ +_{Ω + r +} +

+ is the circular area around the position +

+ r +

+ with a radius equal to +

+ R +

+ W +

+ is the kernel function defined here as

+

+ + W + (+ d +) + + = + +^{+ (+ \frac{+}{d} + - + 1 +) + + 2 +} +

+ and

+

+ m +, + R +

+ are the constants defined earlier +

+ +

Or in other words, for each particle, find all the other particles within a radius of 2, weight +the distance between the two by the $W +$ function, multiply by the particle mass of 1, and sum up all these intermediate results. +That's the particle's density.

+ +

Particles that are part of a solid wall get an additional density of 9, so don't forget to add +that too.

+ +

It is recommended that you do this step before you render any output results since you may want +to use density values to color the output. Endoh's simulator doesn't bother, however.

+ + +

Calculating Acceleration

+ +

The acceleration of each non-wall particle is the sum of two components, gravity and interaction +forces. Gravity is very simple as it is just the gravitational constant already defined earlier. The +interaction forces acting on each particle can be calculated by:

+ +

+ +_{a}^{+} + = + + \underset{\sum}{+} + \frac{+}{+ 1 + - + q + (+ i +, + j +) +} + + [+ P + + (+ +_{ρ + i +} + + + +_{ρ + j +} + - + 2 + + +_{ρ + 0 +} +) + + (+ +_{r + i +} + - + +_{r + j +} +) + - + μ + + (+ +_{v + i +} + - + +_{v + j +} +) +] + +

+ where

+

+ +^{a + + i + n + t + e + r + a + c + t + +} +

+ is the interaction force acting on a particle
+

+ ρ +

+ is particle density
+

+ r +

+ is particle position
+

+ +_{Ω + r +} +

+ is the circular area around the position +

+ r +

+ with a radius equal to +

+ R +

+ v +

+ is particle velocity
+

+ q +

+ is a function defined for convenience as

+

+ + q + (+ x +, + y +) + + = + \frac{+}{+ | + +_{r + x +} + - + +_{r + y +} + | +} +

+ and

+

+ P +, + +_{ρ + 0 +} +, + μ +, + R +

+ are the constants defined earlier +

+ +

A lot to take in, I know. A bit too much to rephrase in plain english this time, even though it +is a simplified form compared to the usual smoothed-particle hydrodynamics formula. But as promised, +once you get past all the variables there is still only elementary math involved.

+ +

So, the gravity plus the interaction force. That's the particle's acceleration.

+ +

Acceleration of non-wall particles can be ignored since they will never move and the value won't +have any affect on other calculations.

+ + +

Updating Particle Positions

+ +

As implemented in Endoh's simulator this is by far the easiest step. For each non-wall particle, +merely divide the acceleration value by 10 then add that to the velocity value. Then add the +velocity to the particle's position. The division by 10 is an arbitrary scaling factor to make +things work in the space a standard 80x25 size terminal gives us.

+ +

If you want to go the extra mile and add collision detection between moving particles and wall +particles, this would be the step to implement it. I haven't bothered. Partially because collision +detection is tricky, but also because doing so would result in visibly different behaviour.

+ + +

Display Rendering

+ +

Believe it or not, this is actually the most complicated part of this whole thing. It might be +fairly easy to explain in concept, but the actual implementation is more finnicky than any of the +previous steps.

+ +

The algorithm in use here is called Marching Squares. You calculate whether there are any particles present at the +corners of each character cell on an 80x25 terminal, then use those results to look up which +character should go in that cell from a predetermined mapping of cases to output characters. Some +experimentation may be required to find characters that look close enough, as the ASCII character +set was not made with this in mind.

+ +

Be sure to scale the vertical axis back down by a factor of 2 before you perform these +calculations in order to take the input doubling into account.

+ +

The 16 possibilities for rendering cells, with blue for empty space and + purple for filled areas

+ +

Various small tricks with bitwise-or operations can be used to make this process more efficient, +but going into those is beyond the scope of this article.

+ +

To clear the screen and reset the cursor between output renders, +ANSI escape codes are +used. They are also used if you want to add color to the output, with an escape code inserted before +each character to change the color according to the average density of the particles contributing to +that cell. Since the escape codes to do this are quite long, the resulting string will get decently +large. It won't affect the size when displayed to the terminal, however.

+ +

In my experience, the average density in a given cell usually remains in the range 0-20 unless in +the middle of a thick solid wall. Scaling the colors used to that range tends to work well.

+ + +

Putting It All Together

+ +

The entire program consists of reading in the input, then looping through calculating density, +rendering output, calculating acceleration, and updating the particle positions. That's really it. +The only other thing you will probably want to do is have some step to get rid of particles should +their position go too far off-screen. Both to avoid unnecessary computation and the potential for +values to overflow and cause an error.

+ +

The calculation and update steps are all embarrassingly parallel, so if you're looking for places +to improve things beyond adding color then there would be a good place to start. Neither Endoh's +implementation nor mine do anything with that, but that is more due to lack of need to put in the +effort.

+ +

My fluid simulator with input tanada.txt

+ +

Now, was this entire exercise ultimately pointless, since it is concerned with ASCII rendering +done by intentionally obfuscated code? Yes. Was it nonetheless interesting and fun? Also yes.

+ +

Thank you Daniele Venier for your informative, if incomplete, +article on this same +topic which let me avoid having to analyse the IOCCC entry from scratch myself. Although really, it +probably would have still been easier to construct something from first principles anyway.

+ +{% endblock -%} + + diff --git a/project/templates/tags/physics.xhtml b/project/templates/tags/physics.xhtml new file mode 100644 index 0000000..c88b7e5 --- /dev/null +++ b/project/templates/tags/physics.xhtml @@ -0,0 +1,10 @@ + +{%- extends "tags/base_tag.xhtml" -%} + + + +{%- block title -%}{{ tag_title ("Physics") }}{%- endblock -%} +{%- block content %}{{ tag_content ("Physics") }}{% endblock -%} +{%- block footer -%}{{ tag_footer ("physics.xhtml") }}{%- endblock -%} + + diff --git a/project/templates/vidframe/base_preview.xhtml b/project/templates/vidframe/base_preview.xhtml new file mode 100644 index 0000000..eaf0bea --- /dev/null +++ b/project/templates/vidframe/base_preview.xhtml @@ -0,0 +1,60 @@ + +{%- extends "vidframe/base_vidframe.xhtml" -%} + + + +{%- block style %} + body { + background-color: black; + } + a { + position: absolute; + top: 0; + left: 0; + } + img.thumb { + opacity: 0.5; + } + div.playbutton { + opacity: 1.0; + position: absolute; + width: 100%; + height: 100%; + top: 0; + left: 0; + } + svg { + position: absolute; + fill: #fff; + width: 100px; + height: 100px; + left: 50%; + top: 50%; + transform: translate(-50%, -50%); + } + div.playbutton:hover svg, + div.playbutton:focus svg { + fill: #17e617; + } +{% endblock -%} + + + +{%- block video %} +

+ +

+ + + + + +

+{% endblock -%} + + diff --git a/project/templates/vidframe/base_video.xhtml b/project/templates/vidframe/base_video.xhtml new file mode 100644 index 0000000..f298705 --- /dev/null +++ b/project/templates/vidframe/base_video.xhtml @@ -0,0 +1,26 @@ + +{%- extends "vidframe/base_vidframe.xhtml" -%} + + + +{%- block style %} + body { + margin: 0; + padding: 0; + } +{% endblock -%} + + + +{%- block video %} +

+{% endblock -%} + + diff --git a/project/templates/vidframe/base_vidframe.xhtml b/project/templates/vidframe/base_vidframe.xhtml new file mode 100644 index 0000000..4f2e00e --- /dev/null +++ b/project/templates/vidframe/base_vidframe.xhtml @@ -0,0 +1,17 @@ + + + + + + + + + +{% block video -%} +{%- endblock %} + + diff --git a/project/templates/vidframe/endoh1_column_preview.xhtml b/project/templates/vidframe/endoh1_column_preview.xhtml new file mode 100644 index 0000000..9a444e6 --- /dev/null +++ b/project/templates/vidframe/endoh1_column_preview.xhtml @@ -0,0 +1,9 @@ + +{%- extends "vidframe/base_preview.xhtml" -%} + + + +{%- block vidlink -%}/vidframe/endoh1_column_video.xhtml{%- endblock -%} +{%- block thumbnail -%}/vid/endoh1_column.jpg{%- endblock -%} + + diff --git a/project/templates/vidframe/endoh1_column_video.xhtml b/project/templates/vidframe/endoh1_column_video.xhtml new file mode 100644 index 0000000..3cebb18 --- /dev/null +++ b/project/templates/vidframe/endoh1_column_video.xhtml @@ -0,0 +1,11 @@ + +{%- extends "vidframe/base_video.xhtml" -%} + + + +{%- block vidfile -%}/vid/endoh1_column.mp4{%- endblock -%} +{%- block vidwidth -%}806{%- endblock -%} +{%- block vidheight -%}490{%- endblock -%} +{%- block backup -%}/vid/endoh1_column.mp4{%- endblock -%} + + diff --git a/project/templates/vidframe/fluid_tanada_preview.xhtml b/project/templates/vidframe/fluid_tanada_preview.xhtml new file mode 100644 index 0000000..9e27878 --- /dev/null +++ b/project/templates/vidframe/fluid_tanada_preview.xhtml @@ -0,0 +1,9 @@ + +{%- extends "vidframe/base_preview.xhtml" -%} + + + +{%- block vidlink -%}/vidframe/fluid_tanada_video.xhtml{%- endblock -%} +{%- block thumbnail -%}/vid/fluid_tanada.jpg{%- endblock -%} + + diff --git a/project/templates/vidframe/fluid_tanada_video.xhtml b/project/templates/vidframe/fluid_tanada_video.xhtml new file mode 100644 index 0000000..4328290 --- /dev/null +++ b/project/templates/vidframe/fluid_tanada_video.xhtml @@ -0,0 +1,11 @@ + +{%- extends "vidframe/base_video.xhtml" -%} + + + +{%- block vidfile -%}/vid/fluid_tanada.mp4{%- endblock -%} +{%- block vidwidth -%}806{%- endblock -%} +{%- block vidheight -%}490{%- endblock -%} +{%- block backup -%}/vid/fluid_tanada.mp4{%- endblock -%} + + -- cgit