Evolutionary Gaming

I've been fascinated recently with evolutionary/genetic algorithms. My favorite, of course, is electric sheep, but today I caught glimpse of a simpler one, Evolve.

This kind of approach to dynamism got me thinking about how social voting algorithms could be worked into a game. To have a game (single-player or multiplayer) tune itself to the player's desires would be fantastic, surely. But forcing the player to submit a vote explicitly is a bit much. Instead, what mechanisms could be used to imbue the engine with the capacity to observe the player and tune something (the physics, the environment, the textures) according to the player's tastes?

I find myself thinking about how much I dislike desert levels in games. I hated it in all the Star Wars games that ever used Tatooine, I hated it in Diablo II, I hated it in Ratchet and Clank... I just hate desert levels. But whether it's the sense of dryness, the wasteland quality, or just that piss orange color, should the engine be able to detect that I don't like it?

In a game like Vyde, the player will ideally encounter areas having many different themes. Travel far enough, and you may encounter a fire cave, then an ice cave, then a rainforest cave, not necessarily in that order. But can't something be said about the users that deliberately avoid certain types of areas? If a player repeatedly encounters a fire cave and retreats within sight of it, can't the engine assume that that user just doesn't like (i.e. won't play through) fire caves? And if that assertion can be made, wouldn't it make for better gameplay if the engine tunes itself to avoid that type of level? (This assumes, of course, that we're talking about an engine whose responsibilities include randomly generating territories, but the principle could've easily been applied to, say, the random item generation algorithms that drove the Diablo series or even Nethack.)

I want Vyde to be procedural to an unprecedented degree. Though Spore may beat me to it, I'd still like Vyde to have self-tuning capabilities that make it possible to encounter variations on themes based on the areas I choose to explore.

The system itself shouldn't be hard to implement. The engine would keep counters related to the number of times a user encountered a certain type of area. An encounter would be defined as, well, the event that occurs when the engine decides to switch themes in response to a freshly-broken tile. Even if the engine is capable of creating an infinite variety of areas, it can cull old tallies and maintain some kind of cache of "recently explored themes" that it can use to govern its future theme-choosing behaviors.

Projects like electric sheep and Evolve always make me wonder if, given enough participation, an "ideal" result could emerge. I'm still reading Emergence by Stephen Johnson, and even in my humble capacity as a hobbyist I feel obligated to recommend it to all game designers.

There is a terribly encouraging trend emerging in the capability of hardware to outthink its users, and when applied to gaming, it isn't hard to imagine a day when a game can rework itself to a player's tastes. Could we be so bold as to assume that it would increase the marketability of replayability?

Progress Report

This post is actually quite a bit late, as the prototype described here was completed a few weeks ago at least. But life has been hammering, hammering, hammering at my free time. I wanted to dedicate the proper amount of time to this post.

My goal for this first prototype was to create a simple console application that would let me move a "cursor" around a grid of tiles that would expand as needed. The cursor would be capable of moving only up, down, left, or right based on which arrow key was pressed. At each step, a printout of the cursor's location would describe what tile it resided upon and what that tile's relationship to its parent grid was.

The object model for this prototype works something like this:

The "world" in the prototype is comprised of Tile instances. TileGrids are special kinds of Tiles that contain other tiles. I thought it was clearer to make the distinction rather than just have Tiles contain other Tiles. It makes type checking a little easier and makes the code a bit more readable overall.

Every Tile instance can be parented by a TileGrid. A new TileGrid is created whenever the cursor attempts to move away from an unparented Tile or when it crossed the edge of a TileGrid.

The TileCursor calls the TileMunger's encapsulate function when either kind of movement occurs, causing a specific Tile instance to be parented by a new TileGrid and placed within the new TileGrid's list of Tiles. As the cursor moves farther and farther away from its origin Tile, more and more TileGrids are created in a recursive fashion.

A given tile is parented by some grid, which may be parented by another grid, which may be parented by another grid, etc. This grid hierarchy is organized into "tiers" that the cursor traverses to move among the tiles. When the cursor is told to move across the edge of a grid, it "ascends" the tier hierarchy until it is able to move without crossing an edge. At each step, the TileCursor has the TileMunger create a new parent grid if necessary. When it's high enough, the cursor moves in the requested direction, and descends again until it rests on the same tier on which it started, making sure to adjust its position at each step to correspond to its original position along the original grid's edge. As it descends, the cursor has the TileMunger subdivide tiles to create the necessary grids.

In this prototype, each grid is 3x3 tiles in area. Each grid has a coordiante system with [0,0] in its upper-left corner. The screenshot above shows a cursor starting in the center of a new TileGrid, at position [1,1]. It then moves one tile south, to position [1,2]. When I tell it to move south again, two things occur: a new TileGrid is created on tier 2, and a new TileGrid is created south of the original grid on tier 1. The grid at tier 2 parents the two grids on tier 1. (I don't really have a good illustration of this yet — that's the next step in the prototype.)

The code to make all this happen is short, but not easy to follow. Most of the work is done in TileCursor.Move(), which works recursively.

What bugs me about this prototype is how intertwined all the components are. I don't like that the TileCursor calls TileMunger methods, i.e. that it is responsible for altering the world. I'd rather the TileCursor be responsible only for hopping from tile to tile, without having the responsibility of initiating the creation of new elements in the world. I think future designs will repurpose the TileCursor to be a "digger" that really is responsible for altering the world. Or, perhaps I'll assign more responsibility to the TileMunger class; but what will invoke it?

I want exactly one class to be responsible for creating new grids and populating those grids with tiles. The TileCursor is not a candidate class, as it should, semantically, be responsible only for pointing to a specific Tile, providing facilites for moving from tile to tile. Currently the TileCursor is limited to north,south,east,west movements in 1-tile hops. I want to eventually create a Move(dx, dy) method, but the current world growth algorithm doesn't facilitate that very well.

I'm worried that I'll get to a point where my cursor movement algorithm will flow something like this:

1. Does a tile exist south of the current tile?
2. {perform lots of calculations to "hop" to that cell and find no tile}
3. If not, create a tile south of the current tile.
4. {perform many of the same calculations to "hop" to that same cell, create a tile tile there, and return the new tile}
5. Move to the new tile

Looking at it now, I think I can refactor it into something I'm happy with.

Looking ahead, the next step is to create a GUI that actually renders the tiles that have been created. The first GUI would likely plot only those tiles that occupy tier 0, but I haven't figured out how to start the algorithm. I can't figure out yet where the recursion starts, whether it's on a tier 1 grid or a grid on some arbitrary tier. One problem I'm faced with is translating this nested coordinate system into a normal coordinate system understandable by, say, the System.Drawing API. But I think I can solve that pretty easily by building something that traverses an arbitrary grid and aggregates all tier-x tiles in that grid's hierarchy into a simplified 2D array that can be rendered.

If I can get the tiles at tier 0 plotted onto a canvas, I'd like to then illustrate the creation of grids by painting them as semi-transparent layers on the canvas.

Then, I'll turn my attention to prepopulating the grids with content for the TileCursor to move over, like ore veins. :)