knight666/blog

My view on game development

Tutorial: A practical example of Data-Oriented Design

For this tutorial, I’m going to assume a couple of things.

  • You are familiar with C++
  • You have at least a basic  knowledge of OpenGL 2.0
  • You know what object-oriented programming is

Bonus:

  • You are familiar with game programming
  • You are familiar with low-level optimizations
  • You know what a cache is

Ready? Alright, here we go!

What is Data-Oriented Design?

Data-oriented design (DOD) is when you look at your game’s state as data transforming into other data. In object-oriented programming (OOP) you view things as objects, each holding their own state and interacting with the world. A small example.

Suppose this is our game world. We have four balls bouncing around a room. When the balls hit a wall they go into a different direction.

In OOP, we say each ball has a position, a direction and a speed. Each ball gets an Update function that updates the position and a Render function that renders the ball’s sprite at their current position. This is what the data looks like:

We have a Ball class with some members and we have a BallManager class that has a list of Ball instances. To update the balls, the BallManager calls each ball’s Update and Render function.

void Ball::Update(float a_DT)
{
	m_Pos += m_Dir * m_Speed * a_DT;
}

void BallManager::Update(float a_DT)
{
	for (unsigned int i = 0; i < m_BallTotal; i++)
	{
		m_Balls[i]->Update(a_DT);
	}
}

So what’s the problem? Works fine right? Each ball has its own properties and you update those properties.

The main driving force behind data-oriented design is that you never tend to work with single objects, you work with groups of objects. So what would that look like?

Now, there is no Ball class. There is only the BallManager. And instead of a list of Ball instances, it has a list of ball properties. Now its Update function looks like this:

void BallManager::Update(float a_DT)
{
	for (unsigned int i = 0; i < m_BallData.filled; i++)
	{
		m_BallData.pos[i] += m_BallData.dir[i] * m_BallData.speed[i] * a_DT;
	}
}

The advantages are not obvious. It just looks like I moved some stuff around. How is that going to help?

A good way of trying to wrap your brain around data-oriented programming is to think of it as a factory: data comes in, an operation is performed and data comes out.

The Problem with Object-Oriented Programming

You might not realize there is a problem. But it’s been slowly creeping up on the industry. Computers, consoles and even phones nowadays have multiple cores. But our programs are traditionally written for one-cored computers. Yes, we can do multithreading. Yes, we have job systems. But our data is not inherently multithreadable. Each object is treated as its own entity, which makes it difficult to stream.

The inherent problem is that while our processors have been steadily increasing in speed (at about 60% per year), memory hasn’t kept up, increasing speed by only 10% per year. The gap is widening, and it is a problem. Keeping your data in cache (very fast but small memory near the processor) is becoming increasingly important. If you can keep all your data as near to the processor as possible, you can squeeze some significant performance from it.

As a game programmer in training, I learned about the difference between an Array of Structures (AoS) and a Structure of Arrays (SoA). I never paid much attention to it, because it seemed like such a hassle. But that was because I wasn’t forced to think exclusively in AoS. When I did an internship intake for a large gaming company, they asked me to use data-oriented design. I found that there wasn’t much available on the subject. A handful of talks and a couple of blogposts. But no practical examples and no source code.

So I decided to write my own. :)

The Test Program

The program we’re going to discuss is a voxel renderer. Voxels are essentially three-dimensional pixels. You can build and shape worlds with them, but they are traditionally very expensive to render. That is because graphics cards aren’t optimized for square blocks, they’re optimized for triangles. On top of that, we’re going to throw a raytracer on top of it. Each voxel casts a ray from a target position to itself. If the ray hits a block other than itself it is not visible and culled.

There are two versions, one using object-oriented programming (OOP) and one using data-oriented design (DOD). I have set some restrictions for myself for this example:

  • No macro-optimizations – The OOP and the DOD version both use the same algorithm.
  • No micro-optimizations – The DOD version does not use SIMD functions, even though it totally could.
  • No multi-threading – Mostly because I didn’t want to multithread the OOP version.

Controls:

  • Left and Right – Rotate camera
  • Spacebar – Switch between OOP and DOD
  • G – Generate new voxels
  • Q – Decrease amount of voxels
  • W – Increase amount of voxels
  • R – Turn raycasting on or off
  • D – Turn debug lines on or off

Format:
The example was built with Microsoft Visual Studio 2008. A VS2008 solution is provided. It should be forward-compatible with VS2010. The code will not compile out of the box on Macintosh or Linux machines, because of Microsoft-specific features (Windows window, Microsoft extension for font rendering).

Download:
VoxelExample-1.0.zip (1.5 MB)

This example is provided without any license. That means that anyone can download, modify, redistribute and sell it or any part of it. This example is provided “as-is”, without any guarantee of bug fixes or future support.

The Basics

We’ll need a window with an OpenGL context. This is handled by Framework.h and Framework.cpp. It’s not that interesting overall so I won’t focus too much on it. Suffice to say it creates a window, handles to the game code and runs their Update and Render functions. It also does some global key handling.

Common.h contains includes and global defines. Included with this example is part of my Toolbox: TBSettings.h, TBMath.h and TBVec3.h. You are free to use these headers in your own projects, if you wish. There are no license requirements attached to them.

The two interesting classes are OOPVoxels and DODVoxels. They are both children of the Game class.

We create voxels with a very simple algorithm. It starts at position (0, 0, 0) in the world and for every voxel, it takes a step forward, backwards, left, right, up or down. The color is a random color between (0, 0, 0) and (1, 1, 1, 1). The result is a colorful, but rough, “snake” of voxels.

The Object-Oriented Approach

I’ll skip the part where I generate the voxels. It’s not really relevant for this example. If you want to look at it you can find it in OOPVoxels::GenerateVoxels.

We will need some kind of container for voxel data. We are going to store the voxels in a VBO buffer. Every voxel consists of 6 quads, so each voxel will need to add its sides to the vertex buffer. The size of the voxels doesn’t change, so we store position offsets for each of the coordinates in the game class.

// offsets

float halfsize = m_VoxelSize / 2.f;

m_VoxelOffset[0] = Vec3(-halfsize, -halfsize,  halfsize);
m_VoxelOffset[1] = Vec3( halfsize, -halfsize,  halfsize);
m_VoxelOffset[2] = Vec3(-halfsize,  halfsize,  halfsize);
m_VoxelOffset[3] = Vec3( halfsize,  halfsize,  halfsize);

m_VoxelOffset[4] = Vec3(-halfsize, -halfsize, -halfsize);
m_VoxelOffset[5] = Vec3( halfsize, -halfsize, -halfsize);
m_VoxelOffset[6] = Vec3(-halfsize,  halfsize, -halfsize);
m_VoxelOffset[7] = Vec3( halfsize,  halfsize, -halfsize);

Next, we initialize our data and create a VBO to hold our voxels as a streaming quad and color buffer.

// voxel buffer

glGenBuffers(1, &m_VoxelVBOVertex); CGLE();
glBindBuffer(GL_ARRAY_BUFFER, m_VoxelVBOVertex); CGLE();
glBufferData(GL_ARRAY_BUFFER, m_VoxelDataSize * sizeof(Vec3), m_VoxelVertices, GL_STREAM_DRAW); CGLE();

glGenBuffers(1, &m_VoxelVBOColor); CGLE();
glBindBuffer(GL_ARRAY_BUFFER, m_VoxelVBOColor); CGLE();
glBufferData(GL_ARRAY_BUFFER, m_VoxelDataSize * sizeof(Vec3), m_VoxelColors, GL_STREAM_DRAW); CGLE();

glBindBuffer(GL_ARRAY_BUFFER, 0); CGLE();

What our voxel needs to store for now is its position, a color and whether it is clipped.

class Voxel
{

	Voxel();
	~Voxel();

	void SetClipped(bool a_State) { m_Clipped = a_State; }
	bool IsClipped();

	void SetColor(Vec3& a_Color) { m_Color = a_Color; }

	Vec3& GetPosition() { return m_Pos; }
	void SetPosition(Vec3& a_Position);

private:

	Vec3 m_Pos;
	Vec3 m_Color;
	bool m_Clipped;

};

In the PostTick function, we loop over every voxel and set its clipping state to false.

for (unsigned int i = 0; i < Framework::s_VoxelCurrentTotal; i++)
{
	m_Voxels[i].SetClipped(false);
}

And now for the slightly harder part. In the Render function, we want to lock the vertex and color buffer and add voxels that aren’t clipped to it. So we add an AddToRenderList function to the Voxel class. It takes a destination vertex buffer, a destination color buffer and the offsets for each vertex of the voxel.

Every voxel needs to check its clipping state before it can add itself to the buffer.

// write visible voxels to buffers

glBindBuffer(GL_ARRAY_BUFFER, m_VoxelVBOVertex);
Vec3* write_vertices = (Vec3*)glMapBuffer(GL_ARRAY_BUFFER, GL_READ_WRITE);

glBindBuffer(GL_ARRAY_BUFFER, m_VoxelVBOColor);
Vec3* write_color = (Vec3*)glMapBuffer(GL_ARRAY_BUFFER, GL_READ_WRITE);

unsigned int total = 0;
for (unsigned int i = 0; i < Framework::s_VoxelCurrentTotal; i++)
{
	if (!m_Voxels[i].IsClipped())
	{
		m_Voxels[i].AddToRenderList(write_vertices, write_color, m_VoxelOffset);

		write_vertices += 24;
		write_color += 24;

		total++;
	}
}

glUnmapBuffer(GL_ARRAY_BUFFER); CGLE();

glBindBuffer(GL_ARRAY_BUFFER, m_VoxelVBOVertex);
glUnmapBuffer(GL_ARRAY_BUFFER); CGLE();

glBindBuffer(GL_ARRAY_BUFFER, 0);

The Voxel::AddToRenderList function is very long, but most of it is copied. It writes its position plus an offset to the buffer and copies the same color to all six quads.

void OOPVoxels::Voxel::AddToRenderList(Vec3* a_Vertex, Vec3* a_Color, Vec3* a_Offset)
{
	Vec3* dst_pos = a_Vertex;
	Vec3* dst_color = a_Color;

	Vec3* offset[] = {
		// Front
		&a_Offset[0], &a_Offset[1], &a_Offset[3], &a_Offset[2],
		// more offsets here
	};

	Vec3** read_offset = offset;

	for (unsigned int j = 0; j < 24; j += 4)
	{
		dst_pos[0] = m_Pos + *read_offset[0];
		dst_pos[1] = m_Pos + *read_offset[1];
		dst_pos[2] = m_Pos + *read_offset[2];
		dst_pos[3] = m_Pos + *read_offset[3];

		dst_color[0] = m_Color;
		dst_color[1] = m_Color;
		dst_color[2] = m_Color;
		dst_color[3] = m_Color;

		dst_color += 4;
		dst_pos += 4;
		read_offset += 4;
	}
}

We use the unsigned int total to figure out how many voxels are actually in the quad buffer. Then we render.

// draw buffers

glEnableClientState(GL_VERTEX_ARRAY); CGLE();
glEnableClientState(GL_COLOR_ARRAY); CGLE();

glBindBuffer(GL_ARRAY_BUFFER, m_VoxelVBOVertex);	glVertexPointer(3, GL_FLOAT, 0, 0); CGLE();
glBindBuffer(GL_ARRAY_BUFFER, m_VoxelVBOColor);		glColorPointer(3, GL_FLOAT, 0, 0); CGLE();

	glDrawArrays(GL_QUADS, 0, total * 4 * 6); CGLE();

glBindBuffer(GL_ARRAY_BUFFER, 0); CGLE();

glDisableClientState(GL_COLOR_ARRAY); CGLE();
glDisableClientState(GL_VERTEX_ARRAY); CGLE();

Alright, voxels on the screen!

Now, let’s focus on the raytracing portion. When raytracing is turned on, every voxel generates a ray that starts at the target position and points towards the voxel. This ray then stores the voxel instance that is closest to the target position. So, each ray checks each voxel to see which is the closest. Luckily one of my teachers had a very fast ray-AABB collision check.

bool OOPVoxels::Ray::CollidesWith(Voxel* a_Other)
{
	float t0, t1;
	float tmin = 0.f;
	float tmax = 10000.f;

	t0 = (a_Other->GetMin().x - m_Origin.x) * m_Direction.x;
	t1 = (a_Other->GetMax().x - m_Origin.x) * m_Direction.x;
	if (t0 > t1)
	{
		tmin = (t1 > tmin) ? t1 : tmin;
		tmax = (t0 < tmax) ? t0 : tmax;
	}
	else
	{
		tmin = (t0 > tmin) ? t0 : tmin;
		tmax = (t1 < tmax) ? t1 : tmax;
	}

	// same for y and z axes

	if (tmin <= tmax && tmin <= m_TimeMin)
	{
		m_TimeMin = tmin;
		m_Hit = a_Other;

		return true;
	}

	return false;
}

But still, every ray needs to check every voxel. This results in horrible performance!

The obvious optimization is to update the algorithm so we don’t need to check so many voxels. But this is supposed to be an example in data-oriented design. ;)

The Data-Oriented Approach

Instead of thinking in terms of voxels, what is the minimum amount of data we need per voxel? Well, they’re all the same size. So all we need is a position and a color. So what we have now is a container for all our voxels.

struct VoxelData
{
	float* x;
	float* y;
	float* z;

	float* r;
	float* g;
	float* b;
};

What next? Well, our voxel data needs to be transformed into triangles on the screen. But what is the data that the VBO’s need to put stuff on the screen? It’s a position and a color. So we need a container for the vertex data.

struct VertexData
{
	Vec3* vertex;
	Vec3* color;
};

As the final step, we need to transform voxel data into vertex data. We’re going to use a function for that acts like a factory. Here is the diagram:

The internal structure of the function is much the same as the OOP version. However, I have split the saving of position and color data to improve caching. You can find it in DODVoxels::GenerateFaces.

So, what needs to change when we want to add raycasting? Obviously we’ll need a structure to hold our ray data.

struct RayCastData
{
	float* ox;
	float* oy;
	float* oz;

	float* dx;
	float* dy;
	float* dz;
};

And we’ll need a function that takes voxel data and generates ray data.

void GenerateRayCast(
	RayCastData* a_OutRays, unsigned int& a_OutRayCount,
	VoxelData* a_InVoxels, unsigned int a_VoxelCount,
	Vec3 a_InTarget
);

Finally, we’ll need a function that converts ray data into vertex data.

void SolveRayCast(
	VoxelData* a_OutVoxels, unsigned int& a_OutVoxelCount,
	RayCastData* a_InRays, unsigned int a_InRayCount,
	VoxelData* a_InVoxels, unsigned int a_InVoxelCount
);

This is, in my opinion, the biggest advantage of DOD over OOP. It’s clear where your data is and in what way it needs to be converted. The DODVoxels::SolveRayCast function is the biggest change from the OOP version. It has become massive. But the algorithm is the same.

Now, putting it all together:

void DODVoxels::PostTick()
{
	if (Framework::s_RayCast)
	{
		Vec3 target(
			Math::CosDeg(Framework::s_TargetRotation) * 500.f,
			10.f,
			Math::SinDeg(Framework::s_TargetRotation) * 500.f
		);

		GenerateRayCast(
			m_VoxelRayCast, m_VoxelRayCastTotal,
			m_VoxelData, Framework::s_VoxelCurrentTotal,
			target
		);

		SolveRayCast(
			m_VoxelRenderData, m_VoxelRenderTotal,
			m_VoxelRayCast, m_VoxelRayCastTotal,
			m_VoxelData, Framework::s_VoxelCurrentTotal
		);

		m_VoxelRenderDataUsed = m_VoxelRenderData;
	}
	else
	{
		m_VoxelRenderDataUsed = m_VoxelData;
		m_VoxelRenderTotal = Framework::s_VoxelCurrentTotal;
	}
}

But, what if we wanted to multi-thread? For instance, what if we wanted to split up the solving of raycasts into multiple jobs? With DOD it becomes extremely simple. We extend the SolveRayCast function to not only take a count of data it needs to chew, but also an offset into the array. Because we don’t read and write to the same array, we can split it up without race conditions.

A crazy cool benefit, wouldn’t you say? :)

Results

I made this example with an idea: I’m going to take an algorithm that abuses the CPU’s cache and apply data-oriented design to it to make it faster. The results are… disappointing. Here is the graph for just dumping voxels on screen:

Mind the gap between 5000 and 10000 voxels. As you can see, the DOD version is consistently faster than the OOP version. Even at 90,000 voxels it is 1 fps faster.

But then we get the graph for the version with raycasting:

What happened? The OOP version is consistently faster than the DOD version! To be honest, I haven’t a clue. The DOD version is aligned better in memory and with improved caching comes better performance. But I don’t get any.

Conclusion

I really like data-oriented design. Forcing you to think in terms of data instead of objects means you’re taking multithreading into account from the ground up. It can, however, be extremely tricky to think in terms of data. But I’m positive that will change with experience.

The reason I wrote this tutorial was because there wasn’t any proper literature on the subject. I hope my endeavors have saved you some time. :)

Capture the Glowstone in Minecraft

So here’s a cool thing a friend had set up: team-based capture the hill in Minecraft.

The premise is simple: each team is placed on top of a tall mountain and given a glowstone to protect. Glowstones cannot be moved: if you destroy it using a pickaxe, it doesn’t yield a glowstone but some soulsand. It’s a good way to make sure the stone is kept in the same place.

So the winning team is the one who can destroy the other team’s glowstone. This is a lot harder than it sounds, and oh my goodness is it fun. We played for about five rounds. We played this mode in two different classrooms. Each team (red and blue) had its own room. I played in red, we had four members while blue had five. There were also two “referees” with admin powers, who made sure people were following the rules (no cheats!) and teleported them to the right locations. During the game, we were constantly shouting back and forth tactics and suggestions. It was very hard to keep track of what everybody was doing, because most of the time you didn’t really know what you were doing either either. The team was fortifying the front of the base to ridiculous levels, but you tend to forget the back. Twice, we lost because we failed to notice a player simple walking around the mountain, digging through it and digging up.

If you look veeeeery closely, you can see the glowstone at the other end of the canyon

When you begin, you start to frantically look around. What do we need? We need wood. Go go go, punch some trees! Good, now we need a crafting table. And one of the most important items in this form of play: the chests. They contain all the stuff your team collects. Because, oh yes, you will need to work together. Wooden pickaxes are quickly replaced with stone pickaxes and a fortification begins to arise around the glowstone.

But then, after the initial scramble, something strange happens. One of the players will take a few stone pickaxes and start digging straight down. As any experienced Minecraft will tell you: oh my god that’s a terrible idea. And it’s true: you could fall into a cave and get jumped on by a horde of zombies *instantly*. You could fall straight into lava and lose everything. This is all true, and it’s a risk.

The unfortunate truth is that digging straight down is pretty much the only way to get iron. Because you are so high up on a naturally raised platform, there’s almost no way to get down without falling to your death. If you’re lucky you’ll find a safe way down, but then you still have to find a cave to explore. And keep in mind: the other team wants to *kill your glowstone*. You’re not really concerned with safety, you want an advantage over the other guys.

I can tell you: being that lone digger sucks. You’re digging straight down for what seems like miles, hoping you won’t find a quick death. You’re in pitch-black because torches haven’t been made yet. But if you’re lucky, you will have done an awesome thing for your team: you’ll have given them a means to make buckets (which can be used to extract lava and water) and maybe you’ll even find a diamond or three.

But then you have a new problem: how are you going to get the goods up to the rest of the team? You dug straight down, for hundreds of meters. You’re boned. There is no way to build any kind of contraption to propel the ore up to the rest of the team. That’s where this gameplay mode really excels: working together for the greater good. The whole team benefits from having buckets, so they’ll happily assign a guy to you whose only job it is to make ladders. As a last resort you can also keep building blocks below you, but obviously that means you can’t go back to your mining location.

What we ended up with in one of our matches is that both teams started building bridges towards each other. This is pretty much the “the only good defense is a good offense” tactic. It turned into a trench war, with both teams building bridges, swashbuckling over precarious heights. And not really gaining any ground. It wasn’t until the other team sneak attacked from behind that they actually won the round. They later told us that they didn’t really understand why we kept going at them with crappy stone swords, while they had iron swords. We had to keep going at it, because otherwise they would have overwhelmed us. At one point, my job was nothing but making pickaxes, shovels and swords. And we were running out as fast I could make them.

Overall, I had a blast. It’s definitely something I want to do again. However, it’s unfortunate that a lot of things don’t really work. You wouldn’t think iron would be so rare, but when the pressure is on it becomes a choking point. It’s tough to get iron fast enough for it to tip the scales. When I started, I thought we would coat the entire glowstone in obsidian, but that’s just no feasible. It takes forever to get a bucket, and then forever to retrieve lava, and then forever to coat it.

For next time, I would want the teams to start every life with a diamond pickaxe and shovel. It’s really bothersome how much time was spent just gathering resources for tools. I’d like to see some mods, like a block that spawns bonemeal. The stuff is brilliant in Capture the Glowstone. You can instantly remove your wood problem. And you could equip your team with bread when they go to the trenches. Wheat grows so slowly that the idea of a farm was abandoned fairly quickly.

You can download the maps here: CTGS_Maps.zip (11.2 MB)

Installing YoghurtGum

Before we begin, you must, must must keep in mind that YoghurtGum is still heavily in alpha. This means features will break, applications will blow up and stuff will just plain not work.

With that in mind, let’s play around with the engine.

For this tutorial, we’re going to install YoghurtGum on Linux so we can compile and run the Galaxians example.

Installing YoghurtGum on Linux for Android

The installation will do the following:

  • Alter the user’s .bashrc file
  • Create a new directory containing the Android SDK and Crystax NDK
  • Install Java
  • Create an emulator device
  • Create a keystore, which is used for compiling

The script has been verified as working on Linux Mint 10. I cannot guarantee anything for other Linux distributions.

The first thing you must do is copy the latest version from Google Code. Open a terminal and go to a directory of your choosing:

cp ~/YoghurtGum

Use Subversion to copy the repository:

svn checkout http://yoghurtgum.googlecode.com/svn/trunk/ yoghurtgum-read-only

Now, give the install script run permissions and run it as root. We’ll do it in one command:

chmod +x ./Install.sh && sudo ./Install.sh

The script will display the following:

testbox@testbox-VirtualBox /media/sf_YoghurtGum2 $ ./Install.sh
Welcome to the YoghurtGum 0.3 installation script.
Checking if 'sed' is installed...
Checking if 'wget' is installed...
Configuration checked.
1) Android
What would you like to install?

Type 1 and press Enter.

The script will ask you where you want to download the Android NDK and SDK to. The directory does not have to exist yet, but it cannot contain special characters (for instance, ~ for the current user’s home doesn’t work).

Where would you like to install the Android SDK and NDK?
/home/testbox/Android

The Android SDK will be downloaded. Now you are asked whether you want to download the NDK as supplied by Google or the custom-built NDK built by Crystax. Choose the latter, the official compiler does not work with YoghurtGum.

Please select the version of the NDK you would like to install:
1) Vanilla (Google supplied, safest)
2) Crystax (experimental, more C++ features)
Version: 2

Downloading may take a while, because the package has to come from a private server instead of Google’s awesome server farm.

Next comes a step I cannot automate. Android has to download the proper packages.

pic

Click “Select all”, then on “Install”. Let Google do its thing. You will have to close the window manually when it’s finished.

After that is done, some final things are set up. We need to create an emulator to target.

Creating Android Virtual Device...
1) Android 2.3.3 (API 10)     4) Android 2.1 update-1 (API 7)
2) Android 2.3.1 (API 9)     5) Android 1.6 (API 4)
3) Android 2.2 (API 8)         6) Android 1.5 (API 3)
Select the target Android version: (Pick '1' if not sure)

Go for Android 2.2, it’s the version on my phone and therefor pretty much guaranteed to work. ;)

Next it will ask for a name. This is just so you can keep the different emulators apart.

Name of the AVD?
Test

Now it will ask for the name of the keystore. Again, this is just for your sake. The keystore is personal and will be used to sign your applications, so use your own name or your company’s.

Name of the keystore?
YoghurtGum
Password?
******
Name of the alias? (Left blank it's the same as the one before)
YoghurtGum
Password of the alias? (Left blank it's the same as the one before)
******
Enter keystore password:
Re-enter new password:
What is your first and last name?
[Unknown]: knight666
What is the name of your organizational unit?
[Unknown]: YoghurtGum Inc
What is the name of your organization?
[Unknown]: YoghurtGum Inc
What is the name of your City or Locality?
[Unknown]: Awesomeville
What is the name of your State or Province?
[Unknown]: Noord-Brabant
What is the two-letter country code for this unit?
[Unknown]:
Is CN=knight666, OU=YoghurtGum Inc, O=YoghurtGum Inc, L=Awesomeville, ST=Noord-Brabant, C=Unknown correct?
[no]: y
Generating 2,048 bit RSA key pair and self-signed certificate (SHA1withRSA) with a validity of 10,000 days
for: CN=knight666, OU=YoghurtGum Inc, O=YoghurtGum Inc, L=Awesomeville, ST=Noord-Brabant, C=Unknown
Enter key password for
(RETURN if same as keystore password):
[Storing /home/testbox/Android2/YoghurtGum.keystore]

And that’s it. YoghurtGum has been installed.

Creating a project

This is one of the areas in which YoghurtGum is lacking. This will all improve in the future.

Every test has a Project.mk. Not really, but bear with me. This file indicates how a project should be built and where its files are located. Let’s go over the Project.mk file for the Galaxians example:

YG_TYPE=game

This line indicates the project is a game and should be treated as such.

PROJECT_PACKAGE_NAME=yg.game.Galaxians

The package is the Java package name. This has to be defined here because it cannot be derived.

YG_SOURCE_DIRS=src

The location of the C++ source code. Multiple folders are supported (separated by spaces), but it’s very buggy.

PROJECT_LIB_HEADERS=-I$(YG_ROOT)/Third-Party/libzip/src

Additional headers required for compilation.

PROJECT_INT=int

The folder to dump the intermediate objects to.

These are required settings for compilation.

Let’s generate a project for Galaxians. Go to the root folder of the SDK (~/YoghurtGum) and type the following:

make t=Tests/Galaxians project-create-android

Now you’re ready to build.

Compiling a project

Currently it’s a mess of third-party dependencies, but we’ll gloss over that. We’ll assume you somehow have the correct version of every third party library. You need to compile them before continuing.

If you want to see what commands are being executed, you can add “V=1” at the end of the make command to see the actual commands.

Go to the root folder of the SDK (~/YoghurtGum) and type the following:

make build-third-party build-libraries

This will build the third-party libraries and the YoghurtGum libraries. You only need to do this once, after that you can just link to it.

We’re going to compile the Galaxians project. When you want to compile a project, you have to specify the relative path to the directory containing the Project.mk file. So, again, we go into the root of the SDK and use make:

make t=Tests/Galaxians build-game

If everything went okay we will have a working game!

Running the game in the emulator

First, open a new tab in the terminal. Type the following to run the emulator:

make emulator

It can take a seriously long time to open. Anticipate a waiting time of at least 2 minutes.

This tab has to remain open in order for the emulator to run.

Ready? Let’s run the game. Switch back to the other tab and type the following:

make t=Tests/Galaxians run

This will uninstall any previous version of your game, install the new version, clean the log, start the game and log the results.

If not, well, it crashes. Sorry.

Conclusion

This whole process hangs together with ducttape. It’s a miracle it even runs. When I release YoghurtGum 0.3, all this will hopefully be smoothened out.

YoghurtGum: Two Years of Work

Due to popular demand (one guy searching on Google) I decided to make an article explaining how to install YoghurtGum: Installing YoghurtGum

I should explain what you see here.

For the past two years, I’ve been on and off working on an open source 2D game engine for mobile devices called YoghurtGum. Both devices are running the same game, even though they run two completely different operating systems (Windows Mobile 6.1 and Android 2.2, respectively). The engine takes that into account and makes sure features are always available on every supported device. Although I’m not quite that far yet. ;)

A little over a month ago I bought a new phone, mostly because I wanted one but also as an excuse to work on my engine. I develop in Visual Studio, but I compile for Android in a Linux Mint VirtualBox. I actually started working on YoghurtGum when I heard about Google releasing an NDK for Android. That didn’t really go anywhere, so I ported it to Windows Mobile.

To give you an indication of how long I was working on this: when I started, Windows Mobile 6 was a viable platform. Phones were still being made with it!

On the left you have the device that started it all:

HP iPAQ 114 Classic:

  • Windows Mobile 6.1
  • 624 MHz ARM processor
  • 64 MB RAM
  • 100 MB internal memory
  • 240×320 pixels
  • Purchased in 2007

On the right we have the newcomer:

Samsung I5510:

  • Android 2.2
  • 600 MHz ARM processor
  • 128 MB RAM (not sure)
  • 160 MB internal memory
  • 320×533 pixels
  • Purchased in 2011 (about a month ago)

YoghurtGum is coded in C++. It’s divided into a number of modules:

  • YoghurtGumBase – static library that contains functionality for all other modules
  • YoghurtGumMain – static library that contains the engine itself; this is what games link to
  • RenderMethodDirectDraw – an implementation of rendering stuff on the screen using DirectDraw
  • RenderMethodOpenGLES – an implementation using OpenGL ES

    The game running in the Windows Mobile emulator

In a few weeks I’ll give a talk at my school about my engine. I’ll see if I can upload it somehow.

I hope this will finally drag the engine out of “stone soup” territory and into haute cuisine!

In the mean time, you can check out the source for YoghurtGum on Google Code:

http://code.google.com/p/yoghurtgum/

Please note that this is in no way production ready. It only barely works on both devices. The Windows Mobile version even has a huge memory leak that causes it to crash after about 2 minutes.

If you want to work on it, feel free to contact me at my e-mail address, which is knight666 at gmail dot com.

Why Picasa sucks at tagging

A few months ago, I was looking for something to tag my images. I have a huge collection of images and I was getting sick and tired looking for the ones I wanted.

First, I tagged them with IrfanView. This was extremely cumbersome. To tag an image, you have to do the following:

  • Press I to open the Image Properties window
  • Press I to open the IPTC Information window
  • Click Keywords to enter keywords

Repeat this process for every image for every folder spread out over God knows what drives.

It became impossible to keep track of commonly used tags, because you have to remember them, even if you use a Word document to keep track.

Next, I tried XnView. This basically had the same problems. Yes, it’s an image manager, but tagging is still hard. It has a commonly used tag list, which is great. Buuut I have a lot of tags, and it becomes impossible to categorize them. Worse still, not all images can be tagged! XnView can only save tags in IPTC or EXIF (JPG tags), it can’t tag PNG or GIF.

And then there was Picasa. An image manager made by Google, who wants to make everything searchable? Yes please!

But oh no, this had problems of its own.

Search sucks

For a Google product, this is extremely surprising. As an example, these are the tags (“labels” in the Dutch version) for my wallpaper folder:

This is a work in progress, I haven’t even tagged 1% yet. What I do is tag everything with “later” and “wallpaper” (select everything, add tag). Then I went through it and tagged them either as “widescreen” or “normal”. When I’m done tagging an image, I remove “later”.

And now the problem: the folder contains 538 images. 538 of those are tagged as “wallpaper”. 342 are tagged as “widescreen”. 193 are tagged as “normal”. 342 + 193 = 535. Uh-oh, I missed three!

Luckily I can search for images that are tagged with “wallpaper” but NOT “widescreen” or “normal”. Oh wait, no I can’t. I can search for “wallpaper widescreen”, which will give me all widescreen wallpapers and I can search for “wallpaper normal”, which will give me all normal wallpapers. That’s not helpful at all!

What I would like is more logical operations in the search function:

  • NOT: the image doesn’t contain “this”
  • OR: the image contains “this” or “that”
  • AND: the image contains “this” and “that”
  • XOR: the image contains “this” or “that” but not both

This is especially infuriating when I’ve added a bunch of new images to the folder. Now I have to go through all of them to see which ones aren’t tagged yet!

The tagging buttons

In theory, this is a very useful feature:

These are called “quick tags”, you have ten of them. Instead of typing something in, you can just click on one of these. You can also have the bottom three represent your three most commonly used tags.

  • I have over 50 commonly used tags, spread out over multiple topics.
  • There are no hotkeys for these buttons, it’s mouse only.
  • There is no option to change the amount of buttons.

Even if you like the commonly used tags thing, there are only three of them.

What I would like to see instead:

  • A hierarchical tree of tags, separated by category: wallpapers, photographs, funny, etc.
  • Keep the commonly used tags, but assign them to all 10 buttons
  • Assign hotkeys for select tags; how about Ctrl+<numberkey>?

Misspellings are saved

Say you misspelled wallpaper as “wallpapur”. Now when you type in “wal” you get “wallpapur” as well.

Whoopsie-daisy! I guess I’ll search for it, remove it and everything will be fine? Nope, it’s still in there. Only when you restart the program is the tag database updated.

The database is stored on the C drive

And it can only be changed using a hack! My C drive is almost filled, so I wanted to move the database to the F drive. You can’t! You have to move the files to a different location and make a symbolic link to it. This suggests the location of the database is hardcoded!

Conlcusion

Picasa is a great program, but its tagging capabilities seem tacked on. Maybe I’m just using it wrong. ;)