Interfaces

You know what’s really hard in game development? User interfaces. That doesn’t seem obvious: there are certainly lots of areas that require hard stuff: maths, physics, etc. Graphics, physics, advanced AI, procedural generation – these all require pretty advanced concepts; and user interface generally does not. But the fact is, I’ve seen good existing libraries for all of these things; I’ve never seen a good GUI library. And none of my fellow developers had, either. Every game GUI system out there is weird, quirky, slow, hard to use and/or badly coded. Sometimes all of the above. Here’s what GUI systems are commonly used with Unity3D engine.

UnityGUI

Unity3D has a built-in system called UnityGUI. It’s pretty weird: all interface is created by code, and controls are function calls. Here’s what I mean: usually, GUI systems have a notion of “control”: a button, a line of text, a checkbox, etc. These controls are created either in some kind of editor or directly by code, like this:

var button = new Button();
button.Width = 100;
button.Height = 30;
button.Caption = "Click me";
button.Click = DoStuff;

Then this “button” is placed somewhere, like in a window, and the GUI system takes care of drawing it in the right place, checking for clicks, etc. You can still change the button after it’s created, i.e. resize it or change color or whatever.

In UnityGUI, though, there is no explicit button. Instead, the code calls a function that draws a button on screen immediately, and also checks for clicks. This makes the code dead simple:

if(Button(100,30,"Click Me"))
{
    DoStuff();
}
unityGUI

This is how UnityGUI looks like.

But while this is simple and easy to code, there are many problems with this approach. First, since there is no button, there’s no easy way to change its size, or text, or whatever, dynamically. Second, it requires that the code that draws the button, and the code that runs on button click, are specified in one place. This is called “tight coupling” in programmers’ parlance, and is a big no-no: it causes code to become tangled, intertwined, and ultimately unusable. And third, since all GUI elements are drawn immediately with this approach, it tends to be quite slow.

UnityGUI is essentially so bad, even Unity Technologies employees don’t advise using it. It does have its use, though: when you need to draw lots of mostly independent controls, and don’t care much about visual prettiness or performance, UnityGUI really shines. This is not the case with games, but this is exactly what’s needed for game tools. My editors for procedural generation, game objects and settings, and lots of other stuff all use UnityGUI and I love it; but it can’t be used for the actual game.

NGUI

This is how NGUI looks like

Another GUI system commonly used with Unity is NGUI. It’s a relatively nice system, based on the common approach of creating various controls in the editor (it basically reuses Unity level editor). However, it does not cut it for my needs. NGUI is based on the premise that all controls are basically created and laid out in advance, and the game might show or hide them, with animations maybe, but not create new ones. Not that dynamic creation is impossible in NGUI – it’s just not really thought out. In the same vein, NGUI does not offer any ways for laying out (positioning) controls on screen, except the most basic. This is enough for many interfaces, but Xenos is going to need more. I plan lots of different windows: inventory, character and NPC information, dialogs, crafting tables, etc; simple layouts of NGUI are not enough. Also, NGUI costs $95 – it’s not much, but still an investment.

Other systems

There are some other GUI systems usable with Unity out there, but they’re less widely used and are probably less functional. There are also two really advanced alternatives: Flash and HTML/Javascript GUI (basically, integrating a whole another renderer into Unity). These are nice, but they require advanced capabilities of Unity3D Pro license, which I don’t have (and it costs $1500 and I’m not willing to spend this much just yet).

This leaves me with no other choice but create my own GUI system. Now, I can’t really hope to best literally everyone out there. Most probably, my GUI system would turn out to be bad too. However, what I do hope to achieve, is make a system that is good enough in the areas that really matter for this game, and maybe is shitty in some less important ones. Also, having GUI system written by myself means that I’d probably understand it really well and would be able to fix things relatively easy. That’s not guaranteed, though.

XGUI

XGUI is the name of system that I ended up with. It’s not fully finished yet, but all the big stuff is in. I can create windows and controls using a visual editor. I can automatically generate “glue” code that makes using these windows easy, and de-couples control creation and use. I can create and change anything dynamically. I have a small, but effective library of simple controls that can be combined to create complex interfaces. And I have advanced automated layouting system, that adapts to target resolution.

Basically, what’s missing is drag-and-drop support (it’s pretty easy to add) and a system for editing and playing animations in GUI.
And, of course, missing is any kind of nice artwork to actually show off the interface. For now, all my GUI consists of differently colored boxes. But I hope to enlist an actual artist’s help for this, so stay tuned. Meanwhile, here’s how the GUI looks now.

xgui-editor xgui-ingame

Places to go, people to see

Activities

Last time, I was talking about pathfinding algorithm in Xenos. But where would the NPCs  go? For now, there’s not many places for them to visit; just enough to demonstrate that they can do something and the code actually works.

Here’s how it works. When the game generates a house, it marks some areas of it as activity zones. Right now, there are 3 types of such zones: farm plots outside are marked as farming zones, beds inside are marked as resting zones, and the whole house is marked as idle zone. Then, when an NPC spawns, it checks all zones around and prepares a list of all activities it can do.

Npc activity

An NPC selected farming zone and is “tending to crops”.

The idea is that during the game, NPCs would somehow select the most “preferable” activity, go to its corresponding zone, and play required animations there. For example, at night resting in a bed is preferable, and during the day, farming or some such. Right now, though, they just select a random activity every few seconds… which is already surprisingly effective. Even three really simple activities make the village seem alive; adding more would probably be even better.

Locations

When I had a whole village of NPCs doing stuff (OK, pretending to do stuff), I wanted to add some other places. The village is far from done, of course, but I think the most interesting gameplay would happen outside, and I had no outside at this point.

For Xenos, I want to build a game world consisting of many discrete locations. There would be a short loading screen when moving between them: not because of some technical difficulties, but to make generation simpler, so that different locations don’t have to line up exactly. Also, having a clear line between “loaded” and “unloaded” locations simplifies game mechanics: I don’t have to worry about some place being unloaded suddenly – only as a part of leaving the whole location behind.

Adding another location brought an unexpected difficulty: the whole procedural generation system is quite unwieldy when I add new content. For example, at first I created an asphalt tile and a concrete wall tile. Adding them to the game took maybe a couple of minutes, but to actually see them, I had to create a new map generation feature that creates something out of asphalt and concrete, and then use it in some bigger feature that would create a “town” location… that was unacceptably slow.

Location editor

Creating a small town map

So, in addition to procedural generation, I had to create an old-fashioned map editor, so that I could create locations and test new stuff quickly. This took quite a long time, but would hopefully be faster in the long run.

Of course, I’m not dropping the procedural generation from the game. Instead, I hope it would work well together with hand-made maps: the systems are connected, and I can both use procedural system to generate something in the editor, and feed parts of hand-made maps into generation (i.e. a generation system creates a town layout, and fills it with buildings that are made by hand).

With the editor in place, I quickly added a few tiles and objects that can be encountered in a town, and built a little sample location. Next, I wanted to start adding actual gameplay, but there still were one system to build: user interface…

 

NPCs and pathfinding

First things first, I’m sorry for the long delay since the last post. It’s been over a month, and my only excuse is that New Year happened in the meantime – which was quite disruptive for my work.

So, anyway, what did I do during this month? One of the interesting things, that was mostly done back in december, was adding actual NPCs to the game. They don’t do much for now, but the two most important items are checked now: pathfinding and NPC activities.

I never thought I’d have to spend much time on pathfinding: I’ve had already implemented it countless (that is, at least five) times in various games. In most games, including Xenos, pathfinding is based on a popular algorithm called A* (pronounced A-star). You can read about it just about everywhere, and I’ll just explain the basic idea behind it. Which is: suppose we have a grid (square, in case of Xenos) where each cell can be passable or not. To find a path from one point to another on this grid, we basically have to examine all possible paths, until we either find one that reaches our target, or conclude that target is unreachable. To do that, we look at grid cells: beginning with the nearest neighbours of our starting point, then their neighbours, then theirs, and so on, until target is reached; in every cell we store link to “previous” cell – these links form a path. The key insight in A* is that when we have several possible neighbours to look at, we start looking with the one that is closest to the target point (more exactly, the one where distance to the target point+length of path so far is minimal). This seems a really obvious idea, and it is; what’s more, it actually works (which is more than you can say about many obvious ideas). It turns out that in many situations A* almost never even considers points that are not part of the final path.

See how A* path (cyan) looks unnatural because it follows grid lines

So, this was the algorithm I implemented immediately after I put NPC models in the game. But it turned out to have two problems. First: it was slow, but not every time. With 20 NPCs walking around randomly around the village, pathfinding sometimes would take 20-30 ms to complete – which is unacceptably slow for a game with many NPCs. Second problem is easier understood with a picture. Remember how in A* all paths only go from grid cell to adjacent grid cell, never “skipping” any in-between? It turns out that this looks quite unnatural in mostly-open spaces, like my village: real humans don’t go along grid lines, they just turn directly to their goal.

Starting with the second problem, I decided to use an additional trick with A* called θ* (pronounced theta-star). It’s pretty simple: in addition to normal A*, whenever we examine new grid cell, we also look if a line from previous-previous cell (i.e. two steps back on path) to current cell is free of obstructions. If it is, we remove previous cell from path, and go directly from previous-previous to current. In other words, we just corners whenever we can. This algorithm is pretty fast, and it produced paths exactly like I wanted to see… almost always.

A path can go directly through the grid corner – which should not be passable. To prevent this, all cells in the yellow square were checked.

To understand problem with my first implementation of θ*, look at the picture. Sometimes, when checking for obstructions, the line-of-sight would go right through the grid corner, and narrowly miss one or both obstacles along the way. I struggled with this problem, trying first to check for obstacles “a little to the side”, then checking several parallel lines some distance from each other, but then I settled on a very simple, but effective, rule: when checking this line-of-sight for obstacles, whenever a new grid cell is entered, I check that the whole 2×2 square, made by this cell and its neighbours along the line, is empty. This is easy, fast, and ensures that NPCs only cut corners where they can actually fit through. It’s a bit counter-intuitive, because it seems like this algorithm would break near doors – after all, doors are only one cell wide, and the line checking would surely stop at the doorway. But that’s not a problem, because there’s still “normal” A* going along grid lines, that can fit through narrow places just fine. In fact, it even looked better: NPC would go directly to a point close to the door, then turn and go through the doorway, then turn again toward their next destination.. sort of human-like.

With unnatural movement out of the way, I still had my performance problem. I tried many different optimisations, until I found, to my embarrasment, that I completely forgot to ever check the distance to target! That’s the main point of A* and I somehow managed to miss it. So, all this time, this wasn’t even A* at all. I felt really stupid, but also relieved… however, even fixing this didn’t solve the performance problem completely.

After some checking, I determined that the slow searches (they were down to 10-15 ms by now) happened when there was no path to destination. No matter how clever, in this case any algorithm has to examine all paths, before concluding that there’s no solution. And with the size of Xenos maps, it was going to be slow no matter what.

I know how to deal with this problem, but for now it’s left as-is. Occasional 10-15 ms slowdowns are not really noticeable with current frame rate (which is over 1000 on my, admittedly pretty beefy, machine), and I can fix this if and when it becomes a problem.

In the next post, I’ll probably talk more about NPC activities and life simulation – or maybe something else entirely.

3D models and pixel art

In last post, I was talking about world generation for project Xenos, and how it was working pretty great. This time, I want to talk about models for Xenos… and not everything is so rosy.

Having map creation sorted out (for now, at least. It’s absolutely not its final form), next thing on my agenda was adding a player character, and some NPCs. After all, having a village with no inhabitants would be pretty boring. But there’s a problem with characters: they require models with animations. I can sort-of create static 3D models that are made of boxes – see walls or tables on screenshots – but anything more complex seems beyond my abilities. Especially if it needs animating. But I had a plan: I would find a couple of free humanoid models on the internet, and animate them using Unity3D famed new Mecanim system.

Free human model from AssetStore

Of course, random free models from internet wouldn’t look good, but at this stage I don’t need good, I just need something. Browsing Unity3D Asset Store, I did find some models that were not bad. Actually, they were good, just not in the style I want for Xenos. I also downloaded a set of animations for Mecanim, that Unity Technologies helpfully provide for free. But… it didn’t work out so well. The hyped “retargeting” ability of Mecanim spewed cryptic error messages and refused to apply animations to my models. The system is barely documented, and quite new, so I couldn’t figure out what was going on, and finally decided that it’s simply broken. It was time for plan B.

I had no plan B, so in desperation I went to YouTube and searched for some animation tutorials. Here I was pleasantly surprised. An open-source 3D editor called Blender is, it turns out, pretty easy to use and I learned to create simple animations in a matter of hours. Of course, “easy to use” is relative – most 3D software easily beats aircraft cockpits in complexity, and Blender is no exception. But at least the animation part was manageable.

I made a couple really simple animations (sort of how Minecraft characters move). These animations were looking really weird when applied to relatively high-poly, realistic models. I tried to make some boxy somewhat-human-looking models to go with it, but they were either really ugly, or really minecraft-rip-off-looking (also ugly).

Then I thought about pixel art. I can’t draw, and I can’t make 3D models, but I can create passable pixel art. It’s nothing to write home about, but at least it’s not causing you to rip your eyes out. So – maybe I could use this to make models? Make some sort of 3D pixel art?

"Voxel Art" editor

“Voxel Art” editor

A digital image is a grid of squares, each having a color. When these squares are big enough, it’s “pixel art”. In the same vein, one could create a three-dimensional grid of cubes, each having a color. If the cubes are big enough, it’s “Minecraft”, but they’re smaller… let’s call it “voxel art”. I’m not the first one to imagine this: there are many games that use small cubic voxels, like 3D Dot Game Heroes. And they look pretty good. So, this is what I’d decided to do: create models with voxels.

I don’t know if there’s any software out there to create voxel models of this kind. But it didn’t seem too difficult to create my one tool, and that’s exactly what I did. I think that maybe I would bundle this editor with the final game as a tool to make mods, or something… anyway, for now it’s a standalone tool. And I’m putting it on this site, so feel free to download and play with it.

Human model in-game

It took me all of two days to create this editor, which is about the same time that I spent wrestling with Mecanim and free models. With the editor, I made my first voxel-art human, animated it in Blender and put him into the game. Of course, it’s still ugly, but now I at least have some idea how to improve it. I plan to replace all my models with voxels later, but for now the first priority is adding NPCs. Stay tuned!

Starting Xenos

With project Xenos being in full-scale development for three weeks already, I figure it’s time to write something about it. Maybe if I show this page to enough people, someone will actually read it (and maybe even – gasp – become interested in my game). So, what did Xenos become after first three weeks?

I decided to start with one of the harder features of the game – procedural generation of game maps. Starting with difficult parts seems a good strategy: I’d rather fail now, than after I spend months on stuff that wouldn’t work anyway. And the fact that generation algorithms are really interesting to code is purely coincidental, trust me!

My first generator simply sprinkled some random tiles around the map. This was just to test the fact that I had a map, and could display it and scroll around. Then I went to more advanced solution: the L-System.

L-Systems are a well-known concept, widely used to generate natural-looking plants and buildings. Although Wikipedia article seems pretty intimidating, actually L-systems are not that hard – at least, the one that Xenos uses. Basically, what I did was this: imagine some code that takes a rectangular area on map, and creates something inside. Some trees, for example. Let’s call it something-generator. Then, what if you want to create several something-s, arranged in some way? The L-system solves this with code, that takes a (bigger) rectangular area, splits it in some way, and then feeds the resulting parts into something-generator. Voila – several something-s. This is one of the fundamental actions in an L-system – split, then generate. There’s also another one: imagine that you have two different something-generators, and want to choose one of them randomly. To solve this, an L-system has code that takes an area, and then feeds it to another generator, chosen randomly, or maybe based on some criteria.

Now, these two operations – split and choose – don’t seem all that powerful. The real power comes from the fact that they can be combined! To generate a game location, we can split it into several areas, and feed each into a random selector, that then feeds each part into another split, etc, etc, until we get to the bottom and finally put something on the map.

Here’s how it all worked out for Xenos – with pictures!

 

Simplest building block: fill area with floor tiles

This is the basic “something generator” of the system: just fill the area with floor tiles. Doesn’t look all that interesting. Let’s split it!

Split into walls and floor

In this picture, I’ve split starting rectangle into four “sides” and an “interior”, and then fed three of the sides into wall creator. And I get something like a house…

More splits: and we have rooms and doors

Split it further – in two halves to make rooms. Then split two of the walls in a random point – insert doors. OK, now it’s definitely a house.

Adding more and more in this manner, I combine lots of elements to achieve this:

 

The whole village! (Click for larger version)

This is where I stand after 3 weeks of development. I haven’t mentioned in this post the time it took me to make all the textures and models for this… as you can see in the screenshots, I’m a lousy artist. And I intend to write another post on creating tools and editors for all this stuff, which actually took me longer then the L-system itself, but would save me a lot of effort in the long run. But this post is too long as it is, so… until next time? And remember, tell all you friends about Xenos. It’s gonna be awesome!