In the general case, to normalise a vector we can divide it by its length. Clearly this works because a number divided by itself is 1, and dividing a vector by a number will cause the length to be divided also. The only problem then is finding the length of a vector. In 2-D this is as simple as Pythagoras’ Theorem. So the length of vector V is: Sqrt( V.x * V.x + V.y * V.y ). Why is this of any interest? Simply because Sqrt is, as low level functions go, slow. It’s more than fast enough for most uses, but what if you need to normalize thousands of vectors per frame?

Solutions

Ok, firstly, we aren’t interested in the square root nearly as much as we are in 1/Sqrt(x). Lots of people have put time into solving this, and possibly the most famous was used in Quake 3 Arena. The code itself reads:

float Q_rsqrt( float number )
{
        long i;
        float x2, y;
        const float threehalfs = 1.5F;

        x2 = number * 0.5F;
        y  = number;
        i  = * ( long * ) &y;                       // evil floating point bit level hacking
        i  = 0x5f3759df - ( i >> 1 );               // what the fuck?
        y  = * ( float * ) &i;
        y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
//      y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed

        return y;
}

This function, while it does work, and is very clever, is not that fast. There is in fact an assembler instruction to calculate an approximate reciprocal square root, called rsqrtss. This can be used in c++ either by using inline assembler, or by using *intrin.h functions, specifically (in Microsoft’s compiler) _mm_rsqrt_ss. For additional accuracy, one iteration of Newton-Raphson can bring the result more than close enough for any given application.

But How Much Faster

With all optimisation, it is a good idea to really get an idea of what the trade-offs are between the possible methods. While rsqrtss certainly should be faster than other methods, it’s not intended to produce accurate results. So, while there may be cases where the accuracy isn’t all that necessary, we need to know if rsqrtss + NR is more accurate, and if it is faster than doing 1/sqrt(). This requires careful timing, and is not something I’m really qualified to talk about. I will, at least, post an update on my findings later.

Code

For anyone wanting to try the rsqrtss-based methods, here’s the source code I came up with. Note that this is Visual Studio specific, and only tested in VS2010!

	float inline InverseSqrt( float X )
	{
		float out;
		__m128 __X = _mm_load_ss( &X );
		__m128 Out = _mm_rsqrt_ss( __X );
		// equiv:
		// __X = X
		// Out = 1/sqrt(X)
		//0.5 * (Out + 1/(Out * __X))   This is newton-raphson
		_mm_store_ss( &out,
			_mm_mul_ss( _mm_set_ss( 0.5f ),
				_mm_add_ss( Out,
					_mm_rcp_ss( _mm_mul_ss( Out, __X ) ) ) ) );
		return out;
	}

	float inline InverseSqrtFast( float X )
	{
		float out;
		_mm_store_ss(&out, _mm_rsqrt_ss( _mm_load_ss(&X)));
		return out;
	}

It’s currently using a perspective transform, and it just fills the chunk with randomly chosen blocks, so it’s not too interesting to look at.

Story Time

However. No amount of fluency with tools, or excellence of those tools is going to fix a bug for you without the use of your own mind. In writing the map rendering code for Sim Game (I really have to think of a better title) I created a bug where… well, we’ll get to what was happening. Anyway, the optimisation was to check each of the six surrounding blocks, and if none of them was transparent, then not bother rendering this block. What came out was a sort of bottom part of the shell. Mystified, I stepped through the code and it did precisely what I expected it to do. I thought about what I was trying to do, and rewrote the early exit condition. This gave me the same output. After repeating this dance a few times I decided that it wasn’t a programming day and decided I’d come back to it later.

Today, I sat down, reset the function to how it was in the first version, with the reasoning that if they all produced the same output, the first one is as good as any, and was the simplest anyway. After thinking very carefully I realised the following:

• The program did not exhibit the expected behaviour
• The logic behind the method was sound
• The code executed as expected

So where does that leave me? I was perfectly certain of the first point, extremely certain of the second point, and I also knew the third point to be true. This lead to the conclusion that my expectation of where the code path should go was in fact flawed. With only a cursory check I saw that while most of the code in the inner loop was indeed only related to rendering that block, a very important and non-optional step happened afterwards – moving the draw point to the next block position. This was simple to fix and, of course, perfectly fixed the problem.

So What Did We Learn Here?

The main point I’m trying to make here is this: evaluating a bug in terms of your expectations is a good first step, but it really isn’t a guaranteed solution. A Good Programmer needs to understand their code, and failing to do this leads to all sorts of trouble. While I did understand the code I’d written, I failed to really think about the change I was making and what it meant to the code it was changing. “Yeah, we can just skip out from here” was the big mistake, and cost me an afternoon of messing around like an idiot. Go: Think, debug, repeat from Go.

#include <stdio.h>

That include line is a preprocessor macro, and it gets information about functions in a library somewhere else. I will be discussing here more complex macros, and their uses and pitfalls.

So I’ve Got a Bunch of Things

Repetition is something which, in programming, should be avoided at all cost. That is, programs will do repetitive tasks all the time, but programmers should avoid doing repetitive tasks like the plague. Most of the time there is a non-repetitive solution which might cost time in the short term, but it’ll save time for the rest of forever. Sometimes it might seem like this is unavoidable: you need a bunch of classes called “Foo”, “Bar”, and “Baz”, but they don’t really do anything important, they just initialise a base class with some data. These classes might look like this:

class Base {
public:
int x, y, z;
};

class Foo : public  Base{
public:
    Foo() : x(0), y(1), z(50) {}
};

class Bar : public  Base {
public:
    Bar() : x(3), y(100), z(3) {}
};

class Baz : public  Base {
public:
    Baz() : x(-6), y(123), z(0xdeadbeef) {}
};

This is repetitive, and a waste of time to write. In the Sim/Management game I’m currently working on, it’s worse still and I’ve got an enum of the names of the base classes too. So rather than waste time writing this out, I set up a pre-processor macro to do it for me.

Pre-processor macros usually look like:

#define SOMETHING Something(); if(Maybe()){ LotsOfStuff();}

but they can also take arguments. And importantly the arguments can be other macros, including other macros which take arguments. In the above list of class definitions there are lots of sections where the only thing that changes is the name (and some numbers, but we’ll get to that). Now that means the code could be replaced by a macro taking that name as an argument. But we can also supply those arguments using a macro if we will be using the same list of arguments frequently!

Here We Go: The Argument List Macro

#define ALLTHETHINGS(f)\
    f(Foo)\
    f(Bar)\
    f(Baz)

To explain, what this does, is given an argument f, it treats f like a function and calls it with Foo, Bar, and Baz as arguments. Note that the preprocessor acts on source code, these are not strings but typeless text, whatever the function of the text is after the macro is processed is what it does – it can be string data, int constants, keywords, or anything else.

An easy example of how this can be used would be to make an enum with these names, this would be most easily achieved by writing the following.

enum Names {
#    define ENAMES(op) op,
    ALLTHETHINGS(ENAMES)
#    undef ENAMES
};

Voila! To add an entry to the enum, just add it to the ALLTHETHINGS macro, and it’ll exist. The reason for undefining the ENAMES macro after its use is we don’t want to leave defined macros lying around where they could cause problems.

That’s no great saving, adding the entry in one place to save adding it in one place, but let’s look again – our definition of the classes above could be made into a macro as well. We will have to make a few changes however, the simplest being not defining the constructor in the class definition, so we only need a macro like:

#define CLASSTYPE(op) \
class op : public Base { \
public: \
     op(); \
};

And we can then use it with the ALLTHETHINGS macro as above. To sort out those constructors we will unfortunately have to repeat ourselves a little. The macro I’ll describe shortly requires the name of the class, as well as the value of the initialisers, it goes like this:

#define CONSTRUCTOR(Type, X, Y, Z)\
Type::##Type() \
    : x(X), y(Y), z(Z) {}

You can then call this as (for example) CONSTRUCTOR(Foo, 0, 1, 50) and it will create that constructor definition for you.

MACROISE ALL THE THINGS

So what’s the downside? If you get it wrong, the error messages are not going to be very helpful. They’ll point to the line which generated the error, but you could have a one line composite macro produce literally thousands of lines after the pre-processor has done its thing. Depending on the mistake you make that could produce thousands of errors as well. The other problem which appears if you work in a nice and friendly IDE, or at least work in Visual Studio, is that code completion is not going to understand what you’ve done. Intellisense will tell you that these classes do not exist and all references to them are errors. Even in Visual Studio Pro 2010, it marks macros inside enums as erroneous.

There is a solution which addresses both of these problems, but I believe has it’s own issues – mainly adding a build step. You could write a small program to expand the macros for you, while not expanding the #include calls. This would mean that the resultant header file would be easy for Intellisense (and non-microsoft equivalents) to parse, and the errors should in theory be easier to trace. Having IDEs call your program as part of the build process is certainly possible, though perhaps not as easy as writing it into a makefile (if you are that kind of developer). It also occurs to me that pre-compiled headers might be a solution, but I’ve never used them so I can’t comment.

I’m no expert on macros, the things I’ve listed above are approaches I’ve used (recently) in my own project. There are many more uses macros may be put to, and many other things the pre-processor can be persuaded to do for you (try looking up template meta-programming, for example) and even many things that they can do to make programming harder. RTFM, and use wisely.

At my end I use Visual Studio 2010 Pro (A leftover from my student years) although I believe there is enough backward compatibility to get it to work with things at least as far back as VC++2008 express. If you wish to not use Visual Studio, then the project requires linking against the following:

• SDL
• SDL_main
• SDL_image
• OpenGL32
• glu32

For the truly brave, compiling in linux should be possible, with the openGL libraries renamed appropriately. If anyone does this and finds changes are required, please tell me. If you can give me a patch file, even better!

Now one of the corner stones of the design is allowing things to be built out of any material, whether that means blocks of stone or swords made of cheese. This means that the two need to be stored independently where possible. Firstly though, we need to examine what these two parts mean in themselves.

Material

Materials will be anything that can, sensibly or not, be used to make things. The first one I added was Air, which will be the most common ‘no material’ material. Others are likely to include Chalk, Granite, Diamond, and yes, Cheese. A material needs to have a visual representation, i.e., a texture, and properties. Properties might include things like weight, hardness, conductivity, transparency, and two-state properties like breathable, passable and so on. Now it’s certain that there won’t be a material matching every possible combination of these properties, which means that storing all of that data for every instance of a material would result in a lot of redundant material.

Instead it’d be better to store a canonical list of materials which exist, and only refer to entries in that list via some suitable enumerator. This principle is something like the Flyweight pattern as mentioned in Design Patterns, an excellently useful, if a little dry, book which I thoroughly recommend.

Blocks

What I referred to earlier as ‘things’ actually needs splitting down a little. Parts of the environment are subtly different from other objects, in that those objects can (or rather, are intended to be able to) be picked up and manipulated by NPCs. Or be NPCs. These will also be considerably less numerous than environment blocks, and so special treatment is something which they can be afforded. Environment blocks then are specifically shapes. Most commonly these will be natural features, or at least what makes them up. Solid blocks, and partial blocks, and such useful shapes. This will inevitably end up including other shapes which are less natural, such as walls, windows and columns.

Map Storage

Now, we need to store, at a minimum, one of each of these things in each. Trying to keep to reasonable computer-friendly numbers, this probably means a byte for each, or 16 bits total, per block. That doesn’t sound like much, but we may want to have a large working set in memory at once, which can add up quickly, and not be very friendly to the CPU cache. A quick search online tells me that a fairly decent processor (the Intel i7) can have an 8MB L3 cache. That’s not that much, not really. That would be filled by a 128x128x256 map chunk. We ideally want to go smaller than that, but the size is something which will require careful balancing with several machines to work out a useful size.

Of course, this 2-byte per tile has its own limitations. As soon as either materials or block shapes number more than 256, that part will require an additional byte. Not too likely, so perhaps not a big worry, but something that might come up a way down the line. The other is that we don’t have any per-tile storage at all. Those blocks must be exactly identical, which means anything that has directions would need to be stored as four separate tiles. This will eat up tile IDs fast, but ensures that the myriad of tiles which don’t need extra data aren’t wasting space. The only other neat way to fix that is to have variable sized tiles, but that destroys any chance at fast indexing.

In Conclusion

Using a Flyweight type design for materials and block types seems to be ideal, although dereferencing the index will add an overhead, it is a necessary one. Fixed sized tiles are necessary, but picking the right size will be key, too little and I’ll have to revisit the whole problem and make any previously generated data out of date, too much and it’ll be too hard to process, take up too much memory, and waste hard disk space. A lot of testing will be required to really decide where to put the boundaries though!

This project is very much in the early stages.