Friday, May 13, 2011

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.

1 comment:

  1. It is indeed very important that it simulates correctly, otherwise we wouldn't have all the influence of the player on the game world...