In Profundis Progress 9/17

ARGH

There is a bug in the game, an infuriating one that has got me, at the moment, stumped.  It has to do with the system the game is using to keep track of cells that potentially need updating.  In one specific circumstance, that being when fluids hit the edge of a platform and flow down off the side, some of it is often refusing to remain mark active long enough for all the fluid to flow off the ledge; it just pools up there, unsupported.  If something happens next to it it causes it to "wake up" long enough for some more of it to flow away, but only for one frame.

I'll figure it out eventually.  Just wanted to expose you all to my current personal hell.

In Profundis Progress (5/22)

I'm back baby!

So, here is the thing that's been consuming my development time lately.  Cellular automation for use in real-time games frequently has to be heavily optimized.  When you're cycling though every cell of a hundreds by hundreds array every frame, then even the overhead from those cells in which you just check contents and decide nothing needs to happen is significant.

My current strategy for negating this is to not use a big loop that iterates through every cell.  Instead, I keep a list of every cell that _might_ change this frame.  I calculate those and, any that do change, I add adjacent cells to the list for the next frame.

It's much MUCH faster, but it's worth noting that this is entirely because, for most of the game world, large portions are static between each frame.  Stone is largely inert, so we don't need to worry about it except how other things react to it -- they are the initiating factors in that, so their routines handle the work.  Empty spaces (that don't contain weird gases) are similar.  These two cell types are 90% of the world.  By removing them from consideration, it's worth a huge performance gain.

A huge gain, but it turns out, not huge enough.  I remind you that, before, we kept performance under control by only updating the screen and a short distance outside of it.  Under this system we update the whole world, and factoring in all of the cells that CAN change, it's a bit too much to reliably handle.

There is a way around it.  We sort the update list, using one of the handy-dandy, heavily-optimized Python sort functions, with the sort key being a simple Cartesian distance from the player or cursor.  Then we can just pop off the first few hundred or so every frame, and leave the rest for the next frame.  If the player never goes anywhere near them they won't get handled, but as soon as he does they'll enter consideration.

It's a cheat, but real-time game development is basically a convoluted series of cheats, a set of makeshift concessions to processor speed and memory limits.  Now that we have multicore machines and multi-gigabyte memory spaces this fundamental fact is sometimes obscured, but it doesn't change it.

In Profundis progress (5/13)

The biggest change, which is so big that I've been taking a break from development for a few days to consider what it means, is to the way the sim looks at which cells to calculate.

Originally, it just iterated through a loop through the whole world, from bottom to top, examining each cell and deciding what should happen there.  That took a long time.

More recently, it'd just been updating a frame around the currently visible portion of the world.  That's  much faster, but causes certain bits of weird behavior in some circumstances.  For example, if enough water pouring off screen in a place eventually it'll fill in the cells in the no-update region off the bottom of the screen, and then it'll pool on top of that.  If the screen then scrolled down somewhat, it'd suddenly all start falling as the "plug" dissipates.  Similarly, water flowing off-screen will eventually act as if it's reached a wall and begin pooling, but if you move forward it'll start flowing out again.

The new system is a rather more radical change.  Now the game has a list of cells to update, compiled originally by scanning through the world.  Cells that are mostly inert, like walls and empty spaces, don't make it into the list, and thus no cycles are spent on them.  When an operation is performed on a cell, the game adds nearly adjacent cells to the (initially empty) list of cells for the next frame.  Those calls are "activated."  Since the most distance away a cell can affect the world on a single turn is one space, we never have to add too many cells to the list.

If a space containing some possibly-active element, such as a liquid or boulder, does nothing this turn, it is left off the list for the next frame.  The simulation doesn't even consider it until something happens close enough to it that it might be upset.  Minecraft does something similar with its sand; sometimes you'll find a place where the world generates sand blocks that are unsupported, or even hanging in air


When the player does something that affects the game world under this system, the nearby cells have to be added to the update list in case there's any simulating to do.  That's what causes Minecraft's sand to suddenly realize that gravity exists and begin falling.

In Profundis progress (5/8, part 2)

Did some more work today on speeding up the simulation.  Before, the cells that were calculated were all of them within the borders of the screen plus a small area outside of it.  Current work is towards switching to a system where changed cells in a given frame mark cells adjacent to them for calculation in the next frame.  The idea is that changes don't happen randomly; they're always spurred by other changes.  So, there's no need to, say, check a boulder every frame to see if it should roll.  If it's stable on a given frame, it won't be checked again unless the space around it is disturbed.

Since most of the game world is fairly static each frame, the result is potentially much more efficient world calculations, meaning being able to simulate more of it each frame.  The biggest drawback is that gases are unsuitable for this system, since they'd be constantly spreading bit by bit regardless of whether the neighbors change.  Even so, it's a promising direction for development.

Gamasutra article up

The Gamasutra article offering a rough view of the cellular automation liquid algorithm in In Profundis is up.

In Profundis progress (4/20)

Today was mostly consumed writing an article on fluid simulation using cellular automation.  It links to the Kickstarter project page, hopefully it'll enable the project to keep up its momentum.

Program progress: image loading code for sprites, drawing animations, prep work for the platforming engine.

Second pitch video

This is mostly the same as the one on Kickstarter:

New Project: IN PROFUNDIS

Coming to Kickstarter soon!  This is really promising, so watch this space!