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 →

LINQ Extensions 3: Batch into sub-sequences

After last weeks post on extracting elements out of a list by minimum or maximum keys Ody Mbegbu mentioned on Google+ how he feels that something LINQ is missing is the functionality to batch, page, or divide a sequence into sub-sequences of a given size.

That is what we are going to look at today!

Continue reading →

LINQ Extensions 2: Minimum/Maximum by key

Last week we talked about LINQ, its usefulness, and how to write our own methods to make it even more powerful. Today, I want to look at another couple of methods that I have found handy in a number of different situations. We will look at how to extract the maximum or minimum element of a list by a given key or selector.

Continue reading →

Snake: Smooth and accurate following behaviour

Following another object is one of the most basic movement behaviours an item can exhibit – both in the real world, and in games.

There are many different ways in which objects can follow each other, and depending on the circumstances, different kinds of movement may be appropriate.

Today we will look at one particular kind: A number of objects following another in a trail at regular distances. The movement found in games like Snake.

However – unlike the original Snake and many of its spin-offs – we will neither constrain ourselves to a grid, or to fixed time steps.

Instead we want our solution to follow arbitrary paths with arbitrary accuracy.

Continue reading →

Localised Crepuscular Rays

Crepuscular rays, volumetric rays, or god rays have become a common effect in games. They are used especially in first and third person games – where the player can easily look at the sky – to give the sun, moon, or other bright light sources additional impact and create atmosphere.

Depending on how the effect is used it can emphasize the hot humidity of a rain forest, the creepiness of a foggy swamp, or the desolation of a post-apocalyptic scene.

While there are multiple ways to achieve this and similar effects, the method we will look at in particular is the approximation of volumetric light scattering as a post-process using screen-space ray marching.

In this article we will quickly step through the idea behind this algorithm, and how it is commonly used. We will then show how we can easily expand from there to create a solution that works well with multiple light sources, including some source code and images.

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 →

Random elements, subsets and shuffling collections – LINQ style

LINQ was a major part of the release of .Net Framework 3.5, and has since been one of the most powerful features of the C# standard libraries.

Part of LINQ’s usefulness comes from the clarity that it can give to complex code handling collections.

In fact, it is not only useful for programs where one would classically use queries – like database applications – but can be used in a variety of ways in almost any application, including games. The most common use cases of LINQ deal with selecting, converting, combining and returning items from collections in clearly defined and deterministic way.

When it comes to selecting items from collections, many games have additional requirements not covered by LINQ.

One of them is randomness. We often need to:

  • select a random element from a set;
  • select a subset of elements from a set;
  • or shuffle an ordered collection.

In this post we will construct methods for exactly these purposes, using the same extension method style of LINQ.

Continue reading →