Design realignments

I've been thinking hard about the future of the project and the best way to go from here.

1. I'm more and more convinced a platformer, or at least not the style the engine currently runs, is not the way to go.  The thing is that the cellular engine can change the world, from turn to turn, in ways that it's not simple for a real-time platforming engine to overcome, at least not one developed by a single guy.

Solution: Go with something more tile-based.  Not abandoning the real-time aspects, but instead of worrying about subpixel-level movement accuracy, instead have the player move from cell to cell.  That doesn't mean it would look exactly like a roguelike, we can have intra-cell animations, but under the hood movement will be discrete, one block at a time.  And by not trying to be an action game, the framerate consistency problems, searching for a solution to which having been the secondary cause of the development delays (the primary one being having to keep myself fed and clothed -- I live well beneath the poverty line) are no longer a problem.

2. The high-degree of substance property randomization isn't as interesting as I thought it would be, and the code is a snarl in any case and difficult to maintain.

Solution: Ditch the lot of that and simulate, for the most part, a number of preset, interesting substance types, that each might have zero or one special properties.  There are too many substances that it's just plain out useful to have around for gameplay purposes: water for swimming, sand for piling up, oil for burning, and so forth.  There are reasons World Of Sand games always tend to simulate those basics.

3. The game world generator doesn't produce interesting spaces to explore.  Oddly, the nearly completely random world builder that I had in the earlier versions made much more interesting terrain than the current maze builder algorithm.  This is actually a case where more randomness is more fun than less.

4. The game world is so large that we can't simulate the whole thing easily, which makes large-scale structures (such as flowing rivers) difficult or impossible to do accurately.

Solution: Try simulating a smaller world.  Also, I've come to realize that 8 levels of fluid in each cell is almost certainly too many.  We could get away with 4 or even 2 levels, and the result would be far less calculation.

5. There is still work to be done towards optimizing the cellular engine.

Solution: There are four possible approaches to the engine, which I've tried to different degrees over time:
A. The one that I've been using the most lately uses a "spiral" scheduling system; cells are calculated going in a square-cornered spiral around the current view focus (either the player or the cursor).  Advantage: if we want to calculate fewer or more cells due to real-time requirements, we can just stop whenever we want.  Disadvanges: iteration overhead, if we're not trying to be an action game, unnecessary, and iterates over every (well, every other) in its region regardless of need.
B. The obvious alternative is a rectangular region around the focus.  Advantage: the sim
plest scheduling system, so the least overhead.  Disadvantage: Iterates over every cell in region regardless of need.  If there's nothing in a cell it moves on fairly quickly, but it's still a matter of concern.
C. Use a list of "dirty" cells, compiled as the previous frame is worked on, and only calculate those spaces.  Advantages: We can calculate much more of the world each turn within the same period of time.  Disadvantages: More complex, and thus more fragile.  This is one of the reasons I moved away from this approach before since the increase in complexity wasn't matched by the performance gains.  With a smaller world, however, we might be able to use this approach to simulate the whole world... making the large-scale structures I really want to implement possible.  I think this is the most promising avenue.  Since we're using random world building, instead of one gigantic world we could instead explore a series of smaller worlds.
D. Use the weird column-based "sort" I've been working on and wrote about in the past few posts.  I think it might be viable eventually... but it is a weird thing, it's good for moving fluids vertically quickly, but we still have to iterate through those cells anyway to handle side-to-side fluid movement.  And it's so weird that I think it'll also be even more fragile, that is, vulnerable to being broken by other engine changes, than the dirty cell list system.  So I'm not using this technique for this project, it might be an interesting experiment some other time but now isn't the time for that.

Tonight I went into the code and switched it from the spiral turn scheduler to a rectangular field one.  I also tried running the game with a smaller world, and it seems to work okay if I make sector sizes smaller.  If I make fewer sectors I get an error, but so it goes.  It'll get fixed, and so will the next one, and the one after than.  Until it's done.

It's nice to think it'll be done.  You've all been waiting all this time.  I've been laboring under this weight, this sword of Damocles, for two years now.  I don't ask for pity or for forgiveness -- I'm not sure I deserve either.  I just say, I have not forgotten it over all this time.  I have never considered abandoning the project, for even a second, and I'm not going to abandon it now.  When I make a promise to do something, I get it done, even if it takes a while.  If you thought to yourself "sure, we've heard that before," I wouldn't blame you in the least.  I'm still trying to think of this in constructive ways, though.

Well, that's where we are.  Next up: getting the smaller world size to work, derandomizing the substance properties, and designing a better world generator.

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.