Friday, August 16, 2013

More on multitile objects, NumPy

Cellular automation works best on entities that are the same size as a single cell.  Once you start simulating things that are smaller or larger than that, things get complicated.

The smaller case is why, in the rewrite, I abandoned the previous tactic of simulating multiple fluid layers in a single tile.  As for larger, well, I'm implementing that in the form of multitile objects.

Everything that has an extent that goes into more than one tile is a multitile object.  That includes the player and other actors in the world.  It will also include things like boulders (which are going to be two-tile objects, at least) and even oddly-shaped solid objects that fall due to gravity.

There are a number of challenges to simulating these things.  For example, how to tell if one should fall or not?  You have to check beneath every tile in the object, but more than that, if the whole object falls every time any of its cells come up for a turn it'll end up falling much faster than other things in the simulation, and yet, each tile cannot just fall itself if the object as a whole is to keep together.  How about if something breaks apart a multitile object so it splits in two?  If you have two of the same kind of object next to each other, how will the system know they aren't part of the same thing?  And so on.  And there are some weird edge cases too, like two objects each "supporting" each other, so as a collective unit they both hang in mid-air.

Today's work has been in putting in more multitile object support.  In order to hurry lookup, we're using a weird system where a Python dictionary (known as a map or hash in other languages) is used to index them by their coordinates.  This trades off a little bit of speed for much reduced memory usage -- we don't have to store zero or None for tiles without multitile objects.

By the way, one of the greatest things about Python is the universe of third-party modules available.  Of these, one of the most prominent is NumPy, which is an optimized interface to a C-style array with several powerful optimizations applied to it.  In Profundis does use NumPy, but not, in the normal case, to hold the map at this time.  This is because the various overheads of Python don't interact with C well quickly; while arrays are held in a highly optimized state storage state in memory, Python converts each value into a Python object when read, and when stored back it converts it back, and this is an expensive operation.

What we do is, simply, use NumPy as a shortcut to creating the map grid, converting the whole thing into a list of lists easily in one method call (.tolist).  It's a bit wasteful in memory, but it's really a lot faster this way, the new emphasis on smaller regions saves some memory anyway, and compared to the large amounts of memory even inexpensive systems are shipped with regularly these days it's not projected to be a problem.

The system is set up that a flag can be set to use NumPy arrays for the world state instead.  This is because Cython can potentially make much better use of C arrays, so if we take the step of going with Cython as the implementation basis we've already got one foot in that direction, so to speak.

No comments:

Post a Comment