Анализатор команд (Interactive Fiction. Техническая часть) (http://taplap.ru/articles.php?op=show&aid=41)
Отправлено: Olegus t.Gl.
2002-02-07 17:05:57

Interactive Fiction. Техническая часть
АНАЛИЗАТОР КОМАНД
copyright © 2001, 2002 Olegus t.Gl.

 

     Вступление

     В начале 2001 года я наткнулся на небольшую группу людей, которые как и я интересовались текстовыми играми. Помимо обсуждения общих вопросов некоторое место в наших дискуссиях было отведено теме реализации анализатора команд, вводимых игроком на русском языке. Поначалу все (и я в том числе) хватались за голову и сетовали на все, что только можно - падежи, предлоги и тому подобное, видя в них лишь препятствия для создания более или менее сносного алгоритма.
     О том, что такой алгоритм нужен, говорило многое. Некоторые проблемы (склонение слов по падежам, относительно произвольный порядок слов в предложении и прочие) автору игры практически невозможно решить самостоятельно в процессе создания игры. Возня с подобной рутиной может запросто похоронить весь проект. При этом нужно учитывать еще и то, что удобство ввода команд игроком во многом определяет его интерес к самой игре (особенно в России, где популярность текстовых игр практически нулевая).
     Возьмем для примера фразу "Привяжи лошадь к забору веревкой". Игрок может с легкостью заменить ее одним из множества аналогов: "Привяжи к забору лошадь веревкой", "Привяжи веревкой к забору лошадь" и т.п. Если прописать в программе только один или несколько вариантов, то автору придется либо очень долго объяснять игроку, как нужно строить подобные команды, либо надеяться, что он сразу (или после нескольких попыток) наткнется на предусмотренную фразу. Поскольку раздражение оттого, что вполне естественные команды не воспринимаются игрой (и не только в текстовых играх, но и в графических квестах), мне очень знакомо, я начал разрабатывать эту тему и вскоре пришел к мысли, что первая проблема, а именно падежи, вовсе не так уж страшна, к тому же они даже помогают с определением порядка слов в предложении.
     Несмотря на то, что особого энтузиазма на нашем форуме идея не вызвала, я продолжал развивать ее и через некоторое время обнаружил, что все проблемы с особенностями русского языка решаемы, а алгоритм на самом деле довольно прост!
     Поскольку с тех пор ни от кого дельных предложений по этому вопросу не поступало, а алгоритмы, которые были задействованы в играх 2001 года, как мне кажется, весьма далеки от совершенства и удобства игры и работы, то я решился вынести некоторые свои идеи и мысли, касающиеся анализа вводимых игроком команд, на всеобщее обозрение.
     Я не претендую на уникальность этого алгоритма. Ни в коем случае. Идеи, на которых он основан, слишком просты и очевидны, поэтому глупо предполагать, что нечто подобное никем до меня не создавалось. Но тем не менее хочу отметить, что при разработке этого алгоритма чужие работы мною не использовались. Все, ниже изложенное, есть результат лично моих раздумий над этой проблемой. В конце концов метод идентификации человека по отпечаткам пальцев был изобретен двумя совершенно разными людьми, так что можно смело сделать вывод, что человек может самостоятельно дойти и до более сложных вещей, чем разбивка фразы на слова и выстраивание их в нужном порядке.
 

     Немного о структуре предложения

     Сперва, необходимо определиться, что же представляет собой команда игрока и из чего она состоит.
     Все команды в принципе можно разделить на две большие группы. Во-первых, это системные директивы, с помощью которых игрок может узнать содержимое своих карманов ("инвентарь", "инв", "вещи"), запросить какую-либо справочную информацию ("помощь"), выйти из игры ("выйти"), узнать свой статус или количество набранных очков ("статус") и так далее. Это сравнительно небольшая группа, и поскольку директивы, как правило, состоят из одного слова, сложности они не представляют. Во-вторых, это команды, относящиеся к манипулированию предметами и прочими объектами игрового мира. Эта группа намного объемней, и команды, относящиеся к ней, намного сложнее и разнообразней.
     Возьмем за основу обычный вариант, когда игрок управляет одним героем, а общение с другими персонажами сводится к командам герою поговорить с ними или сделать что-нибудь еще. К тому же для большей простоты пока ограничимся следующими частями речи: глагол, предлог и существительное. Этого на первое время хватит, чтобы понять суть алгоритма, к тому же, в принципе, уже достаточно для создания довольно приличной игры.
     Основа основ команды - это глагол, то есть непосредственное указание того, какое именно действие хочет совершить в той или иной ситуации игрок. С положением глагола в предложении все в принципе ясно. В подавляющем большинстве случаев он стоит в предложении первым (про наречия, то есть характеристику действия, как-нибудь в другой раз). Ведь обычно говорят "возьми яблоко", а не "яблоко возьми", "поверни рычаг", а не "рычаг поверни". Поэтому примем это пока за факт. Глагол всегда идет первым.
     Далее в команде игрок перечисляет несколько дополнительных объектов, которые уточняют действие, отвечая на вопросы: "над кем (или чем) он хочет совершить это действие?", "с помощью чего он хочет это сделать?" и тому подобные. Таким образом в предложении появляются существительные, а с ними и проблемы склонения и порядка следования. Отодвинув ненадолго в сторону падежи, подумаем над порядком следования слов в предложении. Он абсолютно неинформативен и не несет никакой смысловой нагрузки. Какая разница, захотел ли игрок привязать к забору лошадь веревкой или привязать веревкой лошадь к забору? Никакой. Поэтому изначальный порядок слов для автора игры не важен. В данном случае ему нужно лишь знать, что игрок хочет привязать, к чему он это хочет привязать и с помощью чего он хочет это сделать. Таким образом все многообразие вариантов написания этой фразы, да и других тоже, можно свести к одному виду, который назовем шаблоном:

ГЛАГОЛ + ОСН.ОБЪЕКТ + ДОП.ОБЪЕКТ + ВСП.ОБЪЕКТ

     Так, для действия "привязать" глагол будет, разумеется, "привяжи" или какой-либо его синоним, а объекты будут отвечать на следующие вопросы:
     ОСН.ОБЪЕКТ - что именно игрок хочет привязать.
     ДОП.ОБЪЕКТ - к чему именно игрок хочет привязать осн.объект.
     ВСП.ОБЪЕКТ - чем именно (или с помощью чего) игрок хочет привязать осн.объект к доп.объекту.

     Именно в такой шаблон и должен преобразовывать любой вариант предложения анализатор команд. Автору остается только брать из этого шаблона информацию и обрабатывать ее нужным ему образом, уже зная что она из себя представляет. То есть, в случае с забором и лошадью, как бы игрок не ввел фразу (в разумных пределах), автор всегда должен получать информацию, скажем, в следующем виде:
     Глагол = "привязать";
     Осн.объект = "лошадь";
     Доп.объект = "забор";
     Всп.объект = "веревка".
     И он уже может исходить из того, что игрок хочет именно привязать, именно лошадь, именно к забору и именно веревкой.
 

     Построение словаря

     Однако прежде всего нужно вспомнить одну простую вещь. А именно то, что изначально компьютер не знает ни о каких глаголах или существительных. Для него каждое слово - это просто набор символов, не имеющий никакого смысла. Значит следует этим наборам символов смысл придать. Проще всего это сделать с помощью словаря, в котором будет храниться информация о тех словах, которые возможно будет использовать игрок. Как уже говорилось, на первое время, ограничим словарный запас компьютера глаголами, предлогами и существительными.
     У каждого слова есть несколько свойств, которые как раз и будут раскрывать компьютеру если и не смысл (в высоком понимании этого термина) слова, то по крайней мере порядок его обработки. Итак, каждое слово будет у нас обладать следующими свойствами:
     Во-первых, это "Форма", то есть слово, как его может ввести игрок. Так у слова лампа может быть много форм: "лампа", "лампы", "лампе", "лампу" и т.д.
     Во-вторых, это "Часть речи", то есть чем является это слово: глаголом, предлогом или существительным.
     В-третьих, это "Основа" слова. Это свойство необходимо рассмотреть подробнее. Дело в том, что в русском языке существует множество слов, которые в определенном контексте могут вполне заменять друг друга, не меняя общего смысла фразы (особенно в игре). Так, допустим, что слова "бери", "брать", "возьми", "взять", "хватай" и т.п. воспринимаются компьютером как одна и та же команда, говорящая о том, что игрок хочет взять что-либо. Поэтому у всех этих глаголов может быть одна основа - "взять". Следовательно, автору игры необязательно будет предусматривать обработку всех этих слов. Описывая реакцию компьютера на желание игрока взять какой-нибудь предмет, он может лишь указать, что для выполнения этого действия игрок должен ввести глагол, основа которого - "взять". То же можно сказать и о существительных. Так, общую основу могут иметь слова "ступенька" и "ступень", или "монетка" и "монета", или "тропа", "тропинка" и "тропка".

     С общими свойствами, пожалуй, все. Теперь рассмотрим отдельно свойства каждой части речи.

     ПРЕДЛОГ. Это самая простая (на данном этапе) часть речи и дополнительных свойств не имеет. В словаре просто перечисляются все предлоги, которые необходимо знать компьютеру в виде такого списка:

Форма

Основа

Часть речи

в

в

предлог

из

из

предлог

к

к

предлог

на

на

предлог

под

под

предлог

     СУЩЕСТВИТЕЛЬНОЕ. Эта часть речи пока будет иметь только одно дополнительное свойство - падеж. Например: "возьми лопату", "ударь лопатой", "подойди к лопате". Следовательно, необходимо внести в словарь все формы данного существительного, которые могут употребляться в игре (это самый простой и быстрый вариант). То есть слово "лопата" в словаре представлена таким списком:

Форма

Основа

Часть речи

Падеж

лопата

лопата

сущ-ное

Именительный

лопаты

лопата

сущ-ное

Родительный

лопате

лопата

сущ-ное

Дательный

лопату

лопата

сущ-ное

Винительный

лопатой

лопата

сущ-ное

Творительный

лопате

лопата

сущ-ное

Предложный

     ПРИМЕЧАНИЕ: Можно ужать этот список немного, указав что у слова "лопате" два падежа - Дательный и Предложный.

     ГЛАГОЛ. Вот о глаголе следует поговорить особо. Чтобы реализовать возможность произвольного порядка объектов в предложении, необходимо для глагола создать таблицу связанных с ним объектов. То есть примерно следующее:

     Глагол: "ПРИВЯЗАТЬ"
     Как может использоваться: Привязать (что-то) (к чему-то) (чем-то/с помощь чего-то)
     Пример: Привяжи (лошадь) (к забору) (веревкой)

таблица 1

Осн. объект

Доп. объект

Всп. объект

Предлог

Падеж

Предлог

Падеж

Предлог

Падеж

-нет-

Винительный

к

Дательный

-нет-

Творительный

 

 

возле

Родительный

с помощью

Родительный

 

 

около

Родительный

посредством

Родительный

 

 

над

Творительный

 

 

 

 

под

Творительный

 

 

     Глагол: "ВЗЯТЬ"
     Как может использоваться: Взять (что-то) (откуда-то)
     Пример: Возьми (книгу) (со стола)

таблица 2

Осн. объект

Доп. объект

Всп. объект

Предлог

Падеж

Предлог

Падеж

Предлог

Падеж

-нет-

Винительный

из

Родительный

-нет-

-нет-

 

 

с

Родительный

 

 

 

 

со

Родительный

 

 

     ПРИМЕЧАНИЕ: Для экономии времени, памяти и нервов советую создавать таблицу не для каждого глагола, а только для основы. То есть, если глаголы "бери", "брать", "возьми", "взять" и "хватай" означают одно и то же действие ("взять"), то целесообразней создать таблицу только для основного глагола, а остальные пусть на нее ссылаются.

     Таким образом эти глаголы будут в словаре представлены так:

     Глагол: "привязать":

Форма

Основа

Часть речи

Таблица

привяжи

привязать

глагол

таблица 1

привязать

привязать

глагол

таблица 1

прикрути

привязать

глагол

таблица 1

прикрутить

привязать

глагол

таблица 1

     Глагол: "взять":

Форма

Основа

Часть речи

Таблица

возьми

взять

глагол

таблица 2

взять

взять

глагол

таблица 2

бери

взять

глагол

таблица 2

брать

взять

глагол

таблица 2

хватай

взять

глагол

таблица 2


     Все слова, которые может в процессе игры ввести игрок, должны соответствующим образом описаны в словаре. Эти данные будут просто необходимы для работы алгоритма.

     Анализ предложения

     Имея на руках образцы заполнения словаря, можно уже перейти непосредственно к алгоритму.
     Заведем себе несколько переменных: Глагол, СущОсн, СущДоп и СущВсп, которые будут описывать шаблон предложения (глагол + объекты). Вычленяя из предложения слова, мы будем постепенно этот шаблон заполнять. Итак, вот сам алгоритм:

  1. Получаем из предложения очередное слово.
  2. Ищем в словаре по колонке "Форма" полученное слово.
  3. Если этого слова в словаре нет, то гордо сознаемся в этом "я не знаю такого-то слова" и прекращаем анализ (или пропускаем это слово и возвращаемся к пункту 1).
  4. Если слово есть, то определяем часть речи.
  5. Если это глагол, то запоминаем его в переменной "Глагол". В свойстве "Форма" этой переменной запоминаем это слово в том виде, как его ввел игрок, а в "Основе" - основу этого глагола. Возвращаемся к пункту 1.
  6. Если это существительное и глагол еще не определен, то начинаем думать. Если предложение состоит только из одного слова (например: "инвентарь", "помощь", "выход" и т.п.), то просто запускаем обработку этого слова. Если же предложение состоит из нескольких, то возможны разные варианты действий. Можно, например, запускать обработку этого слова, представляя, что оно означает направление движения (то есть как бы перед этим словом стоит глагол "иди"). Таким образом у нас будут срабатывать фраза "к озеру" или "озеро" вместо фразы "иди к озеру". А можно просто заявить "Я не понял фразу!" и прекратить анализ ( Еще раз замечу, что для простоты этот алгоритм подразумевает, что глагол стоит в предложении первым).
  7. Если это предлог, то запоминаем его и переходим к пункту 1.
  8. Если это существительное, то начинается самое интересное. Нужно определить, каким из объектов (основным, дополнительным или вспомогательным) является это существительное. Вытаскиваем из закромов таблицу объектов найденного ранее глагола и начинаем ее изучать. Здесь нам очень пригодится сохраненный ранее предлог (если он нам попался, конечно же). Пробегаемся по столбцам сверяя значения предлога и падежа найденного существительного. Если есть совпадение, то запоминаем это слово в соответствующей переменной (если нашли в колонке "Основной объект", то в переменной "СущОсн", если в колонке "Дополнительный объект" - "СущДоп" и т.д.) и переходим к пункту 1. Если слово не подходит, то можно его просто пропустить и продолжить анализ дальше, перейдя к пункту 1.

     И так, пока не пробежимся по всему предложению. После этого заполненный шаблон отправляется в обработку.

     Для примера проанализируем фразу "привяжи веревкой лошадь к забору":

     Таким образом в каком бы порядке в предложении слова не стояли, автор игры всегда получает информацию о том, что:
     Действие = "ПРИВЯЗАТЬ";
     Основной объект = "ЛОШАДЬ";
     Дополнительный объект = "ЗАБОР";
     Вспомогательный объект = "ВЕРЕВКА".

     ПРИМЕЧАНИЕ: Игрок может, конечно, извратиться и написать "привяжи забор к веревке лошадью". Компьютер старательно разложит эту фразу, поскольку написана-то она правильно, но вот что будет делать с ней автор игры?! Но это уже его личное дело.
 

     Заключение

     Конечно же, этот алгоритм представлен в довольно упрощенной форме. Некоторые интересные моменты из него были убраны для того, чтобы сделать его максимально простым для понимания. А так, путем несложных доработок можно ввести в него обработку наречий и прилагательных, местоимений и числительных (вот числительные - это пакость еще та!), а также использование нескольких основных объектов с одним глаголом ("возьми камень и яблоко"), нескольких команд в одной фразе ("подними меч и заруби им гоблина") и т.д.
     Если вас заинтересовала эта тема и вы хотите высказаться по этому вопросу, что-то покритиковать или обсудить, то заходите на форум сайта "Interactive Fiction по-русски", а также пишите мне письма.

Olegus t.Gl.
hello@olegus.ru