[Microbe] Implementing compound and agent clouds

Hi everyone,
since it's a pretty central part of the microbe stage, we need to talk about how we will handle the clouds of compounds and agents (from now on only referred to as "agents") that will float through the environment. However we implement it, the requirements are:

• Microbes must be able to gather agents, reducing the amount in the environment
  
• Microbes must be able to produce agents, increasing the amount in the environment
  
• Agents in the environment should be able to interact with each other
  
• Agent clouds must dissipate over time
  
• Agent clouds must diffuse over time
  
• The diffusion process should take currents into account
  
• Agent clouds should look good. Ideally, like a drop of ink in clear water.
  

So far, there are several ideas floating around on how to implement agent clouds.

Discrete particles
When inserting an agent cloud into the environment, spawn a handful of discrete, small entities that represent the particles. Touching a particle with a microbe removes this particle. Let the physics engine handle the simulation of currents, particles bumping into each other and similar.

Pros:

• Easy to implement
  
• Easy to understand for the player: "Touch a particle with the microbe, and it's gathered up"
  

Cons:

• Taxing on the physics engine if each particle has its own collision hull. Preliminary tests show that as few as 30 particles on screen can severely degrade performance, especially on Windows. The more particles touch each other, the worse it gets.
  
• Bland graphics. More like powerups, not like a chemical floating around.
  

Floating alpha map
When inserting an agent cloud into the environment, spawn an entity that holds an alpha map of suitable size. The values in this alpha map depict the concentration of the agent at this pixel. At each time step, a filter is run over the alpha map to simulate diffusion and dissipation. By biasing the diffusion filter in one direction, currents can be simulated. A microbe that enters the cloud causes an additional filter to be applied. This filter takes a bitmap depicting the microbe's shape, uses it as a mask for the agent alpha map, and decreases the agent concentration in the appropriate regions so that it looks like the microbe is gobbling up the agent.

Pros:

• With the right parameters for the filters, this should give a nice "cloudy" look for agents
  

Cons:

• Agents have to dissipate before reaching the edge of their alpha map. So either the dissipation is very quick or the alpha map must be very large.
  
• Big alpha maps may be quite taxing on the filters, reducing the overall framerate.
  
• Each time a new agent cloud is spawned, we need a new alpha map
  

Grid of alpha maps
The mechanics for spawning, diffusing and dissipating agents are exactly like in the floating alpha map approach above. The difference is that instead of one alpha map per agent spawn, the environment is partitioned into a rectangular grid of alpha maps, say 64x64 px per grid cell per agent. The alpha maps are created on demand, i.e. only when an agent cloud is spawned or when it diffuses over from an adjacent grid cell is the alpha map actually allocated. When the maximum concentration inside a grid cell reaches a low threshold, the alpha map is destroyed, freeing the memory.

Pros:

• With the right parameters for the filters, this should give a nice "cloudy" look for agents
  
• Agent clouds can freely diffuse through the game world without reaching the edge of their alpha map
  

Cons:

• Difficult to implement in comparison to the above approaches
  
• Care must be taken to allow grid cells to despawn in a timely manner, lest they hog processing resources.
  

Note that with both alpha map approaches, the concentration resolution is not required to be the same as the visual resolution. Depending on how we want to handle the rendering of agent clouds, we can easily translate a 2x2 or larger area on the screen to 1 pixel in the alpha map.

To me, the grid approach seems the most promising. Anybody have other ideas or remarks about the solutions presented?

This raises a few concerns.
For a discrete particle model, instead of giving particles collision hulls, can we represent them as points in the engine? Ideally the particles will be visibly small enough (about the size of this "o") for the player not to notice if it passes through their membrane slightly before they pick it up. Would that decrease the load on the engine substantially?
Does this mean that we'll need to keep the screen fairly clear of other microbes ingame because the physics engine can't handle too many entities?

For the floating map design, could we, as I suggested in the microbe stage main thread, judge what compounds a microbe picks up by the compound values in the centers of hexes at its functional edge, and decrease the cloud as a whole based on absorption instead of decreasing the compound value in areas a microbe has been through? I really don't think the "compound wake"- the area behind where a microbe just swam and absorbed the compounds- is very important in terms of gameplay.

For the grid map idea, (which I like) there may be a simpler solution based on how we run the fluid dynamics simulation. Is fluid dynamics grid based at all? A while ago I was thinking about how we could make a grid-based fluid dynamics simulation which would be imprecise but visually understandable, and I think, easy to run. Keep in mind that I don't know how fluid dynamics systems usually work, or if this idea is a flawed mirror of how it's already being done.

The environment is covered in grid squares,each square holds a vector at its central point. The vector holds the velocity of fluid at that point, which is translated to be the velocity of the fluid throughout the entire square. Each frame, the direction and magnitude of each square is created based on the direction and magnitude of the vectors of squares around it last turn. So long as frame rate is high, I don't think this will create any problems, but I'm kind of just spitballing here, trying to figure out ways we can make fluid dynamics and compounds as cheap to process as possible.
From this simulation, we could easily run a discrete particle model or a grid map, but instead of a map, just store a compound concentration level inside each square. I don't know of how visuals would work for this, but i imagine the system would be fairly inexpensive to process.

Depending on responses to these questions, I'll have a better opinion on what model we should use. Thanks for the excellent post.

~sciocont wrote:

instead of giving particles collision hulls, can we represent them as points in the engine?

Yes, and this would reduce the performance impact dramatically. It would also mean that the particle's wouldn't interact in any way (unless we implement interaction manually).

~sciocont wrote:

Does this mean that we'll need to keep the screen fairly clear of other microbes ingame because the physics engine can't handle too many entities?

The physics engine can comfortably handle hundreds of entities. What it can't handle is a large number of those entities colliding with each other frequently. So it's only a problem with small, plentiful entities close to each other.

~sciocont wrote:

For the floating map design, could we, as I suggested in the microbe stage main thread, judge what compounds a microbe picks up by the compound values in the centers of hexes at its functional edge, and decrease the cloud as a whole [...]

Yes, but for anything except very small compound clouds, this would look weird. Touching a cloud with a microbe would "shrink" the cloud around its origin until it no longer touches the microbe. The effect on gameplay may be minor, but it will be confusing and break the impression of swimming through a cocktail of chemicals.

~sciocont wrote:

[Vector field fluid dynamics]

Hm... could work, but I'm wondering how we would generate the graphics for that? The thing is, I'd really like the agent clouds to show up as a clearly recognizable area on the screen, maybe a bit frayed and, for low concentrations, faint. But however we render it, the player should see that if he touches this area with his microbe, something will happen.

I think you suggested somewhere else that we might render agent clouds as discrete particles popping in and out of existence. That would create ambiguous situations where a player sees one particle over there and one over here, but doesn't immediately see anything in between. Is that just because the render system hasn't deigned to show something there, or is that area really clear of potentially harmful agents? This ambiguity is a real problem that can get frustrating, especially when the player is on the run from a predator and needs to make quick decisions.

Nimbal wrote:

Yes, and this would reduce the performance impact dramatically. It would also mean that the particle's wouldn't interact in any way (unless we implement interaction manually).

Do particles really need to collide? I don't think it's an essential feature, and it means that more can be squeezed into one space. After all, particles are essentially points, and we're just showing where they are with icons.

Nimbal wrote:

Yes, but for anything except very small compound clouds, this would look weird. Touching a cloud with a microbe would "shrink" the cloud around its origin until it no longer touches the microbe. The effect on gameplay may be minor, but it will be confusing and break the impression of swimming through a cocktail of chemicals.

Good point.

Nimbal wrote:

Hm... could work, but I'm wondering how we would generate the graphics for that? The thing is, I'd really like the agent clouds to show up as a clearly recognizable area on the screen, maybe a bit frayed and, for low concentrations, faint. But however we render it, the player should see that if he touches this area with his microbe, something will happen.

Could we pair this with the discrete particle model and scrap concentration values? Is this system needed/ what other fluid dynamics options do we have?

Nimbal wrote:

That would create ambiguous situations where a player sees one particle over there and one over here, but doesn't immediately see anything in between.

Again, good point.

What about generating compound clouds as a polygonal mesh? A cloud is a group of n points (beginning as a regular n-gon), and each of these points is affected by fluid dynamics separately (the points also have some constant outward velocity to account for diffusion). The area in between them contains the compound. The compound concentration at any one point within the cloud is determined by the position of that point on a line between some "central" point in the cloud and the nearest edge, the central point being at 100%, the edges being at 0%. This could give us an "ink in water" implementation effect as well as a relatively easy way to implement it visually: we could do a color gradient method, or generate sprites within the cloud whose alpha values correspond to the concentration at their point.
I'd imagine this could get a bit processor intensive, though.

So I spent some time reading up on fluid dynamics simulation. As far as I can tell, there are three families of methods. The first is based on a static grid, also called Eulerian method or Navier-Stokes (after the equations the algorithm uses), which is explained in this excellent paper. It's relatively easy to implement and produces good visual results (see this video for an example. However, it doesn't scale well when simulating multiple interacting fluids. It's also difficult to simulate interaction with obstacles (such as microbes swimming through the fluid, pushing the liquid aside).

Then there is the Lattice Boltzmann Method. LBM is also grid-based, but a little more sophisticated than the Navier-Stokes algorithm. It looks pretty hard to implement, but produces outstanding visual results. It also play well with obstacles, with a little extra work.

Third in the menagerie are the Lagrangian methods, or Smoothed Particle Hydrodynamics. SPH basically fakes the fluid by simulating a flarge number of particles (the more, the better). Values like fluid density, flow vector etc. in the space between the particles are interpolated between the nearest particles. SPH is great for simulating multiple fluids at once, but takes some work for getting obstacles right.

The most promising approaches right now seem to be LBM and SPH. I'll have to research some more and maybe do a test implementation to give a judgement which one will be best for us. In any case, I expect that for believable visuals, we'll need to utilize the GPU, probably via OpenCL.

Excellent work. I think the best bet here is to go with LBM, since SPH seems a bit brute force. However, if we treat the hexes of cells as particles in SPH and make the "h" the radius of a hexagon (defined as central point to edge midpoint, I think that would make cells pretty easy to deal with computationally.

Also, did you see the above post with the polygonal approach to compounds?

Actually, your polygonal method is very close to SPH (which I really wouldn't call brute force, considering that grid based methods usually simulate just as many particles, only in a static way).

I also discovered an excellent series of articles about fluid simulation here, which discusses a whole other class of algorithms, based on "vortons". The video demonstrating the visual results of that algorithm shows a fantastic level of detail for bodies moving inside the fluid. I think that's exactly what we need.

I was only aware of the last method. It is the one used for blender fluid dinamics (i believe) and the one used on From Dust, which implements some really nice fluid dinamics.

The second one (at least the video) seems really similar to any air dinamics i've seen. Do you know if it could be used to calculate aerodinamics in 3D? It seems very realistic and could be good for that. Of course that is eventually, a fist aerodinamics model could only take into acount the surface exposed to the air flow.

For an example on something that looks like the last option, you can look at powder game.

I dont think we need multiple fluids interacting with each other. We could just layer them on top of each other, so each one interacts only with the obstacles, but not with other fluids.

Daniferrito wrote:

I dont think we need multiple fluids interacting with each other. We could just layer them on top of each other, so each one interacts only with the obstacles, but not with other fluids.

Imagine a microbe squirting a fast moving jet of agent A into a cloud of agent B. Wouldn't you expect a disturbance of that cloud? Note that for particle-based simulations, multiple liquids come almost free. The only difficult thing would be rendering, not simulating.

Actually, the concentrations of agents in water are really minimal. A fully saturated body of water with oxygen will be 0.0001% Oxygen. What pushes the cloud of agent B is the water, not the agent A.

However, if there is no drawback for multiple liquids at the same time (i know that is true for the third method, i wasnt sure for the other two) we can just do them all at once (separating them is actually more costly)

I guess your idea of what agent clouds should look like is very different from mine. If the amount of an agent relative to the environment is in the ppm range, we wouldn't need to simulate it anyway, much less render it. The player just wouldn't notice it.

Also, just because it's actually the water pushing aside agent B doesn't mean that it wouldn't look like the liquids interact. After all if we look at it with realistic numbers (which is ridiculous, we are making a game here, not a medical simulation), the cell wouldn't squirt pure agent A, but a jet of water with a tiny bit of agent A in it. And that jet would certainly disturb the cloud of agent B.

So, with an SPH model, we would treat compounds as individual entities in the fluid, essentially as their own particle that pushes against all of the others?

Basically, yes. Those particles serve as placeholders for the moles of molecules that would realistically be constituting the fluid. Between the particles, the values like density or velocity are interpolated. If you want to get fancy, you can also dynamically create particles in high-interest areas (e.g. vortices behind an airfoild) and destroy them in static areas to only simulate the fluid where it really counts.

The article series I linked above actually introduces a hybrid approach (particles coupled with static grid) that brings the best of both worlds at slightly higher memory cost. Since the author is doing it in 3D and we need only 2D, I'm really optimistic that we can achieve a high resolution without taxing the PC too much.

Well, yes, the water we can just ignore, and only simulate the agents we are interested in.

The question is if diferent agents should interact with each other or just pass through each other. Either way is fine for me.

If the original autor does it in 3D, 2D should be just fine and fast.

Nimbal wrote:

Basically, yes. Those particles serve as placeholders for the moles of molecules that would realistically be constituting the fluid. Between the particles, the values like density or velocity are interpolated. If you want to get fancy, you can also dynamically create particles in high-interest areas (e.g. vortices behind an airfoild) and destroy them in static areas to only simulate the fluid where it really counts.

The article series I linked above actually introduces a hybrid approach (particles coupled with static grid) that brings the best of both worlds at slightly higher memory cost. Since the author is doing it in 3D and we need only 2D, I'm really optimistic that we can achieve a high resolution without taxing the PC too much.

What do you say to hexgrid-based resolution? If the cell kernel appears around 40px by 40px

while playing the game, I think that would be a pretty good resolution.

Using a hex-grid instead of rectangular wouldn't gain us much (anything?), but will complicate the algorithms involved. For example, how would you discretize the differential equations for fluid movement on a hex-grid? For rectangular grids, it's straight-forward with x and y coordinates. For hexagons, I'm not even sure it's possible.

Nimbal wrote:

Using a hex-grid instead of rectangular wouldn't gain us much (anything?), but will complicate the algorithms involved. For example, how would you discretize the differential equations for fluid movement on a hex-grid? For rectangular grids, it's straight-forward with x and y coordinates. For hexagons, I'm not even sure it's possible.

No, i was referring to using the hexgrid shape of a microbe to determine how it interacts with the environment- I'm well aware that using hexgrids for differential equations would be useless and at least mind-boggling.

Oh, sorry. The actual resolution of the grid, how many particles (if any) we use, etc. will be easily tweakable later on. If we go with a pure gridbased method, 40px will be pretty coarse. As a supporting grid for a particle approach it might be fine, though. In the end, we'll probably want to use a non-uniform grid anyway, so the actual resolution won't matter much.

Nimbal

Quote :

Actually, your polygonal method is very close to SPH (which I really wouldn't call brute force, considering that grid based methods usually simulate just as many particles, only in a static way).

I also discovered an excellent series of articles about fluid simulation here, which discusses a whole other class of algorithms, based on "vortons". The video demonstrating the visual results of that algorithm shows a fantastic level of detail for bodies moving inside the fluid. I think that's exactly what we need.

Now that was a mind-blowing video. I'm really far away from programming but this looked beautiful!

Just as a small update, I've decided to put fluid dynamics on ice for now. I'll definitely revisit it once we have fleshed out the gameplay a bit more, because ultimately, it's a visual gimmick, not something that will influence gameplay in a dramatic way.

For the first versions, I'd like the agents to be represented by small, discrete particles with the following behaviour:

• Simple movement: when spawned, they get an initial impulse. Due to viscosity, they will slow down over time and eventually stop.
  
• Simple collision: Agent particles do not collide with each other
  
• Limited lifetime: After a set amount of time, agent particles just disappear.
  
• Simple microbe interaction: when an agent particle touches a microbe that can interact with the agent, the particle disappears.
  

Implementing this kind of agent behaviour will give us an idea on how agents will fit in with the gameplay. Going from the simple movement described above to eye-candy fluid dynamics won't be too difficult. The fluid dynamics simulation will calculate the velocity field of the water the agents are swimming in. Then all we need to do is move the particles according to that velocity field.

Thanks for the update. As I understand it then, you want to keep the discrete particle method for at least the first few iterations, with possible forays into other methods saved for when we have the time. Correct?

Methinks it's time to revive this thread. Why?

I'm seeing mention of SPH, LBM, and other true fluid-sim methods, which is nice because they work. However,they're all designed to provide realistic results in the macroscopic size regime. I noticed that someone was worried about what would happen if a microbe squirted some water into an agent cloud -- if we want to simulate the possibility, then it makes sense that we'll want a proper fluid sim.

However, and this is a big however, water doesn't squirt like that at microbe sizes. There's a reason it's known as the inertia-free size regime -- viscosity effects dominate so heavily that nothing can coast -- neither a microbe, or a bunch of water. Thus, we don't really need a fluid sim (yet) that is as fully-featured as SPH et al.

Instead, I've been touting recently the use of curl noise; since all we need is a divergence-free turbulence field -- or perhaps several, layered at different scales. Then, we just advect the density field for each compound through that noise field, using diffusion coefficients to scale the effect.

(For some perspective, glucose, with a diffusion coefficient of 5e-6 diffuses about 32 microns in one second, which is just about cell size)

Edit: Technically though, we wouldn't be using diffusion coefficients directly, but derive an "advection coefficient" of sorts, since we're scaling the speed along a wonky path, while the diffusion coefficient is calculated in terms of straight-line speed; so we use the diffusion equation.

You're right in that we weren't properly understanding our reference scale in previous discussions of fluid dynamics integration, and implementing it more realistically along the lines you suggested looks like it would not only prove more realistic, but also be less difficult.
The webpage for diffusion coefficients you linked is great, since that should help us a lot in balancing diffusion times in the game.

How exactly were you imagining this all to work? Are the compounds discrete particles, zones of concentration, or something else? What are the effects, if any, of the fluid environment on cell movement?

Beyond those questions, there's also the problem of playability. If we make the environment too noisy, movement becomes frustrating, so we may have to make the environment flow a bit more than is really scientifically accurate.

I was thinking we'd have two layers of curl noise -- one high-frequency, for making pretty-looking compound diffusion, and one low-frequency, for moving microbes and other large things around. Compounds, stored as concentration grids, are moved by both layers, while the larger stuff ignores the high-freq layer. As for scientific accuracy, we're actually pushing turbulence a little too low on the size scale to be perfectly accurate. So the low-frequency noise layer can approximate the scientifically accurate minimum vortex size (probably on the smaller end), as that way we can have a drifting player microbe change direction often enough to make currents noticeable (vortex size about half a screen at smallest); while the high-frequency layer is just a graphics decision -- it looks prettier than brownian motion.

moopli wrote:

I was thinking we'd have two layers of curl noise -- one high-frequency, for making pretty-looking compound diffusion, and one low-frequency, for moving microbes and other large things around. Compounds, stored as concentration grids, are moved by both layers, while the larger stuff ignores the high-freq layer. As for scientific accuracy, we're actually pushing turbulence a little too low on the size scale to be perfectly accurate. So the low-frequency noise layer can approximate the scientifically accurate minimum vortex size (probably on the smaller end), as that way we can have a drifting player microbe change direction often enough to make currents noticeable (vortex size about half a screen at smallest); while the high-frequency layer is just a graphics decision -- it looks prettier than brownian motion.

Is the concentration grid global or based on a global grid? (a concentration grid underlying the entire map)
Also, the two layers is a good idea. Do they interact directly or do only concentrations see effects from both large and small grids?