Pompi Pompi – A Gamers and Developers blog for indie games

It can be fun to think hard about something. But sometimes we waste a lot more thought than we could to achieve the same goal and even better. Let’s say that efficient use of thought resources is to choose the path that requires you the minimum thinking and effort to achieve the same goal or better.
I will try to bring a metaphor, because I am afraid a math or code example would be less intuitive.
Let’s say you need to carry rocks from one place to another. You can pick them one by one, by hand, and carry them. In some cases this will be the best solution, but what if you need to carry rocks every day for the whole year? Wouldn’t it be better to build or buy a wheelbarrow? Though, if you needed to carry a few works than maybe getting a wheelbarrow is not worthwhile.

In programming this can mean planning ahead how you are going to solve a problem, or researching for the right existing technology to use.
However, things are not as simple as that. Planning consume thought resources or effort. You might end up planning too much ahead or investing long hours in planning something you don’t really know if it will work. This means there need to be a balance between planning and just trying things out. It might sound funny, but I believe you don’t want to sweat too much most of the time you code. A game requires large amounts of code and work, and if every minute of it would require you a lot of thought and effort, you will quickly burn out. A lot of the time coding should be easy or with very little effort. Of course, sometimes it’s tough. And sometimes it gets really tough, but you want to minimize the times it gets really tough.

The thing that inspired me to write this article is some code I had to write to build a tree from a data structure. This data structure is the result of a text file I parsed with boost::spirit(more about that in future post). In my first attempt I simply used a tool I had available, of building a tree. I forgot I had another tool built upon it that would make my life much easier.
The basic tool would call two virtual methods, build child and build sibling, and with those you are suppose to build the tree. The code I wrote for this tool was long, ugly and didn’t work. After this failed attempt I realized I have a tool I built upon the basic tool. This tool allows me to add the edges of the tree. I have an AddEdge method that gets parent index, child index and node data. The implementation make sure all those edges I add will create a tree after I call BuildTree. A lot simpler.
The first code snippet is of the advanced tree building tool, and the second code snippet is of the basic building tool. Notice the code is not spartanized much, and you don’t really need to try and understand it. Just try to see which one looks prettier. You might not see the code if you are not at the original blog website(because it’s a lot of code, and because of different plug-ins), so for the code you should visit my blog.

	void
	NodeFunction::NodeFunctionCall::AddNode (MathNode n, DWORD A_Parent, DWORD A_ListIndex, Tree::Builder & b)
	{
		using boost::fusion::at_c;
		this->CurrentIndex++;
		DWORD i = this->CurrentIndex;
		if (at_c<1>(n.Node).size()!=0)
		{
			NodeFunction::NodeFunctionCall::ParameterNode NodeData;

			NodeData.IsOperation = true;
			NodeData.Operation = at_c<0>((at_c<1>(n.Node))[A_ListIndex]);
			b.AddEdge (A_Parent, i, NodeData);
			if (A_ListIndex==0)
				this->AddSingleNode (at_c<0>(n.Node).get(), i, b);
			else
				this->AddSingleNode (at_c<1>((at_c<1>(n.Node))[A_ListIndex-1]).get(), i, b);
			if (A_ListIndex+1==at_c<1>(n.Node).size())
				this->AddSingleNode (at_c<1>((at_c<1>(n.Node))[A_ListIndex]).get(), i, b);
			else
				this->AddNode (n, A_Parent, A_ListIndex+1, b);
			return;
		}
		this->AddSingleNode (at_c<0>(n.Node).get(), A_Parent, b);
	}

Basic tree builder code.

	MemberClass >
	NodeFunction::NodeFunctionCall::Builder::CreateNode (MathNode A_Node, MathNode A_ExtraNode, DWORD A_Index, bool A_ExtraSibling)
	{
		MemberClass > Result;

		NodeFunction::NodeFunctionCall::ParameterNode NodeData;

		Result->bCreate = false;
		bool IsExtraSibling = false;

		if (A_Index!=0 && A_ExtraSibling && (A_Index-1)==boost::fusion::at_c<1>(A_Node.Node).size())
		{
			IsExtraSibling = true;
			A_Index = 0;
			A_Node = A_ExtraNode;
			A_ExtraSibling = false;
		}

		while (boost::fusion::at_c<1>(A_Node.Node).size()==0)
		{
			MathSingleNodeType * SingleNode = &(boost::fusion::at_c<0>(A_Node.Node).get().Node);
			boost::recursive_wrapper * p = boost::get >(SingleNode);
			if (p==NULL)
			{
				Result = this->CreateSingleNode (boost::fusion::at_c<0>(A_Node.Node).get());
				if (IsExtraSibling)
					Result->Data.IsSibling = false;
				return Result;
			}
			A_Node = p->get();
		};

		if (A_Index(A_Node.Node).size())
		{
			ComplexNode c = boost::fusion::at_c<1>(A_Node.Node);
			NodeData.IsOperation = true;
			NodeData.Operation = boost::fusion::at_c<0>(c[A_Index]);
			NodeFunction::NodeFunctionCall::BuilderData b;
			b.IsSibling = true;//!IsLast || A_ExtraSibling;
			boost::recursive_wrapper * Single = A_Index==0?&boost::fusion::at_c<0>(A_Node.Node):&boost::fusion::at_c<1>(c[A_Index-1]);
			MathSingleNode n = Single->get();
			if (boost::get >(&n.Node)!=NULL)
				b.Node = boost::get >(n.Node).get();
			else
			{
				MathNode m;
				boost::fusion::at_c<0>(m.Node) = *Single;
				b.Node = m;
				if (A_Index==0 && !IsExtraSibling)
					b.IsSibling = false;
			}
			bool IsLast = A_Index==boost::fusion::at_c<1>(A_Node.Node).size()-1;
			b.IsNull = false;
			b.Index = A_Index;
			if (IsLast)
			{
				b.IsExtra = true;
   				boost::recursive_wrapper * Single = &boost::fusion::at_c<1>(c[A_Index]);
				n = Single->get();
				if (boost::get >(&n.Node)!=NULL)
					b.ExtraNode = boost::get >(n.Node).get();
				else
				{
					MathNode m;
					boost::fusion::at_c<0>(m.Node) = *Single;
					b.ExtraNode = m;
				}
			}
			Result->bCreate = true;
			Result->NodeData = NodeData;
			Result->Data = b;
			return Result;
		}
		GlobalErrorWrap::Assert (false, "Unreachable ParsedGUI build code");
		return Result;
	}

Some people(my friend) think that if you can copy and paste some code it means it is a reusable code. That is wrong in two ways. First, reusable code means that the same code can be used in many different projects, it doesn’t say how many times you need it in one project. Secondly, as a rule of thumb, copy pasting in programming is a bad thing(sort of).
In this post I will not talk about reusable code, but rather how to avoid copy pasting. There is actually a very important mechanism for copy pasting in code. That is inheritance. Inheritance helps you copying the same code from one class into a new class, without actually having the same code written twice. Lets try to show a code example in C++.


class BaseSpriteDrawer {
public:
    void DrawCenter (int x, int y, Texture & t)
    {
     this->Draw (x-t.GetWidth()/2, y-t.GetHeight()/2, t);
    };
    virtual void Draw (int x, int y, Texture & t) = 0;
}

class SpriteDrawerA: public BaseSpriteDraw {            
public:
    void Draw (int x, int y, Texture & t);
};

class SpriteDrawerB: public BaseSpriteDraw {            
public:
    void Draw (int x, int y, Texture & t);
};

In this example you can see there are two different implementations for drawing sprites. Each one of those have different code for Draw. However, DrawCenter has the same code for both implementations so instead of writing the same code twice for each of the implementations, I have used inheritance. We have “copy pasted” the content of the class BaseSpriteDrawer or “copy pasted” DrawCenter.
The reason copy pasting is bad, is that you have the same code to maintain in two different places. If you discover a bug inside a function, you need to fix all the places you copy pasted that function. You just have more code to maintain, more copies of the same thing to maintain which translates into more work and more bugs.
There is also the additional bonus of saving you a lot of time. Sometimes you need the same code with small variations, and it would seem more work to figure out how to do this with inheritance, instead of just copy pasting and having two copies of the same code. However, in case you need a third copy of the code, with the inherited code it would be a lot easier to create the third “copy” of the code instead of copy pasting the same code for the second time.

If you are a beginner, I suggest you try to avoid copy pasting almost completely. It would be a good exercise or a good challenge to try doing something else each time you have the urge to copy paste some code. That being said, I myself don’t completely avoid copy pasting. While as a rule of thumb, its better to avoid copy pasting, sometimes its the fastest immediate solution. The thing is, not all of my code get the same treatment. Some code get better treatment than other code. If its code that is not so important and is not long, then I might copy paste it. I also might copy paste something, and when I see I get back to the same code to add something new, I would fix my bad practice of copy pasting and make a better, cleaner code.

There is a lot more to talk about this subject, and a lot more examples and techniques of how to avoid copy pasting. Copy pasting is actually implied from spartan programming, I have already mentioned spartan programming  and I hope to talk about it in future posts.

Performance is a strange beast.
I was just profiling a section in Labyrinthica that was responsible of drawing the walls sprites. The function had a loop that iterates about 200 times and each iteration calls a sprite draw call. Inside the loop there was the following code:

ostringstream OStr;
OStr<<"Not 1 or 2("<<i<<")";
Error::Assert (i==1 || i==2, OStr.str());

With this code the walls drawing function took 7% of a specific time. Then I changed this part of code to:

ostringstream OStr;
OStr<<"Not 1 or 2";
Error::Assert (i==1 || i==2, OStr.str());

After this change I got 4%. I then changed it to:

Error::Assert (i==1 || i==2, "Not 1 or 2");

And I got down to 2%. The conclusion is that performance can be very tricky. What might seem innocent(A simple string handling) might turn to be big CPU usage when performed inside a loop.
I found that there is quite an imagination between profiling and debugging. Maybe there is a way to reduce the time of profiling and avoid from these kind of pitfalls? I hope to figure this out in the future. I think there is something that might help.

In a previous blog post, I talked about bug negative verification. I also said that debugging should be avoided as much as possible.
That is true, debugging is mostly a waste of time. You spend a lot of hours trying to figure out why what you yourself wrote doesn’t work as it should. After you solve the bug, you don’t have a new feature, there is no prevention that you will make the same mistake in the future and you might have to redo the same wasteful debugging process you just did. Right? Well, not exactly.
A good philosophy to adopt is, can I do something so the same kind of bugs won’t reappear in the future? If you invest some time, after solving the bug, to figure out how to prevent future similar bugs from happening you might learn or gain something from the bug. That is why a bug is an opportunity to learn how to prevent similar bugs in the future.
For instance, a buffer overflow is when you are accessing an array beyond its allocated size. In c++ it would be doing something like this:
int a[4];
a[10] = 12;
If your program is doing weird things, you might eventually capture this bug. But its obvious it is better to use an array that is safe. Such as, an array that check if the index provided for cell access is within the boundaries of the array. If its not, it will report a run time error and let you know you did something wrong.
However, things are not always as simple as in the case of the array. Sometimes its not clear how you can prevent certain bugs. Lets say you have a game with medieval weapons such as swords and daggers. You want to give the dagger a power of 2 and the sword a power of 3. You gave the sword a power of 3, but you accidentally gave the dagger a power of 4. This is a bug, even though nothing will crash. It would be very difficult to prevent this kind of bug, but I can think of ways that would help catching this bug early.
Another concrete example is GPU shaders. You can write a shader in some high level language such as HLSL for directX. These shaders often have global parameters you can set through your program. I had a bug in a shader that it didn’t draw what I meant for it to draw. I then began debugging. First I checked if the color texture was really passed to the shader. Then I checked the normals in the vertex data and etc. I finally found that I forgot to set one of the global parameters of the shader. I wasted an hour or two to figure out this bug. A way to prevent this bug is to keep track of which parameters are set before each draw call, and report an error if not all the parameters were set.
However, you sometimes don’t want to set all the parameters in a shader, so what is the right choice?

I would say its a good habit to do some thinking after solving a bug, and not immediately move on to the next task. Why this bug happened? How I solved it? Did I really solve it? How can I prevent similar bugs from happening in the future? Should I prevent similar bugs in the future or is it not cost effective and having this kind of bug from time to time is acceptable?

Last but not least, you need to take what I said with a grain of salt. This is something that worked for me, from my own experience under certain conditions, but you don’t have to do exactly the same. Its not formal anyway, because you can’t 100% formalize programming. Its an advice, not rules or a recipe to follow blindly.

Abstract
Suggesting a technique of implementing a Geometry based Anti Alias(GAA), instead of using the built in 3D graphics AA. This technique has the potential to improve performance and quality of the AA under certain conditions. In short, I am using a geometry based or fins geometry outline technique, and use it to draw translucent smooth edges with the same color of the original 3D model.

Pre Requirements
In order to implement this algorithm, one need to have a geometry based or fins geometry Non Photo Realistic outline shaders implemented. 
This type of shader use a mesh of fins. For every edge or intersection between two triangles in the original mesh, there is a fin in the fins mesh. When rendering this fins mesh, we select in the shader which fins will be visible and which will not. The fins that are visible are those that one of the two triangles the fin belongs to is facing the camera and the other doesn’t. This cause that the viewable fins are the outline fins of the projected mesh on the screen space.
Some articles explaining how to do this, can be found here:
Single Pass GPU Stylized Edges
NPR with Pixel and Vertex Shader

How it works
Once you have the fins geometry, either by precalculating or using the geometry shader, you need to add additional information to the vertexes of the fin. If you are drawing a black fading outline using the fin geometry, you already have a V coordinate that is 0 where the fin is touching the 3D model and 1 at the farest point of the fin from the 3D model. For the faded black outline, we use this V coordinate to determine what alpha value we want the fin to have in the pixel.

The additional information we need to add, is all the information we have in the 3D model vertex where the fin come out from, which is used to calculate the final color of the correspondent triangles. For instance, if the vertex keeps a normal to calculate diffuse lighting, we need to keep this normal in the correspondent fin vertex as well.
We pass this information from the fin vertex to the pixel shader and on the pixel shader we calculate the color just like we would calculate the color in the pixel shader of the 3D model.
The next step is to multiply the fin color with an alpha, much like we did with the faded black alpha, and we get the anti aliased edge.
The results are shown in the following images of a ball and a scene from the game Labyrinthica: The quest of lima. For comparison I have included a render with no AA and a render with AA from an NVIDIA Geforce 8600 GTS set at 16Q.
Also a render of GAA outline without the 3D model.

Aliased ball

Built in Anti Alias

GAA ball

GAA only

Performance, quality and issues
GAA might prove to have better or worse performance than the built in AA of the graphics card.
The main bottlenecks of GAA are the vertex shader, in case no geometry shader is available, and part of the bottlenecks that the 3D model suffer from depending on the shader it use to calculate color. For instance, a use of texture might cause a memory bus bottleneck. On the other hand, GAA will most likely be calculated for only small part of the pixels on the screen, unlike the graphics card AA which is calculated for all the pixels in the screen.
In terms of quality, GAA has several differences from built in AA. You can control the fin’s thickness, making it possible for smoother and more pleasing AA. It does not make textures or models’ surfaces blurred or smoothed. And you can add a black outline for NPR rendering almost for free.

GAA might not work for edges with very high curvature or surface with unsmooth normals or unsmooth parameters used for calculating the color. Problems may arise due to the fact that the color on a specific vertex of a mesh is not the same color as the pixel next to it. Because the data at the pixel is the interpolation of 3 vertexes and not the exact data in the closest vertex. This might cause problems such as back facing normals on the fin.