Building Microbe Stage

Well, back at school after a half term holiday/vacation in the middle of the school term. The UK summer holidays/vacation start/s in about six weeks and go/es on for six weeks. Sometimes I envy US students - you have a much longer holiday/vacation.

OK, It's time to discuss the visuals of compounds. This is going to involve both our programmers and our artists, because we not only need to let the player know what's what, we need to handle what would be >billions of particles in a simple way. The actual movement and behavior of compound entities needs to be properly defined.

Here are the options that I can think of of handling compounds.

Spoiler:

Unless someone has a better Idea, I'm going to assume the Density Cloud system will be used: in previous discussions, I believe Nimbal or Dani have alluded to a system like that described. If you have another system in mind, feel free to post it.
Now, about that clever visual system.

I'd propose we still handle the visuals of the compounds with sprites, but the sprites in question will exist within the microcosm of the compound cloud. Let me explain.

The compound cloud is essentially a bitmap that is scaled and faded (lowered in opacity) as it disperses. We can use the alpha values of the cloud to render sprites at random positions within the cloud, then change the sprites' opacity to match (or scale with) the opacity at their position. That way, we get visual representation via shape and color without having to handle all of the sprites individually in terms of the physics. To illustrate that the sprites rendered within the cloud are not individual items, they can "twinkle" byt fading from an alpha of 0 to the max alpha at their position, then disappearing, with a new sprite being rendered somewhere else in the cloud.

Spoiler:

I too vote for density cloud system as well. This system will work very well. A few examples I came up with:
-When a cell dies all compounds inside it would spill out in a high gradient.
-As you evolve, you could mutate organelles that acted as sensors, so that when you entered a cloud a visual representation would begin to show. This could be upgraded to show other toxins that cells have excreted, etc.
-You could couple this with toxins that you have evolved to show other cells where food is, or to trick other species into a deadly toxin.

This system excites me. I'm not sure about visual system. I thought just an alpha map with a more intense gradient as the compound grows more sense. Great idea, ~scio.

Bumping to draw attention to the proposed visuals.

~sciocont wrote:

I'd propose we still handle the visuals of the compounds with sprites, but the sprites in question will exist within the microcosm of the compound cloud. Let me explain.

The compound cloud is essentially a bitmap that is scaled and faded (lowered in opacity) as it disperses. We can use the alpha values of the cloud to render sprites at random positions within the cloud, then change the sprites' opacity to match (or scale with) the opacity at their position. That way, we get visual representation via shape and color without having to handle all of the sprites individually in terms of the physics. To illustrate that the sprites rendered within the cloud are not individual items, they can "twinkle" byt fading from an alpha of 0 to the max alpha at their position, then disappearing, with a new sprite being rendered somewhere else in the cloud.

Spoiler:

I much prefer the cloud idea as well. Plus, the manner of using sprites for the graphic would be very effective too.

I vote for it to. Does anyone have any other idea?

That sound pretty good.

Before I comment on the compound visuals, I'd like to remind you that the naming issue of toxins / enzymes is still up in the air. The wiki still says "enzyme", which is apparently incorrect. I'd like to rectify that, but not without the blessing of someone more knowledgeable in biology than me. The proposed names so far:

• Toxin (confusing for beneficial stuff)
  
• Enzyme (scientifically incorrect or inaccurate)
  
• (Biological) Agent
  
• Protein (Wikipedia says they "perform a vast array of functions within living organisms", which seems kind of fitting)
  

Ideally, I'd like to have one general term for both beneficial and harmful stuff, and one specialized term for each. Toxin is a great, immediately recognizable name for harmful stuff. But what about the general name and beneficial stuff?

Now, about the compound visuals. I like the idea of a mixed alpha map / sprite approach. But I' wouldn't dismiss the straight-forward approach of discrete particles just yet. At least in theory, the physics engine we use can handle it. And manipulating an alpha map with potentially thousands of pixels isn't exactly cheap either. I'll see if I can whip up a test run with a few hundred particles in our current engine.

I'm with Nimbal here. Having independant entities for the compoundsis is what our engine is most used doing. And simulating many entities in the physics engine wont be too hard for the computer, taking into acount that whenever they colide, they will disapear and get added to whoever colided with them. Usually collisions are the reason physic engines lag. On top of that, if we just leave the compound "bubbles" there, without moving them, they will just be tagged by the physics engine as inactive, which makes them much easier to simulate.

@Nimbal: I'm quite sure that video is "baked", which means it is simulated as perfectly as possible in whatever fps it comes out, and then re-speed up so you cant feel the difference. I believe he said it was like a night to simulate that 12 seconds of video.

Ok, good to hear from you guys. Is there a better way to handle the cloud than an alpha map? Maybe a 3D gaussian function or some f(x,y)=z where the z coordinate is the toxin level at (x,y)?
If we can handle 1000s of particles at once with everything else that's going on, that's fine, but I want to make sure of it before we release a game that runs at 10 fps, hence the density cloud backup.

Well, if you want the cells to actually modify it, you will need an alpha map. Lets say the cell is absorbing the "protein/enzime" cloud from the left. Only the actual parts it is going through should get their values reduced, not the whole function as a whole (that is, the right part should stay without change). You could describe the simple maps as a function, but not once cells start to add or remove from it.

Other than that, a cloud visually representing the proteins would look nice.

But would it really be an issue if we did subtract from the function as a whole? That was my original idea, since there would (in reality) be billions upon billions of particles in the cloud and they would be diffusing about fairly uniformly? I don't think there would really be gameplay ramifications if you simply updated the magnitude of the entire compound cloud based on absorption of all of the cells within it each frame. Also, we're representing what is really a 3D space in a ostensibly 2D environment: In a 3D space, there would be a lot of space for the compounds to move in and around the cells easily- they're not large enough or moving fast enough to have a very large effect on the currents around them that a wake caused by their passing would last very long.

Either way, I'm perfectly happy to use the individual entities system, provided Bullet can handle it well.

Another issue I'd like to clear up would be cell membrane shape generation in the editor. I'm sure both Dani and Nimbal have a pretty good idea of the algorithm for it, but in the interest of collaboration, here's mine.

Spoiler:

Does that seem good ? What better ideas do you have? I'm trying to write as much pseudocode as possible as I'm beginning to learn LUA.

That should work for the outer periphery. For inside "holes" in the cell, I think the anchor points have to lie on the edges of the hexagons, not the corners.

But to start from the beginning, we have the following requirements and goals:

• The final shape of the microbe should not betray the hex-grid underneath
  
• The hex-representation of the microbe must be completely contained inside the rendered shape. Otherwise, artists will have a hard time predicting how large an organelle may be.
  
• A lone hexagon should be rendered as a perfect circle
  
• A "circle" of hexagons (e.g. one hexagon in the centre together with its six direct neighbours) should also be rendered as a perfect circle.
  
• A "line" of hexagons should be rendered as a straight line with rounded end points.
  

Smooth curves in computer graphics usually require Bezier curves or splines. Splines are a little easier to control because they actually go through the control points, so I'd go with (cubic) splines.

That leaves us with the problem of finding those control points. Scio has already described part of the algorithm, but it's still a little nebulous (among other things, it doesn't give the order of the control points), so let's formulate this a little stricter. First off, some terminology and conventions:

• A hex is said to be "active" if it's part of the microbe's shape. Otherwise, the hex is "inactive".
  
• We use flat-topped hexagons and the axial coordinate system (the last one described in the link).
  
• The right most corner of a hexagon is labeled "A". From there, it goes clock-wise through the alphabet, with the upper-right corner being the last one with the label "F".
  
• Each corner has three adjacent hexes: "left", "above", "below". In the algorithm below, these adjacent hexes are also called "neighbours" of the corner.
  
• Note to self: find a nice drawing program that can handle hex-grids without too much fiddling.
  

Now, the algorithm in pseudo-code:

Code:

// List of control points, initially empty
controlPoints = []

// Outside shape counter. We will use this counter to detect
// when a control point should be in the center of an inactive
// hex instead of on the corner of an active one
osc = 0

// Find any hex on the outer edge of the microbe
currentHex = findPeripheralHex()

// Select corner A as the currentCorner
currentCorner = currentHex.A

// Find a corner that has at most 2 active adjacent hexes
while currentCorner.activeNeighbours == 3 do
    currentCorner = currentCorner + 1
end

repeat
    if currentCorner.activeNeighbours == 1:
        controlPoints.add(currentCorner)
        osc = 0
        currentCorner = currentCorner + 1
    else if currentCorner.activeNeighbours == 2:
        osc = osc + 1
        if osc == 2:
            // Since the current corner has two active neighbours, there can be
            // only one inactive one
            inactiveNeighbour = currentCorner.findInactiveNeighbour()
            controlPoints.add(inactiveNeighbour.center)
        currentHex, currentCorner = switchHex(currentHex, currentCorner)  // See below
until controlPoints.size > 2 and controlPoints.first == controlPoints.last

Note: the scrollbar for code sections in this forum is really annoying.

The "switchHex" function used above takes a hex and one of its corners that has only two active neighbours. It then returns the other active neighbour along with the same corner, but in the neighbour's coordinate system. For example (better make a sketch of this), say we have two active hexes, Hex1 and Hex2. Hex1 is directly above Hex2. Hex1 is our current hex, and B is our current corner. That's the left hand corner that both hexes share. The "switchHex" function would then return Hex2 and F. Same corner, but on a different hex.

I've tested the above algorithm on paper for a variety of hex arrangements. If you find an edge-case where it produces undesirable results, please post that case here.

Regardless of whether that algorithm works or not, it doesn't handle "holes" in the cell, i.e. areas of inactive hexes that are enclosed by active hexes. I don't have the time to write out the whole algorithm for those right now, but the main problem here is not finding the control points (just use the midpoints of the edges instead of the corners), but rather finding those areas. That's still not really complicated though, a flood fill algorithm will take care of that.

Great post. Eventually I will be able to help with this sort of thing to a somewhat competent extent.
Also, this webpage that you linked is fantastic. Props to the author.

Over in the Agent Cloud Implementation thread, I've mentioned some ways we could simulate believable clouds of agents and compounds in the environment. But there are some details of microbe / agent interaction we need to flesh out before we can make a decision on which algorithm to use. Since they have gameplay consequences, I'll post them here.

• Do microbes absorb agents? In other words, is the agent concentration diminished by a microbe moving through an agent cloud?
  
• If yes, do all microbes absorb all agents? Or just those that would have an effect on the microbe?
  
• If agents are not absorbed (i.e. they are only removed from the world by dissipation), do microbes displace agent particles, pushing a wave of agents in front of them when they move through a cloud?
  

1) Yes, microbes should decrease the amount of agent in the area they are, as long as they are absorving it.
2) No. A microbe should not keep absorving something once it is "full". More on that later
3) I would vote for yes. That way, when the player is a multicelular creature (but still composed of cells), outer cells will absorv components before they get to inner cells. That allows for a much simpler early multicelular implementation.

What about this: Agents have a concentration of compounds stored inside them. That includes oxygen, CO2... and of course agents. If the inner concentration is higher than the concentration around the cell (CO2, for example), it will throw away the excess amount until the water around it and itself have equal percentages. Similar with the oposite case, if the inner percentage is lower (like for oxygen), it will absorv from the outside to equalize.

Here are some examples:

• As a cell uses oxygen, its internal reserve will decrease. That makes the outside percentage higher, so it will start absorving to refill its reserves.
  
• When the cell creates CO2, it will throw it away whenever its concentration gets higher than the outside concentration.
  
• To throw agent to other cells, it will release them into its internal storages. As the outside contentration is 0%, it will start to "bleed" it off.
  
• Whenever another cell enters an agent cloud, as its internal percentage for that agent is 0%, it will start absorving it untill the percentages equal. Whenever the agent is inside itself, it will "spend" it to perform the action the agent does, decreasing its internal amount of the agent.
  
• Cells surrounded by other cells (like an internal cell from a multicelular creature, or a cell that was surounded by enemies) doesent get any concentration outside of its membrane, so it wont get any intake. For cells from a multicelular creature, it will echange compounds with them directly. If the other cells dont allow such thing (like the cell surrounded by enemies) it will eventually starve to death.
  

The Lattice Boltzmann Method you mentioned on the other thread seems the best aproach (looking at the videos)

You mean you want to simulate osmosis? That can get really confusing when the player moves from a compound rich environment to a compound starved environment and suddenly loses resources like a leaking pinata. It also poses algorithmical and conceptual challenges. For example, how would you calculate the concentration values for "outside" and "inside"? What about if the concentration is high on one side of the microbe and low on the other side? How would you communicate to the player that the concentration over there is high enough that he can gather stuff up, but over here it's so low that he would lose his reserves?

I agree with pretty much everything Dani just said. That's a great way of simulating absorption, but it will only work if we're using an alpha map style system, not an individual entity system, since we don't know concentrations inherently with an individual entity system.
Another problem is that cells need more of many compounds inside them than outside. Compounds that diffuse freely across the cell membrane like simple gases (O₂,CO₂) and water can be modeled easily like this, and we simply need to specify a constant ATP drain rate that the cell must spend to keep these concentrations within a certain range. 
However, for larger compounds, such as glucose, fats, proteins and agents, the cell has to spend energy to transport them across its membrane, and thus just needs to expend some energy when it comes into contact with them, but doesn't need to spend a constant amount to keep them from falling out.
Agents are designed to be pumped out on command, so the source cell doesn't need to worry about their concentrations except to stop making them when they're full.
In conclusion, some compounds dissipate freely (water, oxygen, nitrogen, methane, carbon dioxide) and require energy to keep in the correct concentrations, while other compounds (agents, fats, proteins, sugars) simply need to be picked up and require a small energy expenditure when they are picked up.

Guys, slow down. For one, you are proposing half-cooked ideas again. The whole point of this design document for the microbe stage was that we have clear, concise rules that serve as a straight-forward guide to implementing the game. So if you want to have such a system, please take the time to fully think them through with all odds and ends, then formulate them.

Also, don't worry about the specific method for fluid simulation here. Just think of the gameplay, not the way to implement it.

Oh, i just realized i missed a few things in the last part of my post. But yes, i meant simulating osmosis to some extent. (scio comented some of the things i was intending to say)

Cell membranes have a few extra properties. For example, they can prevent some compounds going through or allow them, depending on the situation. When Oxygen (or any other usefull compound) gets under a thereshold, it prevents it from going out.

Membranes also contain "pumps" that can force some compounds in or out ignoring the gradient, in echange of some energy. That means that even though you will most of the time have more sugar than the outside, you will absorb any that comes by. You would never let sugar out.

The value for inside is easy. As it is only stored as a number, you can easily make calculations with it. If the volume of the cell is 3/4*Pi*r³, the concentration is amount/volume, with the right units.
For the outside, we just take an average. Either we take the area the cell "reaches" or we divide that area into smaller sections and treat each one individually.

For showing the player if it is gathering or losing compounds, we could show a table with the internal and external percentages, and an arrow in between that indicates where the flow is going. The faster the transaction, the bigger the arrow. That table would be hiding most of the time and only show up if the player decides it. A more visual method would be better, but i'm not really good at such things.

@Nimbal: Sorry for starting this. It just seemed natural to me that if this level of simulations with agents could be reached, the next natural step would be to simulate all compounds as agents.

Thanks for stopping us Nimbal. So the current system is:
"Cell comes into contact with compound and absorbs it unless it is already full of that compound."
Correct? That's about the simplest thing we can do, and I think it will work.

As usual I'm following whats been posted here, but haven't really had time to post much of a reply.

The ideas on how compounds (including agents) will be transfered between cells and their environments have been around for some time, though I'm not sure if they're explained in full anywhere.  Some details may be covered in the compound system thread, other aspects were certainly discussed by me and Scio over PM last year (@scio - you posted some of these in a thread in the hard development section before the restructure, I can't seem to find them now?). 

From memory (and as mentioned by Scio and Dani above), only a few compounds will freely osmose accross the membrane, most will need to be channelled or pumped.
- Channelling allows compounds too large for regular osmosis to pass freely over the membrane, effectively making them subject to osmosis.  In this way, the cell can allow or not the osmosis of certain compound by having/not having chanels.
- Pumping, as explained by Scio, moves compounds accross the membrane at an energy cost.  These compounds may or may not be affected by osmosis otherwise.  This is the only way to transport compounds against a concentration gradient, and the only way to maintain a concentration other than that outside for compounds subject to osmosis.

Concentrations inside the cell are calculated as the quantity stored / maximum capacity.  Depending on the compound that capacity may be the total volume of the cell, or depend on the size of storage organelles like the vacuole.  Concentrations outside the cell would be the amount present in a location / that locations volume.  I've meant to post on this before, but haven't had time - this is one key reason why some sort of alpha map approach would be much nicer than a particle approach for running the compound system.

Also, some of the discussions on fluid flow seem to assume that different agents/compounds will interact (i.e.: seperate).  Most compounds we use (with the exception of water, I would suggest all compounds, for simplicity) are dissolved in water, so they aren't actually seperate fluids.  What's flowing isn't the compounds/agents but the water they are dissolved in, so there doesn't need to be any interactions, most compounds/agents should mix perfectly.

...ninja'd ofc, originally wrote this into Nimbals post.
@ Dani - mostly agree.
@ Scio - that works for now, but it won't be enough if that's all we're going to do.  We need cells to be able to excrete compounds as a minimum.  Whether they do that for osmosis, active pumping of waste products, or production of agents, we need to be able to do roughly the same thing for the fluid simulation - calculate the rate at which agents/compounds are placed/absorbed in each fluid grid cell according to the presence of a cell and its contents.

This post is really rather rushed, but some of it needs to be mentioned before this discussion goes on.  If you need me to clarify anything I'll try and do so tonight.

EDIT - and I just noticed the new posts in the fluid dynamics thread, which cover atleast some of what i posted here, sorry.

By all means, I didn't want to discourage the osmosis idea. It just needs a lot more work until it's ready for implementation.

Nimbal wrote:

Also, don't worry about the specific method for fluid simulation here

As an amendment: just assume that you can query the density and velocity of a given fluid at any point, or the average of those values in a given area. Whatever simulation method we end up using, that's the minimum it should be able to do. And I don't know any method that can't do that.

I would just like to ask, I never saw anywhere how the effects of the agents you produce will be decided. Will it be procedural? Customizable? Will the effects of the agents you secrete evolve as you do? If it does evolve, is it independent of you or do you control its progression?