Limegarden.net Personal site of Wouter Lindenhof

Acyclic Visitor

Thanks to Jasper Bekkers, a good friend of mine, the design pattern described in "Possible connector design pattern in c++?" finally has a name. It is actually an Acyclic Visitor combined with an Observer Pattern. The reason why I didn't know of this pattern is because (again, thanks to Jasper for explaining) this pattern was not in the book of GoF and partly because of that it is not wide-spread. I only own two books on design pattern (actually one, since I lent the otherone to another friend) and neither of them described the Acyclic Visitor.

On the website of c2.com there is also a nice link to a pdf in which the original acyclic visitor pattern is designed including code samples. They use dynamic_cast though, while I use typeid. The downside of dynamic_cast is that the cast is not constant while typeid is  constant. I do expect however that using typeid is generally slower (especially since i perform a string comparison) but dynamic_cast did not feel natural for me. In retrospect it is rather easy to use dynamic_cast once you accept that once it returns a NULL pointer the casting was incorrect.

Possible connector design pattern in c++?

Recently I was working on an AI assignment and I needed a method to pass around notification which would cause the receiving objects to act upon it. Problem however was that none of the objects knew each other. I had many AI modules which were all split up (for example driving to a destination would exist out of destination chooser, path-finding algorithm, obstruction evader , driver mechanism, etc) and not all of them needed to concern themselves with notifications (a notification would be “change destination”) and often they only cared about a single notification.

As long as the AI stays simple, you are good with a few notification (in fact I think I only needed two) but as I was writing it I noticed that adding another notification would require changing 4 different classes. If I would heavily rely on my notification passing system I would have been in big trouble. 
There are a few ways to make the system simpler and the first one would be that there was only one notification which hold all possible data a notification could have and an ID which would help figure out what the type of message it was. The downside of this method I would need to check the ID and then act upon it. This was something I did not like.

Another method would be to have all AI components derive from a base class which had all the receiving notification messages ( OnChangeTarget(int targetID); ). This was the method I choose in the end (as I started to get me more and more off track while I should be working on the assignment) and since I need only two functions (remember, two messages) it wasn’t that hard . However I promised myself that after delivering the assignment I would find a way to improve this.

And this morning while I was walking the dog something suddenly hit me. Since neither type can recognize the other one (they both start as abstract classes) I need to find a way to connect the types. I had thought of this option before, but since the connecting method would need to be able to handle abstract types it should be abstract as well.

Since I'm assume this has become quite confusing so far I will post the code that demonstrate what I want to do.

//////////////////////////////////////////////////////////////////////////
// Two different notifications
struct HelloNote : public INotification {};
struct WorldNote : public INotification {};

// The receivers
// ...
// 

int main ()
{
	INotification* Note1 = new HelloNote();
	INotification* Note2 = new WorldNote();

	INotification* AllNotes[2] = {Note1, Note2};

	IReceiver* HelloRCV = new HelloReceiver();
	IReceiver* WorldRCV = new WorldReceiver();
	IReceiver* HelWoRCV = new HelloWorldReceiver();

	IReceiver* AllReceivers[3] = {HelloRCV, WorldRCV, HelWoRCV};

	for(int i = 0; i < 2; i++)
	{
		for(int j = 0; j < 3; j++)
		{
			AllReceivers[j]->InitialReceive(AllNotes[i]);
		}
	}

	// Removing all types types
	delete Note1;
	delete Note2;

	delete HelloRCV;
	delete WorldRCV;
	delete HelWoRCV;

	return 0;
}

As you noticed there is no coded type identification within the message (in fact except their names they are identical) and because the receivers are downcasted as well you can no longer see which type should recieve what kind of message. However after we run the final version of the exact same code (I promise I won’t change main at all) the classes will recieve the correct messages.

I’m not certain if the following method is an existing design pattern (believe me, I looked for it). But it is similar to the mediator pattern, but were the mediator pattern acts between two different set of variables, I'm acting between two different types. The solution I provide mediates based on type and not on instance. For now I think the description of an "abstract connector" would be better, but since I'm not 100% certain I will leave it at "possible".

Although I Intended to explain it I decided against it, since the code looks simple (as it is in fact), but it will be faster to experience and then explain it than the otherway around.

#include <iostream>
#include <typeinfo>  //for 'typeid' to work
#include <list>

//-------------------------------------------------------------------------------------
// Library code
// You can copy this straight in your code and it will never have a need for
// modification.
//-------------------------------------------------------------------------------------
struct INotification{
	virtual ~INotification(){};
};

class IReceiver;

struct BaseConnector
{
public:
	virtual void Connect(IReceiver* aRCV, INotification* aNote) = 0;
};

struct Translator
{
	const char*		m_Type;
	BaseConnector*	m_Interupter;
	Translator(const char* type, BaseConnector* inter) :
	m_Type(type), m_Interupter(inter)
	{}
};

typedef std::list<Translator> TranslationList;
class IReceiver
{
protected:
	TranslationList	m_Translators;
public:
	void InitialReceive(INotification* aNote) {
		TranslationList::iterator begin = m_Translators.begin();
		while(begin!=m_Translators.end())
		{
			if(strcmp((*begin).m_Type,(typeid(*aNote).raw_name())) == 0)
			{
				(*begin).m_Interupter->Connect(this, aNote);
			}
			begin++;
		}
	}
	void Receive(INotification* aNote) { std::cout << "Unhandled\n"; }
};

template <typename R, typename N>
struct TConnector : public BaseConnector
{
public:
	void Connect(IReceiver* aRCV, INotification* aNote)
	{
			((R*)aRCV)->Receive((N*)(aNote));
	}
};

template <typename R, typename N>
struct CTranslator : public Translator
{
	CTranslator() : Translator(typeid(N).raw_name(), new TConnector<R, N>) {}
};
//-------------------------------------------------------------------------------------
// User code
// This is what you will be writing.
//-------------------------------------------------------------------------------------

//////////////////////////////////////////////////////////////////////////
// Two different notifications
struct HelloNote : public INotification {};
struct WorldNote : public INotification {};

//////////////////////////////////////////////////////////////////////////
// Our Hello Reciever, only accepts HelloNotes
class HelloReceiver : public IReceiver
{
public:
	HelloReceiver()
	{
		m_Translators.push_back(CTranslator<HelloReceiver, HelloNote>() );
	}

	void Receive(HelloNote* aHello) {
		std::cout << " " << __FUNCTION__ << "(HelloNote* aHello)\n";
	}
};

//////////////////////////////////////////////////////////////////////////
// Our world Reciever, only accepts WorldNotes
class WorldReceiver : public IReceiver
{
public:
	WorldReceiver()
	{
		m_Translators.push_back(CTranslator<WorldReceiver, WorldNote>() );
	}

	void Receive(WorldNote* aWorld) {
		std::cout << " " << __FUNCTION__ << "(WorldNote* aWorld)\n"
	}
};

//////////////////////////////////////////////////////////////////////////
// Our HelloWorld Reciever, accepts both messages
class HelloWorldReceiver : public IReceiver
{
public:
	HelloWorldReceiver()
	{
		m_Translators.push_back( CTranslator<HelloWorldReceiver, WorldNote>() );
		m_Translators.push_back( CTranslator<HelloWorldReceiver, HelloNote>() );
	}

	void Receive(WorldNote* aWorld) {
		std::cout << " " << __FUNCTION__ << "(WorldNote* aWorld)\n";
	}
	void Receive(HelloNote* aHello) {
		std::cout << " " << __FUNCTION__ << "(HelloNote* aHello)\n";
	}
};

int main ()
{
	INotification* Note1 = new HelloNote();
	INotification* Note2 = new WorldNote();

	INotification* AllNotes[2] = {Note1, Note2};

	IReceiver* HelloRCV = new HelloReceiver();
	IReceiver* WorldRCV = new WorldReceiver();
	IReceiver* HelWoRCV = new HelloWorldReceiver();

	IReceiver* AllReceivers[3] = {HelloRCV, WorldRCV, HelWoRCV};

	for(int i = 0; i < 2; i++)
	{
		for(int j = 0; j < 3; j++)
		{
			AllReceivers[j]->InitialReceive(AllNotes[i]);
		}
	}

	// Removing all types types
	delete Note1;
	delete Note2;

	delete HelloRCV;
	delete WorldRCV;
	delete HelWoRCV;

	return 0;
}<

If you would look at TConnector you will notice that the virtual function (connect) has an implementation which based on the design casts the receiver and the notification to the correct type.

If now you would look at IReceiver you will see that the InitialRecieve function uses typeid to recover the type information and checks it against an internal list to see if we have a connection for it. Since by dereferencing we will find out the original type we will work with a known type.

Now look at the receiver classes. You see that in each receiver class we need to store a connection. We have to define a connection and the corresponding function. If the connection is missing the data will not be send to their respective receive function. If the function is missing you will get an error.

There are also many things that could still be done to improve it

Also attached to the article you will find the entire solution inside a zip file: PatternDesign Connector (4kb, source)

Lime engine update

Today I worked on and finished texture support. So far everything has been quite simple and straight forward as most features are shared by both DirectX and OpenGL. My first primary goal, trying to keep the majority of the core components completely platform independent has been achieved. For example, textures are API independent, only until they enter the graphics system they will be transformed to a DirectX or OpenGL specific format. Of course there were some times where I really hated this goal of mine, because DirectX uses textures as in ARGB while OpenGL wants it in ABGR (compared to DirectX). This means that OpenGL will have a drastic performance impact and I know this can easily be solved by flipping it once before sending it to the engine, or let the engine create and store another texture for internal use.

However, the LimeEngine is just a baby and I knew that this part would be easy and yes the above problem is what I call easy. The next part is going to be hard since it is almost impossible to stay platform or API independent. The problem is called shaders.

There are three popular shading languages. DirectX HLSL, Nvidia CG and OpenGL GLSL. The problem is that although the languages look identical they are not the same. Sometimes the variable naming is different. Further HLSL can only be used with DirectX and GLSL can only be used by OpenGL. CG is an odd one in that category as it has an implementation for both API's. However that requires an additional library and to be honest I prefer HLSL as the documentation is better than that of CG. GLSL is completely new to me and it requires an extension. An alternative could be that I write my own shader language, but doing so would most likely mean that other developers would hang me, burn me and forbid me to ever touch a computer again.

However the problem won't be with the coding but the use of the engine. Everyone using my engine should be aware that the engine is not intended as API independent, since it never is. You can learn a cat to bark, but it will never be a dog. Working with my engine will bring you as close as possible to the API without actually having to work with it and in fact this has always been my intention. This line is paper-thin and you might be better off seeing the LimeEngine as huge library filled with helper functions than a separate API.

But the next part is going to be hard as Shaders languages are all unique and I still want to abstract it until it is being used by the graphics engine.
There is one thing that the engine doesn't have which I'm not certain of if I want to add it. Since the engine is focused on shader there is no real need to add TL (Transform & Lighting) as these transformations are done by the vertex shader while the lighting is done by the pixel shader.

After that the engine will hit it's very first milestone as it will have all the features I have set out to add. And with a bit of luck I will meet the requirements of that milestone tomorrow. Actually there is the fact that I have to correct the documentation and oh... the fact that there are many small bugs I have to hunt and I bet a lot not so fun things that require my attention but let's not spoil the fun, shall we?

Update: Fixed point math

It has been a long time since I updated my blog so here is yet another piece of free code. For those who don't know what fixed point math is: Fixed point math is math without using floating point (no floats or doubles allowed) and in general fixed point math is more precise and faster than floating point math. A way to simulate floating numbers like 0.5 is by shifting the numbers to something bigger like 500 (0.5 times 1000), however when you multiply 500 by 500 you want the result to be 250 (0.5 times 0.5 is 0.25).

For a recent assignment I had to create a fixed point rasterizer, think of DirectX but then everything code by yours truly without using anything of DirectX. However I'm not too happy with the result as there are a lot of things that could be improved or added and for that reason I won't upload the rasterizer. When will I upload it? When I'm happy with it. When will I be happy with it? Once the feature set is on par with DirectX and rendering a full screen quad will be above the 200 fps.

I'm pretty strict on when something is good so don't expect the fixed point rasterizer being uploaded anytime soon.

What I do upload is the fixed point math part. It's a collection of classes. You have FX32 and FX32S which are types who have a different fractional part. And there are two converter classes (FX32Convertor and FX32SConvertor) who can be used if you want to combine FX32 and FX32S. Of all the four classes you have a 'fake mode'. This fake mode is the exact same class but instead of holding an integer it holds a float. By changing the define in config.h you can simply switch between fake and real fixed point math.

Warning: Don't test performance in debug mode but in release mode. Fixed point math is more instructions then floating point, but these instructions are cheaper than floating point. However in debug mode the compiler will add 'optional breaks' (which allows you to pause execution on every line) and this has a lot of impact on the speed of the fixed point mode.

If you are a person who worries about the fact that all the code is in classes which means function call overhead, then I want to point out that the compiler should allow inlining or if possible force it for those files. If that happens then even the overloaded operators will be inlined removing the function calls and this should generate similar code as if you were doing it manual (without using classes). However this is all depended on how well your compiler inlines.

The downloads can be found on my portfolio or if you are lazy you can always grab the direct link: fixed point math.rar

Runge-Kutta 4th order

Finally I got RK4 working. I never had highly sophisticated math and more then half of the books you come across start easy, telling you how to program (the part I do know) and then suddenly they shift in high gear and expect you to suddenly understand all the math that is throw at you.
It seems that most of these physics books are written for physics students and not for programmers. But also wikipedia assumes that I'm a math guru, which I'm not. In fact I like things that don't require me to think, you don't want to know how an engine exactly works if you only need to use it.

So I decided to post my own C++ implementation of RK4, which you are free to steal and use, but you can't hold me liable. I would like to hear if it worked for you or not, but don't feel obligated. My own version is a bit advancer than the one you will see, but that is only because I need to have drag, impulse, etc. I'm not going to explain as I simply don't understand every step, it is more stable than euler (read: it takes longer to break).

If you are really intersted in how RK4 works I suggest that you contact your math teacher and keep asking until you know the exact ins and outs of it.

struct Particle
{
	Vec3f Position;	// Vec3f is a vector (3d position) which should initilizes with all zero
	Vec3f Velocity;
	Vec3f Acceleration;
};

void EulerIntegration(Particle p)
{
	p.Position += p.Velocity;
	p.Velocity += Acceleration;
}

// We will use this function later, it's just to make it c++ correct
// DT is DeltaTime, just use 1.0f if you don't know what I mean with that.
void RK4Eval(const Particle p, float DT, const Vec3f d[2], Vec3f* output);

// DT can be 1.0f if you don't know what I mean with that
void RungeKuttaIntegrator(float DT, Particle& p)
{
	Vec3f k0[2]; Vec3f k1[2]; Vec3f k2[2]; Vec3f k3[2]; Vec3f k4[2]; // remember all should be initiliazed zero
	RK4Eval(p,    0.0f, k0, k1);
	RK4Eval(p, DT*0.5f, k1, k2);
	RK4Eval(p, DT*0.5f, k2, k3);
	RK4Eval(p, DT     , k3, k4);

	const Vec3f dxdt = (1.0f/6.0f)*(k1[0] + 2.0f*(k2[0]+k3[0]) + k4[0] );
	const Vec3f dvdt = (1.0f/6.0f)*(k1[1] + 2.0f*(k2[1]+k3[1]) + k4[1] );

	p.Position = p.Position + dxdt * DT;
	p.Velocity = p.Velocity + dvdt * DT;
}

inline void RK4Eval(const Particle p, float DT, const Vec3f d[2], Vec3f* output)
{
	const int x = 0; const int v = 1;	// otherwise I keep thinking arrays
	Vec3f state[2];
	state[x] = p->Position + d[x]*DT;
	state[v] = p->Velocity + d[v]*DT;

	output[x] = state[v];
	output[v] = p->Acceleration;
}

Reading material

• Game Physics - A book recommend by my school, which I don't recommend, as it's a lot of math while the code is simple.

• Game Physics Engine Development - A book I do recommend, it's quite easy going and it brings you to a goal namely a physics engine. So far no complains.
• gaffer.org - It told me the step I was missing (the derivatives)

Fuzzy Logic

A while ago I was contacted with a question if someone I didn’t know (feel free to mail me, you could be the second person I haven’t met) could use my SSAO shader because he was in a desperate need for fuzzy logic. First of all the SSAO shader is free and second I don’t see where fuzzy logic is in my shader, but I wrote the code a long time ago so maybe I put it in without thinking too much of it.

However the term fuzzy logic is how do I put it… fuzzy for me as well. I have heard the term before and I can describe it, but what it exactly is? As I’m writing this post I already know what it is but just for fun I will describe my original explanation.

Old explanation:
Fuzzy logic is making a logical decision based on an inexact (or fuzzy) value. With an fuzzy value we refer to a value in a certain range.

The above is not correct, but not completely off. And how can a number something that we can measure (1, 2, 3, etc) be inexact? Anyway the second explanation is better and after you have read how I came to that explanation it will make sense.

New explanation:
Fuzzy logic is making a logical choice based on the range in which the value currently resides.

It’s a bit hard to explain with an example, but you will know after this most simple example. If you ask someone “how fast is your car?” he can answer with a number, if someone asked me that question I could answer that it max speed is 180 KM/H. However that is a quantity which is an exact number. However I could say that it is pretty fast and that is a fuzzy answer.

In code we could make it look like something:

However lets say this is the next version of GTA in which everybody is crazy about his car, including the character to which you told "My car is pretty fast, do you want to race?".

The above is an example of fuzzy reasoning.
If you think about the answer you can find a lot of cases in which you can apply fuzzy logic.

• Freezing, cold, warm, hot
• Light, twilight, dark
• Young, grown up, old, ancient

Now one last example: Let's say we have a story teller which based on your character attributes tells something about it.

Intellect: 8
Charisma:  7
Luck:      8

"He was a good looking (based on charisma) student (smart people often study) who had girls waiting in line (based on charisma and luck)."

If you still have trouble understanding try to change the character attributes and change the sentence. Like what would happen if we would drop his luck to zero? Would it become "Who was so good looking that all the girl fainted and had therefor never had a date in his life" or would that only happen if we increase his charisma to 9 and drop luck to zero?
References:

• Wikipedia: Common RPG attribute names
• Wikipedia: Fuzzy logic