Sunday, August 11, 2013

Two kinds of turns

One of the things I figured out while working on Employment Project during the hiatus was an alternate way of scheduling turns for slower cellular automation.  I don't know of anyone else doing this, so I figure I should mention it aloud in case others find it useful.  I am using it for slower effects in In Profundis, such as corrosion, erosion and gas diffusion.
In Profundis uses two systems for scheduling cellular "turns."  The first is a queue of active cells, which is continually updated each frame with the output from the previous frame.  This is based on the principles that:
- Each tile is mostly static.  Solid walls of stone don't require any processing, and big airy voids don't have a lot going on.  Similarly, bodies of water don't do anything generally unless disturbed, except on the surface.
- So, instead of performing a big loop iterating over every tile in the area, we keep a queue of tiles in a Python list, and iterate through that.  While processing, each tile changed adds its coordinates, as well as the coordinates of adjacent tiles that might have been "dislodged" by this event, into a new list.  Once the first list has been exhausted, we replace it with the new list for the next frame.

(Note 1: actually, we only give half the cells turns each frame, in a checkerboard pattern that alternates, so we don't end up with as many situations where turn ordering influences the sim.  It's not entirely successful at this, due to the vagaries of the ordering of the tile queue, but it's good enough.
Note 2: The list added to is actually a Python set, as it automatically excludes dupilcates.)

This vastly cuts down on the overhead of running a cellular system, and allows us to do it in ordinary Python at a reasonable speed, at the cost of being a little less certain about the outcome (since tiles that act earlier in the queue might create a situation that prevents tiles occurring later from acting -- if this were a problem we could use the bisect module to ensure the list is ordered), and for being less efficient if very large numbers of tiles change in a frame.  The first doesn't matter too much in practice, and the second would produce too chaotic a world to be interesting anyway.

I've talked about this before, I seem to remember.  What's new, however, is a second kind of turn, used for longer, slower processes.  Not every cell gets one of these "slow turns" each frame; indeed, about 1-in-64 of them do.  Since there aren't as many of these things happening, we can afford to look at every tile, and thus we can use this to simulate a wider variety of effect.  We'll get to that in posts to come.

No comments:

Post a Comment