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/assets/img/marching_squares.png | Bin 0 -> 59358 bytes project/assets/robots.txt | 4 + project/assets/vid/endoh1_column.jpg | Bin 0 -> 70112 bytes project/assets/vid/endoh1_column.mp4 | Bin 0 -> 1193216 bytes project/assets/vid/fluid_tanada.jpg | Bin 0 -> 56063 bytes project/assets/vid/fluid_tanada.mp4 | Bin 0 -> 1668509 bytes project/complexity.yml | 6 + project/context/articles.json | 6 + project/context/tags.json | 1 + 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 + 18 files changed, 707 insertions(+) create mode 100644 project/assets/img/marching_squares.png create mode 100644 project/assets/robots.txt create mode 100644 project/assets/vid/endoh1_column.jpg create mode 100644 project/assets/vid/endoh1_column.mp4 create mode 100644 project/assets/vid/fluid_tanada.jpg create mode 100644 project/assets/vid/fluid_tanada.mp4 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 diff --git a/project/assets/img/marching_squares.png b/project/assets/img/marching_squares.png new file mode 100644 index 0000000..6ca2d66 Binary files /dev/null and b/project/assets/img/marching_squares.png differ diff --git a/project/assets/robots.txt b/project/assets/robots.txt new file mode 100644 index 0000000..5d00a8e --- /dev/null +++ b/project/assets/robots.txt @@ -0,0 +1,4 @@ + +User-agent: * +Disallow: /vidframe/ + diff --git a/project/assets/vid/endoh1_column.jpg b/project/assets/vid/endoh1_column.jpg new file mode 100644 index 0000000..4d90d97 Binary files /dev/null and b/project/assets/vid/endoh1_column.jpg differ diff --git a/project/assets/vid/endoh1_column.mp4 b/project/assets/vid/endoh1_column.mp4 new file mode 100644 index 0000000..75c684f Binary files /dev/null and b/project/assets/vid/endoh1_column.mp4 differ diff --git a/project/assets/vid/fluid_tanada.jpg b/project/assets/vid/fluid_tanada.jpg new file mode 100644 index 0000000..ad9a586 Binary files /dev/null and b/project/assets/vid/fluid_tanada.jpg differ diff --git a/project/assets/vid/fluid_tanada.mp4 b/project/assets/vid/fluid_tanada.mp4 new file mode 100644 index 0000000..5cc0db0 Binary files /dev/null and b/project/assets/vid/fluid_tanada.mp4 differ diff --git a/project/complexity.yml b/project/complexity.yml index 7efaa87..64eeb99 100644 --- a/project/complexity.yml +++ b/project/complexity.yml @@ -15,6 +15,7 @@ unexpanded_templates: - "contributions.xhtml" - "deckconv.xhtml" - "fltkada.xhtml" + - "fluidsim.xhtml" - "grasp.xhtml" - "index.xhtml" - "integral.xhtml" @@ -38,9 +39,14 @@ unexpanded_templates: - "tags/library.xhtml" - "tags/maps.xhtml" - "tags/mathematics.xhtml" + - "tags/physics.xhtml" - "tags/politics.xhtml" - "tags/programming.xhtml" - "tags/transport.xhtml" - "tags/utility.xhtml" - "tags/videogames.xhtml" + - "vidframe/endoh1_column_preview.xhtml" + - "vidframe/endoh1_column_video.xhtml" + - "vidframe/fluid_tanada_preview.xhtml" + - "vidframe/fluid_tanada_video.xhtml" diff --git a/project/context/articles.json b/project/context/articles.json index e08c95c..e1a0c45 100644 --- a/project/context/articles.json +++ b/project/context/articles.json @@ -1,5 +1,11 @@ [ + { + "title": "ASCII Fluid Simulator", + "anchor": "/fluidsim.xhtml", + "taglist": ["application", "physics", "programming"], + "postdate": "26/11/2022" + }, { "title": "Number Wall Visualiser", "anchor": "/numberwall.xhtml", diff --git a/project/context/tags.json b/project/context/tags.json index 8910e07..323b09f 100644 --- a/project/context/tags.json +++ b/project/context/tags.json @@ -9,6 +9,7 @@ "library", "maps", "mathematics", + "physics", "politics", "programming", "transport", 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:

+ + + +

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:

+ + + +

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 + + = + + + ∑ + + j + ∈ + + Ω + + r + i + + + + + + 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 + ) + + = + + + ( + + d + R + + − + 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 + i + + i + n + t + e + r + a + c + t + + + = + + + ∑ + + j + ∈ + + Ω + + r + i + + + + + + + 1 + − + q + ( + i + , + j + ) + + + ρ + 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 + ) + + = + + + | + + r + x + + − + + r + y + + | + + R + +

+ 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.

+ +
+ Marching squares algorithm cell cases +
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 %} +
+ + Click to load 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 %} +
+ + Download 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