Pyglet engine work

One of the things that has blocked the project for so long has been a shift of the engine from Pygame, which is easy to use but relatively slow because it does its rendering in software, and furthermore doesn't play well with any Python speedup module other than Psyco, to something else that's hardware accelerated and will work with PyPy.  That something else being: pyglet.

But despite the fact that it's been around for a few years now there's not a huge amount of stuff on the web about pyglet.  Most of what I've found has been its own documentation and a presentation called Stretching pyglet's Wings.  A few months ago I did a promising graphics test that taught me a bit about how pyglet puts together its images.  Now I've gotten something like that going in a tile engine, and it looks promising.

The reason for making the switch, and also for trying out weird cellular automatic schemes, is that, under the old system, I wasn't getting the performance that I was looking for.  When you're simulating only a portion of the world instead of the whole thing each frame, some things start to act funny at the edge of the simulation frame.  For something like Life that would be deadly, but here in practice it doesn't seem to cause huge amounts of problems so long as we spend some time at the start of simulation calculating over the whole map, in order to let fluids settle.

But it does have one problem that has always bothered me greatly, and that is, we can't have running "rivers" in the simulation between two distant points, because if one of the points is outside of the simulation frame the whole flow stops.  This means that most bodies of fluid the player encounters are static, which greatly limits the utility of having a cellular engine game in the first place.

Well performance-wise pyglet looks like it's got what it takes.  It can display a whole screenful of tiles nearly instantaneously.  Pygame takes a lot more time to do stuff like that unless you use tricks like only drawing parts of the screen that have changed, which is somewhat problematic for a scrolling game, and even more problematic for one where arbitrary tiles may change each frame.

pyglet

The most annoying thing about using pyglet, by far, is that nearly all the good sources on the library are either 1. the "Pyglet Programming Guide," available on the pyglet site in PDF form which is unwieldy and concerned with getting you started with the barest basics and little more, or "Stretching pyglet's Wings," which is a bunch of presentation slides with accompanying source code archives.

Maybe something to talk about soon....

Having to deal with a maze of personal issues, there hasn't been much to talk about concerning In Profundis lately.  (Some of them have had to do with negative comments on the blog here -- please, don't berate me for the time it's taking, I already know and feel awful enough about it as it is.  But I have to keep myself fed.)  But I might have something to tell regarding the "sort algorithm" I mentioned before, that I've been thinking very hard about lately concerning modelling falling and mixing fluids.  I think the idea is genuinely novel, and so maybe some of you might get some use out of it?  At the very least it might represent a substantive step towards getting this thing finished.  I still have tests to run with it though.

Where I've been

Yes everyone, I still exist, and In Profundis weighs heavily on my mind.  I've not been talking about it here lately because I reckon it gets pretty old being told the same old things about its progress.  Unfortunately I have bills to pay and the Kickstarter money doesn't really last that long, and I'm loathe to ask you good people for more.

But hopes run high in the near future.  The big project that's been consuming my time concerning ends meeting is about to publicly release, so maybe I can get back to devoting time to (the unfortunately acronymed) IP.  It also has to do with cellular automation, and I've picked up a couple of ideas relating to In Profundis while working on it.

Progress: OpenGL, pyglet, new fluid dynamics, optimization rewrite

Not a lot to show publically, I'm rewriting the engine to make it more optimizable (a big part of this is switching from a Python class for cells to parallel arrays that can be turned into C arrays a lot more easily), and while I'm at it I'm learning pyglet and all about creating vertex lists and loading them into memory.  This, plus the fluid sorting experiment, should provide for much better performance, although it remains to be seen how that will work.  More soon.

bubble vs decorated sort

There were some comments on the previous post about using a limited number of bubble sort runs, as opposed to a full sort of the whole list weighted by original position, which was an appealing argument in a Keep-It-Simple-Stupid kind of way.

So I'm running some performance tests comparing limited bubblesorting of lists against a decorated sort weighted by initial position.  Here is the code tested:

# This is run on the data eight times by the testing code
def bubblepass(sortlist):
    skip = False
    for a in xrange(len(sortlist)-1):
        if skip == False:
            if sortlist[a] > sortlist[a+1]:
                temp = sortlist[a]
                sortlist[a] = sortlist[a+1]
                sortlist[a+1] = temp
                skip = True
        else:
            skip = False
    return sortlist

def decsortundec(sortlist):
    templist = zip(sortlist,range(len(sortlist)))
    declist = [(item[0]+(item[1]/4),item[0]) for item in templist]
    declist.sort()
    return [item[1] for item in declist]

In performance tests on lists of 3200 random small integers, the decorated sort runs from 40-60% faster than the bubblesort, despite it creating three entirely new lists along the way.

decsortundec uses list comprehensions, which are a powerful, yet to me somewhat confusing, aspect of the language.  To my understanding they are a way of creating a new list from a source list quickly, and along the way you can modify each item of the original list and/or choose whether to include it or not.  Note that this code runs in Python 2.7; Python 3 list comprehensions create iterators instead of lists, so the return value must be explicitly turned into a list, using list().  (There might be a better way to do this, in Python 2, using functional programming, but my brain hasn't been twisted into thinking in that particular Lispy way yet.)

Notes:
1. bubblepass is not a pure bubble sort, because on our trip through the list we skip positions that have already been swapped from the previous position.  That doesn't matter in a true bubble sort where we're ultimately trying to sort all the items as quickly as possible, but we'd need it here since we specifically don't want particular items to travel far.
2. It is possible that PyPy will optimize the bubblesort better, maybe far better, since it uses fairly elementary Python, while the other uses list comprehensions which are mostly implemented in C by the virtual machine.
3. I'm new to writing list comprehensions (which decsortundec uses twice) so it's possible there's a more efficient way to write this.  Would anyone know of a better way to factor in an item's original index number into its sorting weight?
4.  It might be possible to use some of that list comprehension stuff on the bubble sort, but I don't see how to implement it off the top of my head.

Weird simulation idea

I think I've had something of a breakthrough on this project.  Think about this for a bit:

Ultimately, the simulation is just a kind of inefficient sorting operation.  Fluids travel from higher places to lower places.  Other things get in the way.  If things aren't falling, then they might migrate side to side.

Sorting is a hard problem, but it's one that a lot of effort has been poured into.  Python particularly has some good sorts written in optimized C.

We already use Python's sort functions in the code, to arrange the positions of different slices of liquid in a single cell.  My idea is to extend it beyond that cell -- to sort whole columns of fluid at once.

The biggest problem with this is that sorting works too well -- heavy fluid will transmigrate from the top of a column to the bottom instantly, with no possibility of affecting anything along the way.  There needs to be some way to limit how far an individual slice of fluid can travel in its passage.  There are no sorts that I'm aware of that support this kind of travel limiting, but it might be doable using a Python trick more frequently used back in older versions, called Decorate-Sort-Undecorate.  That is, you first modify the contents to encode additional information into it that weights each item in the sort by some variable, in this case that would be initial position in the column.  The weights would have to be chosen in such a way that the fluid weights would overpower the positional weights over short distances but not long ones.  Then we sort the column, then remove the extra information (or in our case, overwrite it with new positional information the next time we do a sort).

Another problem is that we would still need to make another pass through each column to handle sideways motion.

How does that sound to you folk?