Monthly Archives for October 2015

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 →