knight666/blog

My view on game development

PostApocalypse DevDiary 2: Of Saves and Trading

This is part 2 of an on-going series. Start here if you don’t know what’s going on.

Hello readers!

Last week I spent most of my time working on a school assignment, but I still managed to find some time to cram in some new features into this fancy indie game I’m making.

But most of all, I spent time playing one of my favorite indie games of all time: Mount & Blade: Warband. So I want to start this blogpost with a critique of that game, as well I started with sport betting, I just checked the info of the professional  from Fantasy Punter, and I decided to be part of this.

What’s so bad about MB:W?

When looking for comments about it online, you’ll find a lot of people talking about the first person combat, and not a helluva lot of talk about the third-person world overview. Even though you’ll be spending close to 70% of your time in it!

The way it works is that you get an iconic representation of your party: a horse with a dude on it with a number representing its movement speed. All the other parties get the same treatment, so you can start fights by colliding with them.

However, that is just one way to get rich. You can also try your hand at trading at this site. But how do you know if the price you’re getting for an item is amazingly cheap or horrifyingly expensive?

You don’t. And it’s very problematic. In fact, I started a spreadsheet just to see what the average price of items was:

What is this, EVE online?

After a while, you start seeing patterns. For instance, if you see grain at

However, if you buy iron for <70, you can sell it for ~300 denars. A huge profit! And it would be nice if the game actually told you about these things. If it let you discover the workings of the local economy, to help you make a profit without bloodshed.

But enough about this hugely popular and successful game built by two people in an apartment. Let’s talk about new features in online casinos like mydailypapers!

Saving game state

This proved to be quite the headache. How do you store game state in a file? Well, remember how I talked about MVC last week? That model is very, very handy when you want store only the state of the game and not any additional fluff. You simply store the variables in the Data modules, because you don’t have to care about the rest!

But what should the save file structure look like? My first thought was to use an .ini like structure. And you should always start small before investing a lot of time an energy into a new system, so I started with saving and restoring the camera’s position and rotation:

[Camera]
Position=Vec3(123.5, 23.4, 677.0)
Orientation=Quat(0.0, 0.0, 0.0, 1.0)

This looks fine, but it has a problem. These guys can explain it much better: Engine Tech: Concurrent World Editing. They talk about the problems they had with their save file system and how they resolved it. The gist of it is that when you store floats as strings, you tend to lose precision real fast. Did you know that the floating point number “0.2” cannot be accurately represented in the floats we use in our floating point hardware? It’s true and it’s not a conspiracy! It’s just how the math works out.

The result of this is that it’s a bad idea to store floats as strings. So I looked at the article I linked earlier to see how they fixed it. Well, here’s what they do:

; position
    46.103531 : 42386a04
    108.079681 : 42d828cc
    8.694907 : 410b1e57

They store the float as both a string representation and they store it as a hexadecimal integer! That’s brilliant, because you can always read the hex correctly and convert it to a float.

But as I tried to implement this myself, I realized: why don’t I just make a binary file in the first place?

The tool I\’m using here is called 010 Editor. It\’s awesome.

That probably looks like a big ol’ pile of gobbledygook to you. As well it should! But after reverse-engineering a great many stupid file formats, I know what makes a great file format.

The savefile

The most important thing of any binary format is the header. This helps identify the type of file you’re dealing with, but also the type of data. I use a PNG-like block structure, where each block has its own header.

This is the structure used for that:

	struct SaveSectionHeader
{
	char name[4];
	dword version;
	dword length_in_bytes;
};

Keeping the header separate like that allows you to load the entire header in one go, without those pesky conditionals. The name variable is used to identify the block. Right now I have only two blocks: “PASV” (PostApocalypse SaVe file) and “CAMR” (Camera). The first block allows you to quickly identify that yes, this is a PostApocalypse save file and it also tells you how many blocks are going to follow.

The camera block simply has its data (position and rotation) dumped into the block as bytes.

And that’s it. :) Surprisingly easy to work with, reliable and extensible! The version variable might seem like overkill, but it will vital in allowing backwards-compatibility. Hopefully, by the time this game reaches completion, I will still be able to convert and load this savefile.

The Graphics User Interface

UI is one of those things that nobody ever enjoys doing, but is vital to what separates a mediocre game from a great game. Mount & Blade: Warband, that game I use to steal… I mean get inspired by? It has a terrible user interface. It tells you either too much:

Why not just tell me: 108 prisoners. Sure would save screen estate.

Or too little:

How many days can I survive on these food supplies? How much does each horse increase my movement speed? What the hell is encumbrance even for?

So I set out to improve upon that by designing a great UI from the start and integrating it with the rest of the game.

Firs things first: that silly font rendering I had had to go. Obviously it was Windows-specific and it would be a pain to port to other platforms. But I’ve used FreeType in the past and I could never get it to render quite right. Also, I don’t want to spend all of my time designing a system I don’t really care for, so let’s take an existing package.

I don’t want to use CEGUI, because last time I used it I produced code looking like this:

That RockScroll image on the right side really tells you all you need to know about the GUI code.

But I didn’t want to let my prejudices get in the way of progress, so I gave it a try anyway. And then I found out that you can’t really control anything. Don’t want to use XML to load scheme files? Too bad, the scheme loader uses private, not protected members. Want to use your own font render? Yeah, no, this one just works for us you know?

So I decided to look at alternatives. And I ended up with libRocket, the cute little engine that could.

Even its logo is adorable

Now I should explain my thought process regarding it:

  • Stage 1: Dismissal – “Using HTML and CSS to render UI’s? Come on, that’s overkill! Besides, I’ll bet it’s really slow.”
  • Stage 2: Testing the waters – “I bet the source is a real mess. No, actually it’s not. And I get to specify my own renderer? Sweet!”
  • Stage 3: Acceptance – “Listeners are awesome! Input is awesome! I love this library!”

That’s not to say I haven’t had problems with it. For instance, what if you want to know whether input should be handled by the game or by the UI? I still haven’t figured out a reliable way, but here’s what I came up with:

	void InterfaceManager::Update()
{
	m_Context->Update();

	Rocket::Core::Element* hover = m_Context->GetHoverElement();

	Rocket::Core::String tag_handled;
	if (hover)
	{
		tag_handled = hover->GetTagName();
	}
	else
	{
		tag_handled = m_Context->GetFocusElement()->GetTagName();
	}

	m_HandledByGUI = true;
	if (tag_handled == "#root")
	{
		m_HandledByGUI = false;
	}
}

It seems kind of… clunky, to be honest. And then there’s the div hell web developers should be familiar with:

I just want that little X to the right of that dummy text. WHY MUST THIS BE SO DIFFICULT?

But overall: I really like it! Using HTML/CSS for UI makes a lot more sense than trying to get the same results using relative and absolute offsets like in CEGUI.

Next week

I’m hoping I can finally start getting some gameplay next week. I have the basic systems set up, now it’s a matter of getting more content.

And that may involve… me learning GIMP and Blender. D:

See you next time!

PostApocalypse DevDiary: Week 1

Recently I’ve picked up work again on my indie game: PostApocalypse.

Beginnings

Last summer, I needed to stay busy. You don’t want to come out of your summer holiday with a set of blunt tools, so you need to continue using them. It was actually my father who gave me inspiration for this game. My dad is an accountant who specializes in automating business processes. Yes, it’s as dull as it sounds. But he was complaining that if the world were to end, his skills wouldn’t be of use to anyone. I disagreed, because even after the apocalypse food supplies will need to be kept track of, trading will still have to be organized and eventually governments are to be rebuilt.

And that… sounded like a pretty cool game to me. If you like games, you probably are going to enjoy Online Casino Canada.

What helped was that at the time, I was playing boatloads of Mount & Blade: Warband. If you’ve never heard of it, it’s a game where you start with a lonely fighter on a horse and end up with a mighty army. But what I especially enjoyed was the trading, because you can make a lot of money with very little effort. Some settlements will have a surplus of one material, but lack another. For instance, grain will be cheap in city A, but expensive in city B. If you can keep track of those differences (for instance, on a piece of paper) you can send caravans from one city to the other and reap mountains of gold.

Mount & Blade: Warband

It took me forever to find this screenshot of Mount & Blade: Warband. Apparently nobody else enjoyed the boring bits as much as I did.

So my very first design goal became: if you don’t need paper to keep track of “hidden” game state, the design has failed.

False start

Another thing I wanted to try was to build a game completely data-oriented. Previously I have blogged about data-oriented design and how it could help your game run faster, but I wanted to see what would happen if I did everything that way.

It was a disaster.

One thing I decided early on was that I wanted hexagonal grid cells as a landscape. So I had a “Landscape” class and it had “DataChunks” and “DataCells”. The cells themselves would have to be built every frame, using the center position as a reference. Using some math you can then derive the normals for each triangle of the cell. That’s all fine and dandy, but the function to do that (_GenerateNormals) assumes cells are in one chunk. When you add more chunk, it becomes increasingly complex.

Basically: the code architecture was horrible to work with and impossible to add features to once written. I had coded myself into a corner.

I abandoned the project and started focusing on school projects again.

Reboot

That was half a year ago and now I know better than to try and build a game using data-oriented design. I now (almost) have enough credits to go on an internship. For the first time in a long while, I have some free time. So this week, I decided to take a look at PostApocalypse again.

Yup, still as bad as I remembered. I could reuse maybe 5% of the old code, but threw the rest away.

Progress

Right now, the game looks like this:

So what currently works?

  • Generating a landscape using Perlin noise
  • Generating a default mesh with a default texture
  • Loading DDS textures (the grass)
  • Rotating the camera using the keyboard
  • Rendering the landscape and the units using OpenGL
  • Placing new units on the landscape
  • Selecting and deselecting units
  • Pathfinding between points on the landscape
  • Moving units across the map
  • Saving and loading game state.

I’d say that’s pretty good for one week of development. :D

And now for the cool part: explaining the game’s architecture!

New architecture

The solution is divided into three projects:

  • Game – The actual game code
  • Render – The rendering library
  • Tools – Static library both projects link to

Game links to the Render project, but obviously doesn’t do any of the rendering. This will make it easier in the long run to port the project to other systems. Because both the Render project and the Game project need to log to the same file, the logging class is put into the Tools project. Ever wanted to use a singleton across the DLL-Executable barrier? Here’s how you do it:

static Log& Get()
{
	if (!s_Instance)
	{

#ifdef PROJECT_DLL

		typedef Log* (*GetLogFn)();
		HMODULE mod = GetModuleHandle(NULL);
		GetLogFn GetLog = (GetLogFn)::GetProcAddress(mod, "LogGetInstance");
		s_Instance = GetLog();

#else

		s_Instance = new Log;

#endif

	}

	return *s_Instance;
}

And then in the Game project:

extern "C" __declspec(dllexport) Log* LogGetInstance()
{
	return &Log::Get();
}

So how does that voodoo magic work? Well, the Render project defines PROJECT_DLL, while the Game project does not. So when the Game class compiles the header, it creates a new instance of the Log class and returns it. But when the Render class compiles it, it calls a function inside the executable exposed to the DLL’s that returns that very instance. Now, both the executable and the DLL have the same pointer to the Log class. :D

RenderManager

Because I’m trying to avoid OpenGL deprecated calls, I’m using a RenderManager class. This keeps track of global state like matrices, the current material and the current shader. It makes it easy to abstract all kinds of rendering operations without losing performance.

I built the first version of the rendering architecture for my Procedural Generation class. I wanted to experiment with using “new” OpenGL (> 2.1) and had to figure out how I could still have global state.

The epitome of modern OpenGL

For instance, this is the Render method of the Model class:

void Model::Render()
{
	RenderManager::Get().SetShader(m_Shader);

	for (unsigned int i = 0; i < m_MeshTotal; i++) { if (!m_Mesh[i].m_VertexArray) { continue; } Mesh* curr = &m_Mesh[i]; RenderManager::Get().SetMaterial(curr->m_Material);
		RenderManager::Get().Begin();

		curr->m_VertexArray->Enable();
			glDrawArrays(GL_TRIANGLES, 0, curr->m_VertexFilled); CGLE();
		curr->m_VertexArray->Disable();

		RenderManager::Get().End();
	}
}

You only have to set the shader once, so we can do that outside the loop. It’s almost starting to look like DirectX calls, so perhaps those guys are on to something. ;)

Coincidentally, I could copy the Perlin class, the Sphere generator and the texture generator directly from my Procedural Generation assignment. Sometimes it can be nice to have clean code. B)

Model-View-Controller pattern

Another thing I wanted to try this time was the Model-View-Controller (MVC) pattern. For instance, let’s say we need to keep track of people. Here’s what you start with:

struct DataPerson
{
	std::string name;
	int age;
};

Okay, pretty cool, but we need to keep track of all people, not just the one. How do we do that?

class ControllerPerson
{

public:

	void SetName(DataPerson* a_Person, const char* a_Name);
	void SetAge(DataPerson* a_Person, int a_Age);

protected:

	std::vector<DataPerson*> m_Persons;

};

Aha, that makes sense. You might want to read data from a Person, but if you want write data to a Person, you will have to use the Controller. So how do we display the information to the screen?

class ViewPerson
{

public:

	void DrawOnScreen(DataPerson* a_Person);

};

Pretty sweet. But what if want find a person by name in our database? We’ll add a method to the Controller:

	DataPerson* GetByName(const char* a_Name);

MVC in PostApocalypse

This pattern is the best I have ever seen for game development. Because you keep everything separated, it becomes a breeze to add new logic or update the rendering. Currently, there are three controllers:

  • ControllerLandscape – Keeps track of the landscape, the chunks and the cells.
  • ControllerUnit – Keeps track of the units on the landscape.
  • ControllerPath – Combines data from the landscape and the units to find a path for a unit between two points.

When you place a unit, you need to know what cell to add it to. So first you do a raycast into the scene to get the cell:

tb::Vec2 mousepos = Mouse::Get().GetPosition();
tb::Vec3 ray_start = RenderManager::Get().ProjectInWorld(mousepos.x, mousepos.y, 0.f);
tb::Vec3 ray_end = RenderManager::Get().ProjectInWorld(mousepos.x, mousepos.y, -1.f, 2.f);
tb::Vec3 ray_dir = (ray_end - ray_start).Normalize();

g_CellSelected = ControllerLandscape::Get().SelectCellRaycast(ray_start, ray_dir);

Then you can create a new unit:

if (Keyboard::Get().Released(KEY_1) && !g_UnitAdd)
{
	g_UnitAdd = ControllerUnit::Get().CreateUnit(g_CellSelected);
	g_UnitSelected = g_UnitAdd;
}

And the highlight the path from the selected unit to the cell under the cursor:

ControllerPath::Get().GetPathTo(g_Path, g_UnitSelected->m_Cell, g_CellSelected);

On the screen:

Beginnings of pathfinding using A*

I can’t stress enough how easy I got this working. I spent two hours doing pathfinding and an hour to put it into its own controller, but when I was done it was completely abstract.

Saving the game

What I’m currently working on is trying to save the game state to a file and loading it back in. You might think this is a bit early in the project, because I don’t have that much state left to save. But I’m doing it this early because it’s easier to keep adding to a save game implementation than it is to retrofit it when the game is done. All you have to do is set up the basics and make sure it continues to work throughout the project.

So I have two classes: GameSave and GameLoad. When you press F5, the following happens:

if (Keyboard::Get().Released(KEY_F5))
{
	GameSave* autosave = new GameSave("autosave.sav");

	autosave->StartSection("Camera");
	autosave->WriteValue("Position", cam->GetPosition());
	autosave->WriteValue("Orientation", cam->GetOrientation());
	autosave->EndSection("Camera");

	autosave->Finish();
}

And when you press F9:

if (Keyboard::Get().Released(KEY_F9))
{
	GameLoad* autosave = new GameLoad("autosave.sav");

	autosave->AddCallback("Camera", LoadCameraState);

	autosave->Parse();
}

It’s a bit clunky, it’s a bit messy, it uses XML and it doesn’t save everything. But it’s a start.

Next week

That’s it for this week, I’ll try and think of stuff to add for next week. :D Maybe… gameplay?

Naww.

TinyImageLoader 1.7.0

It has been a long time since I’ve released a new version. This is mostly because TinyImageLoader went on the backburner. I’m still supporting it though.

What is TinyImageLoader?

TinyImageLoader (TIL) is a very small C++ library that can load PNG, BMP, TGA, GIF, ICO and DDS images. It does so without fluff or safety guarantees.

Here’s an example on how to load an image as an OpenGL texture:

	g_Load = til::TIL_Load("media\\PNG\\avatar.png", TIL_FILE_ADDWORKINGDIR | TIL_DEPTH_A8B8G8R8);
	glBindTexture(GL_TEXTURE_2D, g_Texture);
	glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_NEAREST);
	glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MAG_FILTER, GL_NEAREST);
	glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_S, GL_REPEAT);
	glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_T, GL_REPEAT);
	glTexImage2D(
		GL_TEXTURE_2D, 0, GL_RGBA,
		g_Load->GetPitchX(), g_Load->GetPitchY(),
		0,
		GL_RGBA, GL_UNSIGNED_BYTE, g_Load->GetPixels()
	);

Before loading, you specify the target pixel format. That way you immediately have your data the way you need it.

For a full list of supported formats, please refer to the “Supported formats” page in the supplied documentation.

TinyImageLoader is licensed under the MIT license.

What’s new?

1.7.0 introduces flexible pitch. Pitch refers to the width plus padding of an image. In TIL’s case, I talk about both horizontal and vertical pitch. Why is that handy?

Well, suppose you need to load images on a platform that doesn’t support non-power of two textures. How would you ensure that the image is always a power of two when you load it? You can’t with 1.6.3. In fact, you’d have to load the image and then pad the data manually. Not fun.

In 1.7.0, you can write a function like this:

	void CustomPitchFunc(til::uint32 a_Width, til::uint32 a_Height, til::uint8 a_BPP, til::uint32& a_PitchX, til::uint32& a_PitchY)
	{
		til::uint32 high = (a_Width > a_Height) ? a_Width : a_Height;

		til::uint32 closest = 0;
		til::uint32 move = high;
		while (move >>= 1) { closest++; }
		if (high - (1 << closest) > 0) { closest++; }

		a_PitchX = 1 << closest;
		a_PitchY = a_PitchX;
	}

This function takes the width and height of an image and sets the horizontal and vertical pitch.

Then you can attach the function to the pipeline, after initializing TinyImageLoader.

	til::TIL_Init();
	til::TIL_SetPitchFunc(CustomPitchFunc);

And now your images will always be padded until they are the nearest power of two.

You will most likely not have to use this functionality in your projects. In fact, you're more likely to walk over to your artists and smack them on the head for not sticking to powers of two. But it's nice to have and it has other uses too.

DDS support

1.7.0 comes with improved DDS support. DDS has many forms of compression, but only uncompressed, DXT1 and DXT5 are supported, as these are by far the most common types of DDS textures.

New is support for cube textures and the ability to load mipmaps.

Google Code

You can download TinyImageLoader from Google Code:

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

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 advanced 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 with tons of blackjack casinos games, 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. As a parent or grown up you can also have fun playing a game, Slots UK Casino is for adults and you have the chance to win cash prizes.

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 glow stone.

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. When looking for a different game to play, here you can online casinos revenue.

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 glow stone*. 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, when looking for different games to play while in a safe environment, visit securityxploded. 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)

seo resell