Implementing type-safe position, velocity and acceleration types

As discussed in this post there are some potential advantages in representing physical quantities like position, velocity, and similar in a type-safe way.

Instead of using simple floating point types, we can write our own wrapper types that have semantic meanings like ‘length’, ‘speed’, or ‘time’ and only allow physically correct operations between them.

That is exactly what we will look into here. We will implement the basic types for such a system, and show what operations between them are relevant and well defined.

Continue reading →

Design patterns in game development: parsing OBJ files

Today we will take a look at a common task in game development: parsing asset files – from a code design standpoint.

Using the example of Wavefront OBJ files, we will explore the usefulness of thinking about our code using design patterns.

Our goal will not be to use design patterns to create code. Instead, I would like to highlight how much of our code is full of such patterns – whether we think about them or not – and how realising this can help us communicate more efficiently with other programmers.

Continue reading →

Roche Fusion Technical Recollection

A few days ago I was idly scrolling through my twitter history reminiscing about the last few years of my activities as game developer. For about two years a major part of that – and my life in general – has been Roche Fusion, the game project I started together with Tom Rijnbeek in September 2013, and which we finally finished – with a team of 7 – in January 2015.

For today’s post I thought I step through the major points of Roche Fusion’s early development from a technical standpoint, and give some insight in our development process.

Continue reading →

Using arrays to speed up static tree traversal

Over the last two weeks I wrote about how to construct and query a string prefix-trie. We used the data structure to quickly find all strings with a given prefix, and to find the longest common prefix in that list.

Today we will take a look at how we can use arrays to improve performance even further. We will also take a closer look at the run-time of our algorithms from last week’s posts and show how our new approach is significantly better.

While we are looking at the example of a prefix-trie, the same method can be applied to any static tree.

Continue reading →

Matching string prefixes using a prefix-trie 2

After discussion the general problem of matching string prefixes two weeks ago, we starting on the implementation of a prefix-trie to solve the problem efficiently last week.

Our implementation so far is able to quickly construct a prefix-trie from a list of strings. What is still missing is any kind of functionality to query the data structure for information.

Today we will take a look at how to use this data structure to enumerate all strings with a given prefix, and how to obtain the longest common prefix in that list.

Continue reading →

Matching string prefixes using a prefix-trie

Last week we discussed the problem of matching string prefixes and designed algorithms on the basis of a sorted list of strings.

Our solutions had good runtimes given the constraint, however we can do much better by using a specialised data structure instead.

The data structure in question is a trie, also called radix tree or prefix tree.

Today we will look at how to construct exactly that.

Continue reading →

A discussion on matching string prefixes

Strings are an exceptionally flexible data type. They can be used to represent virtually any kind of data, or even behaviour – think of clear text script files.

With all this flexibility also come certain drawbacks however. Doing a lot of computations on or using strings can be very expensive – especially in languages like C#, where strings are immutable.

This is why especially in game development one has to find a balance between the use of strings, and more statically typed code. However, even if we optimise entirely for performance, there will always remain use cases for strings.

Today I want to look at one specific use case of strings: matching string prefixes.

Continue reading →

DIY: Useful LINQ Extensions

LINQ (Language Integrated Query) is one of the most powerful features of modern .NET. Powered by generics, lambda expressions, method chaining, extension methods, and deferred execution it allows to write extremely concise code when dealing with collections.

In this post we will look some useful LINQ extensions I have written over the years to make my work with LINQ even easier and quicker, and help me simplify my code.

Continue reading →