Gamelogic Words

Words is a library with algorithms that are useful for word games.

Most algorithms require a dictionary – a data structure that can do quick lookups on large lists of words. Dictionaries can be loaded from simple text files.

Words can be configured to work with different alphabets, including alphabets that treat multiple characters as a single letter. This is also occasionally useful even in English games. For example, in many word games, the character pair qu is treated as a single letter. Algorithms on words that don't require a dictionary usually require you to specify the alphabet.

These are the basic class types in Words, and most methods revolve around them.

There are also some algorithms that work with grids, the principle class type of our Grids 2 library. Grids is a rich library with many concepts of its own. If you are making a grid game with words, you should also read the Grids documentation here: Grids 2 API.

Words also uses our Extensions library, which is documented here: Extensions API.

Dictionaries

General

The main functionality provided by dictionaries is documented in the IWordDictionary interface.

We also define some extension methods on IWordDictionary.

Our concrete implementation of this interface is the TrieDictionary class. It can perform fast lookups of words and prefixes, but also supports various other searches.

Loading dictionaries

There are two main ways of creating dictionaries:

  • Construct a new TrieDictionary and load words into it in code using one of the extension methods defined on IWordDictionary. Note that you need to specify an alphabet; this is explained in a section below.

  • Add an empty game object to your scene, add the WordsDefaultDictionaryComponent component to it, and attach your text asset containing your list of words. You can then access the dictionary through the Dictionary property of this component. It also allows some basic filtering and lets you select the alphabet from a drop-down list.

Filtering Dictionaries

In some cases, you may want to create a new word list file by filtering a larger word list. We provide some basic filtering through a wizard that you can access through the menu: Tools | Gamelogic | Words | Dictionary Filter.

Setting up the alphabet

For English games, we provide the LatinAlphabet class with two constants of letters defined: one is the normal 26-letter alphabet, the other is one where instead of the letter q, the letter qu is used.

You can also provide your own characters when constructing the alphabet, which should be useful for many other languages.

Searching in the dictionary

The @Gamelogic.Words.IDictionary provides several lookups. For ordinary words, these work as you would expect. But the dictionary also allows you to search for patterns (somewhat simplified regular expressions):

Character Matches

Character Matches Example pattern Matches
? Any single letter. at??? All words that start with at and have five letters, such as atoms
* Zero or more letters. at* All words that start with at, including at itself
+ One or more letters. at+ All words that start with at, except for at itself.

The dictionary does not support more general regular expressions directly. However, dictionaries work with LINQ, so you can always perform (somewhat slow) arbitrary searches like this:

var matches = dictionary.Where(w => WordSatisfiesSomeCondition(w));

which may include matches against full-blown regular expressions.

Other Dictionary Functions

Dictionaries also have some other functions. Consult the API documentation for more detailed explanations.

  • Adding words
  • Whether words with a given prefix exist
  • Finding anagrams and anagrams of subsets
  • Finding subwords

Generators

A generator is a simple class that has a single method Next that gives you "the next item". The particular generator determines what "the next item" means.

Our Extensions library comes with a whole bunch of useful generators, and some extension methods that make them very powerful. You can read more about generators here: Generators.

Words come with word and letter generators to generate random elements from the dictionary or alphabet. For example, the following will return random words that have more than 4 letters, and convert them to uppercase:

var generator = WordGenerator
    .Uniform(dictionary)
    .Where(w => w.Length > 4)
    .Select(s => s.ToUpper());

The shuffle generator shuffles the letters of words, and mutation generators that shuffle words with so that the edit distance between the shuffled word and edit distance is at least a given value. (This is useful for anagram games, where you don’t want random shuffles that are too close to the original).

Letter generators also support generating letters with specific frequencies, and specific conditional frequencies. These are useful for procedurally constructing puzzles with high probability of having words or having letters that can be used to form words.

See the following for more information:

Algorithms

The WordAlgorithms class provides various algorithms for words, including these:

  • Edit Distance
  • Word mutation
  • Largest Common Substring
  • Largest Overlap

See here for more detail: WordAlgorithms.

Grid Algorithms

The GridAlgorithms class provides some functions for working with words in grids, including these:

  • Filling grids with words that cross
  • Determining whether placement of a word in a partially filled grid is legal (as in Scrabble)
  • Finding lines of connected words
  • Finding a word in a grid at a point

See here for more detail: @Gamelogic.Words.Grids.GridAlgorithms.