v1.00 Public Beta Testing

The biggest Bitphoria game in history.

Looks like some people have started taking interest in Bitphoria. There are a lot of kinks to work out, some people are having issues starting a game and having their friends join. I'm looking into it. Lots of little things are being figured out: players can be hard to see, chat messages disappear too quickly, the server I'm running crashed in the middle of the night while two people were playing, AI guys are more aggressive than they need to be, etc.

The end result is inevitably a new release, v1.01, which will have a new network protocol version. The master server will only relay game servers to your version of Bitphoria that are running with the same network protocol. I will be updating my game server to v1.01 when it's released, so people who are still playing with v1.00 will not be able to see it or play on it. An auto-update feature will be implemented down the road, for now my focus is on the engine.

It was also suggested that an automated installer would make it easier for some people to start playing Bitphoria. I already have a process in place for achieving this and wasn't planning on utilizing it until Bitphoria was out of beta, but I have decided to include an automated installer with the next release.

I estimate v1.01 to be released some time next week, maybe sooner.

Thanks to everybody who downloaded the current version and has been playing with it. This has been more fun that I could have imagined :)

Bitphoria v1.00 Beta Released

Pre-release early screenshot of Bitphoria.

Bitphoria has been released. It's in public beta, and this is the very first (aka 'worst') version ever. Start games (don't forget to forward your UDP port if behind a router) and play with others. Dive into the scripting system and make whatever your heart desires. Let's see what Bitphoria can do.

An engine guide is in the works now, to help users better understand the various console variables and how to make full use of them as a sort of 'power user'. I'm sure anybody with their wits about them could figure out most of them just by surfing the console typing a few characters and pressing 'tab'. The confusion, by comparison to most engines with a console, will lie in the fact that the vast majority of console commands are for scripting, and not intended to be executed while in a game, or while just idling in the main menu system.

If you're the type of person who likes to get into new things, unafraid, and share your findings with others, then by all means download Bitphoria, start screwing around, and Youtube your experiences. Share this thing with the world. If you could notify me of your intentions to release a video of your time with Bitphoria that would be great, just so I could follow along and gain some insight as to what I should work on or do differently.

Final Day Thoughts

I started Bitphoria in April of 2014, focusing solely on how the world was generated, represented, rendered, etc.. I had a pretty clear vision of what I wanted the engine to be capable of, and I feel I have achieved that.

Yesterday I finally reached the 20k lines of actual code that I predicted Bitphoria would have by its release date. The scripting manual for making games out of Bitphoria is complete. I'll be uploading the game tonight for release. It's a public beta version that has all of the features I wanted but are not fully polished and probably have some bugs. The goal is to see what kind of feedback comes from releasing it in the state it is in. I haven't been actively promoting Bitphoria very much at all, and figure that if it's any good it will sell itself by spreading via word of mouth. People will post screenshots, youtubes, start making games, playing against eachother online, etc..

Only time will tell.

Bitphoria's source code folder, comprised of 20k actual lines of code.

Tomorrow I will be sharing its release on Reddit and other various online communities, so we'll see what sort of response develops. This blog itself has just been a place for me to share my thoughts, and it does get a few dozen hits a day now, but nothing I would consider a great internet success, not by a long shot. I hope some people have found enjoyment and value in my blog, and perhaps if more people knew about it there would be more people that did find value in it.

I developed Bitphoria on my own time, while being a full-time stay-at-home Dad and running an Etsy business with my wife Heidi. It's a project I've always wanted to do, that I've attempted many times for the past 20 years, and life always seemed to get in the way. It was a matter of time before I finally made something.

Bitphoria's future is in the hands of the people after today. Once it's out there I'll probably stop working on it altogether unless it starts developing some kind of following or fanbase and I begin receiving feedback. At this point, it will serve as a great portfolio piece that demonstrates how well-rehearsed I am with all aspects of game development, from graphics programming, to networking programming, procedural techniques, and everything else in-between. This is just what I could do by myself in a limited amount of time, and I could do a lot, because I always dreamed to.

Bitphoria avoids issues like asset management and art pipelines, because I didn't plan on having artists, I planned on the players being the artists, almost in the same way that Quake and Half-Life were made popular by Team Fortress and Counter-Strike respectively. It wasn't the base game that made the game famous so much as it was the creativity of the masses. I'm counting on this, somewhat, with Bitphoria, and the fact that people like to make stuff. Bitphoria is meant to serve as a platform for people to create and share their creations, by abstracting things in a highly simple fashion that is easily accessible through a simple script-based construct.

Bitphoria's initialization function.

My goal was to have three separate games for players to play that were somewhat fleshed out. I will probably flesh them out in time, but I spent more time in the engine code than I had thought I would, so this first release will only really feature the deathmatch game, and the two barely-started CTF and instakill games that are far from complete. Fortunately every functionality of the scripting system is utilized by these games, for I had to test each one while developing it, so they appear somewhere in at least one of the three games' scripts. Hopefully this, in combination with the scripting manual I toiled to produce, will allow someone to start making something more inspired than the default games. The capabilities required to make a great game is there, that's a promise.

The master server will be running once I upload and link the release. I haven't fully tested it yet, so if you're one of the first people to download and playtest with a friend, please let me know if you encounter any issues immediately, so I can rectify them as quickly as possible and get something that people can fully dive into without having to worry about being able to connect with other players.

This is going to be a sort of Wild-West time if Bitphoria picks up and people start taking interest. There will probably be bugs and simple tricks to take advantage of the game, perhaps malicious server-crashing bugs, etc. that will be discovered and exploited. If these are found I will solve them just like everything else throughout the game's development, and they will only be found if people are actively trying to enjoy it. If people want more from Bitphoria, I will work to provide it, and it will be a process but we can get it there. I've been developing Bitphoria in a virtual vacuum, without much outside influence or suggestion, aside from the few comments coming from my long-time friend Paul Hindt. Other than that, this is the first time Bitphoria will see the light of day. This is going to be the worst Bitphoria release yet, and better ones are to come if enough people are interested.

If the game is DOA and nobody takes interest, I will eventually release the engine's source code as well, because I feel it is important for people to have resources to gain inspiration, insight, and ideas from. I took a lot of inspiration from the Quake engine, and the original Cube engine, insofar as some of the conventions for game logic are concerned.

Following in the same vein, Linux and MacOS ports will not be hard to produce being that the game runs almost entirely ontop of SDL2, but I don't plan on doing the necessary steps to releasing ports unless a demand arises. The only platform-specific code involved in the engine, as a matter of fact, is the code that lists all of the games in the games folder. There is no platform-independent method for listing the files in a directory so I wrote a simple command-line that performs a 'dir' command and dumps the result into a temp file that is loaded and the names of the game files are then extracted from. Other than that everything is occurring through SDL, so it shouldn't take very much time to compile ports.

All-in-all this release could have happened sooner, but I didn't want to have an Alpha release that lacked many features from the final product. At least at this point they are present and accounted for. There are maybe two or three little things I'd still like to add in, but at this point the project needs to get into the hands of the public so we can see what happens with it and where it should go next, if it is something that's bound to go anywhere at all.

Ultimately, if Bitphoria becomes somewhat popular, I will be pushing for actually selling it. To mitigate piracy I will be selling online player accounts, following the Minecraft model, which will integrate with the master server and be required in order to play on servers that are listed on the master server. That's down the road, but is solidly the plan if, again, people show interest.

Bitphoria's Release Date Announcement

 I have decided to make my 30th birthday the release date for Bitphoria, which happens to be August 30th 2016. There are several things I'd like to finish, among bug-fixes and networking improvements, before the first release and I thought I'd share that list here. Whatever state Bitphoria is in on that day it will be released.

It is obviously crunch time now (a great motivator for me) so the things on my list that I'd like to have done might be cut short, but I will continue working on it well into the future beyond the release. This will manifest itself in the form of new and updated releases. The initial release itself is meant to serve further development of Bitphoria by allowing other people to finally start messing around, playing games, scripting games, and providing me with bugs and feedback about everything.

I plan on releasing Bitphoria as a sort of public beta, for people to get to know it and see what I've dumped almost two years of my life into. Maybe down the road I will sell it for a few bucks on Steam/Itch.io. Maybe I should crowdfund polishing it, because I clearly have something that's worth something to someone, somewhere, out there, and I think it has a chance at being a crowdfunding success (after all the hard work is done already).

Hardware contributions/donations are always welcome! ;) I'm currently developing Bitphoria on four different machines: two low-end laptops from a few years ago, a low-end pre-built HP desktop from the same time, and a custom-built desktop - all with integrated graphics. I did manage to borrow an nVidia GTX 680 in the custom-built desktop system that allowed me to record some footage of Bitphoria earlier on, but have since been without and could definitely use a decent GPU just for the sake of tuning Bitphoria's graphics to where high-end systems can be fully taken advantage of for hardcore PC gamers, as well as allowing me to record updated videos of what Bitphoria looks and behaves like. Recording video is actually my primary goal insofar as GPU acquisition is concerned, because without it I will have a harder time demonstrating the game. Worst-case scenario hopefully fans out there will take it upon themselves to youtube videos of Bitphoria. If nobody does that then I've failed at making something that sells itself, obviously, and that's the goal of any project of mine!

If the case is that nobody ever cares about Bitphoria, and it just gathers cobwebs and dust in a dark corner of the web (on this blog, and in a few reddit posts), never amounting to anything more than just a "portfolio piece" for me to acquire a dead-end soul-crushing software engineer job, then at that point I will just release the code in its entirety for everyone to tinker with and learn from. At any rate, the code will ultimately be released eventually. The 'when' of that is still up in the air, and probably will be for at least another year. But if I can earn a living for my family via my lifetime hobby then I'm certainly going to try before giving it all away. Over two decades of programming experience has gone into this project, and there are even things that I learned along the way while developing it that I'd like to invest into a new game engine project, but those are things that I'm just going to hang onto until I feel that this project is 'done', through-and-through, which includes promoting it to a respectable degree that hopefully provides it with enough exposure to ascertain as to whether or not it is something that there is interest in.

As far as my pre-release todo-list is concerned I believe that setting up a master server for people to find each-others' games is imperative, otherwise the whole project is pretty pointless if people can only start a game server, run around by themselves, and then quit out and never play it again. Scripting features and functionality seem less consequential and could be added in along the way at a later time after the initial release, but the existing setup is rather competent. Finishing the scripting documentation also remains a top-priority issue due to the fact that I wish for people to be able to start playing around with the engine itself to see what they can come up with within the creative sandbox that it represents. It has its quirks and nuanced requirements insofar as game performance are concerned (graphically, physics-wise, and networking) which is the case with any game engine out there. However, I would like to point out that it takes no game-development know-how or modding experience to make something out of, or with Bitphoria. Anybody should be able to simply open up the script files that comprise the default games included with Bitphoria and start surfing the documentation to figure out how it all comes together.

Here's my list of things left to do for Bitphoria before releasing it that I'm currently focusing on for the next few weeks:


Master Server: Write and launch a master server to run here from my home to allow players to be able to start and find/join eachothers' games. Along with this I'd prefer to invest in a domain name that points to the master server (my house IP) for the in-game server browser to download the server list from. This would actually kill two birds with one stone. Firstly, it would eliminate the learning curve of PHP and MySQL that I'd need to traverse if I were to create an HTTP master server. I *do* have enough experience with both to make it happen but I'm not competent or well-rehearsed enough to simply knock it out within a day or two - and it would require that I implement HTTP request functionality into Bitphoria, be it by hand or integrating CURL/libCURL. Secondly, running a custom-coded master server from home would allow me to easily implement a NAT-punchthrough handshake protocol to allow anybody to start a game without being required to deal with their router/firewall and port-forward. Conversely, anyone else would also be able to join any game regardless of whether or not they themselves are also behind a router/firewall. This functionality requires that the master server notify game servers when someone is trying to join them, and from what IP/port, allowing the game server to go ahead and send a 'trailblazing' packet to the client player for the sake of tunneling through the NAT and have it route packets from that client player's address to the game server. To have a console application running in the background on my desktop, written in C, using winsock or SDL_net, that would be easy to manage would be much simpler and cheaper than any remote/online option I've come across so far. If at some point there's too much traffic for my home connection I'd then move the master server program to a dedicated virtual host and simply point the domain name at that, and everything will just continue working for everyone without any changes for end-users.


Network Buffering: Implement a network buffering system to, for one, allow for the simulation of latency and its fluctuation for testing/tuning purposes. So far I've only been able to generate repulsive/gross/erratic network behavior when my daughter watches Youtube/Netflix on her machine while I have two machines sharing a Bitphoria game over our wireless LAN. Also, in spite of my efforts to fight network update jitter using extrapolation when an update packet arrives later than intended, it would seem that Gaffer's strategy (gafferongames.com) of simply buffering network updates long enough to encompass most network jitter and then subsequently emitting them to the engine internals at the interval they were intended to arrive at would be vastly more effective in its precision and lack of interpolated correction. Buffering network packets as such would also allow me to simulate internet conditions locally without having to track down willing testers (I'm not really a 'people-person', and I have no more computer friends left) and fine-tune everything for what I like to think of as the 'fringe-market' - people who don't have high-end gaming systems (a netbook) or fiber-optic connections. I'm of the mind to release a game that looks prettier the better the setup, but also is completely performant on less ideal setups. Why focus on one area of the market if you can focus on the entire market?

Scripting System Documentation: Finish the scripting system documentation, which would include indications as to where inside of the the sample/default games that are packaged with the initial release that users can find examples of each script command, along with tips/tricks. Also, early on I made it a point to document everything that I script for Bitphoria because I know that people out there should be encouraged to tinker around and pull everything apart.

Artificial Intelligence: Add in simple AI functionality that allows an entity to seek out other entities and designate them as its target, which it can then follow or aim at. This would make it possible for simple zombie-type enemies that just follow players and harass them while they try to carry out other things. I'd like to include some kind of simple navmesh generation that is derived from the distance field of the world but I am thinking I am just going to literally index the distance field and use that for obstacle avoidance while entities try to pursue other ones. If a target is unreachable then it could back out following the distance field outward until the target is visible again, or a new target is found.

World Generation Modes: Add options for the style of the world generation itself. Right now it's a fixed algorithm and starting a game server entails selecting a random seed and then a vertical-scale which is forwarded to clients so they can then generate the same world themselves and play. The world is generated as a 128^3 volume and there's a lot more that could be done with it than just leaving one algorithm in there for people to experience.

Physics Attachment: Entity attachment which allows for an entity to literally attach itself to another entity and inherit its position/motion, with or without an offset that is oriented with the entity being attached to. This could be used for CTF games or power-up modes that want to display some kind of visible effect.


These are more-or-less listed in order of priority. What actually happens by the release date is still completely variable, these are just my intentions and goals, and it's hard to say what exactly will occur as I pursue each bullet point.

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.

World Representation

It's been a while since my last post, a lot of brain storming (as opposed to actual coding) has been going on. I've been exploring world generation and possible data structures for representing the world in memory. This all required that I make some important defining decisions about the world.

At the time of this writing, I have yet to decide on making the world dynamic (modifiable). This is primarily because of the cost of updating the world, finding a balance between CPU/GPU loads, and doing so over the network between the game server and clients. Another issue involves when a client joins a server, they must download the current state of the world from the server as it exists after any modification that has occurred. There are tricks and techniques for minimizing this data flow, so that the entire world volume doesn't need to be uploaded to each connecting client. Right now this is not a priority, or even a necessary feature for what I am trying to accomplish with this current project. This could change!

Being that the world is volumetric (voxels) it was clear that there needed to be a data structure to hold the volume in memory, not just for rendering, but also physical interactions with entities. Following with Revolude's original design - the world would be procedurally generated (as opposed to loaded) when a game was started, or joined. This data structure would require that it could perform efficient read/write access.

I examined the possibilities of a few different algorithms and data structures for dealing with volumetric data. A lot of algorithms for storing compressed volume data rely on the fact that the data represents direct visual data, like the pixels of an image, in the form of red/green/blue/alpha color channels. This allows for all sorts of neat 'lossy' image-compression style tricks to be used, which forsake exact reproduction of the original compressed data in exchange for smaller size. For applications where the volumetric data represents relatively finely detailed data, these algorithms are great.

For my project the worlds are not that large, or that finely detailed. Voxel size is on par with games like Minecraft and Infiniminer. The primary difference from these games is that voxels will not be cubes. Voxels are also represented using a single byte to store a material-type value, allowing for up to 255 different materials (material zero is empty space). Worlds are also not intended to be infinite. Instead of having worlds extend infinitely through procedural means, they will be a finite size, and wrap around seamlessly. There will be no edge to the map, nor will it go on forever into places that nobody will ever go.

I'm still settling on a specific world size. With the sizes I'm considering, storing the raw voxel data becomes feasible, without the use of any sort of sparse data structure. For example, with a world size of 1024x1024x256 the size of the world data is then 256 megabytes. Each horizontal slice of the world is one megabyte. The only qualm I have with just leaving the data sitting in memory, when virtually every machine capable of running the game has enough memory, is cache coherency. The larger the volume, the further apart in memory two neighboring voxels could lie. This is not good for performance!

It's arguable that using flat storage for a finite volume won't produce a significant slow-down when the volume is queried for things like collision detection and rendering. Personally, I just don't want to be using more memory than I need to, especially if a byproduct of reducing the size is gained speed. Above all else, I love the challenge implementing a sparse data structure ;)

The first obvious option on everyone's mind is a sparse voxel octree. This is a wonderful structure, but can become computationally expensive to iterate as it deepens. One strategy I had a while ago to 'enhance' the octree is to allow each node to have more than 8 children. Instead of 2x2x2, it could be 4x4x4, for 64 child nodes. This would allow an octree with a dimension of 1024 (gigavoxel) and 10 tree levels to only have 5 levels to iterate through from root to leaf. The issue here is that there would be excessive 'empty' child nodes all over a volume. This would be the price for faster iteration.

Another strategy, one which I became quite fond of since my last post, is to store volumes as run-length encoded columns. This is especially attractive because it effectively reduces a volume into a few 2D images, and would work extremely well where voxels represent a limited number of materials (as opposed to highly variable 32-bit RGBA values). Many areas of the volume would be one or two column 'segments'. This approach was almost the one that I finally settled with, but I was having implementation indecision issues, trying to find a 'sweet spot' balance between speed, size, and simplicity. My obsessiveness with finding the perfect solution became a hindrance to progress.

Ultimately, this lead me to fall back on an older idea, which is really an amalgam of a few ideas. At the coarsest level, I represent a volume using a sort of hash-table. This is just a flat array that divides the world up into fixed size 'chunks'. The trick here, then, is to use a sparse voxel octree to represent the contents of each chunk. Using some efficient design, a chunk that is entirely one material (including empty) is stored as four bytes. The rest of the chunks, which I call 'boundary' chunks, are stored using a variable number of octree nodes. Each one has its own pool of octree nodes from which it builds the sparse octree representing the organization of voxels and their material indices. This node pool starts out small, and is reallocated as needed by doubling its size each time it fills up.

Currently I am working with chunks of 32x32x32, which is 32768, or 32k, of voxels. This seems like a nice round number, because I can fit an octree node index into 15-bits (16th bit flags leaf-node status). Now, in an octree, if each voxel could be a different material (32k different materials) then there would be an overflow because inner nodes would require more address space for 4680 nodes, but I am willing to bet that with less than 256 possible voxel materials this 'special' case chunk will never occur. Most chunks will never even see 10k of nodes.

With chunks that are 32k voxels in size, this means that a 64-gigavoxel volume (4096^3) would consist of 32k chunks. The flat array of chunks for a 64-gigavoxel volume would be less than a megabyte. The total size of the chunks themselves could vary, but would average less than 100 megabytes. This is really great for 64 gigavoxels. Now, I'm not going to be representing a world that is 64 gigavoxels, I don't think. I'm thinking smaller, because the goal here is a game that is more of a multiplayer online battle arena than some sort of vast expanse for an MMORPG.

This is actually how all volumes will be represented in memory, in terms of materials, and out of chunks. Some game objects will be displayed using volumes, some using other graphical techniques. This is a global 'voxel' solution.


Links of interest:
Visualization of Large RLE-Encoded Voxel Volumes
An Analysis of Minecraft-like Engines
Ken Silverman's Voxlap Page

Procedural Content, and Aiming Too High

At the outset of this project my initial aim was to allow full control over the entirety of a scene, as far as level design and editing is concerned. After sitting down and carefully considering potential routes of implementing functionality to allow users to create custom worlds and other assets, I've come to the decision that the work required to provide an interface for editing such assets will only hinder my ability to actually complete this project.

With my previous project, Revolude, it seemed rather slick to procedurally generate the world when the game starts. Whoever was responsible for launching the game server had access to various sliders and coloration options they could play with to customize the 'style' of the world that people would experience while playing in the game they are hosting.

the "start game" menu screen from my previous project 'Revolude'

This functionality alone was simple enough to implement, and was (to my mind) the happy medium between designing your own level, and choosing an existing one from a list when launching a game. A world seed value (not exposed via the UI menu screen) along with all of the server's world-generation parameters are gathered up and sent off to connecting clients who are joining the game, so that they can generate their own local copy of the entire world for rendering and collision detection prediction.

One of the primary advantages to this approach is that every server can be running a completely unique world without clients being required to download or store any map geometry from the server. The only thing transferred are some parameters for the procedural generation of the world. This is, in my mind, the great advantage to using procedural methods.

What with my non-existent experience concerning floating point determinism, I did run into some serious bugs where trees would sometimes be planted, or not, in specific 'close call' spots that seemed too steep to some CPUs, and not too steep on others. This resulted in worlds that were somehow slightly different on two machines that were playing in the same server. These sorts of issues are resolvable, especially if you are aware of them before writing any code in the first place.

Nonetheless, I really like the idea of providing a user with procedural tools to create a base scene volume, from which they could construct their vision by hand. These worlds would be saved, in compressed form, to disk, and would be uploaded to connecting clients. I envisioned a full built-in editor for flying around sculpting worlds, placing entities and detail props, etc.. Along with a procedural materials editor, an entity voxel volume editor, and possibly a synthesized sound editor (Revolude actually featured console-scripted sound synthesis, with enveloping and a few effects, but required hand-editing sound parameters in an external text editor and alt-tabbing back and forth to listen to the resulting sound).

It just seems like too much work for what I'm trying to accomplish. What I would rather do is give a preview to a user that is starting a game. This would just be a more advanced version of what Revolude does. Storing to disk, and transmitting actual compressed volume data to clients just sounds too expensive, and defeats what I initially hoped to accomplish by utilizing procedural methods in the first place.

Voxel Polygonization and Game Engines

 Hi, and welcome to my blog. I wanted to have a place online for the world to see what I am doing, something to keep me focused. Right now I am currently polishing an algorithm I had conceived a few years ago for generating a triangular mesh from a voxel volume. From the algorithm's inception I've understood what I wanted it to output. It wasn't until recently whilst starting on my (latest) game engine project that I finally had the insight to help me solve writing the algorithm.

 I was trying to nail down what sort of world I wanted my current game project to present to players. In my previous game engine project, Revolude, the terrain was a simple heightmap and a static ROAM type algorithm was used to perform a simple polygon reduction before dumping each terrain chunk to a display list consisting of triangle strips and fans.

Revolude, with some pseudo-trees and buildings, and some missiles hitting the ground.

 I was just about to opt for creating a much more involved version of this same type of terrain when I had a stroke of ingenuity. The algorithm is logically very simple, and produces the equivalent output of what I would like to call the dual of a cubrille mesh. In other words, it takes a Minecraft-esque type mesh and converts every face into a single point, and each point into a triangle. The dual of a cube is an octahedron, and the algorithm I wanted to create essentially produced an octahedral mesh from a voxel volume.

A cube, and its 'dual' - an octahedron. Notice how each of the six cube corners becomes a single triangle, and each cube face is collapsed into its center point.

From an outside standpoint, this really seems very simple to do. One approach could be to first generate a simple boxy cube mesh, and then try to brute force convert it into its dual, an octahedral mesh. This became an appealing option after only a while, but I only approach problems with the intent of devising a novel solution, so that was out of the question.

Ideally, I was hoping to create an algorithm in some way similar to marching cubes - where each cube was inspected along with its neighbors to produce geometry. Something that achieved the desired output through such an immediate method was the goal. This approach, however, became much more involved than I had initially believed it could be.

The end product works in multiple passes, on the volume as a whole. The first pass examines 8 voxels at a time, determining whether vertices should be placed, and where. The second pass connects vertices to form edges. Edges can only exist between vertices where the dot product of their normals is greater than or equal to zero. So, vertices must either be facing in the same direction, or up to 90 degrees apart. The third pass involves detecting triangles formed by edges. This is done by searching for 'complement' edges for each vertex, where two edges connected to the vertex are connected to a third edge.

The last operation involves detecting all the left-over quads formed by edges, by doing a similar search to the triangle detecting pass. Instead of looking at the edges connected to a point, we look at the edges connected to an edge, and see if there is an opposite edge on the ends of its connected edges.

These operations, naively implemented, can be extremely slow. Fortunately, it is not too expensive to store extra connectivity information which is used to quickly search edges, vertices, and triangles for related geometry. The end product can then be reduced to simple vertex information and vertex indices for triangles.

Here is a quick video of the algorithm at work with an evolving volume. Forgive the choppiness of the video, my little netbook isn't very awesome. The slowest part of this demo is generating the volume itself. The next step will be to utilize a compressed data structure as the data source, as opposed to raw volume data.