Sunday, October 30, 2011

In Profundis Problem: Continually flowing water

One of the reasons there was a bit of a delay in work on the game was because I was mulling over for a while solutions to certain problems with the game as envisioned.  Here I explain one particularly annoying problem that I'd really like to see fixed, but currently don't have a very good solution for.  Maybe one of you might have an idea.  At the very least, maybe some of you might find thinking about this interesting.

In Profundis uses a cellular automation system for flowing water, yet because of the closed nature of the game world, most flow is ultimately user-initiated.  Liquid tends to pool and collect and remain as low as it can get, and remain there collected.  It doesn't actually end up flowing much except at the start of the simulation.  Once it gets to the lowest point it can reach, there it remains until something disturbs it.

This is not particularly interesting from a gameplay perspective.  What would be more interesting is if water could enter and leave the map, or at least flow through two locations in the world, repeatedly and endlessly.  Then the player might have to find some other way around it, or maybe divert the liquid to give himself a safe path.

The problem is that, because of the size of the game world, we can't compute the whole thing every frame and keep within an acceptable speed.  Some distance outside of the visible screen we have to abandon calculations.  This causes liquid to "pile up" when it flows outside the border.  If we recycle liquid between two "portals," unless both of them are within the calculation region at the same time, the flow will stop.  And as the player scrolls around the map the calculation region changes, meaning while approaching the area there will almost always be a time when one portal is in the region and one is outside.  If they are far enough apart, there could result in instances where the player is suddenly beset by a rush of liquid that has "backed up" because of the simulation border, then suddenly uncorked by the scroll.  (This could actually be interesting from a gameplay standpoint, but it goes against the philosophy of the game.)

I'm not sure there is a viable solution to this problem, but here are some possibilities:
* One thing I could do is consider the region between the two portals an "all-or-nothing" region for calculation; if one cell of the rectangular region between the pair is calculated, then do the whole thing.
* The larger the simulated region, the less evident the problem becomes.  If we work on enlarging that area (maybe by slowing down the rate at which fluids flow, which I've been considering for a while), the problem will become less visible.
* It's possible that the problem won't be perceivable to the player most of the time.  Because his range of vision is limited, even on-screen backups won't be too apparent so long as they're outside his field of view.
* The real-world solution to this would be a evaporation/condensation cycle, but that would probably require a scale larger than what we're looking for here.

16 comments:

  1. I'm having a bit of trouble getting my head around CA, so this might not make sense at all, but would it be helpful to store a "flow rate" for each block, which measures the amount of liquid which can move through the block in each update? Then the movement of liquid could be calculated based on that, rather than directly on the amount of liquid in each block.

    Flow rate for a block would be determined be the available flow in neighbouring blocks, so empty blocks would start off with the maximum possible flow rate, and solid rock would have a flow rate of zero.

    Then rather than linked portals, certain blocks could have permanent, small flow rates which attempt to add or remove liquid from the world, and drawing from or returning to a "world sink", so the total amount of liquid remains the same.

    ReplyDelete
  2. Yes, I don't think I quite grasp your idea. it sounds like a way to cheat liquid sources, which might be useful if I figure out your idea. I'll think about it a bit.

    ReplyDelete
  3. To be honest, it wasn't a very clear idea! Just playing around with it, it doesn't really seem to help much. I thought having a time based "flow" property would mean you could just overfill blocks outside of the active area, trusting their flow value to be correct, then bring them up to date at a later point. It stops liquid from building up on the edges of the area, but it means you just end up with one massively overfilled block instead.

    ReplyDelete
  4. Aah, that is an interesting idea. I think it would have unexpected consequences though; what if a huge amount of liquid got packed into a block, then the player went around and approached that block from below and scrolled it onscreen while it was discharging? Still though, I like this kind of thinking.

    ReplyDelete
  5. Didn't you use an update system which calculates the X changes closest to the player (eventually updating even distant changes)? I remember you talked about it, but I suppose it didn't work out?

    Otherwise - and this is an immediate idea I haven't really thought about for more than 30 seconds - maybe you could use your "all-or-nothing" approach, but keep a separate lists of cells containing liquids from a generating "source", so you only need to calculate the cells affected by anything that's generated. If a player sees generated liquid, calculate the next state for everything in its list. If a player doesn't see it, freeze the whole list.

    ...

    I realize this would probably lead to other problems, depending on how it works now, but maybe it'll give you some other idea. :)

    ReplyDelete
  6. Always compute cells containing liquids ? That could lead to a lot of lag issues I guess, but trying it out to see the actual impact would be interesting.

    ReplyDelete
  7. I like evaporation and condensation! I would try it and see how it works, and if necessary I suppose I'd cheat my way out of doing calculations that could be approximated quickly.

    One question: Is the whole game world contiguous, or is it split into multiple "rooms" of sorts, with "doors" connecting them?

    ReplyDelete
  8. It is continuous. I had planned evaporation and condensation at first, but with eight different fluids slopping around and each needing to be tracked individually, plus other gases, it started to get kind of unwieldy.

    ReplyDelete
  9. My immediate thoughts:
    Each cell has a 'river' flag and an indicator of the prior cell in the river (except the head, which is a special case I haven't put thought into yet) and the next cell in the river (again, except the tail).
    When calculated:
    If the prior cell doesn't point to the current cell unset the river flag and the two cell references and let the water flow naturally.

    If the prior cell does still point to this cell then estimate where the water would flow; for the purposes of this estimation assume cells flagged as rivers have no fluids in them. Set the next cell as wherever the water would have gone. Set the river and prior cell attributes on that cell as well (though not the next cell reference since you'd have to calculate that cell to figure it out and we don't want to do that yet). It's possible that water could flow into multiple cells, so I guess as a failsafe against a grey goo scenario you'd have to limit the creation of new river cells to the first cell water flowed into or perhaps whichever cell got the most water flow?

    If after the calculations a river cell isn't full of water (or half full, or some arbitrary amount?) you magically restock it. If the next cell reference points outside the frame of calculations then you assume the water flowed into that cell and leave the cell as-is. In the specific case where a newly created river cell occurs at the edge of the frame of calculation you'll still have build up, unless you allow the calculation to 'peek' outside the frame (imagine routing a river into a freshly dug out waterfall). Since the water in a 'river' isn't really moving and the destination cell will be filled with water by normal river mechanics as described before the player sees it allowing the calculation to look at cells outside the frame makes sense (assuming it's possible in the code).

    On further thought, this actually looks a lot like a linked list. I expect there'll be problems when a river fills up a basin creating a lake, and if the linked cells ever try to cross each other.

    Basically, you assume the water level in a 'river' is static (and cheat to keep it that way). If at any point it reaches the edge of calculation you just assume the water went where it's expected to. Since that cell is outside of calculation that should be a safe assumption.

    Though.... if you have the possibility of multiple fluid types having 'rivers' then you'll need to add a lot of new attributes to each cell. A flag and 2 cell references for each fluid type to be precise, though I can only think of a case for lava and water to have river-like qualities and as those two are mutually opposing you should be able to work around it.

    ReplyDelete
  10. I'll have to think about that. My current idea is to reduce the liquid flow rate by a factor of four(which should be more realistic anyway), allowing me to greatly increase the size of the calculation area, and making sure that source/exit pairs are close enough together that it doesn't come up all that often.

    ReplyDelete
  11. If you have a defined exit (irregardless of everything else) how do you detect and what do you do when the player changes the course of the fluid such that the pairs are now very far apart?

    ReplyDelete
  12. I didn't say it was perfect, heh. Probably it'd have to be done by nominating one bit of fluid as a tracer, and using that to detect if continuity has broken, which might be more trouble than the idea is worth.

    ReplyDelete
  13. Could you chain source/exit pairs, so that rivers are made out of several shorter, transparently connected rivers?

    ReplyDelete
  14. @davidmear You still have to deal with continuity between endpoints and also then continuity between pairs. If you don't then you'd end up with broken up river segments in multiple places. Though taking that approach combined with something like the linked list approach might eliminate some of the problems with both.

    Another solution might be to maintain a separate map (just an array of cell references really) for each river and for each update test for the presence of a river cell within the calculation frame. If true then calculate all the river cells. Of course then your rivers will have scaling limitations.

    ReplyDelete
  15. Good point. I guess I'm getting away from the self contained nature of CA a bit.

    I think what I was going for with the flow rate idea was to have some per-update property that you could trust for blocks outside of the active area. At the simplest extreme, if there were a liquid sink block that removes a certain amount of liquid per update, you could safely overfill that block if it was just adjacent to the updated area. Working back from that block, you could assign blocks in a stable, connected river similar "sink" values. You'd still have to update the whole river if the terrain changed, but until that happens it would be safe to let liquid pass out of the updated area according to the blocks' flow rates.

    ReplyDelete
  16. I guess you've got to accept that pretty much any shortcut is gonna have drawbacks in one way or another.

    my thoughts are that breaking the world up into rooms would greatly reduce area to calculate at once as well as the overall calculation time per frame. at the cost of realism I guess. I think it's something to consider though

    ReplyDelete