Added ASCII fluid simulator article

1 files changed, 537 insertions, 0 deletions

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 %}
+<h4>ASCII Fluid Simulator</h4>
+
+<p>Git repository: <a href="/cgi-bin/cgit.cgi/fluid-sim">Link</a><br />
+Yusuke Endoh's original:
+<a href="https://web.archive.org/web/20190127192827/http://www.ioccc.org/2012/endoh1/hint.html"
+class="external">IOCCC</a> <a href="https://invidious.namazso.eu/watch?v=QMYfkOtYYlg" class="external">
+Invidious</a> <a href="https://www.youtube.com/watch?v=QMYfkOtYYlg" class="external">Youtube</a></p>
+
+<h5>26/11/2022</h5>
+
+
+<h5>Overview</h5>
+
+<p>One of the submissions for the 2012 International Obfuscated C Code Contest was
+a 23, 30, or 31 line piece of seeming
+<a href="https://web.archive.org/web/20201111232320/http://ioccc.org/2012/endoh1/endoh1.c"
+class="external">nonsense code</a> 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.</p>
+
+<p>While it didn't win, it did receive an honorable mention and has also attracted the occasional
+<a href="https://hackaday.com/2015/03/07/animated-ascii-fluid-dynamics-simulator-is-retro-cool/"
+class="external">article</a> over the years since then. Often with commenters in awe of how it
+does what it does. Because it is damned cool.</p>
+
+<div class="figure">
+    <!--  In an ideal world this object would be 806x490, but...  -->
+    <object type="application/xhtml+xml" data="/vidframe/endoh1_column_preview.xhtml"
+            width="806" height="500">
+    </object>
+    <div class="figcaption">Endoh's fluid simulator with input column.txt, monochrome version</div>
+</div>
+
+<p>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
+<a href="https://en.wikipedia.org/wiki/Smoothed-particle_hydrodynamics" class="external">
+smoothed-particle hydrodynamics</a> 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.</p>
+
+<p>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.</p>
+
+
+<h5>Reading Input</h5>
+
+<p>First thing to note is what we are dealing with. Every particle is stored as a structure
+containing five values:</p>
+
+<ul>
+    <li><i>Position</i>, a two dimensional quantity, typically a complex number.</li>
+    <li><i>Is_Wall</i>, a flag denoting whether or not that particle is a solid wall or not.</li>
+    <li><i>Density</i>, a one dimensional real valued quantity.</li>
+    <li><i>Acceleration</i>, another complex number.</li>
+    <li><i>Velocity</i>, yet another complex number.</li>
+</ul>
+
+<p>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.</p>
+
+<p>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.</p>
+
+<p>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.</p>
+
+<p>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.</p>
+
+
+<h5>Various Constants</h5>
+
+<p>Before going into the physics calculations, there are a handful of useful constants that are
+going to be needed:</p>
+
+<ul>
+    <li><math xmlns="http://www.w3.org/1998/Math/MathML"><mi>R</mi></math>, a radius distance from a
+    given particle, set here to be 2</li>
+    <li><math xmlns="http://www.w3.org/1998/Math/MathML"><mi>m</mi></math>, the mass of a given
+    particle, set as 1</li>
+    <li><math xmlns="http://www.w3.org/1998/Math/MathML">
+        <msub>
+            <mi>&#x03C1;<!-- ρ --></mi>
+            <mn>0</mn>
+        </msub>
+    </math>, a density constant used in calculating interaction forces, set as 1.5</li>
+    <li><math xmlns="http://www.w3.org/1998/Math/MathML"><mi>G</mi></math>, the gravitational
+    constant, which will be set to a magnitude of 1</li>
+    <li><math xmlns="http://www.w3.org/1998/Math/MathML"><mi>P</mi></math>, the pressure parameter,
+    which will be set to 4</li>
+    <li><math xmlns="http://www.w3.org/1998/Math/MathML"><mi>&#x03BC;<!-- μ --></mi></math>, the
+    viscosity parameter, which will be set to 8</li>
+</ul>
+
+<p>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
+<math xmlns="http://www.w3.org/1998/Math/MathML">
+    <mrow>
+        <mn>0</mn>
+        <mo>+</mo>
+        <mi>i</mi>
+    </mrow>
+</math>. Endoh avoids this issue by switching the axes.</p>
+
+<p>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.</p>
+
+
+<h5>Calculating Density</h5>
+
+<p>The density of each particle can be calculated by:</p>
+
+<div class="precontain"><div class="mathblock">
+    <math xmlns="http://www.w3.org/1998/Math/MathML">
+        <msub>
+            <mi>&#x03C1;<!-- ρ --></mi>
+            <mi>i</mi>
+        </msub>
+        <mo>=</mo>
+        <mrow>
+            <munder>
+                <mo>&#x2211;<!-- ∑ --></mo>
+                <mrow>
+                    <mi>j</mi>
+                    <mo>&#x2208;<!-- ∈ --></mo>
+                    <msub>
+                        <mi>&#x03A9;<!-- Ω --></mi>
+                        <msub>
+                            <mi>r</mi>
+                            <mi>i</mi>
+                        </msub>
+                    </msub>
+                </mrow>
+            </munder>
+            <msub>
+                <mi>m</mi>
+                <mi>j</mi>
+            </msub>
+            <mi>W</mi>
+            <mo stretchy="false">(</mo>
+            <mo fence="false" stretchy="false">&#x007C;<!-- | --></mo>
+            <msub>
+                <mi>r</mi>
+                <mi>i</mi>
+            </msub>
+            <mo>&#x2212;<!-- − --></mo>
+            <msub>
+                <mi>r</mi>
+                <mi>j</mi>
+            </msub>
+            <mo fence="false" stretchy="false">&#x007C;<!-- | --></mo>
+            <mo stretchy="false">)</mo>
+        </mrow>
+    </math><br /><br />
+    where<br /><br />
+    <math xmlns="http://www.w3.org/1998/Math/MathML">
+        <mi>&#x03C1;<!-- ρ --></mi>
+    </math>
+    is particle density<br />
+    <math xmlns="http://www.w3.org/1998/Math/MathML">
+        <mi>r</mi>
+    </math>
+    is particle position<br />
+    <math xmlns="http://www.w3.org/1998/Math/MathML">
+        <msub>
+            <mi>&#x03A9;<!-- Ω --></mi>
+            <mi>r</mi>
+        </msub>
+    </math>
+    is the circular area around the position
+    <math xmlns="http://www.w3.org/1998/Math/MathML">
+        <mi>r</mi>
+    </math>
+    with a radius equal to
+    <math xmlns="http://www.w3.org/1998/Math/MathML">
+        <mi>R</mi>
+    </math><br />
+    <math xmlns="http://www.w3.org/1998/Math/MathML">
+        <mi>W</mi>
+    </math>
+    is the kernel function defined here as<br /><br />
+    <math xmlns="http://www.w3.org/1998/Math/MathML">
+        <mrow>
+            <mi>W</mi>
+            <mo stretchy="false">(</mo>
+            <mi>d</mi>
+            <mo stretchy="false">)</mo>
+        </mrow>
+        <mo>=</mo>
+        <msup>
+            <mrow>
+                <mo stretchy="false">(</mo>
+                <mfrac>
+                    <mi>d</mi>
+                    <mi>R</mi>
+                </mfrac>
+                <mo>&#x2212;<!-- − --></mo>
+                <mn>1</mn>
+                <mo stretchy="false">)</mo>
+            </mrow>
+            <mn>2</mn>
+        </msup>
+    </math><br /><br />
+    and<br /><br />
+    <math xmlns="http://www.w3.org/1998/Math/MathML">
+        <mi>m</mi>
+        <mo>,</mo>
+        <mi>R</mi>
+    </math>
+    are the constants defined earlier
+</div></div>
+
+<p>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 <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>W</mi>
+</math> function, multiply by the particle mass of 1, and sum up all these intermediate results.
+That's the particle's density.</p>
+
+<p>Particles that are part of a solid wall get an additional density of 9, so don't forget to add
+that too.</p>
+
+<p>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.</p>
+
+
+<h5>Calculating Acceleration</h5>
+
+<p>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:</p>
+
+<div class="precontain"><div class="mathblock">
+    <math xmlns="http://www.w3.org/1998/Math/MathML">
+        <msubsup>
+            <mi>a</mi>
+            <mi>i</mi>
+            <mrow>
+                <mi>i</mi>
+                <mi>n</mi>
+                <mi>t</mi>
+                <mi>e</mi>
+                <mi>r</mi>
+                <mi>a</mi>
+                <mi>c</mi>
+                <mi>t</mi>
+            </mrow>
+        </msubsup>
+        <mo>=</mo>
+        <mrow>
+            <munder>
+                <mo>&#x2211;<!-- ∑ --></mo>
+                <mrow>
+                    <mi>j</mi>
+                    <mo>&#x2208;<!-- ∈ --></mo>
+                    <msub>
+                        <mi>&#x03A9;<!-- Ω --></mi>
+                        <msub>
+                            <mi>r</mi>
+                            <mi>i</mi>
+                        </msub>
+                    </msub>
+                </mrow>
+            </munder>
+            <mfrac>
+                <mrow>
+                    <mn>1</mn>
+                    <mo>&#x2212;<!-- − --></mo>
+                    <mi>q</mi>
+                    <mo stretchy="false">(</mo>
+                    <mi>i</mi>
+                    <mo>,</mo>
+                    <mi>j</mi>
+                    <mo stretchy="false">)</mo>
+                </mrow>
+                <msub>
+                    <mi>&#x03C1;<!-- ρ --></mi>
+                    <mi>j</mi>
+                </msub>
+            </mfrac>
+            <mo>&it;</mo>
+            <mo stretchy="false">[</mo>
+            <mi>P</mi>
+            <mo>&it;</mo>
+            <mo stretchy="false">(</mo>
+            <msub>
+                <mi>&#x03C1;<!-- ρ --></mi>
+                <mi>i</mi>
+            </msub>
+            <mo>+</mo>
+            <msub>
+                <mi>&#x03C1;<!-- ρ --></mi>
+                <mi>j</mi>
+            </msub>
+            <mo>&#x2212;<!-- − --></mo>
+            <mn>2</mn>
+            <mo>&it;</mo>
+            <msub>
+                <mi>&#x03C1;<!-- ρ --></mi>
+                <mn>0</mn>
+            </msub>
+            <mo stretchy="false">)</mo>
+            <mo>&it;</mo>
+            <mo stretchy="false">(</mo>
+            <msub>
+                <mi>r</mi>
+                <mi>i</mi>
+            </msub>
+            <mo>&#x2212;<!-- − --></mo>
+            <msub>
+                <mi>r</mi>
+                <mi>j</mi>
+            </msub>
+            <mo stretchy="false">)</mo>
+            <mo>&#x2212;<!-- − --></mo>
+            <mi>&#x03BC;<!-- μ --></mi>
+            <mo>&it;</mo>
+            <mo stretchy="false">(</mo>
+            <msub>
+                <mi>v</mi>
+                <mi>i</mi>
+            </msub>
+            <mo>&#x2212;<!-- − --></mo>
+            <msub>
+                <mi>v</mi>
+                <mi>j</mi>
+            </msub>
+            <mo stretchy="false">)</mo>
+            <mo stretchy="false">]</mo>
+        </mrow>
+    </math><br /><br />
+    where<br /><br />
+    <math xmlns="http://www.w3.org/1998/Math/MathML">
+        <msup>
+            <mi>a</mi>
+            <mrow>
+                <mi>i</mi>
+                <mi>n</mi>
+                <mi>t</mi>
+                <mi>e</mi>
+                <mi>r</mi>
+                <mi>a</mi>
+                <mi>c</mi>
+                <mi>t</mi>
+            </mrow>
+        </msup>
+    </math>
+    is the interaction force acting on a particle<br />
+    <math xmlns="http://www.w3.org/1998/Math/MathML">
+        <mi>&#x03C1;<!-- ρ --></mi>
+    </math>
+    is particle density<br />
+    <math xmlns="http://www.w3.org/1998/Math/MathML">
+        <mi>r</mi>
+    </math>
+    is particle position<br />
+    <math xmlns="http://www.w3.org/1998/Math/MathML">
+        <msub>
+            <mi>&#x03A9;<!-- Ω --></mi>
+            <mi>r</mi>
+        </msub>
+    </math>
+    is the circular area around the position
+    <math xmlns="http://www.w3.org/1998/Math/MathML">
+        <mi>r</mi>
+    </math>
+    with a radius equal to
+    <math xmlns="http://www.w3.org/1998/Math/MathML">
+        <mi>R</mi>
+    </math><br />
+    <math xmlns="http://www.w3.org/1998/Math/MathML">
+        <mi>v</mi>
+    </math>
+    is particle velocity<br />
+    <math xmlns="http://www.w3.org/1998/Math/MathML">
+        <mi>q</mi>
+    </math>
+    is a function defined for convenience as<br /><br />
+    <math xmlns="http://www.w3.org/1998/Math/MathML">
+        <mrow>
+            <mi>q</mi>
+            <mo stretchy="false">(</mo>
+            <mi>x</mi>
+            <mo>,</mo>
+            <mi>y</mi>
+            <mo stretchy="false">)</mo>
+        </mrow>
+        <mo>=</mo>
+        <mfrac>
+            <mrow>
+                <mo stretchy="false">&#x007C;<!-- | --></mo>
+                <msub>
+                    <mi>r</mi>
+                    <mi>x</mi>
+                </msub>
+                <mo>&#x2212;<!-- − --></mo>
+                <msub>
+                    <mi>r</mi>
+                    <mi>y</mi>
+                </msub>
+                <mo stretchy="false">&#x007C;<!-- | --></mo>
+            </mrow>
+            <mi>R</mi>
+        </mfrac>
+    </math><br /><br />
+    and<br /><br />
+    <math xmlns="http://www.w3.org/1998/Math/MathML">
+        <mi>P</mi>
+        <mo>,</mo>
+        <msub>
+            <mi>&#x03C1;<!-- ρ --></mi>
+            <mn>0</mn>
+        </msub>
+        <mo>,</mo>
+        <mi>&#x03BC;<!-- μ --></mi>
+        <mo>,</mo>
+        <mi>R</mi>
+    </math>
+    are the constants defined earlier
+</div></div>
+
+<p>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.</p>
+
+<p>So, the gravity plus the interaction force. That's the particle's acceleration.</p>
+
+<p>Acceleration of non-wall particles can be ignored since they will never move and the value won't
+have any affect on other calculations.</p>
+
+
+<h5>Updating Particle Positions</h5>
+
+<p>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.</p>
+
+<p>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.</p>
+
+
+<h5>Display Rendering</h5>
+
+<p>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.</p>
+
+<p>The algorithm in use here is called <a href="https://en.wikipedia.org/wiki/Marching_squares"
+class="external">Marching Squares</a>. 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.</p>
+
+<p>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.</p>
+
+<div class="figure">
+    <img src="/img/marching_squares.png"
+         alt="Marching squares algorithm cell cases"
+         height="525"
+         width="525" />
+    <div class="figcaption">The 16 possibilities for rendering cells, with blue for empty space and
+    purple for filled areas</div>
+</div>
+
+<p>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.</p>
+
+<p>To clear the screen and reset the cursor between output renders,
+<a href="https://en.wikipedia.org/wiki/ANSI_escape_code" class="external">ANSI escape codes</a> 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.</p>
+
+<p>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.</p>
+
+
+<h5>Putting It All Together</h5>
+
+<p>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.</p>
+
+<p>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.</p>
+
+<div class="figure">
+    <!--  In an idea world this object would be 806x490, but...  -->
+    <object type="application/xhtml+xml" data="/vidframe/fluid_tanada_preview.xhtml"
+            width="806" height="500">
+    </object>
+    <div class="figcaption">My fluid simulator with input tanada.txt</div>
+</div>
+
+<p>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.</p>
+
+<p>Thank you Daniele Venier for your informative, if incomplete,
+<a href="http://asymptoticbits.com/posts/ascii-liquid/" class="external">article</a> 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.</p>
+
+{% endblock -%}
+
+