User interfaces and flightless birds

There are several ways to build a graphical user interface.

The oldest one is absolute positioning. For every button, label, etc., you specify the position and the size yourself (usually in pixels). Anybody who has ever used MFC knows why this is a bad idea. If you want a resizable window, you'll have to catch the window events yourself, and calculate/set the position and size for each widget. Translations usually break the layout; your best bet would be to make separate dialogs for every language.

A very popular method is the box/packing/struts/glue/springs model. It might even have a proper technical name. You define a layout using horizontal and vertical containers, anchor points, springs, fixed spacings, and the toolkit does the layout for you. Much better already!

Another method is the constraints-based layout, and it has been slowly gaining popularity. It is not new; the first Lisp implementations appeared in the early 90s. But for example, it is the recommended way to define user interfaces in Cocoa since OS X Lion, and Adobe also uses it in their Adam and Eve framework. In a constraint, you can say, "okay, I want this button left-aligned with this widget, and somewhere below the title", or "I want this field to be just as wide as that one, and preferably somewhere between 40 and 250". The widgets are then laid out according to your wish list.

UI requirements for Hexahedra

For the readers who just tuned in: in Hexahedra, all mods/plugins run on the server. This means we have the following requirements for the in-game user interface:

• Network transparency.
• Has to be able to adapt to different resolutions and screen layouts.
• Good localization support. Not just translations to other languages, but also adapting to right-to-left languages.
• Support for client-side themes.
• Must be easy to define.

Given all that, the constraints-based method sounds pretty good.

The first thing I need is something that eats constraints and poops a widget layout. Turns out such a beast is called a linear constraint solver. There are several, such as Indigo, Ultraviolet, and LP-solve. But the best candidate for the task at hand is Cassowary.

Cassowary hasn't been updated in a decade. It doesn't build on my system without tweaking, it has a bug or two, valgrind reports memory leaks, and defining constraints with it is pretty awkward. Besides, I really want to know how it works in detail.

You can guess where this is heading.

Rhea

So yeah. Rhea. It still needs to be documented and packaged properly, but it's definitely in a usable state.

The user interface library that is sitting on top of Rhea is still under heavy development, but I can show you where it's headed. Let's set up a frame with three text labels in it, and use Rhea to define and solve the constraints:

  ui::theme t; 

  ui::label a (t, L"AAA"), b (t, L"BBBBBBBBBB"), c (t, L"CCCCC");

  ui::frame box;

  rhea::simplex_solver s;

  s.add_constraints(

  {

      box.top == 0,       // Keep the frame's corner at 0,0

      box.left == 0,

      a.top == box.top,   // Align 'a' in the top left corner

      a.left == box.left,

      b.top == box.top,   // Align 'b' along the top

      b.left >= a.right,  // Make sure b is right of a

      // Make sure b is horizontally centered, but make it a

      // weak constraint.  If there's not enough room, b will

      // be placed as close to the center as possible, but always

      // to the right of a (the stronger constraint).

      //

      // Note that 'h_center' is actually a linear expression;

      // the frame class defines it (quite literally) as

      //  "left / 2 + right / 2".

      //

      {b.h_center == box.h_center, rhea::strength::weak()},

      

      b.right <= box.right,   // Make sure b still fits

      c.top >= a.bottom,      // Place 'c' somewhere below 'a'

      c.bottom <= box.bottom, // Make sure it's inside the frame

      c.left == box.left,     // Keep it left-aligned

      c.right <= box.right

  });

  // And yes that is actually C++.

Now that the user interface is defined, the labels will ask the theme for a preferred size (based on the font and the text), and we can tell the solver what we want. In this example, the theme simply assumes every character in a text label is a 20x20 square. Now, let's say we want the frame to be 200 x 150:

  s.add_edit_var(box.width).add_edit_var(box.height);

  s.begin_edit();

  s.suggest_value(box.width, 200);

  s.suggest_value(box.height, 150);

  s.end_edit();

"Edit variables" are special variables in the Cassowary algorithm. A new value can be suggested for them, and the existing constraints are re-solved with a minimum of overhead. Speed is important to keep the UI feel responsive. The widgets now have the following dimensions:  (shown [left, top ; right, bottom](width x height) .)

    box : [0,0;220,150](220x150)

    a : [0,0;60,20](60x20)

    b : [60,0;220,20](160x20)

    c : [0,130;100,150](100x20)

We suggested a width of 200; the solver decided to make it 20 wider, so it ended up 220 x 150 instead. There was one weak constraint it could drop: 'b' is not centered inside the box. But given all the other requirements, the box just couldn't get any smaller than 220. (That's pretty neat: I never actually had to specify this number anywhere, the solver figured it out for me.)

What if we suggest a width of 600 instead?

    box : [0,0;600,150](600x150)

    a : [0,0;60,20](60x20)

    b : [220,0;380,20](160x20)

    c : [0,20;100,40](100x20)

The 'B' label now has enough breathing space to be centered properly.

So we have a resizable window, where an element is centered, unless it bumps into another. The window has a proper minimum size. The layout will also adjust automatically whenever the labels are translated to another language, or a different theme is used. Not bad for 13 really short lines of c++.

Up next

There have been a few other big changes in Hexahedra, so the next blog post will probably be about ENet (the new UDP network protocol) or IQM (the new model format). But UI Part 2 will look at the behavior side of the widgets, hopefully with some actual video footage.

User interface : the hotbar

The hotbar is a staple of game interfaces, and no Minecraft clone can do without it. Players can drag items, blocks, spells, or other actions to one of its slots for easy access.

After shamelessly grabbing some graphics from Dokucraft, this is what it looks like in Hexahedra:

In Minecraft, it's a single bitmap. In Hexahedra, you need to cut  it into smaller pieces: a left "cap" (the rounded corner), an empty slot, a separator (the grey dot between the slots), something to indicate the active selection (the triangles at the top and bottom), and a right cap.

It might sound complicated, but it's for a good reason. Everything is controlled server-side, so it needs to be dynamic. Using Lua scripts, the server can at any given moment change the size and layout of the hotbar. The example you see here was generated with:

on_login(function(plr)

    plr.hotbar_size = 12

    plr:hotbar_set(0, hotbar_slot(1, "cobblestone"))

    plr:hotbar_set(1, hotbar_slot(2, "firstaidkit"))

...

    plr:hotbar_set(9, hotbar_slot(1, "snow"))

    plr:hotbar_set(10, hotbar_slot(1, "glass"))

end)

The function hotbar_set takes a position, and a slot object. The first parameter of the slot determines its type. The following types are available:

• Empty
• Showing a material, either as a block turned 30 degrees, or as a custom 3D model (such as the fence post in slot 7 in the image)
• Showing an item
• Showing a custom icon that represents an action (for example, casting a spell)
• A section separator, for splitting the hotbar in two or more sections

Also, a slot can have one or more extras:

• A colored crawl bar (item damage, gun ammo, ...)
• A number
• A small badge in the lower right corner (powerups, enchantments)
• A cooldown timer
• A disabled mode
• A locked mode (player can't drag it anywhere, or drag another item onto the slot)
• An action mode (slot cannot be the current selection, but the player can trigger its action with a keypress)

Sometimes, a material can't be represented by its 3-D model. For example, a door consists of two blocks, each with its own material. In this case, the programmer should provide an item that represents it with a proper icon, and hook up the appropriate callbacks to this item.

Being able to control the hotbar from the server is great. Yes, you can make it behave just like in Minecraft. But you could also replace broken tools automatically from the player's inventory. For the infinite blackboard game, I just set it to one icon that shows the player's crayon color. For the tower defense game, the hotbar slowly grows as the player unlocks different tower types. Perhaps you need a RPG setup with separate attacks, spells, and items, with the number of slots depending on the character's level? 

DIY fences

Behold! A fence!

Now, fences aren't all that exciting. Minecraft's had them for almost two years now. No, the cool bit is how they were scripted.

The 3-D model

Unlike items and mobs, custom block models cannot be imported from just any Blender or Collada file. To keep things manageable, they are essentially a 16x16x16 chunk scaled down to the size of a block. You define them as a list of boxes, where all coordinates are integers, limited from 0 to 16. Every face of every box can be textured individually, the same way a normal block can.

For example, here's a snippet of the Lua script that defines the materials:

define_material({ name = "fence.0000",

            on_place = place_fence, on_remove = remove_fence,

            custom_model = { { 7, 7, 0,   9, 9, 15,   "fence" } } })

define_material({ name = "fence.000E",

            on_remove = remove_fence,

            custom_model = { { 7, 7, 0,    9, 9, 15,  "fence" }, 

                             { 10, 8, 10,  15, 8, 12, "bark" } } })

A fence can connect to its neighbors in any combination of the four cardinal directions, so we need 16 different models in total. You're free to pick any name you like, but I've used a naming system here that shows in which directions the fence extends. "Fence.0000" is just a post, a single box with the 'fence' texture. "Fence.000E" extends to the east, and consists of the same post, and another box with the much darker 'bark' texture. We also need "Fence.00W0", "Fence.00WE", "Fence.0N00", and so on.

(Ordering the models by binary counting will come in handy later.)

Examples of fence models

All this info is sent to the client on login. So if you join a server, there's no need to install anything, you automatically get to see whatever cool custom blocks they designed for their map.

This is nice for static decoration, but if you want to give the player the opportunity to build his or her own fences, there's a little more scripting involved.

(Note: the idea for custom block models isn't quite new, Minetest recently added "nodeboxes" that can do the same thing.)

Scripting the behavior

Every fence material gets a number. We'll say 'fence.0000' is material number 100, and the others are numbered incrementally. If the player places a fence, the value in the chunk's array gets changed from 0 (air) to 100, and a fence post appears. So far so good, but the second fence placed right next to it also looks like a post. When this happens, we want to connect the two. So the first one should change from 100 to 104 ('fence.0N00'), and the other to 108 ('fence.S000').

You might have noticed we had already provided an 'on_place' and 'on_remove' callback for the fence materials. The first one, place_fence, looks like this:


local function is_fence(a, b)
  return b >= a and b < (a + 16)
end

local function place_fence(p, id)
  local e = p + vec(1, 0, 0)
  local n = p + vec(0, 1, 0)
  local w = p + vec(-1, 0, 0)
  local s = p + vec(0, -1, 0)
  
  if (is_fence(id, get_block(e))) then
    id = id + 1
    change_block(e, get_block(e) + 2)
  end
  if (is_fence(id, get_block(w))) then
    id = id + 2
    change_block(w, get_block(w) + 1)
  end    
  if (is_fence(id, get_block(n))) then
    id = id + 4
    change_block(n, get_block(n) + 8)
  end  
  if (is_fence(id, get_block(s))) then
    id = id + 8
    change_block(s, get_block(s) + 4)    
  end
  
  change_block(p, id)
end

'place_fence' only gets called for "fence.0000". The parameters are the position, and the material ID (in this case, 100). We use this ID to check the four neighbors (e, w, s, and n), to see if they are fences as well. This check is rather simple; we've registered 16 materials, so they should be somewhere in the range 100 to 116.

For every fence we find, we adjust the model of that neighbor block so it connects to the one we're about to place. And of course we adjust 'id' as well, we need to connect them both ways.

Removing a fence is very similar, but instead of adding a given value for each direction, we subtract it:

local function remove_fence(p, id)

  local e = p + vec(1, 0, 0)

  local n = p + vec(0, 1, 0)

  local w = p + vec(-1, 0, 0)

  local s = p + vec(0, -1, 0)

  

  if (is_fence(id, get_block(e))) then

    change_block(e, get_block(e) - 2)

  end

  if (is_fence(id, get_block(w))) then

    change_block(w, get_block(w) - 1)

  end    

  if (is_fence(id, get_block(n))) then

    change_block(n, get_block(n) - 8)

  end  

  if (is_fence(id, get_block(s))) then

    change_block(s, get_block(s) - 4)    

  end

  

  change_block(p, 0)  

end

No need to adjust 'id', at the end we're going to place an air block there anyway.

More to come

Of course, you can build much more with this API than just fences. Doors, stairs, window shutters, pipes, ladders, wooden beams, rails, you name it. How about fences that connect to walls as well? With gates? I'll leave all that to your imagination for now, and in the next few posts I'd like to show other parts of the API, such as the user interface and items.

And my axe!

Got the brilliantly named Assimp library working, so I can now import every 3D file format known to man. I'm not a big fan of the high poly-count models seen in some other blocky games, but this axe just happened to be one of the example files, so I grabbed that one for testing.

The standard renderer that comes with the library uses direct calls. The axe model has tens of thousands of triangles, so it's a miracle I'm still getting 30 FPS. So the next step would be to look for/create a proper VBO-based renderer, and get skeletal animations working (for mobs and players).

More about voxel meshing

The 0FPS blog has a great article about meshing, that ties in nicely with my latest couple of posts here, and explains it better and in more depth than I ever could. Go check it out!

And after recording and posting that video about transparent surfaces, I've ran into cases where the sorting method does not produce the desired results. Back to the drawing board. :)

Polygon merging

Here's a screenshot in wireframe mode to show the merging in action:

In some of the large flat surfaces (grass and water) everything can be merged, and all that's left are the chunk boundaries. The polygon count is reduced by about 60% on average.

Sorting in depth

A while back (too long!) I explained how to draw a bunch of cubes, and made a nonchalant remark about how it is important to draw everything in a front-to-back (or back-to-front, for transparent polys) order. Sorting all voxels by distance every time the camera moves is not an option, so we need to think of something else.

At the chunk level

The first thing we'll do is to sort all the chunks by their Manhattan distance. Instead of calculating the distance using the Pythagorean theorem (what we usually think of as "distance", also known as Euclidean distance), it is the sum of the differences of all three ordinates. If the camera is in chunk (1,2,3) and we want to measure the distance to chunk (5,7,9), the differences in the x, y and z directions are 4, 5, and 6 respectively, and their sum is 15.

The nice thing about the Manhattan distance is that, in our voxel world, it is always a whole number. We use this number to group the chunks, one group for each distance. Group 1 has no more than 6 chunks in it, while group 2 has no more than 18. (Try to imagine how this looks in 3D and you'll see why.)

Grouping chunks by Manhattan distance

It's kind of a lazy version of a bucket sort. We only need to do this once. Whenever we want to render the scene, we traverse this data structure in order. The ordering of the individual chunks does not matter; no two chunks with the same distance  can never overlap each other from the camera's perspective. This gives us more freedom to pick a suitable data structure, e.g. a hash table.

The drawback is that every time the camera enters a different chunk, we need to shuffle this data structure.  Luckily most of the operations are quite cheap. (For very, very large view ranges and slow CPUs, this can even be done in the background. Nobody will notice if one or two frames still use the previous, almost-correct sorting order.)

At the block level

The individual blocks within the chunk must also be sorted. This is trickier, because not only does the sorting order change every time the camera enters a different block, it also changes for some of the surrounding chunks.

We split the surface that needs to be rendered (the set of exposed block faces) into six stacks of 16×16 grid "slices". Six, because there's one stack for each cardinal direction.

Here we see an example. The stack of slices that corresponds to "up" holds the faces A and B. A is at (1,1) o slice 0, B at (1, 2) on slice 1, one level deeper. So in this case, the z-axis corresponds to the actual z-axis of the game world.

The stack that corresponds to "east" (or "right") holds I and II. Although A and B ended up in different slices, I and II end up in the same slice because the z-axis now runs west-to-east.

All six stacks are then drawn in their z-order. Here's an example of the player looking north, down the slices of an eastward grid:

The slices are drawn in right-to-left order in this case. Faces J and K are drawn normally. K is closer to the player, and is drawn on top of J. L is drawn even earlier, if it weren't for backface culling. (It would be possible to start drawing a K's slice, based on the camera position, but finding the right index in the vertex buffer is nontrivial. Besides, the GPU can do backface culling so fast it's not even funny. It's likely you'll spend more time on the CPU trying to find the right starting point.)

This is also where identical, adjacent faces are merged in OpenGL 3.x mode. It isn't difficult to detect the two "N" textures can be merged into a rectangle. Determining the optimal way to merge the faces is an expensive operation, so Hexahedra uses a simple greedy algorithm. (Start at the top-left texture, and keep expanding a rectangle to the right and to the bottom until you encounter a different texture anywhere. Remove all textures in this rectangle, and repeat until the slice is empty.)

Für die Lulz

And because boring wall of text is boring, a video!

Flying through ModernCity

The whole "send surfaces only instead of whole chunks" bit now works properly, so I thought I'd show you guys a video.

(Omagosh I'm allowed to embed Youtube videos again? yay!)

It seems the screen recorder didn't only kill the frame rate as per usual, but also messed with the occlusion queries. So you'll see the occasional hole in the terrain. Let's see if I can figure out why this happens...

Edit: Fixed it by changing the occlusion system. We'll leave that for another blog post. In the meantime:

How to draw a cube

I'm not the only one who tried to draw a couple of cubes after seeing Minecraft, and every now and then I get questions from other programmers about how to structure the data and make it fast. So let's take a look at the basics of cube rendering.

Structure and storage


At the bottom level, we have a block, which is nothing more than a 16-bit value.  This means we can have over 65,000 block types, although special block types could take up multiple slots.  (For example, a staircase that can be placed in four directions would require four ID numbers.)  There is a separate table that holds all the info for a given block type, such as the name, durability, transparency, the collision box, Lua hooks, etc.

Then there's the chunk, a group of blocks arranged in a 16×16×16 cube.  Or at least, that's the concept.  In reality, it is an array of block types, and its size is fixed at 16³ = 4096 elements.  (At 16 bits for a block type, that's 8192 bytes).  The (x,y,z) position of a block is implicit: it is located in the array at index [x + y * 16 + z * 256].

Then, at the highest level, there's the game world.  This is a really, really big cube (4.3 billion blocks in every direction: a few times larger than our own sun), and it's sliced up in chunks.

Unlike blocks, we don't have to keep all 19 septillion chunks in memory at all times.  Chunks are positioned explicitly, meaning we store its position as well.  This allows us to load and unload small sections of the game world as needed.  I store them in a database, where the position is the primary key, and the chunk data is a blob of compressed data. Until recently it used 'deflate' as its compression algorithm.  I switched to LZ4, because it is much faster (7 to 10 times) and compression is only a few percent worse on average.

Rendering

Drawing the cubes on screen seems simple enough.  Load the chunks that are near the player, then go through every block in every chunk.  Grab the right texture for that block type, draw a cube at this position (the chunk's own coordinates, plus the implicit position of the block). Ta dah.

This is really, really slow.  We're drawing a lot of stuff the player can never see, so this is also easy to speed up.  The only thing that is interesting for rendering, are the faces at the surface.  So we still check every block, but we also look at the six neighbors.  If the neighbor is of a different block type, and it is transparent, then we draw the face.  Surfaces are stored as a list of a 16-bit chunk array index, plus a byte that indicates which of the six faces are exposed in the lowest 6 bits.

Much better already!  Combined with frustum culling and occlusion culling (described in detail in an earlier post) performance will be boosted even further.

Opaque and transparent objects need to be drawn separately, so you'll have to generate two surfaces for each chunk.  First you draw all opaque surfaces, in near-to-far order.  Then you turn off z-buffer writes, and draw all transparent surfaces in reverse order, far-to-near.

Surface extraction

The step that converts a chunk to the visibile surfaces is now our new bottleneck.  I know others have experimented with offloading this to the GPU, but this requires a rather modern card, and I'd like to support at least OpenGL 2.1.  So for now, we're still CPU bound.

Hexahedra always runs in a client-server setup, even for single player.  The server also looks for a chunk's surface, even though it doesn't render anything.  It uses this for calculating light, and for collision handling. Now why don't we store this information in the database as well, and send only the surfaces to the client?

This has several advantages.  Clients don't have to go through the same expensive step anymore. Network load will be reduced; a surface is usually smaller than the chunk it was generated from, with only a couple of worst-case scenarios as the rare exception.  Cheating will be harder, since clients cannot see ores or other valuables hidden inside the walls.

Hope you enjoyed this quick peek under the hood!