Storing 100 million unique words in a Roblox game

How I fit a 100M+ word dictionary into my game without blowing up devices.

I've been playing word games for a while. I've always wondered where they get their wordlist from and how they are constantly able to keep it up to date. As much as i've been playing these games, I've only a few times come across a word missing that I knew. This was really impresive to me, so I decided to make my own word game inspired by word bomb.

English obviously does not have 100mil words. Not even remotely close to 100 million. Merriam Webster estimates that there are roughly 1 million words in English. So, where did I get 100 million from?

Well, we must consider that this is a word game which means that the words in the Merriam Webster were NOT made for a game. This essentially means that it must be tweaked and modified so that it would be fit for a word game. The players playing the game have knowlege spanning the entirety of the internet. To keep the explanation simple, this means that words such as scientific terms, brands, common acronyms and slang terms must be included. The Merriam Webster also lacks in words containing hyphens and/or apostrophes.

To my surprise, scraping through the GBIF for English terms only (that include hyphens and apostrophes) gave me a total of ~1.5 million new words added to my English dictionary. And do note that this is simply from biology and only for the English wordlist and that there are many other wordlists to go.

Sure, it may include latin words, but that doesn't change the fact that it will be English players playing those words and not Latin speaking players. And even if the word is Latin, it doesn't mean that it's not used in English!

I scraped through multiple websites which I will not disclose and finally got my English wordlist ready. Now, I only had to do the wordlists of other languages that will be in my game. I used the same method as English by first looking through the language's most common dictionnary, and then scraping terms and appending them.

Let's not talk about German. On the first iteration, I got ~4 million words.

The problem

Now that my wordlists are ready, I came across MANY performance issues. Notably iterating through the words to check for validity and such operations. Mobile players were unable to load or crash mid-game. Sevrers take a noticeably long time before letting the 1st player in. And validating words took a lot of computational power.

What I tried first

Don't store words in a table. Store them in a string.

This is very unintuitive, but has the biggest memory impact. The obvious way to make a wordlist is like this:

return {
	'a',
	'aardvark',
	'aardwolf',
	-- ...
}

This is terrible for a few reasons. Every entry is a separate constant in the script's bytecode, every entry costs a table slot, and the Luau compiler has to parse millions of table entries before your game even starts. On top of that, you eventually run into the same 2^26 table ceiling I wrote about in InfArray.

So I stopped storing a table. I store one long string, newline-delimited, inside a long-bracket literal:

return [==[
a
a'asia
a-and-r
a-axes
a-axis
...
]==]

To the compiler this is one constant. It's about as cheap as data can get in a ModuleScript while also being readable.

Chunking the string across many ModuleScripts

One string is great, but you can't put like 25MB of it into a single ModuleScript. Roblox has a source size cap per script.

So each language folder is a bunch of ~150KB chunks:

Wordlist/
├── English/
│   ├── init.luau                       -- parses all the words together
│   ├── Part1.luau ... Part33.luau      -- general dictionary
│   ├── Bio1.luau ... Bio102.luau       -- the GBIF biology dump
│   └── Extras.luau                     -- slang, brands, memes, *my own name*

Extras.luau is the one file I manually edit when a player reports a missing word. I don't have to regenerate everything to add bombaclot.

Making the client build lazy instead of eager

The client doesn't need all six languages. It needs the one being played right now, and it doesn't need it until a round actually starts. A player who only ever plays English never pays for German.

Client-side prediction, using that same wordlist

This is the reason I bothered shipping the wordlist to the client. In a game where turns are timed to the tenth of a second, waiting for a server round-trip to find out your word was accepted feels awful. So the client runs the exact same checks the server is about to run.

Precomputing the prompts instead of searching for them

This Word Bomb style game needs syllable prompts such as ING or TRA, and that prompt has to be fair and there have to be enough words containing it. So, a prompt generator basically. This would suck if it was generated at runtime. The prompt list is auto generated and its frequencies are calculated beforehand, so the game never has to figure out the frequencies or create any prompts.

Binary searching the difficulty curve

Not only are they generated beforehand, but the frequencies are sorted. This allows me to perform binary search to find the eligible count of words. So, picking a prompt is O(log n) and then one math.random.

Capping the bot's dictionary search

The bots have to find a word matching the prompt, which is the one operation that genuinely has to touch the wordlist's contents. It must give a random word, and not have a constant distrubution of responses for prompts. So, here's what I did:

local FIND_LIMIT = 200

function WordService.FindWordWithPrompt(lang: string, prompt: string, exclude: { [string]: boolean }?, maxLen: number?): string?
	local dict = WordService.GetLanguage(lang).Dict
	local collected = {}

	for word in dict do
		if #collected >= FIND_LIMIT then break end
		if (maxLen and #word > maxLen) or (exclude and exclude[word]) then continue end

		if string.find(word, prompt, 1, true) then
			table.insert(collected, word)
		end
	end

	if #collected == 0 then return end
	return collected[math.random(1, #collected)]
end

Hash iteration order also works in my favour here because it isn't alphabetical, so the 200 collected words are effectively a random sample of the dictionary rather than 200 words all starting with aa.

Honestly, it can be more optimized, but this is good enough and there's no need for the micro-optimization.

Storing the wordlists accent-free

This one is a storage optimization disguised as an input one. Accented characters are multi-byte in UTF-8, and storing café and cafe as separate keys doubles entries for no gameplay reason.

So the wordlists are stored accent-free, and input folds down to match:

local FOLD: { [string]: string } = {
	['á'] = 'a', ['à'] = 'a', ['â'] = 'a', ['ä'] = 'a', ['ã'] = 'a', ['å'] = 'a',
	['é'] = 'e', ['è'] = 'e', ['ê'] = 'e', ['ë'] = 'e',
	-- ...
	['œ'] = 'oe', ['æ'] = 'ae', ['ß'] = 'ss',

	['\u{0300}'] = '', -- grave
	['\u{0301}'] = '', -- acute
	-- ...
}

This does three things at once: smaller wordlists, fewer duplicate entries, and a French player on a keyboard without accents can still type etre and have it count. The combining-mark entries are for input that arrives decomposed (e + ́ ) rather than precomposed. Without those, two visually identical strings would hash differently and one of them would be rejected as "not a word".

That's also why NormalizeWord's allowed-character class is just [^a-z%-\']. After folding, there is nothing left outside ASCII, apostrophe, and hyphen.