diff options
Diffstat (limited to 'project/templates/fluidsim.xhtml')
| -rw-r--r-- | project/templates/fluidsim.xhtml | 537 |
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>ρ<!-- ρ --></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>μ<!-- μ --></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>ρ<!-- ρ --></mi> + <mi>i</mi> + </msub> + <mo>=</mo> + <mrow> + <munder> + <mo>∑<!-- ∑ --></mo> + <mrow> + <mi>j</mi> + <mo>∈<!-- ∈ --></mo> + <msub> + <mi>Ω<!-- Ω --></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">|<!-- | --></mo> + <msub> + <mi>r</mi> + <mi>i</mi> + </msub> + <mo>−<!-- − --></mo> + <msub> + <mi>r</mi> + <mi>j</mi> + </msub> + <mo fence="false" stretchy="false">|<!-- | --></mo> + <mo stretchy="false">)</mo> + </mrow> + </math><br /><br /> + where<br /><br /> + <math xmlns="http://www.w3.org/1998/Math/MathML"> + <mi>ρ<!-- ρ --></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>Ω<!-- Ω --></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>−<!-- − --></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>∑<!-- ∑ --></mo> + <mrow> + <mi>j</mi> + <mo>∈<!-- ∈ --></mo> + <msub> + <mi>Ω<!-- Ω --></mi> + <msub> + <mi>r</mi> + <mi>i</mi> + </msub> + </msub> + </mrow> + </munder> + <mfrac> + <mrow> + <mn>1</mn> + <mo>−<!-- − --></mo> + <mi>q</mi> + <mo stretchy="false">(</mo> + <mi>i</mi> + <mo>,</mo> + <mi>j</mi> + <mo stretchy="false">)</mo> + </mrow> + <msub> + <mi>ρ<!-- ρ --></mi> + <mi>j</mi> + </msub> + </mfrac> + <mo>⁢</mo> + <mo stretchy="false">[</mo> + <mi>P</mi> + <mo>⁢</mo> + <mo stretchy="false">(</mo> + <msub> + <mi>ρ<!-- ρ --></mi> + <mi>i</mi> + </msub> + <mo>+</mo> + <msub> + <mi>ρ<!-- ρ --></mi> + <mi>j</mi> + </msub> + <mo>−<!-- − --></mo> + <mn>2</mn> + <mo>⁢</mo> + <msub> + <mi>ρ<!-- ρ --></mi> + <mn>0</mn> + </msub> + <mo stretchy="false">)</mo> + <mo>⁢</mo> + <mo stretchy="false">(</mo> + <msub> + <mi>r</mi> + <mi>i</mi> + </msub> + <mo>−<!-- − --></mo> + <msub> + <mi>r</mi> + <mi>j</mi> + </msub> + <mo stretchy="false">)</mo> + <mo>−<!-- − --></mo> + <mi>μ<!-- μ --></mi> + <mo>⁢</mo> + <mo stretchy="false">(</mo> + <msub> + <mi>v</mi> + <mi>i</mi> + </msub> + <mo>−<!-- − --></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>ρ<!-- ρ --></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>Ω<!-- Ω --></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">|<!-- | --></mo> + <msub> + <mi>r</mi> + <mi>x</mi> + </msub> + <mo>−<!-- − --></mo> + <msub> + <mi>r</mi> + <mi>y</mi> + </msub> + <mo stretchy="false">|<!-- | --></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>ρ<!-- ρ --></mi> + <mn>0</mn> + </msub> + <mo>,</mo> + <mi>μ<!-- μ --></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 -%} + + |