Создание случайных имён с использованием регулярных выражений

Материал из Клуб любителей рогаликов
Перейти к: навигация, поиск

Данная статья была написана для RLNews Darren'а Hebden'а

Обоснование

Одна из вещей, которые делают roguelike-игры интересными - использование уникальных предметов и тварей. Иметь в качестве оружия Ringil в Angband'е более интересно чем, иметь меч или даже меч +1. И гораздо больше удовлетворения отделаться от Wormtongue (Гнилоуст, Червослов, Змеиный язык и. т. д.) чем от другого "засланного шпионить человека." В случае Angband'а многие уникальные имена были производными от [использованных в] работах J. R. R. Tolkien и использовались, чтобы вызвать такую же атмосферу, как и в его книгах. Tolkien обеспечивает богатый фон игры и много имен. Тем не менее, что вы делаете если хотите создать ваш собственный игровой мир с нуля? Вы можете написать несколько романов и использовать из них персонажи и предметы, или вместо этого вы можете попробовать использовать генератор случайных имён.

Генератор случайных имён - это программа или часть программы, которая может создавать случайные имена. Имена могут быть использованы для всего чего угодно, от присвоения индивидуальных имён тварям как, например монстрам и лавочникам, до присвоения имён артефактам и названий городам и регионам. Тем более, что некоторые результаты могут быть необходимы для разных целей. Например, Brian может быть хорошим именем для орка, и скромным названием для города, но амулет Brian просто звучит несерьёзно. Одна из характеристик, которую должен иметь хороший генератор имён - гибкость. Он должен быть способен с лёгкостью производить разные виды имён.

Регулярные выражения

Один способ сделать это - использование регулярных выражений. Если вам приходилось работать с классом дискретных структур или *nix guru, вы, вероятно, уже знаете что это такое. Для тех, кто не знает, я приведу краткое объяснение. Регулярное выражение - строка, или последовательная серия букв и символов, которые описывают форму, которую может принимать слово, или, говоря техническими терминами, язык. Одна специальная буква, используемая в регулярных выражениях называется пустой символ (null symbol) или пробел. Обычно она обозначается греческой лямбда (lambda), но я вместо неё использую 0. Каждая буква и каждая группа букв в пределах регулярного выражения также является регулярным выражением.

Некоторые регулярные выражения имеют только одну интерпретацию; например, регулярное выражение "bab" можно представить только как "bab". Тем не менее, для того чтобы придать регулярным выражениям больше возможностей, мы можем использовать ряд операторов. Первый оператор, который мы рассмотрим, - оператор "или", обычно обозначаемый |. "Или" в основном означает, что из двух выражений с каждой его стороны, будет выбрано только одно. Так, если мое регулярное выражение - "b|a", в этом языке, есть два допустипых слова "b", и "a". Я могу, также, использовать скобки, как в математике, чтобы группировать письма, так что "(b|a)b" имеет два правильных слова, "bb" и "ab".

В классических регулярных языках есть ещё два оператора. Один - оператор "и", но это подразумевается в форме, которую я здесь использую. В основном, всякий раз, когда выражение стоит рядом с другим выражением, они - складываются (anded), что означает, что они используются вместе (occur together), в том порядке, в котором они записаны. Другое - *, но вместо того, чтобы использовать * (который может сгенерировать бесконечно длинное слово), мы рассмотрим использование чисел в качестве операторов. Рассмотрим регулярное выражение "a3". Это аналогично третьей степени в стандартной математике и результат этого регулярного выражения - "aaa".

Одна полезная техника, которую мы можем использовать с регулярными выражениями - подстановка. Подстановка в основном подставляет единственную букву в регулярное выражение. Так, если я делаю подстановку в форму "D=(a|b)" и записываю "Db" это будет то же самое, как если бы я написал "(a|b)b". Это особенно применимо к генерации случайных имён. Рассмотрим подстановку "V=(a|e|i|o|u)". Теперь всякий раз, когда мы используем "V" в нашем регулярном выражении, в действительности это будет означать подстановку гласной. Аналогично, мы можем определить согласные как "C=(b|c|d|f|g|h|j|k|l|m|n|p|q|r|s|t|v|w|x|y|z)".

Практическое получение нескольких имён!

Теперь мы можем сделать кое-что интересное. Давайте определим новое регулярное выражение, "CVC". Это очень просто, и теперь мы уже можем генерировать такие слова, как например, "bob", "sig", "mop", "non", и т.п. Здесь очень много комбинаций! Давайте попробеум другое: "C(V2)C". Здесь мы используем цифровой оператор. Подставляя V, мы расширяем это до "C((a|e|i|o|u)2)C", так что мы должны сначала выбрать нашу гласную, а затем устанавливать её 2 раза подряд, а не подставлять 2 разные гласные. Это регулярное выражение создаст имена наподобие "baab", "look", "hiig", и т.п. Давайте рассмотрим ещё одно перед тем как продолжить: "(C|0)VCV". Это регулярное выражение может создавать имена наподобие "moli", а также "ago" из-за части "C|0". Использование нулевого оператора вместе с оператором "или" может быть мощным инструментом и предоставит вам широкий выбор.

Теперь, когда вы понимаете как создать несколько основных имён, давайте продвинемся немного дальше. Вы могли обратить внимание на то, что некоторые из полученных имён, которые я перечислил выше кажется нереальным; они не звучат как настоящие имена. Как мы можем это улучшить? Хорошо, и снова нашим другом оказывается подстановка. Я собираюсь определить две новых подстановки, P для префикса (приставки) и S для суффикса. Идея приходит, когда посмотришь на имена. Возьмите несколько, например "Brian", "Scott", "Steve", "Frank", "Casandra", и "Kristen". Все эти имена, как и те что мы обыкновенно видим, в начале или на конце имеют комбинации букв подобно "br" в "Brian" или "nk" в "Frank". Всё, что мы сделаем - возьмём эти префиксы и суффиксы и поместим их в подстановку. Итак, мы получим "P=(br|sc|st|fr|kr)" и "S=(tt|nk|dra|sten)".

Теперь давайте поиграем с нашими новыми игрушками. Помните как имена из "CVC" были не очень впечатляющи? Хорошо, давайте посмотрим, к чему мы придём когда используем "(C|P)V(C|S)": "lott", "brik", "stink", "wodra", "juk", "kosten". За исключением "stink" (зловоние, вонючка), это достаточно хорошие имена, и регулярное выражение для их генерации было красивым и простым. Чтобы устранить имена подобно "stink", мы можем использовать фильтр, который устраняет набор слов, которые мы не хотим получать. Ниже я покажу реализацию такого фильтра.

Реализация

В моей реализации, как я уже упоминал, я рассматриваю оператор конкатенации как явный . Это упрощает [некоторые] вещи в коде но делает его чуть более сложным для того, кто создаёт регулярные выражения. В основном, вам нужно будет использовать несколько больше скобок чем Вы могли ожидать. Рассмотрим приведённый выше пример "C(V2)C". Вы могли ожидать, что способны получить тот же эффект без скобок. Но из-за строковой реализации, в случае непарности скобок может произойти дублирование как согласных так и гласных.

Теперь, с этим предостережением, давайте приступим. У меня есть класс Java, который берет регулярное выражение как аргумент для своего конструктора. Каждый раз, когда вы хотите имя в этом формате, вы можете вызвать метод getName(), и будет сгенерировано произвольное имя этого типа. Наибольшую часть работы классы выполняет в private-методе , который называется parse(), который вызывается из getName(). Ниже я построчно проанализирую его, чтобы вы могли понять что происходит.

      public String parse(String s)
      {
         int index;
         char current;
         StringBuffer b;
         Vector leaves;

         leaves = new Vector();
         b = new StringBuffer();
         index = 0;

Этот код устанавливают переменные, используемые для всего метода, и инициализируют их. Индекс отслеживает где мы в строке s регулярного выражения. Current - временная переменная, которая позволит нам изучать каждый символ по отдельности. B - буфер, использующийся для временного хранения строки. Leaves - вектор (Vector), который будет содержать все возможные результаты для различных "или" в этом выражении. Я называю его leave (лист), поскольку он подобен листьям дерева. Выражение "a|b|c" может быть представлено как:

                                 * 
                                /|\ 
                               / | \ 
                              a  b  c 
         while (index < s.length())
         {
            current = s.charAt(index);
            if (Character.isLetter(current))
            {
               b.append(current);
               index++;
            }

Это устанавливает цикл while, который будет работать пока индекс не станет больше или равным длине строки. Current'у присвается символ по индексу и мы начинаем формулировать, что хотим сделать. Сначала, если current - буква, мы добавлим его в буфер и увеличим индекс, а затем перезапустим цикл.

            else if (current == '|')
            {
               leaves.add(b);
               b = new StringBuffer();
               index++;
            }

Если current - оператор "или", мы добавим строку в наш буфер на вектор листов и создадим новый буфер. Мы увеличиваем индекс и цикл.

            else if (current == '(')
            {
               int count = index + 1;
               int openParens = 1;
               while (openParens > 0)
               {
                  if (s.charAt(count) == '(')
                  {
                     openParens++;
                  }
                  else if (s.charAt(count) == ')')
                  {
                     openParens--;
                  }
                  count++;
               }
               count--;
               b.append(parse(s.substring(index + 1, count)));
               index = count + 1;
            }

Чуть сложнее чем предшествующие части случай, когда мы видим открытую скобку, нам нужно найти соответствующую ей закрытую скобку. Мы не можем просто использовать первую попавшуюся, потому что мы хотим поддерживать вложенные скобки. Как только мы узнаем где находятся открытая и закрытая скобки, мы возьмём то что в скобках и пропарсим это подобно тому как мы делаем с целой строкой. Результат этого парсинга добавим в наш текущий буфер. Затем мы увеличим индекс предыдущих закрытых скобок и завершим цикл.

            else if (Character.isDigit(current))
            {
               int count = index + 1;

               if (current != '0')
               {
                  while (   (count < s.length()) 
                         && (Character.isDigit(s.charAt(count))))
                  {
                     count++;
                  }

Если у нас есть число, мы хотим определить, что это за число. Хотя я не знаю, как часто будут использоваться числа более 9, можно предусмотреть поддержку любого int . Также, поскольку мы используем '0' в качестве пустого символа, здесь мы должны сделать об этом специальное примечание. Приведённый выше цикл while просто подсчитывает количество цифр, которое мы имеем в ряде.

                  Integer exponent;
                  try
                  {
                     exponent = Integer.decode(s.substring(index,count));
                  }
                     catch (NumberFormatException ex)
                     {
                        exponent = new Integer(0);
                     }

Это Java'вский метод преобразования String в int. Он чуть более сложен чем atoi(), но и не так плох.

                  StringBuffer temp = new StringBuffer();
                  for(int i = 0; i < exponent.intValue(); i++)
                  {
                     temp.append(b);
                  }
                  b = temp;

Здесь мы просто копируем весь наш буфер столько раз, сколько определено показателем. Заметим, что это повлияет на всё как от начала регулярного выражения, так и до последнего оператора "или". Это отчасти вариантная запись, но работает, если вы используете скобки для разделения показателей.

               }
               index = count;
            }
         }

Наконец, нам нужно установить индекс равный отсчёту. Если бы мы отсчитали '0', отсчёт должен быть (индекс + 1), так что '0' пропускается. Если это будет любое другое число, отсчёт будет тем местом выражения, где закончились цифры. Последняя конечная скобка выше закрывает весь наш цикл.

         if (leaves.size() == 0)
         {
            return b.toString();
         }

Если leaves пуст, это означает, что в выражении не было никакого оператора "или". Мы просто возвращаем буфер поскольку не из чего выбирать.

         else
         {
            leaves.add(b);
            int whichString = generator.nextInt(leaves.size());
            return (leaves.get(whichString)).toString();
         }
      }

Если leaves не пустой, нам нужно выбрать один из возможных результатов оператора "или". Каждая возможность должна иметь одинаковый вес, но генератор случайных чисел в Java при небольших числах несовершенен. Тем не менее вы всегда получите правильный результат, если имена в нём распределены неоднородно. Здесь мы добавляем конечную string (строку) из буфера, выбираем произвольный индекс Vector leaves и возвращаем индекс, как сгенерированное нами имя.

Здесь немного больше чем класс, но не очень. Просто конструктор и метод getName() который просто вызывает parse(). Вы можете захотеть добавить возможность делать подстановки перед выдачей окончательного имени, или вы можете решить делать их после выдачи с помощью специального класса подстановки. Он должен быть достаточно простым для осуществления, поэтому мне нет необходимости обсуждать его здесь.

Фильтрация

Некоторые могут быть содержимое, чтобы иметь имена подобно "stink" появлялись в их игре, а другие не могут. Особенно родителям может не понравиться, что на их детей могут повлиять бранные слова из игры, даже если они и не используются в качестве брани. К счастью, сравнительно просто обеспечить в генераторе имён фильтр, чтобы предотвратить создание имён такого рода. Вот некоторый псевдокод Java о том, как использовать фильтр:

   do
   {
      String name = nameGenerator.getName();
   } until (!filter.isBad(name));

Теперь, написание фильтра - лишь чуть труднее, чем его использование. В Java, это красиво и просто.

   import java.util.*;
   class Filter extends Hashtable
   {
      public Filter()
      {
         String[] badWords = 
         {/* заполнить плохими словами в нижнем регистре */};

         for(int i = 0; i < badWords.length; i++)
         {
            put(badWords[i], new Object());
         }
      }
      public boolean isBad(String s)
      {
         return (get(s.toLowerCase()) != null);
      }
   }

Этот класс расширяет встроенный в Java класс Hashtable. Он создает массив Strings, которые вульгарны. Затем он складывает их в хэш-таблицу (hash table). Когда вы хотите проверить слово, которое вы желаете фильтровать, он просто хэширует его и смотрит, существует ли такое слово в таблице или нет. Вы можете также применить любую комбинацию хранение/поиск, какую вы предпочтёте, но это так легко осуществить в Java, что кажется, что это тот путь, которым нужно идти.

Вывод

Надеюсь, что после чтения этой статьи вы знаете немного более о генерации случайных имен. Для всего, что я обсуждал выше, я предоставляю исходник. Если у вас есть какие-нибудь вопросы или комментарии, свободно обращайтесь ко мне по email'у bcr19374@pegasus.cc.ucf.edu. Закачать Source.



Автор: Brian Robinson.
Источник: Random Name Generation Using Regular Expressions.
Перевел: Дмитрий О. Бужинский [Bu], 02.06.2005.