Wednesday, May 4, 2011

Cellular automaton, raw image data, and game states

Cellular Automaton

I learned a new term this morning: "Cellular Automaton".  It's basically a grid where something can be in each grid cell and the state of that something depends on certain rules about the surrounding grid cells (its neighborhood).

An example of cellular automaton being used is one of those games where you have to dig tunnels through the dirt, and there are various objects in the dirt which can fall down if you dig out a hole under them (these objects can even crush you depending on the object and the game in question).  Usually your objective in these games is to gather gems and avoid being crushed by boulders.  The motion of the boulders as they fall can be controlled as a cellular automaton.

Controlling the falling motion of boulders is fairly simple and straight-forward (or downward in this case).  A cellular automaton requires a grid.  These games are usually tile based, so we can check that off the list.  The second requirement is that each cell needs a finite number of states.  In our case, the states will be "boulder", "dirt" and "empty".  The third requirement is a set of rules need to exist which control the state of a certain cell based on its neighborhood (usually the immediately surrounding cells).  We want the boulder to fall down until it hits part of the map which hasn't been dug out yet, so the following rule should suffice: If there is a boulder in the north cell and the current cell is empty, remove the boulder from the north cell and place it in the current cell.

To step a cellular automaton forward in "time", iterate over all of the cells and apply the rules to each cell as it is visited.  Depending on the rules you are using, you may want to iterate in a certain order.  For example, it would be a good idea to iterate from the bottom up so that two boulders in a stack fall down at the same time (there would be a gap in between them if you went from the top down).

A very interesting application of this technique, which is discussed in "An Intro to Cellular Automaton", is to simulate fluid flow.  After simulating a boulder falling down, it's not that much of a stretch to simulate water falling down and spreading out when it hits (you just need more states to include how much water there is).  This is actually very similar to a technique our designer/artist GreyKnight mentioned last year.

Raw Image Data

On a completely different note, I had an idea earlier today for loading textures: Rather than storing them on disk as .bmp, .png, or other similar file formats, store just their raw data ready to be loaded directly into a Direct3D texture.  This would simplify the in-game loading code quite a bit if you are trying to avoid D3DX (like I am) since you don't need to put the various image format loaders into the game.  Doing this would require a "compile" stage of sorts before new images could be available in the game, but this may be worth it in the long run, especially if you are already planning on packaging all the game's files into a single database file.

Game State Changing

Back to actual coding progress; I spent most of the day researching, but I did manage to finish the first iteration of the game state changing code.  It works basically like this: When a new game state is entered, it is given input data.  This input data can be things such as the character which the player chose, the socket handle for an open connection to a server, etc.  Each game state has an update function which returns one of these input structures.  If the input structure is empty, the game state doesn't need to be changed.  If the input structure is tagged with a magic state ID, the program shuts down.  And finally, if the structure is tagged with the ID for another game state, the current game state is left and the new game state is entered with the structure as its input.  So to summarize; the output of the current game state is the input for the next game state.

I've decided to scrap the systems layer I talked about in yesterday's blog post. I am going to try a reference counting approach to the problem.


Some useful resources I found today:
Software optimization resources - A treasure trove of C++ and assembly optimization information.
Design for Performance - Sometimes vague, but a pretty good set of slides on getting more performance out of a game.
Mature Optimization - Discusses ways to design your code so that it stays more optimized throughout development rather than saving all optimizations for last.
An Intro to Cellular Automaton - This is the article which introduced me to the term "cellular automaton".  This is a good read, especially if you are interested in further information on the fluid simulation technique.

No comments:

Post a Comment