So I may be a bit late to this party, but I've decided to build a minecraft-like game. I'm not 100% about the exact format, but my thinking is it'll be an FPS shooting with destructible terrain. I envisage that at the end of a round, you'll just be sitting in a crater on top of a pile of bodies... anyway, I've started off with a much simpler problem: how do you turn a 3D voxel array into an efficient mesh?

To begin with, I've started with a very simple data structure, just a single bit for "solid" vs. "empty". I'm working with a 32x32x32 chunk of voxels. I'll expand on that later to support textures and different materials and so on, but I think the general principle is the same.

The first version of my algorithm was very simple: just render a 6-sided cube for each solid voxel:

This is obviously horribly inefficient (it's actually closer to 300k vertices, despite what the display says there: it's doubled because the wireframe causes the vertices to be counted twice -- still, 300k is insane!)

This algorithm is so dumb, I'm not even going to bother posting it. Now, the second version of my alorithm was actually a very minor modification. For each face of each cube, it would look at the neighboring voxel. If the neighbour had the same value (i.e. if they were both solid), it would simply skip that face. The results look much nicer, even with the noise of the wireframe:

OK, so this ends up being about 17k vertices (without the wireframe) which seems pretty reasonable. But you can see in this view that there's actually quite a lot of redundant quads being drawn.

I found a pretty nice algorithm from a few years ago titled "Meshing in a Minecraft game". It was a little math-y for me, so it took me a little while to figure out exactly how it's supposed to work. I prefer to think in terms of pictures. Anyway, this is the result:

Pretty neat! Down from 300k vertices to 3,000. 100x improvement! It's still not 100% optimal, but it's close enough that I don't really care.

OK, so how does it work? The first step is sweeping through the volume one axis at a time. I actually sweep through each axis twice, once for each direction. Then, for each sweep, you generate a bunch of "slices", and populate the slices with quads for each side of the cube on that slice. Here's an example of what you see after I've sweeped through the Y axis only and just rendered all of the quads:

Now, for each slice we end up with a 2D array of the quads and all we want to do is make as few larger quads as possible. Here's a little animation to show how I'm doing it:

As you can see, we just iterate through the slice, find the first quad and then try to expand it to be as big as possible (going as far to the left as we can, then taking it as far down as we can).

As I said, it's not the most efficient algorithm (as in, it doesn't generate the absolute most optimal mesh), but it's pretty easy to understand and it gets us pretty far along. I'm pretty happy with the result overall!

A lot has happened in the last month. Here's the latest gameplay video:

Here's a quick rundown of the changes:

• Particle effects for entities. You can see this in the blacksmith smoke and fire towards the end.
• Clothes/armour (though only clothes implemented for now, armour is the same: just a different sub-model). This is actually somewhat tricky, the way it works is, we have a 'base' mesh that contains a skeleton and the animations, then we have additional meshes for feet, hands, torso, legs and head that attach to that skeleton. So I can replace each of those components idependently of the others.
• The inventory system actually lets you swap items out and it updates the preview at the same time.

So that's it for now. This month I plan to work on dungeons and dungeon-generator.

In this post, I'm going to describe the client/server "architecture" of my as-yet unnamed RPG, such as it is. The basic premise of the game is that it's an open-world, browser-based role-playing game. My expectation is that there could be ~100 players online at a time, and the game should be able to reasonably handle that on a single server. Currently I have no plans for how to handle expanding the game past a single server, apart from some vague ideas about splitting the world geographically.

As mentioned in my last post, the game runs in a browser, so the client is JavaScript. I've chosen to use Go for the server, mainly because I wanted to try something a bit different, and I like Go's concurrency model. So why not?

Overview

With that said, here's a picture of how the server looks today:

From top-to-bottom we have:

1. The actual game clients, running JavaScript in a browser. These connect via a persistent WebSocket to the server.
2. In the server's main process, one "player handler" exists for each connected player. The player handler keeps a reference to the player's entity in the world.
3. The "world" is basically a collection of entities and some supporting data structures (e.g. pathing objects for constructing paths, etc) and a bunch of goroutines acting on those entities.
4. The "long-term storage" (or just "Store" as it's called in the code) is where we store all the things which need to persist between server restarts (things like player stats, inventory, quest status and so on)
5. The "sectors" collection is a bunch of static files which describe a segment of the world. These are 64x64 grids that contain information about the terrain, the entities that should be initially created on the terrain and so on.

Entities

Entities are simply a collection of "components". A component provides the basic functionality of the entities, and can be combined to form any kind of complex entity we like. The components used on the server and client are not always the same (for example, the "Model" component is ignored on the server, but it's obviously very important on the client!)

Some of the components we have defined are described below.

• Position - This contains the coordinates of the entity. It also handles things like "follow terrain" which causes an entity to "stick" to the terrain, or allows it to float above the terrain.
• Movement - For entities which can move, this handles finding paths (on the server) and following paths (on the client).
• Model - On the client, this is used to control the model that the entity is displayed as. Things like animations are controlled by this component as well.
• Mob - This component controls the "AI" of mobs. When not attacking a player, a mob will wander around at random. When attacked by a player, the mob will attempt to fight back.
• Stats - This component manages the entity's stats (health, strength, etc).
• Spawner - This component is used by entities on the server to spawn other entities. It's usually invisible and lets you control things like "spawn X kind of entity, making sure there's never more than N entities active at once).

Sectors

The world is divided up in 64x64 grids, called "sectors". The sectors are all adjacent to each other, and the client will load up to four sectors to ensure that the world appears seemless as you move around. On the server, sectors aren't really used at runtime, except that the data within them is loaded on demand the first time a client enters that sector.

For example, the first time a player enters a particuar sector, the server will load all the data for that server in to memory (for example, there is an entities.json file which contains definitions for all of the entities which exist in that sector (for example, this will describe environmental objects -- trees, rocks etc, as well as things like spawners and NPCs to populate the world with life.

Long term storage

Long-term storage (or just the "Store") is used to store all the data which needs to persist over server restarts. Things like player stats, inventory, quest status and so on. Every time one of these things is modified in the world, the store is automatically and immediately updated as well.

It's important to note that entities in the game are not nessecarily stored in the persistent store. We generally assume that if the server restarts, then when the sector is reloaded, all the entities we care about will be re-created from the sector data.

Client/server protocol

As mentioned above, the client maintains a persistent WebSocket connection to the server. If the WebSocket connection drops out, the client pops up a "waiting to reconnect" dialog and tries to re-connect.

The above shows Chrome's debug tool showing the frames sent over the WebServer to the server (and the data received back from it). Data is encoded using JSON (for now, I might switch to a binary format if size/bandwidth becomes a problem).

Basically, on the server there is a player handler which handles decoding the packets from the client. It maintains a reference to the player's entity in the "world", and whenever a packet instructs it to do something, the entity within the world is notified. For example, when the player clicks on another entity, the player handler will issue an "activate" event on the entity you clicked on. Depending on whether you clicked an NPC or a mob, the NPC might send a "show quest page" packet back to the client. Or if it's a mob, an "entity attacked" packet might be sent to all players within visual range.

Conclusion

That's a basic overview of the architecture of the game, such as it is today.

Obviously this is all quite up in the air, and I haven't really arrived here through considered, careful thought, but more through an organic process of evolution.

Here's the latest update of where I'm at with my still as-yet-unnamed RPG. First, a video:

As you can see, there's a bunch of new features. In no particular order:

• Chat works and looks much nicer. You can actually see who's chatting with you, for example.
• Quest management: when you start a quest, an entry gets added to the "Quests" menu and you can see what tasks you need to do.
• Inventory management: you can open up your inventory and see what you've got equipped.

This post provides a bit of an overview of my plans for my as-yet unnamed RPG. One of the biggest lessons I learned with my previous game (which I talked a bit about here) is that players want to interact. The in-game chat was pretty much an afterthought in my previous game (in fact, it was the very last feature I added before going to "alpha"). Most of the work I did post-release was community-based features -- an alliance system, one-on-one and group private chats, and so on.

So I wanted to make sure my new game supported a vibrant community right from the beginning. Also, I was a little tired of the limitations of working with a phone, so I wanted something that ran on a PC. But more than that, I wanted something that was cross-platform (I personally use a Mac laptop and a Linux workstation, so it needed to run on those platforms as well as Windows, of course). Because I'm a masochist, I decided make the game browser-based.

The first iteration I was using a <canvas> directly and drawing 2D sprites. It worked pretty well, but performance was generally pretty horrible -- and that was with practically nothing on the screen! I actually got pretty far with that 2D engine, including multiple players, chat, animations and so on. Here's a video:

That video didn't have pathfinding, but that was also added before I decided that the performance just wasn't there. My plan was going to be to use webgl to speed up the 2D engine, but as I was coding, this happened

So I made it fully 3D with three.js as the backend renderer. In fact it's actually not that hard to get webgl up and running -- the hardest part, at least for me, was content. The initial "rewrite" was still talking to the same backend server, so it still supported all those wonderful multiplayer features, but I had an MD2 model (from Quake) as my main character, and some procedurally generated tree I found somewhere as decoration.

The most interesting thing about the rewrite is the terrain. I found this cool article on Gamasutra and implemented it as a GLSL shader in three.js.

Then I taught myself how to use blender to create some basic 3D objects and animations. All the content in the current gameplay video was made by me in blender. Yay!

So that's where we are today. I've have a few ideas for the basic premise behind the game and also some information on how the game has been "architectured" (I put it in quotes because it's much more organically developed than architectured...)