Back to Work

So I got married back in November, and after than we had Thanksgiving and Christmas. My time since then has been spent catching up at work and making the first motions toward buying a house. (Oh, and I got a Wii.)

Now that my wife and I are in a conservative spending mode we're spending a lot of time at home. This affords me a lot of time to either play video games or spend time working on one. It's high time I got back to work on Vyde.

I've been spending a lot of time lately thinking about how to facilitate an infinite 2D playfield. It's a problem of address space: how do you address any point in space in an infinite space? My first instinct was to find a way to organize space such that addressing a point was a matter of first finding an area containing that point, then addressing a smaller area within that area, and so on until you arrived at the point you desired. This was the principle behind my most recent prototype&emdash;it worked alright and facilitated very fast jumps through space of arbitrary lengths.

The Quadtree Approach

That approach was powered by a kind of quadtree. But rather than concentrating on subdividing an existing space like so many quadtree algorithms do, I wanted to grow the quadtree from the inside out: as additional "world" was created the quadtree would add another level to its hierarchy to contain it.

I wondered about how I'd store a world expressed in this way: when it comes time to persist the world to disk, how do you write it? The quadtree was divided into nodes and leaves, with nodes being areas containing smaller areas and leaves being some concrete piece of world, maybe about as large as a screenshot. I thought I could write the nodes and leaves to disk such that each "file" had a notion of its children and parent. From such a (spatially indexed) filesystem I could rebuild the world when it came time to load a new game.

Then I wondered about how I'd work with such a playfield in memory. A 2D side-scrolling game needs some concept of a working set: those "tiles" of the world that are kept handy in memory in case the player revisits them. As the player moves through the world, that working set has to be updated without interfering with gameplay. So my attention turned to addressing not just a single point in space, but an area of the world: something that would be returned from a call to a method like, .GetTilesSurroundingPlayer().

All this thinking about complicated data structures overwhelmed me. But the exercise proved worth doing: eventually all that thought helped me realize (once again) that I was making things too complicated. It dawned on me that I was confusing a storage system with a coordinate system, and it further occurred to me that indexing&emdash;being able to quickly locate a piece of data&emdash;is a layer on top of storage.

Storage

Storage of the world need not be complex. Individual areas, each of an arbitrary size, can be stored on a regular filesystem as files, folders, or whatever; the format of the bits that manifest themselves into a piece of the world isn't especially important (yet). How they're organized on disk is also a decision that can be deferred until later.

What's important is that there can potentially be an infinite number of "pieces," and whatever storage mechanism stores them must accommodate that. But of course there's no kind of storage today that can do that. Modern file systems are limited in the number of files they can store, hard drives are limited in size overall, etc.

Instead of solidifying a storage system now, what I need to get the game going is an intermediate layer that abstracts it all away. As additional storage is necessary, that layer can be changed: augmented with additional address space, media support, etc.

Coordinates

In a 2D world, even an infinite one, any point in space can be described using two coordinates: X and Y. When people think about 2D coordinate systems, X and Y's typically assume an integral or floating-point type. But as this discussion of Dungeon Siege describes, a coordinate need not be a single number. It may instead be a more complex data structure.

So, to address a point in an infinite world I need a coordinate system where a single dimension can extend forever and remain addressable. Again, abstraction to the rescue. I don't have to invent that now; I can abstract it away with something that, say, for now only uses integers to describe X and Y. As the game evolves, a cell whose position was once was described as [874338,9713424] might be described with four XML files that locate that cell on a distributed storage system.

Indexing

If the world can be chopped up into small areas that are each addressable and storable, then maintaining performant lookups of these areas becomes my central concern. I learn more and more all the time about how relational databases build their indexes and the constraints placed upon the data's organization on disk. This is a topic that will take a great deal of time to school myself in, but I think it'll be an important part of the game's architecture. Right now, I think I can safely ignore it. With properly-abstracted coordinate and storage systems in place, I think indexing would be a layer sandwiched between them.

Crafting the World

The problem I'm focused on most lately has to do with how I'll craft the tunnels and caverns of Vyde when the canvas is comprised of these individual areas. More on that later.

For now, I'd like to focus on building another proof-of-concept. This one will allow the player to move through an empty space, creating new areas or loading existing areas as necessary.