Name Generator

namegenerator.cpp

#include <alloca.h>
#include <stdlib.h>

#include <string>
#include <vector>
#include <map>

/* Implementation of Nolithius' name generator:
 * Demo: http://www.nolithius.com/game-development/weightedletter-name-generator
 * Code: https://code.google.com/p/weighted-letter-namegen
 *
 * License: GPLv3  (http://www.gnu.org/licenses/gpl.html)
 */

// http://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance
static int damerau_levenshtein_dist(const std::string& sx, const std::string& sy)
{
	if( sx == sy )
		return 0;
	if( sx.empty() )
		return (int)sy.size();
	if( sy.empty() )
		return (int)sx.size();

	size_t size = (sx.size()+1)*(sy.size()+1);
	int* matrix = (int*)alloca(size*sizeof(int));
	memset(matrix, 0, size);

	size_t w = sx.size()+1;
	for( size_t x = 0; x <= sx.size(); ++x )
	{
		matrix[x] = (int)x;
	}

	for( size_t y = 0; y <= sy.size(); ++y )
	{
		matrix[y*w] = (int)y;
	}

	for( size_t x = 1; x <= sx.size(); ++x )
	{
		for( size_t y = 1; y <= sy.size(); ++y )
		{
			int cost = sx[x-1] == sy[y-1] ? 0 : 1;
			matrix[y*w+x] = std::min( { matrix[y*w+x-1] + 1, matrix[(y-1)*w+x] + 1, matrix[(y-1)*w+x-1] + cost } );

			if( x > 1 && y > 1 && sx[x-1] == sy[y-2] && sx[x-2] == sy[y-1] )
			{
				matrix[y*w+x] = std::min( matrix[y*w+x], matrix[(y-2)*w+x-2] + cost );
			}
		}
	}
	return matrix[size-1];
}


struct WeightedLetterGroup
{
	std::map<char, int> letters;
	std::vector<char>	lettersamples;

	void add(char c)
	{
		auto it = letters.find(c);
		if( it == letters.end() )
		{
			auto ret = letters.insert(std::make_pair(c, 0));
			it = ret.first;
		}
		it->second++;
	}

	void expand()
	{
		for( const auto& it : letters )
		{
			for( int i = 0; i < it.second; ++i )
			{
				lettersamples.push_back(it.first);
			}
		}
	}
};

struct WeightedLetter
{
	char letter;
	WeightedLetterGroup next;
	WeightedLetter(char c) : letter(c) {}
};

struct Namegen
{
	const std::vector<std::string> 	seeds;
	std::vector<size_t>		sizes;
	std::vector<char>		firstletters;
	std::vector<char>		lastletters;
	std::map<char, WeightedLetter> letters;

	Namegen(const std::vector<std::string>& _seeds) : seeds(_seeds)
	{
		sizes.reserve(seeds.size());
		firstletters.reserve(seeds.size());
		lastletters.reserve(seeds.size());
		for( size_t i = 0; i < seeds.size(); ++i )
		{
			const std::string& seed = seeds[i];
			sizes.push_back(seed.size());
			firstletters.push_back(seed[0]);
			lastletters.push_back(seed[seed.size()-1]);

			for( size_t j = 0; j < seeds.size()-1; ++j )
			{
				char letter = seed[j];
				char nextletter = seed[j+1];

				auto it = letters.find(letter);
				if( it == letters.end() )
				{
					auto ret = letters.insert( std::make_pair(letter, WeightedLetter(letter) ));
					it = ret.first;
				}
				it->second.next.add(nextletter);

				if( letter != tolower(letter) )
				{
					letter = tolower(letter);
					it = letters.find(letter);
					if( it == letters.end() )
					{
						auto ret = letters.insert( std::make_pair(letter, WeightedLetter(letter) ));
						it = ret.first;
					}
					it->second.next.add(nextletter);
				}
			}
		}

		for( auto& it : letters )
		{
			it.second.next.expand();
		}
	}

	char get_next_letter(char letter)
	{
		auto it = letters.find(letter);
		if( it == letters.end() )
			return 0;
		return it->second.next.lettersamples[rand()%it->second.next.lettersamples.size()];
	}

	char get_intermediate_letter(char before, char after)
	{
		auto it = letters.find(before);
		if( before && after && it != letters.end() )
		{
			const auto& candidates = it->second.next.letters;
			char bestletter = 0;
			int bestscore = 0;
			for( const auto& it2 : candidates )
			{
				it = letters.find(it2.first);
				if( it != letters.end() )
				{
					auto weightedletter = it->second.next.letters.find(after);
					if( weightedletter != it->second.next.letters.end() )
					{
						if( weightedletter->second > bestscore )
						{
							bestletter = it2.first;
							bestscore = weightedletter->second;
						}
					}
				}
			}
			return bestletter;
		}
		else
		{
			return 0;
		}
	}

	bool triple_letter_check(const std::string& s)
	{
		for( int i = 2; i < s.size(); ++i )
		{
			if( s[i] == s[i-1] && s[i] == s[i-2] )
				return false;
		}
		return true;
	}

	bool check_levenshtein(const std::string& s)
	{
		size_t bias = s.size() / 2;
		for( int i = 0; i < seeds.size(); ++i )
		{
			int dist = damerau_levenshtein_dist(s, seeds[i]);
			if( dist <= bias )
				return true;
		}
		return false;
	}

	void generate(int num_to_generate, std::vector<std::string>& generated)
	{
		for( int i = 0; i < num_to_generate; )
		{
			size_t size = sizes[rand() % sizes.size()];
			char firstletter = firstletters[rand()%firstletters.size()];

			std::string name;
			name += firstletter;

			for( int j = 1; j < size-2; ++j )
			{
				if( name[j - 1] )
				{
					name += get_next_letter(name[j-1]);
				}
				else
				{
					break;
				}
			}

			for( int j = 0; j < 5; ++j )
			{
				char lastletter = lastletters[rand()%lastletters.size()];
				char intermediateletter = get_intermediate_letter(name[name.size()-1], lastletter);
				if( intermediateletter )
				{
					name += intermediateletter;
					name += lastletter;
					break;
				}
			}

			if( triple_letter_check(name) && check_levenshtein(name) )
			{
				generated.push_back(name);
				++i;
			}
		}

	}
};

void generate_names(const std::vector<std::string>& seeds, int num_to_generate, std::vector<std::string>& generated)
{
	Namegen namegen(seeds);
	namegen.generate(num_to_generate, generated);
}