BITPHORIA, The Game Itself

It occurred to me that most of what I write about on this blog has been the technical side of my thoughts and ideas while working on my game BITPHORIA. I haven't really been posting much in the way of actual progress on the game itself.

I thought I'd take a moment to share what is going on with BITPHORIA. As of now, by my estimation, the game engine is 80% done, and the game itself is roughly 15% completed. I am currently on the cusp of moving from working in the engine to working in the default game scripts.

I have spent a long while tweaking the visuals over the months, and trying out different little tricks, in an attempt to refine the overall appearance of the game into something that is stimulating and attention-grabbing. My entire philosophy on anything is to make it so visually appealing that anybody who sees a screenshot will automatically find themselves looking for a video, and anybody who sees a video will want to play the game.

If BITPHORIA doesn't captivate, visually, through a screenshot, then something needs to change. I don't want to make a product that isn't good enough to sell itself. 

I think that these screenshots portray the overall aesthetic and graphical design of what the final game will consist of. You'll probably notice the low frame-rates that my netbook achieves. It's playable on here, but you will want something with a half-way decent GPU to perform the raymarching on the 3D texture materials. There will be options to reduce the demand on the GPU so that it will be smoother for players with budget/older hardware.

The scripting system is mostly in place. There are a handful of features that I aim to implement to expand functionality further, but the majority of all the commands for scripting each system are present and operational. There is still a lot of validation and verbose warning/error stuff that I need to go back in and write in there, to help aspiring mod developers along.

Documenting the sets of commands for each system is another task that is needed. I am not sure about when this will happen, because I intend to do most of the scripting for the game myself, and so it isn't something I have a need for until the game is released. Until it's released, I am really the only person who will be using it, and I'd like to finish BITPHORIA as soon as possible.

Netcode is operational. Players can start a server and it can be joined from another machine, on a LAN, or over the internet. There is no server-browsing in the menu yet, but that is on the todo list, which goes along with other menu UI features I'd like to add in for various things. One in particular is a sort of holographic preview of the world-volume that would be generated from the current seed value. As a server admin adjusts a slider for the seed value it updates the preview of the world so the user can get an idea for the type of layout that their game will offer other players who join in.

I have a good number of sound effects already in there that I have produced on my own, some of which have yet to find a use. There are 23 different sound effects, and only about half of them have found a place in the current scripts. I feel that I will use up the leftovers and need to make some more sounds before all the sounds are done.

I have also produced several 2-minute looping music tracks, that suit the general low-fi 8-bit aesthetic that underlies the graphical style of BITPHORIA. I'm not sure if all of them will make the final cut, and I'm not sure if server admins who start a game will be able to choose one themselves or if one will be randomly chosen based on the seed value for their game.

Because of the way the scripting works, where a set of scripts defining one game 'mode' is kept in a folder with the name of that game mode, users will be able to duplicate a game script folder and use it as a base for their own modded game mode. The scripts are relatively simple script files, and all that is needed is the documentation for the various commands that each scripted system utilizes. Anybody will be able to edit their script files to customize their game modes, or just create their own new one from scratch.

When someone has produced a BITPHORIA mod, there is no need for other people to manually download and install anything to their BITPHORIA installation. You simply see what game mode servers are playing in the server browser, and automatically download and run the mod when you join in. Infact, no scripts are loaded when you join a server, you only execute whatever scripts the server executes. This allows complete modding freedom. Anybody with BITPHORIA can play your mod, instantly.

If someone wanted to run their own server using a specific mod, they would need to manually download and install the mod scripts. This could change, I may set it up to allow servers to have the option to 'allow mod copying' for clients, at which point the server would let clients download the actual script text files and save them to their game for later use.

All of this is working, the game is currently playable as a simple little deathmatch game. The UI is vastly incomplete, there are no options for setting up a game, or joining a game. The menu system is started, but not currently 'fleshed out'. It is merely a framework with some minor functionality to traverse menu hierarchies using buttons. There are also nice little editboxes for editing configuration strings :)

I started the code base for BITPHORIA exactly a year ago today. It has just over 16k lines of actual code (not counting comments or whitespacing). I have never written 16k lines for one project in my life, nor have I ever worked for a year straight on one project. I have high hopes for BITPHORIA, not as something that will make me rich and famous (although, one can hope), but as something that the gaming industry takes notice of. I figure, at the very least, it will serve as a good portfolio piece if I ever breakdown and decide to get a job working for someone else (ughh).

I feel I have something valuable to contribute to gaming, as a whole, as well as anybody who aspires to make games or learn programming. I just want to be as valuable a resource as I possibly can, whether that means as a provider of fun and interesting games, or creative inspiration.

I hope people find my ideas as intriguing and enjoyable as I do making them come to life.

Forays Into Entropy Coding

One of the many minutiae that concerns me is bandwidth consumption. The fact of the matter is that the internet is not a particularly forgiving means of conveying data from one place to another. It is merely *the* means for conveying data. It is what we have to work with; everyone with a different connection.

Some poor souls are forced to use dial-up, way out there, in the middle of nowhere, and others are privileged with fiber optic connections (we could use a visit, Google). In the middle are the broadband users, with varying capability, via DSL or cable.

A 'D-' for my perfectly usable connection. It's only near-failing
if the application in question is failing the user.

You can see here that my home cable connection has a bandwidth of roughly half a megabyte downstream and 100k/sec upstream. Nobody reads/writes/sends/receives anything in bits (except for programmers), so I like to look at these things in terms of bytes, because they are infinitely more relevant to me (and you). You can see that my connection's score is a 'D-'. I could see that if my priorities involved watching 1080p video. Instead, I'd give my connection a 'B+' because it is something I almost never have to think about, it is plenty fast for my needs. I'd give it an 'A' if it weren't for the random outage that occurs once every few months for an hour or two.

The reality is that it's not the connection that matters, it's how the application uses the connection, and what the end-user's experience is. It makes no difference how I obtain the experience, via 56k or 1-Gbps fiber, as long as the experience is 'A' worthy. Even the newest consumer GPUs are brought to a crawl by games made by those who have no idea what they are doing. This doesn't mean the GPU isn't up to snuff, it means the game designer is doing gamers a disservice by not taking a realistic idea of common hardware configurations into consideration, especially if they took their money for it.

My strategy with BITPHORIA is to make something new, and interesting, that takes advantage of newer hardware capabilities to perform novel rendering, without requiring the most up-to-date setup. Being a multiplayer game, this applies to a player's internet connection as well.

If I can support the vast majority of the existing configurations out there, then that maximizes the potential player base, which translates to customers. Primarily, though, I don't want to leave anybody out. I want the high-end gaming rig players to be happy with their investment, and I also want the newbies on netbooks to be able to enjoy a rousing session of BITPHORIA.

I don't want people to be forced to play on large fiber-connected servers. I want a newbie with a netbook on a wifi connection be be able to host a game server, that can host at least a few players. Even a 'low-end' broadband connection like my own only has only a 100kb/sec upstream, which could easily be saturated if I were to host a server running any popular FPS game with 8 players. In order to make this possible there must be a minimal amount of data traversing the network connections between the server and player clients.

Naturally there are several strategies for minimizing bandwidth usage when conveying a game state across a network connection. Quantizing, or 'bit-packing' various data based on its type and behavior is one extremely important method. Typically, values for angles/orientation/etc are represented and dealt with as floating-point values (or double-precision, if your application demands it). Floating points values (aka 'floats') are 32-bits, and sometimes only a small range of their capable range is used. For instance, in a game, you may have objects with velocities that never go above a certain speed. This knowledge can be used to effectively remove the extra unused-bits from velocity information about an object.

Another strategy is avoiding sending redundant data, and only send certain properties when they change, instead of re-sending the same information over-and-over. This applies to things like an object's position in the game, and orientation/angles. If the object is stationary, there is no need to send this information about it.

Another issue that comes up is the game's network update rate. The update rate, in most client/server games, must be as high as possible without putting too much strain on the server or client connections. With lower update rates the game can begin to feel a little sloppy, especially to gamers who have acquired a fine sense for such things. I've seen game servers with their update rates so high that some player connections couldn't keep up. This is just plain unacceptable. Some games keep their update rates really low because they are sending too much data per-update to be able to have it any higher without making the game unplayable for slower connections.

Keeping a low update rate is another possible strategy, and needs fine tuning alongside other important aspects of the networking that handles interpolation and extrapolation, and maintaining the game simulation's fidelity.

Compressing the network data on it's way in/out before actually sending it is the strategy I am currently working to employ in BITPHORIA. My initial plan was to just follow suit with Quake3's use of a static-Huffman encoding, which breaks down as a simple method of re-assigning byte values a new binary code, where more frequently appearing values are represented using a smaller bit code, and less frequent values use a larger bit code. This is a form of entropy coding.

With entropy encoding it's all about exploiting the known likelihood that a byte will be a certain value. This is orthogonal to dictionary encoders, which operate on exploiting the fact that there are usually repeating-patterns in data. Entropy encoding doesn't care where the values are in the stream, they can be clumped together next to like-values, or spread evenly, and the output will be the same size as long as there are the same number of each possible value. Dictionary encoders typically produce a much better compression than entropy encoders, but are much slower. They also do not operate well on small pieces of data, and are better equipped to compress large data.

Generating Huffman codes for symbols a1..a4 using their probability to
build a tree from which the codes are derived (ie: 0 = left child, 1 = right child).

There are two major entropy encoding algorithms that exist, Huffman coding, and arithmetic/range coding. The deal here is that Huffman can be reduce to, as I mentioned above, a simple exchange of byte values for bit codes to be output. This works well as a simple array/table look up in code. Arithmetic/range coding lends itself to better compression ratio, because the resulting bitcodes generated more closely suit the probabilities of each possible value, and therefore produces output that is closer to the actual informational content of a piece of data. The catch is that arithmetic/range encoding is more CPU intensive.

Range coding represents data as a single value generated
by recursively narrowing down each symbol in it's "range".

Now, to be honest, I could probably get away with simply using either, and nobody would know the difference. This is where my neuroses comes into play. If I can do better, I will do better. So after some research I saw potential in the idea of using arithmetic coding, specifically range-encoding, which is the integer-based version of arithmetic coding.

After a day I came up with my very own entropy encoding, which was essentially a bastardized hybrid of Huffman and range encoding combined. Without an academic background in math, I was simply fumbling around, hoping to stumble across a discovery. The goal was to produce the speed of Huffman encoding with the higher precision of range encoding. The end result, dubbed "binary-search encoding" has roughly the speed of Huffman, with neither the compression ratio of Huffman or range encoding. So that was basically a failure. I was able to compress a 512 kilobyte sample of BITPHORIA's networking data down to 405kb. So that was a compression ratio of ~1.26, whereas a simple Huffman encoder can get the same data down to 341kb, a ratio of ~1.5. My binary-search encoding was not gonna fly, at least not in this situation.

Arithmetic coding does the same as, or better than, Huffman, because Huffman is essentially a special case of arithmetic encoding where value probabilities are powers of two. This is why it cannot achieve an encoding that is closer to the actual informational content of a piece of data.

During my research to better understand range encoding, and why it works as well as it does, I was hoping to incorporate these principles into my little algorithm to get better compression than Huffman, even if it wasn't as good as true range encoding. This is when I stumbled across Asymmetric Numeral Systems, and Finite State Entropy. A new algorithm recently developed and even more recently made to be as fast as Huffman encoding, with the compression of range/arithmetic encoding.

ANS captures the raw essence of arithmetic coding, without the convoluted means of obtaining such an encoding. At the end of the day the system breaks down encoding and decoding into a table of bitcodes for each possible byte value, just like an optimized Huffman implementation does. The end result, though, is a better choosing of bitcodes for byte values by maintaining an internal 'state' from which encoding a symbol into some bits yields a new 'state' for the next one.

My initial attempt that utilized a binary search was flawed in that it had to 'start from scratch' with each symbol that was to be encoded. There was no internal state being maintained, and each symbol was treated as a lone isolated incident without any context. ANS maintains this context, which allows it to utilize less bits for encoding/decoding.

If you enjoy compression and information theory, please explore these links!

Links:

RealTime Data Compression - Finite State Entropy - FastCompression.blogspot.com

Asymmetric Numeral System - EZCodeSample.com

Simple and fast Huffman Coding - CodeProject.com