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 →

Reusing objects with generic object pooling

Over the last couple of months I’ve been working a lot with WPF (Windows Presentation Foundation), the popular user interface framework by Microsoft.

Something that I noticed quite quickly is how expensive it can be to create WPF controls in code. It could take up to several milliseconds to create a new interface element – even simple ones. The interface I was working on had to be very flexible and could change often however, which would cause it to freeze for noticeable durations regularly, which is unacceptable.

The way I solved that problem is by using object pools.

Continue reading →

Accessing game objects by unique ids

Every game keeps its game object in one or more simple collections. These are used for enumerating the objects every frame to update and draw them.

If objects need to refer to each other, they can easily store a reference to another object, and access it directly. This becomes more difficult however, when we deal with a multiplayer environment. In that case, each game will have its own set of object references, which will never be the same.

That means that we need another way of identifying objects.

Further, we want this access to be fast. After all, a network server might send a client the message that a certain game object should be deleted. If we then need to iterate over all objects to find the correct one, we could easily bog down the performance of our game. Those CPU cycles could be spent much better on something else.

Lastly, whatever data structure we will design for this has to be able to respond appropriately to objects being deleted. See this post for a discussion of how this can be done for simple lists.

Continue reading →

Designing a shader loading and management data structure

Last week we looked at how we can use the builder pattern to build shader programs out of individual shaders. We abstracted away all actual functionality in favour of a clean and easy to read interface.

In that post we assumed the existence of a shader manager – an object that held track of all our shaders and that we could ask for any of them given their type and a string name.

Today we will design a system fulfilling those requirements. Our goal is having this system take over as much work as possible, so that we do not have to bother with any of the details when using it.

Additionally we will look at how we can easily and automatically load shaders from code files – though this part of the system could be easily replaced by one loading them from a different source.

We will take an incremental approach to these topics, building our system step by step, according to our requirements.

Continue reading →

Scheduling cross-threaded tasks using .Net’s BlockingCollection

Concurrency has always been a complicated aspect of computer science.

With modern hardware increasing not only in speed but also in parallelism, it has become necessary to use concurrency in applications to fully exploit available resources.

This is done using threads, which can be thought of as independently running sub-programs of a larger program, or process. Each thread has its own state – including its stack – and executes its own code, but stacks within the same process can generally share other resources at will.

With even the most simple applications being multi-threaded these days, games are no exception. As such, one can hardly find a modern game engine or framework that does not use parallelism in some form or another.

However, today I do not want to talk about how to move complex systems like physics simulation, AI, pathfinding, or even rendering to different threads – like many games do.

Instead I will look at a specific low-level problem:

Assuming we have a multi-threaded program, how can the different threads communicate, and specifically: how can we make sure that certain code is always run on certain threads.

Continue reading →

On Collections

Today I would like to talk a bit (though looking at my notes, probably more than a bit) about collections, collections as in lists of things.

Specifically, I would like to discuss the implementation of such collections in games, and some problems that occur due to the requirements of game development. I will go through some of the solutions I have seen and used myself to solve those problems, and in the end propose, implement and test a new solution I only designed recently.

Continue reading →