Archive for category Technical

Mouse Lag

In 0.7.0, the game draws the custom mouse cursor. The mechanism it does this by is very simple: every frame, retrieve mouse position and draw the cursor sprite.

This is the simplest possible way to draw a mouse cursor in a game environment, and it has two problems (well, technically two aspects of the same problem, but I’m separating them for this post):

 • Latency: you don’t see where the cursor is, but rather where it *was* when the last frame was drawn. When the game’s running at it’s standard 30fps, this can cause the mouse to feel a little bit sluggish, but not so much you can consciously notice it (it’s only consciously noticeable if you turn the windows mouse cursor on, at which point you’ll notice that the cursor doesn’t quite keep up).

If we were making a twitch game this sluggishness might be a problem, but for a slow-paced game like Species it’s nothing major.

 • Lag. It means the mouse is susceptible to low frame rates. When there’s thousands of creatures wandering about and “every frame” means twice every few seconds, this causes it to become very difficult to control the game cursor. Factor in the latency on top of not being able to see where you’ve moved the mouse, and the game becomes practically unplayable with mouse control.

 

Artist's Rendition

Artist’s Rendition

 

This is far more a problem: Species is a game that needs to push the boundaries of what the computer running it is capable of. Having a lag-sensitive mouse is a big issue.

There’s actually an easy solution to this: use the windows cursor. It’s drawn by the operating system, not the game, so is immune to the game’s lag.

Except, of course, I want to use my custom cursor.

Don’t give me that look, the custom cursor is important. It is my right, nay duty as a game developer to hijack your mouse and make it into some ridiculously over-sized and self-indulgent custom sprite.

 

hoogeCursorMenu

(totally to scale)

 

So to achieve that, I had to redesign the cursor display function.

Describing that would be a big pile of steaming boring, so I’ll just skip to the end: rather than hiding the cursor and drawing my own, Species now instructs the windows cursor to display as a custom *.png sprite, using a similar (if slightly more complex) system to the one other programs use to display the wait cursor.

The practical upshot of this? Mouse lag immunity! The mouse now runs smoothly and without latency even when the game is drawing at slideshow speeds.

It’s not a complete fix: the UI itself is still linked to game performance, so buttons remain fairly unresponsive. I do have some idea’s on that front, and for a game like Species they might be worth exploring at a later date (I believe it should be possible, theoretically at least, to get the UI buttons and controls drawing at a consistent 30fps even if the 3d world is lagging).

But regardless of what we may or may not do in the future, 0.8.0’s mouse control is a boatload smoother and more responsive than what we had previously. Which is, by my standards, a Win.

Cheers,
Qu

,

1 Comment

Anatomy of a bug – Loading Death

Hello minions,

Time for another “Anatomy of a bug” post. I’ll try not to get the lymph all over the place, but no promises. Vivisection is a messy business!

A recent bug fix involved a save/load problem: when you load a game, about 10-20% of the creatures would die, but *only* if the game had been running for a few minutes. This was something I hadn’t previously noticed: I didn’t really pay attention to the number of creatures, and they just looked like ordinary corpses after the load, so there was nothing to raise my suspicion.

With the new red-mist effect when creatures die, however, it was quite obvious that a large number of creatures were dying at the exact moment the game was loaded. Nothing quite says “you have a problem” like a couple dozen perfectly-synchronised bloodsplosions.

Liberties may have been taken.

Liberties may have been taken with this rendition of the event.

My first assumption was that this was somehow related to the AI changes: I’d implemented other potential culprits since 0.7.0, things like changes to how growth cost is evaluated and how temperature damage is applied, but since I’d just come off of implementing save/load functions for the creatures new brain, I assumed it was that the AI was being initialised badly. That would also fit the symptoms: 10-20% of creatures would be roughly the amount doing specific, low priority actions (the vast majority of them spend their time feeding), and they always start the game by seeking food which would explain why it took a few minutes to manifest.

But after adding a variety of reset and revaluate functions to completely refersh the behaviour tree, creatures were still dying during load. At that point I had to admit that the AI probably wasn’t the cause.

The next thing to check was that the Save/Load function itself wasn’t broken. That seemed unlikely: typo’s in the save/load routine usually either crash the game or result in *very* noticable problems. Still, maybe I was loading energy as health or something, so it needed to be tested.

I did that by saving the game with exactly 500 creatures, then loading it. Sure enough, when it comes in, there are 428 creatures.

Except… with the power of code, I can put a breakpoint in and study the game’s state at the *exact* moment it leaves the load routine. And at that moment, there are 500 creature’s. The killing blow isn’t actually being delivered until after the game is loaded, in the single update frame between when Loading finishes and the game is actually drawn to the screen.

And that thought, thinking of it as a “killing blow”, caused me to notice something something interesting. After the load, a large number of creatures were Fleeing Randomly. They’d noticed something.

Flee Randomly is actually a very specific behavior: it only occurs when Fear increases with no discernable source. Since fear is only raised under very specific circumstances, we can narrow it down further: they can’t have recieved a threatening ping (since that would give them a source), so they must have taken a significant amount of damage in a single frame.

They weren’t just fleeing in terror from some nebulous threat. They’d been attacked. Eeeenteresting.


Wait, did I say interesting? I meant terrifying. Something is in my game, causing pain and death in the single-frame of darkness between loading and playing, and I don’t know what it is.

After checking that the 8 seals on [REDACTED] were indeed still intact, I started looking for other sources of pain, misery and death in the Species universe. The first was prompted by a strangely beautiful observation: a few particles of snow falling in the desert.

Aha! The temperature map is being initialised one frame too late, hence the snow!

That would mean that for a single frame creatures are subjected to absolute-zero temperature. Or, y’know, -17 degrees Celsius, which is absolute zero in the species universe (FOR REASONS!). That would do some damage: not much, but enough to knock off some of the near-death creatures and scare the rest. Problem solved, and as a bonus we don’t have some wrathful eldritch abomination loose in the game’s universe.

So I went ahead and fixed the temperature map issue.

It didn’t work. The creatures still died.


Welp I guess it really is an elder god. Time to bury your computer, hide in your weird survivalist neighbours anti-zombie bomb shelter and await death or insanity, whichever comes first.

Or we could keep looking for a rational explanation, but where’s the fun in that?

The current UpdatableAttribute system has a neat feature where it records the cause of all changes to an attribute, called “delta’s”. So you can, in theory at least, see what type of health change the delta was: Attack Damage, Temperature, Healing, Pregnancy: you get the idea.

Of course nothing is ever so simple: there are 20-something delta’s split across 4 updatable attributes for 500+ creatures 30 times a second. Getting *specific* information out of it is difficult. Luckily, we know we’re dealing with something unusual here: a large negative spike across many creatures in a single frame. Those are rare, especially now that pregnancy happens over time.

So, some conditional breakpoints and a few false positives later, and we had a culprit:

Aha!

Aha!

ChildhoodGrowth! They’re being attacked by the cost they pay as children to grow to adulthood.

But why?


An answer gives way to more questions. Simply knowing it’s ChildhoodGrowth that is damaging them doesn’t really help: we need to know *why* ChildhoodGrowth is damaging them. What’s wrong with it’s calculation that conflicts with the loading routine?

Here’s the entirety of the code for calculating this amount of growth cost that needs to be paid this from:

if(isChild) 
{
    //Calculate energy cost for growth during childhood
    float energythatShouldHaveBeenSpent = phenotype.childhoodCost.Value * (age / (phenotype.childhoodLength));
    float thisFrameCost = energythatShouldHaveBeenSpent - energySpentOnChildHood;

    energySpentOnChildHood += thisFrameCost;
    health.QueueChange(HealthDeltaType.ChildhoodGrowth, -thisFrameCost);
}

As you can see, it calculates the total amount that needs to be spent (childhoodCost), multiplies it by the ratio between age and childhoodLength, subtracts any energy that has been spent previously, and then applies the result.

Can you see the bug?

No? I couldn’t either, so I created a number of debug variables, to test what the values of everything were before and after saving. The results were as follows:

savedChildhoodCost = 28                 : ChildhoodCost = 28
savedAge = 166                          : age = 166
savedChildHoodLength = 72               : ChildhoodLength = 72
savedEnergythatShouldHaveBeenSpent = 52 : energythatShouldHaveBeenSpent = 28    : BZZZZZT!

Ah! So the difference between what was saved before the load, and what was spent after, lies in energythatShouldHaveBeenSpent, which is…

… calculated from the other three variables. Which are the same before and after the load. So the values should be exactly the same.

What.

Can you see the bug now?

if(isChild) 
{
    //Calculate energy cost for growth during childhood
    float energythatShouldHaveBeenSpent = phenotype.childhoodCost.Value * (age / (phenotype.childhoodLength));
    float thisFrameCost = energythatShouldHaveBeenSpent - energySpentOnChildHood;

    savedEnergythatShouldHaveBeenSpent = energythatShouldHaveBeenSpent; 
            //Note: savedChildhoodCost, savedAge, and savedChildhoodLength
            //are all saved from their actual values at the moment of save.
            //energythatShouldHaveBeenSpent is a local variable, so it has 
            //to be saved here.

energySpentOnChildHood += thisFrameCost;
health.QueueChange(HealthDeltaType.ChildhoodGrowth, -thisFrameCost);
}

The same 3 values being combined in the same way can’t result in a different value. It doesn’t work that way. I must be
missing something. That saved value must have been generated at a different point in time or something…

… wait a sec.

Back up for a bit. I missed something important back here.

savedChildhoodCost = 28                 : childhoodCost = 28
savedAge = 166                          : age = 166
savedChildhoodLength = 72               : childhoodLength = 72
savedEnergythatShouldHaveBeenSpent = 52 : energythatShouldHaveBeenSpent = 28    : BZZZZZT!

There it is. There’s the bug. Can you see it? Look closely.

age = 166
childhoodLength = 72

This creature is not a child.

Why is an adult creature paying the childhood growth cost?


Suddenly everything begins to fall into place.

Immediately after a load, all creatures are initialised with isChild set to true. Their saved age will cause them to *become* adults next frame, but for that first frame, they will pay the outstanding childhood growth cost.

And that outstanding cost is calculated by multiplying the amount it takes to grow out of childhood by their *age*. So if they’ve lived as an adult for any amount of time, that’s quite a lot of growth cost they haven’t had to pay (by virtue of being fully grown), that they suddenly have to pay all at once in a single frame.

And they would have gotten away with dying horribly too, if it wasn’t for us meddling kids.

Thankfully, after all that, it’s an easy solution: just make sure “IsChild” is saved and loaded, right?

Well, not quite. Creature’s are initialised as children, they need to call the GrowToAdulthood method, or they’ll suffer permanent dwarfism. I could call this method manually, but it’s clumsy and inelegant. Plus it doesn’t really address the GrowthCost debt, which keeps accumulating in the background and only takes one wrong line of code to show up and wreck things.

So, a slightly more sideways solution is to make sure EnergythatShouldHaveBeenSpent maxes out at ChildhoodCost. No more excess childhood growth debt, and I can keep initialising creatures with high age values and letting their normal methods take care of growing them to adulthood.

if(isChild) 
{
    //Calculate energy cost for growth during childhood
    float energythatShouldHaveBeenSpent = phenotype.childhoodCost.Value * MathHelper.Min((age / (phenotype.childhoodLength), 1.0));
    float thisFrameCost = energythatShouldHaveBeenSpent - energySpentOnChildHood;

    energySpentOnChildHood += thisFrameCost;
    health.QueueChange(HealthDeltaType.ChildhoodGrowth, -thisFrameCost);
}

Cheers,
Bugkiller Qu.

7 Comments

Good News

I’ve been told the website and forums should be back within the week.

Once we get them back I’ll be releasing 0.6.0 to all our testers and pre-release players.

Cheers,
Qu

2 Comments

Optimisation, Performance, and *shudder* Multithreading…

Yeah, it’s time for another technical post. Sorry guys, I just can’t help myself. If you understand what I’m talking about, you’re probably doing better than I.

CPU Performance in Species is probably the single most restrictive factor of programming the game. It limits the number of creatures, it limits the methods I can use to change their variety, it limits the complexity of their behaviour, it limits everything sooner or later. But with very, very careful programming and optimisation, that ‘later’ can be pushed pretty far back.

Firstly, a little background: Species is ‘CPU Bound’ as opposed to ‘GPU Bound’. A CPU (Central Processing Unit) limited program spends more time computing what it has to draw than it does actually drawing it, meaning the GPU (Graphics Processing Unit) sits idle until the CPU is finished. I could dump a whole load of extra information onto the GPU and it simply wouldn’t care, because it’s hardly working as it is. The GPU is awesome like that.

Shawn Hargreaves can probably explain all this better than I, if you’re looking to read up on it:

An Elf In A Box
How to tell if you are CPU Bound or GPU Bound

I’m loathe to admit it, but I secretly suspect the Terrain LOD system I spent so long programming may be slowing the game down, because it takes work away from the GPU at the cost of a little bit of work on the CPU’s part, and I’m so heavily CPU bound there’s a chance just brute-force-rendering the terrain would be better at this point (I could be wrong, though, and taking it out at this point would be rather silly since there’s so much more yet to implement, on the GPU and CPU)

That’s why some of my systems, like the Billboard Vegetation, are reliant on offloading information from the CPU to the GPU. The GPU can handle it. The GPU can handle anything. (Advertised product may not in fact be able to handle anything)

So that’s fairly simple, right? Drawing takes no time at all, so all our time must be spent updating the simulation.

Nup.

In reality, I’m only spending maybe a quarter of my CPU time in the update call. The reason for this is the bottleneck between the CPU and the GPU. Before the GPU can draw anything, the CPU need to tell it what to draw, in excruciating detail.

So even though I can’t save time by saving the GPU work, I can save time, lots of it, by stopping the CPU from telling the GPU it has work to do. There are a variety of ways I’m doing this…

I’m sure I’ve mentioned before that creatures are made up of a whole bunch of separate ‘part’ meshes. A high detail creature would have a torso, tail, 6 limbs, 6 limb tips, a neck, a head, and a currently unlimited number of Features attached to the head (open to later revision). Multiply this by whatever our creature cap is and we’re calling the draw routine far too many times for good performance.

But it doesn’t have to be called for every creature. Creatures off-screen don’t need to be drawn at all, and we can get away with drawing less detail on distant creatures.

We can also speed this up with State Batching. (Note for technical readers: Model Instancing would have been my preferred approach, but the parameters for each creature are unique. It’s not easy to instance meshes under those conditions). See, in order to tell the GPU what to draw, the CPU has to feed it with the model, texture, and parameters things like animated bone positions, sizes, colours, etc). The easiest method would be just to feed in these three things for every model, every time, and this is exactly what repeatedly calling Draw() in XNA does.

But you don’t actually have to. The GPU remembers: if you just change the parameters, but leave the model and texture as is, you can draw a second copy of it without resending the model. So by carefully rearranging the order of drawing to (for example) draw all creature torso’s one after the other, you only need to set the torso model on the GPU once. You can do the same thing with textures and parameters too, if you’re changing models all over the place but repeatedly using the same texture.

Obviously there are other, more subtle and game-specific ways to improve general CPU performance as well. Moving calculations out of loops wherever possible is a generic one: more than once I’ve caught myself doing a calculation multiple times when it could be done only once. A more specific example was carefully controlling matrix operators: streamlining the modifications I’d made to the skinning animation system cost me some programming time, but resulted in a noticeable performance increase.

But even with all these ongoing optimisations, I’m still not happy with the games performance. I’ve been treating my 4 year old, dual-core laptop as a baseline minimum (not least because that laptop is my development machine), but it struggles keeping the game running at a decent frame rate once the simulation gets going properly. There’s still room to optimise (there’s always room to optimise), but I don’t think I can get it to
the performance levels I’m hoping for with after-the-fact methods and reprogramming individual methods. This leaves one other option…

… multithreading. *dramatic thunder*

(Note: this rest of this post will likely be one long whine. I hate multithreading even more than I hate render targets. I still plan to tame it one day, because it really is a powerful way to improve CPU performance, but not for the alpha release)

Most machines have more than one CPU these days, and many people assume as a result that that means the computer must be faster. 4 cores? FAST. 8 cores? ULTRAFAST. 128 cores? OMG WHY YOU STEAL NASA SUPERCOMPUTER. In reality though, most programs are not designed to take advantage of this. The vast majority of programs do all their actions on a single core, because Multithreading Is Hard.

Multithreading is the process of taking part of what you have to calculate and giving it to a separate process (thread), which can run in parallel on a separate core: in short, it’s telling the computer to do multiple things at once. So for a game, you might tell the main core to render the screen while the second core works on updating the simulation for the next frame.

Of course, describing the process so clinically doesn’t quite summarize the emotional response I have to multithreading. So for that side of things, here’s an alternative explanation: multithreading is the process of juggling 3 plates, 2 watermelons, a chainsaw and a rabid wolverine while walking a tightrope over a pit of giant acid-spitting ants while cyborg trapeze artists take pot-shots at you with AK-47’s and grenade launchers.

I’ve actually attempted multithreading in the past. The results were unpleasant, unpredictable, and impossible to debug, mainly because I didn’t know what I was doing but also partly because that’s just the way multithreading is.

To give you an idea, suppose the first thread retrieves something from the second before the second thread is finished with it. The program might fail (which is what we want, so we can work out why the first thread is retrieving stuff from the second), but it will usually try to keep going. The simulation will start acting strangely, using false values, but not actually telling you it’s doing so. If it fails, it will fail somewhere else in the code that has nothing to do with the multithreading, and you will then spend hours investigating in the wrong place.

The usual approach to multithreading is to implement a lock, so that one thread waits for the other to finish before using any of the same resources. But the draw call needs to use a lot of the same resources that the update call uses, so it would likely spend much of it’s time waiting, and wouldn’t be much of an improvement over single threading.

(There are, obviously, ways around this, and when I do implement multithreading properly I will have to study them in detail)

In addition, for some reason, Multithreading plays havoc with Visual Studio’s debug mode: a multithreaded game seems to run much slower than an equivalent single threaded game in debug mode: so slow that, during my ill-fated attempt, I had run the game outside of debug mode on in order to test it. Less than ideal, and it makes tracing bugs and errors much, much harder.

For the alpha release, and probably for the second alpha release too, we will have to settle for less-than-optimal performance. When I do implement Multithreading I will have to set aside a lot of time to rework a large amount of the code, and to deal with the inevitable problems. With luck, though, I will be able to significantly improve frame rates, which will allow for bigger worlds and more creatures.

Qu

“You know, there’s probably potential for a misogynistic nerd-joke about multithreading in there somewhere.”

, , , , ,

Leave a comment

Enter the Grim Reaper

Removing Creatures from the simulation is as important a part of natural selection as creating them, so let’s take a look at data structures and how they relate to murdering creatures for fun, profit and natural selection.

WARNING: this post contains programmer talk. The blog author will not be held responsible for any hitherto unknown allergic reactions to computer geekery.

Games Programming can be a funny thing. See, the simplest, sanest way to make new objects is, well, to make new objects. I want a creature to give birth to a second creature? Easy: simply call “new Creature()” and add the newborn to the list. Likewise, if I want to kill a creature and remove it from the game? Call Remove(). Also easy! What could go wrong?

Well, in C++, this wouldn’t be an option. C++ makes you manually dispose of objects: so, rather than just removing my creatures from the list, I’d have to make sure to dispose of them and all their references as well. If I didn’t they’d persist in memory and clog up the machine over time.

But .Net, (and by extension, C# and XNA) is smarter than that: it has the Garbage Collector, a marvellous piece of technology which detects and removes unreferenced objects, such as our dead Creature.

So yay! All good, we can get on with the gruesome murder, right?

Wrong! Also, slightly morbid.

See, the Garbage Collector takes time to dispose of objects, and if you’re generating a lot of garbage, say by (to take an example entirely at random) simulating an entire population of rapidly living and dying creatures, that time can add up. You’ll start to notice frequent ‘spikes’ in your frame-rate: frames that take much longer than your usual frames, happening every time the garbage is collected. How bad this is depends on your platform: I’ve not developed for the XBox 360, but I’ve been told it is utterly terrible at Garbage Collection.

But I’m developing for PC, so that’s not as much of a problem. The Windows Garbage Collector is actually quite fast. So, off we go to murder- *smack* Ow! Okay, okay, I’ll stop.

The windows garbage collector is fast, but it isn’t that fast, and for Species CPU time is at a premium. More free CPU time means more creatures, better frame rates, all that good stuff. So the ideal is not to handle any garbage at all, and for that what I need is a way to handle creatures being born and dying without actually creating and disposing of them.

And for that, I need an object queue.

The theory is simple: rather than creating and disposing of Creature objects on the fly, I create the maximum number (1500, currently) of creatures right at the start of the program, and don’t dispose of them until the very end. When a creature dies it isn’t removed: the object just goes into stasis until it’s needed again, at which point it is reincarnated as a completely different creature. Ergo: the Species universe runs on Buddhist philosophy.

Obviously the memory footprint of maintaining 1500 dead creatures is quite large, but it’s no bigger than that of occasionally having 1500 alive creatures, and an old maxim states: your performance is no better than your slowest frame rate (okay, it’s not that old as far as maxims go): I guess the same applies to memory footprint? Maybe? And in the long run, memory is far less valuable real estate than CPU time anyway, so it was definitely worthwhile doing.

So, with all that sorted out: creatures can now die. By which I of course mean “vanish mysteriously”: proper corpsing wasn’t implemented until some time later.

Oh, and for anyone wondering, yes: the very first thing I did after this was make a “murder everyone” function. I swear I did it for debug purposes though, and not at all so that I could sit at my computer laughing manically while continually committing horrific genocide against the hapless population.

Oh don’t give me that look, I know you all did the same thing in SimCity.
Qu

Gah! My allergies!

, , ,

Leave a comment

Creature class and Leg Rendering

Oh hey look, the drawing tablet worskes too.

First things first: I got my computer back! AND IT WORSKES!

Also, I successfully got a post up! Sure it’s like half a week late or something, but I’ll take it. My fragile self-esteem needs all the help it can get.

So, scene setting: I’ve just finished the skinning system. I can render animated and deformed meshes anywhere I want in my environment. I’ve also modeled a few simple animated legs and a torso object.

Now, to be fair, I might be taking a few liberties with the chronology of things here. A lot of the following was worked out in parallel with the skinning system, but I’m presenting it as sequential because it sounds more organised. So don’t mind my temporally-unhinged antics here. I assure you that unless the cooling pump fails on the paradox diffuser the space-time continuum is in absolutely no danger of instantly ceasing to exist. And the chances of that happening are, like, 1 in 10. Or is that 10 to 1? Never mind, nobody cares anyway.

Moving on: there are two possible approaches to take when it comes to laying out a foundation for a class as central to the game as the “Creature” class.

The first is to lay out everything at the start. Take it all from the design document, set up every data structure I need, and then go about tying them together. So, I’d prepare an leg class with some genetically-defined variables for size, width and type, then set aside some ‘combination variables’, such as strength and speed. Then I could use occult magiks to force demonic slaves to write Mathematical Equations to derive the latter from the former, as so: strength = (bicepWidth + tricepWidth * 0.6) * sizeModifier, etc. Or I could do them myself, that works too.

OR… the other option is to wing it. We start by making the creature move at a constant rate, and then we go and set-up the leg rendering and animation code, and then we plumb the size of the legs into speed and then we actually make the size of the legs variable, and then some other things we made up on the spot and then we realise we can make the subjects into ravenous undead flesh-eaters to unleash on an unsuspecting populous and make an absolute killing selling shotguns, and then… you get the idea. Basically making it all up as we go along.

Now, given that both of these approaches are mutually exclusive, in a stroke of certifiable genius I went and enacted both of them at the same time.

… wait, did I say genius? I meant the other thing. Word. Starts with I.

I had a fairly good idea as to how I was going to structure the creature body parts: A torso object, with legs, arms, neck and tail objects attached to that, and head, tailtip, hands and feet, attached to those. I also knew a large quantity of genetic variables I wanted, so I went ahead and put them in so I could tie them all together later. But I also wanted to see it in action as soon as possible, so long before things like “speed” were set up I threw in placeholder values and started on the AI, so that the creature would do more than just stand around looking awesome.

And it worked. Okay, true, I ended up making changes to or deleting the majority of the genetic values, but knowing the basic structure of the class and it’s sub-classes was a great help when it came to prioritising work, and being able to see the effects of the changes I was making kept me enthused.

So, in the fine tradition of starting with the most time consuming thing possible, the very first thing I prioritised was leg and torso visualisation. The creatures aren’t actually held up by their legs in species: instead, I derive a torso-height based on their leg size, and the legs sort of dangle at just the right height to make it look like they’re standing on the ground. Okay, all well and goo: that’ll work fine for horisontally-aligned bipeds, but what about quadrupeds with differently-sized limbs? What about creatures that stand upright like humans, or creatures that drag themselves along with a set of huge legs up the front? Clearly I’d need to do more than just move the torso up.

This was solved by the addition of another, half-derived half-genetic variable called “torsoRotation”. torsoRotation determines the pitch at which the creature’s torso is orientated, from 0 at horisontal to 90 when upright (okay, the value is actually in radians, but who in their right mind says “Pi on 2” when they mean 90 degrees?).

torsoRotation is a genetic variable: creatures can pass it on to their offspring. But if the creature is a quadruped, or if they are overly unbalanced (for example, small legs at the very rear), then torsoRotation will be overwritten with a value derived from a whole bunch of rules depending on their leg sizes and positions. This allows creatures to “stand up” without making it arbitrary or nonsensical: a creature who’s back legs increase in size will automatically pitch forward unless they usually stand upright enough to compensate for it.

My handwriting is banned by at least 3 seperate clauses of the Geneva Convention

Fittingly for a game like Species, this all affects survival in various ways. Any creatures whose body touches the ground suffers a ‘dragging’ energy-loss penalty whenever they move. Upright creatures move more slowly, but use less energy to get around. And so on.

This system of rules, once it was finished, resulted in a large variety of potential body plans, even with nothing more than legs and a torso. And, thanks to the time already spent on the skinning system, I could take randomly generated test renders of them straight away:

Cheers,
Qu

Don’t worry everyone, I swapped his paradox machine for a coffee maker and replaced his timecube collection with fluffy dice. The worst he can do now is make a terribly tacky espresso.

, , , , , , , ,

Leave a comment

Prototyping

Prototyping! It's foolproof, and almost never has bad outcomes!

Prototyping in coding means, roughly, “the process of writing bad code that pre-empts the process of writing good code.” In other words, it’s taking best practices and shoving them where the sun don’t shine (that’s that little place up near Lancre, isn’t it?) so you can rapidly code something that almost works, independant of all other variables. Usual procedure would then be to use what you’ve learned from the prototyping exercise to re-code the thing that almost works so that it actually does work. You know, decently.

As terrible and haphazard as the code behind the prototype will be, the finished product will be polished and professional, a triumph of well-organised project management and good coding practices, and there’s a good chance that the time you spent coding the prototype will pay for itself by allowing you to avoid all the pitholes the second time around. It’s like driving a really crappy car off the cliff so you can find out if you’ll survive when you do it again in your $200,000 Maserati. Only not like that at all. I may have screwed up that analogy. Whoops.

So when working in Species, it’s obvious that I made that most sensible decision of all time ever and chose not to prototype. Coding it twice? That sounds like more work! Screw that!

All those pitfalls? I ran headlong into each and every one of them.

But this did have one noticable advantage: the game served as it’s own prototype. Rather than being mapped from the start, it evolved by trial and error. My first vegetation system failed, so I rebuilt another on top of its decaying carcass, theifing the good and commenting out the bad. It was a process of revision and improvement over design, trial and error trumping any actual organisational skills on my part.

In a weird way, the process of evolution itself was what produced this game. And I’m going to pretend that’s what I was aiming for, because that allows me to continue in the blissful delusion that I’m a halfway-competant programmer for a little while longer. Besides which, it’s quite obviously the same approach the “intelligent designer” took when he was designing the human reproductive system, so at least I’m in good company.

But for the rest of you programmers out there, a bit of advice: PROTOTYPE! It’s worth it.

Qu

In his defence, he’s not as godawful a programmer or as insane a human being as he likes to portray himself as. He just enjoys participating in self-depricating humour… why isn’t my Maserati in the garage?

… Oh hell no.

, , , , , ,

1 Comment

Billboard Trees

No, not like this. Well, sort of like this.

So, I had my fancy schmancy terrain. I could render the ground. Yay. Accomplishment of the century. So, the next task would be to put something on the ground. Ambitiousness!

I figured the best thing to start with would be a vegetation system. I’d need a cheap, plentiful food source for when I started putting creatures on the map, and plants were the obvious choise. In addition, they add detail and make the entire map more interesting than just a ground-plane. To render them, I decided to use billboards.

Who needs more practice with their drawing tablet? You do! Yes you do!

Billboards, in a computer-graphics sense, are one-dimensional shapes that always face the camera so you don’t [i]see[/i] that they’re only one-dimensional. They’re like other-dimensional monsters that always know where you are. They’re used all the time in games, but normally only to represent complex objects that are often some distance away from the camera (like trees), or are too numerous to represent more accurately (like grass). As of the time of writing this, Species is still using billboards for it’s vegetation. This may have to change, but at the moment it’s one of the lower-priority items on the development list: the sprites, tacky as they are, are functional.

It would have probably been best to configure the vegetation to render in tandem with the QuadTerrain system, but knowing I would have to continually update the vegetation based on how much energy any particular vegetation object had, and allow all the creatures on the map to interact with it, I realised that a QuadTree would be less than ideal. The QuadTree system relies on larger nodes being less detailed than smaller ones: for the creature interactions, if not the rendering itself, I would need the same amount of detail everywhere on the map. So I divided the terrain into a simple grid, with each grid-square being given a small number of tree objects to manipulate and render. Creatures more than 2 squares away from a vegetation square don’t process the trees in it at all, saving CPU.

One advantage of a grid is that it correlates exactly with real-world space. Rather than checking the grid square by square, or sinking down through parent nodes in a quad tree, I can simply divide the creatures position co-ordinates by a given value and plug the result into the array to tell me instantly which square they’re in.

Am I being too technical? I’m being too technical, aren’t I? Oh god, what if I’m swamping you with boring technical information? Here, have a picture instead!

Look at the picture! Ignore my crippling insecurities!

Trees!

Now, they’re not perfect. They blend in with the terrain, which I don’t actually want in this case since it should be easy for the player to spot and identify food-sources. And they’re unbelivably tacky-looking because I threw them together in Adobe Flash using a laptop touch-pad. And, of course, they’re billboards. They look okay from a distance, but get too close and the illusion stops being at all convincing.

But then again, hindsight is always 20-20, and even though there’s a lot of things I would/will/might change, the vegetation billboard grid works for now. And maybe that’s good enough. For now anyway.

Want to hear something worrying? I don’t think he was actually being sarcastic in that first sentence.
Qu.

5 Comments

Terrain! from the Past!

Written July 2008

In 3 dimensional graphics, a computer can only render so many triangles before it suffers death by framerate. This is a problem in most games: the artists can never put as much detail into their 3D models as they would like.

With games where you can see and walk to the horison and beyond, this is especially awful. How can a computer render every triangle on a terrain so many kilometers wide, and still get a decent framerate?

The answer is fairly simple: it can’t. But the computer can reduce the number of triangles to be rendered on the graphics card. A distant mountain doesn’t need to have the same level of detail as the ground under the players feet, after all.

This is the point of Level of Detail (LOD) Algorithms: render fewer triangles, but get a visual result very similar to what you would have had you rendered them all. There are many different styles of LOD Algorithm. Species uses a QuadTree.

A Quadtree is a structure where each node is subdivided into 4 children nodes, each child node subdivided into 4 grandchildren nodes, etc. In the context of a terrain, this means that the ‘root’ node would have a low detail mesh, the children would have a higher detail mesh, the grandchildren have higher detail still, etc…

As the camera moves about the terrain, therefore, you can sink deeper into the quadtree and render high detail squares for nearby objects, and not sink anywhere near as far for distant objects, thus rendering them at a much lower detail.

[Present me says: this is where I seamlessly stitched in further detail from a more technically orientated post. You may not be able to follow much of the following without a background in graphics programming and/or wikipedia]

Stitching

Of course, nothing is perfect. Two same sized quadnode meshes next to each other will fit seamlessly, but imagine a high detail node next to a low detail node. The result will be artifacts known as gaps.
This can be fixed by ‘stitching’, where you either add or remove edge vertices from the nodes so that they match each other. In this case, I removed vertices from the higher detail node, creating a triangle pattern which connects to the lower detail node. In this screenshot, you can see it applied to every edge of every quadnode. In this one, it is applied correctly.

Of course, this isn’t as simple as it sounds: each quadnode is now accompanied by 9 meshes, 1 for no stitching, 4 for a single edge stitched, and another 4 for two stitched edges. Since these are generated at runtime, however, they aren’t a problem. [Present me says: well, they’re less of a problem than they would be if I tried to save them in memory. This is a case of putting up with longer loading times to reduce the memory footprint of the game]

Bounding Frustrums

It isn’t only distant objects need to be LODd. Nearby nodes which are not in view because you are looking in the opposite direction need not be rendered at all.

By doing a collision test between the camera’s “Bounding Frustrum” (a 3d shape representing the cameras viewport) and a quadnodes bounding box, we can determine which nodes are outside the view and quickly cut a whole heap of geometry from the render. By combining this with the distance testing, we can stop that from sinking further into off-screen nodes as well!

Multiple Vertex Buffers

One of the things I spent a lot of time on was converting the terrain to run with more than one vertex buffer.
The vertex buffer contains all the vertices read off of the heightmap. In general, it’s best to use a single buffer, because each buffer must be rendered with a separate Draw call. Unfortunately, there is a maximum limit to the number of vertices that can be rendered at once on the graphics card, and going above this limit will force the call to be rendered on the CPU (resulting in death by frame rate).

This limit varies, but on my home computer over a million vertices (a 1024×1024 terrain) is just a bit too much.

So, I implemented a nasty and complex algorithm to separate the terrain into a number of vertex buffers, based on the idea that each quadnode could be entirely contained within a parent vertex buffer if we split it correctly. This (eventually) came out well: it is now possible to split your terrain based on a size value. A 1024×1024 terrain split by 512 vertex buffers will come out as 4, 512×512 vertex buffers, with a fifth for all quadnodes which cover an area greater than 512 (only the root node, in this case).

It’s worth noting that I may have managed this whilst drunk, tired or otherwise incapacitated, as I cannot remember actually coding it, and have no really idea how or why it works. But it does, and seems to be bug free. [Present me says: Yes, that’s right. Apparently, the Ballmer Peak actually exists]

Global Normal Map

This shader was my first attempt at HLSL (High Level Shader Language), and came out brilliantly in my opinion. [Present me says: Hah! Oh you poor naive fool]

Dynamically changing the geometry can have a nasty effect: although the shape of a low detail node may be very similar to that of a high detail node, the shading can result in a fairly large difference in appearance if done per vertex.
To solve this, I took advantage of the power of HLSL, and told the terrain shader to use a global normal texture rather than per vertex normals. The advantage was twofold: My vertex buffers halved in size, and more importantly shading no longer changes between high and low detail quadnodes.

Detail Normal Map

Initially, I didn’t understand the mathematics behind normal mapping, and thought that by simply adding a detail normal map value to my global value in the shader I could create detail normal mapping. The result looked OK, but it wasn’t accurate: the detail normal ‘pulled’ the global normal upwards. When I tested with a high strength value for the detail normal, this was instantly apparent: the entire terrain was shaded as if it was a lot flatter than it truly was.
It wasn’t until after I’d finished the multitexturing that I worked out how to fix this, but when I did the difference was apparent (see below).

Multitexuring

Using a single texture for the entire terrain has two problems: the terrain is too big to be covered with a single texture with a high enough resolution, and tiling the same ground texture over the entire terrain is very bland. Therefore, I went for a multitexturing approach that made use of a blend texture.
In short, mutitexturing is using more than one texture on the same object, and a blend texture uses it’s red, green and blue channels to define the amount of each texture to show. In the sample, Blue represents sand, Green – grass, Red – Foliage and Black displays as Rock.
Quickly back on the subject of Detail Normal Mapping: you can see the difference between my original method, and my final method.

Distance Sorting

“Overdraw” is a term used when the pixel shader renders a distant object, then renders a closer object which completely obscures the distant object. Obviously, rendering the distant object was unnecessary: it didn’t end up being drawn on the screen, and rendering it simply hurt the fill-rate.
The GPU can overcome this if the near object is drawn first: when rendering the distant object, the fact that an object with a smaller Z-Buffer value has already been rendered will be detected, and the rendering process will be skipped.
Therefore, it is to our advantage to render the near quadnode before the far ones. Since a list of Quadnodes to be drawn is built seconds before the quadnodes indices are compiled into the index buffer, it’s a relatively easy fix to add a sort function in between.


Isn’t snarking in italics supposed to be my job?”
Qu.

, , ,

Leave a comment

Getting into 3D

Late 2007

So here’s me, late 2007. University wasn’t going well, and I was beginning to suspect I had chosen the wrong career path. On the other hand, my programming skills had been improving, and I had finally gone looking for a 3D game engine.

I found Blitz3D.

Blitz’s simple interface and use of the BASIC programming language lightened the learning curve going from 2D to 3D graphics, but it also removed from me some area’s of complexity, like collision managment, basic drawing concepts and terrain rendering. In hindsight, I really can’t tell if this was a good thing or a bad thing. On the one hand, it allowed me to build a few projects to near-completion very quickly: on the other, I only had a very shallow understanding of what it was I was actually doing. I remained enthused, but it slowly began to dawn on me that Blitz simply wasn’t powerful enough for my needs.

Losing interest in one project and looking for something else to occupy myself, I decided that I needed a different, more powerful engine. I found something even more powerful than that: the XNA framework.

According to a definition I found on the internet, which means it is absolutely infallible and anyone using any other definition is a blasphemer and a heretic, a game framework is a step above raw DirectX but a step below an actual game engine: it’s used to build the engine, which in turn is used to build the game. I had no idea at the time what this meant, but I saw normal mapping and bloom effects in an XNA project and, eyes shining with innocence, I happily ran after the graphical candy.

Sold his soul for Parallax Mapping,
Qu

, , , , ,

Leave a comment