Aloft Dev Log 2: How I learned to stop worrying and love the FEM
The past week or so I have been working on getting to grips with GameMakers built in physics system, which I intend to use for simulating the internal wood/metal structures of the larger rigid airships, and parts like the cabin/gondola on smaller non-rigids. Nothing particularly interesting to show for that yet though, so I thought I'd talk a bit about the gas simulation system I've implemented, which I showed off in the first update.
Firstly a bit of background on how I came to settle on the gas simulation system I have now. I've been playing with GameMaker on and off for a couple of years in my spare time, coming up with various game ideas and trying them out; no finished projects came out of this, but each one taught me a great deal about working in GM.
At some point I came across the LiquidFun particle system (http://google.github.io/liquidfun/), a subset of which is implemented in GM, and noticed while watching the videos that there was a demonstration showing working particle based bouyancy. This immediately got me thinking about airships and if I could re-purpose that system, with "air" particles instead of water, to simulate the way they fly.
I made a prototype using this system where the lifting gas inside the airship envelope was simulated as physics particles, and while the results were initially encouraging after some more in-depth testing I realised the system was going to be unsuitable; the chief problem was that GM did not provide a way to make a physics enabled collide-able skin to contain the lifting gas - the only solution I could find was to constantly create/destroy a rigid polygonal envelope every game iteration, with it's shape being modified by some physics "probes" reacting to the gas. This caused instability in the physics system, with gas frequently escaping, and would cause performance problems when scaled up to a larger system. Here's a little gif of that first prototype, working as well as it ever did:
However in the time I'd spent working on it, I'd been thinking about the wider concept of making the obvious game that could use this system - one where the player builds airships. I was pretty convinced this would make for an interesting and unique game, so I decided to look for an alternate solution to the gas simulation problem.
A Better (Finite Element) Method
I'd become quite familiar with the methods used for calculating atmospheric buoyancy when validating the performance of the particle based system versus reality, and the maths involved were really not very complicated. This led me to try a new approach based on the finite element method or FEM; FEM is used extensively in all kinds of engineering to model how real world physical systems behave, and I'd worked with them previously. The basic idea is you take an area of space you want to model, like water flowing through a pipe, and then chop it up into little chunks ("elements"). You then use standard scientific principles to calculate the behaviour of each little chunk, based on the initial conditions and states of those around it; you eventually build up a picture of the entire thing you wish to model. Wikipedia probably has a better explanation if you want to know more (https://en.wikipedia.org/wiki/Finite_element_method).
The finite element method usually takes a lot of computing power to run, running simulations that can take multiple days on supercomputers; this means it is mostly ignored in real-time applications such as games. However FEM is only that processor intensive because it is usually run on a 3D grid of elements which are individually extremely small and therefore numerous. I on the other hand only need to simulate my airship lifting gas on a 2D grid (meaning each element would only have to consider 7 neighbouring elements instead of the 25 required in a 3D space) and I could get away with much larger elements because solution accuracy was a secondary concern (each gas element in my current prototype is 4m per side).
The first thing I knew when I adapted the FEM approach to real-time was that I still wanted to use GameMakers physics system for the more mundane bits of physics - the simulation of rigid structures, forces (e.g. turbulence) being applied to the hull of the airship etc. To do that my FEM gas simulation system had to have a point at which the maths behind it connected into the physics simulation in a continuous, non-disruptive way. I did the obvious, which was the construct the "skin" of the airships gas envelope out of physics enabled nodes, tied together by elastic connections (neatly simulating the elastic nature of a balloon's skin). This is part 1 in the diagram below.
Next I needed to use that shape described by those nodes to define which parts of the "gas grid" were inside or outside of the envelope, so that I could correctly allow gas to spread. To do this I used a really cool math trick called a "winding number" (https://en.wikipedia.org/wiki/Winding_number); essentially this allows you to really quickly determine if some point lines within a shape defined by a set of other points by counting how many times an imaginary observer standing at the testing point would turn a full 360 degrees if they looked at each container point in turn; it's quick, intuitive and completely effective. In part 2 of the diagram below you can see each element in the gas grid within the envelope has been marked with a 1.
Finally once the gas simulation within the grid had been finalised I needed that information to feed back out into the rest of the physics system via the skin "nodes". There were two problems here - firstly I needed to know which elements in the gas grid were the "border" elements, as they were the ones whose physical properties would affect the skin nodes, and secondly I need a way to assign which skin nodes received the pressure forces from which border gas elements, which was important to make sure the simulation was physically accurate. After a bit of searching both of these problems were handily solved by a useful algorithm called "Marching Squares" (https://en.wikipedia.org/wiki/Marching_squares); so called because it takes a grid of various numbers and will then "march" out the contour lines between values above/below a certain value - in my case this was easy, I just wanted the borders between 0 and 1 in my gas area masking layer. The algorithm then populates a new grid with numbers, each of which indicates what, if any, kind of border exists between 0 and 1 in the current grid square. Once that is done it is a simple matter to iterate through each grid square marked as a border and assign them to the nearest physical skin node. This is shown in part 3 of the diagram below, with the grid showing the numbers output by the marching squares algorithm and the coloured groups of dots around the envelope border each being physically linked to an envelope skin "node".
This explanation has gone on pretty long now, so I think I'll save the explanation of the rules followed by the gas for another time. For now, here's a little gif I made of me testing out a cigar shaped gas envelope in my simulation - it's a bit jumpy because I haven't really tuned it, but you can see the method of cross connection that will be used to make the gas bags conform to more complicated shapes.
If you got this far good job, and thanks for reading!