Category Archives: Xenos

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!