Опыт веб-разработки при создании игры «Составь слова»
Хочу поделиться своим опытом работы над веб-проектом: реализацией игры «Составь слова». Игра представляет собой известную головоломку, в которой нужно составлять разные слова из одного длинного слова.
Суть статьи — в том, как именно и что конкретно пришлось сделать, чтобы довести всю задумку от идеи до реализации.
Введение
Время от времени я играл в «бумажный» вариант этой игры: мы загадывали длинное слово (например: «Трицераптос» или «Спасо-Преображенский») и за 7–10 минут старались составить как можно больше слов из имеющихся букв. Затем — по очереди называли свои слова, повторяющиеся у соперников вычеркивали. У кого последнего оставались слова — тот и выиграл.
В это же время я искал варианты для проекта, на котором хотел комплексно потренироваться-поучиться веб-разработке.
Требования к проекту были такими:
- не сложный, но и не легкий (по применяемым навыкам и технологиям);
- со сроком реализации примерно в месяц (± две недели, чтобы не затянулся надолго, но и не успел надоесть)
- с применением современных технологий и знаний, которые мне не известны (профессиональное развитие)
- интересный по сути
- общественно-полезный
При всей кажущейся простоте, придумать такую идею сходу у меня долго не получалось. Я обдумывал различные варианты, откладывал, прикидывал — и наконец идея полностью «созрела», обрела четкость и конкретные рамки. Начался этап активных действий, раздумывания остались позади.
План работ, задумки, идеи, архитектура
Общая идея выглядела следующим образом: система будет состоять из бекэнда и фронтэнда (одного или нескольких). На бекэнд возлагается основная нагрузка по расчетам, реализации логики и математики. В виде входных данных на него приходит длинное слово (для разгадывания), результат работы — данные об возможных существующих в русском языке вариантах комбинаций слов. Данные отдаются в формате JSON, бекэнд работает в виде REST-сервиса.
Фронтэнд обращается к веб-сервису с клиентским запросом, получает ответ (набор возможных комбинаций слов) и далее реализует то или иное игровое взаимодействие с пользователем.
На данный момент реализованы два метода АПИ на бекэнде:
http://api.combination.cf/web/words/портал
http://api.combination.cf/web/description/механизм
Первый метод отдает возможные комбинации слов, второй — предназначен для толкования значения конкретного слова.
1. Бекэнд
1.1. Словарь, база слов
Чтобы какие-то слова пользователю выдавать, надо их сначала знать и где-то хранить. Изначально собирался парсить какой-то большой онлайн-словарь или базу знаний (БСЭ, Википедия и т. п.). Но, поискав в Сети, нашел уже собранные и готовые толковые словари в виде отдельных файлов (в текстовом формате). Парсить их, конечно же было намного проще, нежели выкачивать в несколько потоков и разбирать десятки тысяч страниц с сырыми данными. Не говоря уже о том, что список страниц для парсинга так же надо было подготовить.
Базой для игрового словаря послужили следующие источники:
- Ожегов С.И. Словарь русского языка. Ок. 65 000 слов / 16-е изд., — М.: 1984.
- Ефремова Т.Ф. Толковый словарь. — М.: Рус. яз., 1996.
Дабы не засорять игру различными малоупотребительными и редкими словами, отбрасывались некоторые местные, устаревшие слова, прилагательные, множественные формы. Конечно, такая чистка не является совершенной, более корректный результат можно получить привлекая к данной работе человека (желательно филолога).
Но, хорошо хоть в базе данных не оказалось имен, фамилий, названий городов, стран и т. п. (которые есть в энциклопедических словарях, но отсутствуют в толковых).
Если удастся использовать все буквы исходного слова — то получится анаграмма (Анаграмма — литературный приём, состоящий в перестановке букв или звуков определённого слова, что в результате даёт другое слово или словосочетание).
Пример: австралопитек — ватерполистка.
1.2. Размещения без повторений
Итак, у нас есть база слов (базовый словарь). Алгоритм поиска слов сводится к тому, чтобы получить все возможные варианты сочетаний букв и проверить их на наличии в словаре.
Из длинного выражения можно составлять короткие слова различной длины. Значит, нам нужна комбинаторика, раздел «Размещения без повторений». Будем искать слова длиной от 2-х до («длина слова» — 1) символов.
Рассчитаем, сколько вариантов нам надо будет перебрать при различной длине исходного слова. Применим следующую формулу:
Сочетания, размещения, перестановки.
В комбинаторике размещением (из n по k) называется упорядоченный набор из k различных элементов из некоторого множества различных n элементов.
Элементами множества могут быть числа, буквы и вообще любые объекты. Главное, чтобы эти элементы были различными. Т. к. любому объекту можно сопоставить число, то обычно используют конечное множество целых чисел, например, {1; 2; 3; 4; 5}. Хотя множества из букв также можно часто встретить в литературе.
Пример: некоторые размещения элементов множества {А, Б, В, Г, Д}:
по два элемента: {А, Б}, {Б, Д}, {Г, А}
по три элемента: {Д, А, Б}, {А, Б, Д}, {Г, Б, В}
по четыре элемента: {Д, А, Б, Г}, {А, Б, Д, В}
В отличие от сочетаний, размещения учитывают порядок следования предметов. Так, например наборы {А, Б, В} и {В, Б, А} являются различными, хотя и состоят из одних и тех же элементов {А, Б, В} (то есть совпадают как сочетания).
Число размещений без повторений из десяти элементов по K:
| К |
Количество размещений |
| 1 | 10 |
| 2 | 90 |
| 3 | 720 |
| 4 | 5040 |
| 5 | 30240 |
| 6 | 151200 |
| 7 | 604800 |
| 8 | 1814400 |
| 9 | 3628800 |
| Всего: | 6235300 |
Число вариантов для проверки слова длиной N символов:
(суммируем все варианты размещений для слова данной длины)
| N | Количество вариантов для проверки |
| 2 | 2 |
| 3 | 9 |
| 4 | 40 |
| 5 | 205 |
| 6 | 1236 |
| 7 | 8659 |
| 8 | 69280 |
| 9 | 623529 |
| 10 | 6235300 |
| 11 | 68588311 |
| 12 | 823059744 |
| 15 | 2246953104075 |
| 20 | 4180411311071440000 |
| 25 | 2.6652630354867E+25 |
1.3. Бекэнд, YII2
Бекэнд реализован на PHP (YII2), в качестве БД выбран MySQL, кеширование — Memcached. Здесь все просто: создаем отдельный модуль для API, пишем необходимые выборки из базы. Данные отдаем в формате JSON.
1.4. Оптимизация
А вот теперь начинается самое интересное. Требовалось оптимизировать потребление ресурсов приложением и обеспечить быструю работу скриптов. Будем отслеживать использование памяти, процессорного времени, и общее время выполнения скриптов.
Изначально оптимизировал работу с памятью. При передаче слова длиной в восемь символов скрипт падал с ошибкой:
PHP Fatal error: Out of memory (allocated 128545216) (tried to allocate 77824 bytes) in /home/xxxxx/public_html
Этот вопрос удалось решить с использованием генераторов в PHP-коде. Функция стала отдавать данные частями, а не накапливать весь результат в себе. Так же помогло использование функции mysql_free_result ($result) для высвобождения всей памяти, занимаемой результатом запроса к БД. Использование памяти теперь не превышало 12–14 Мб.
Использование процессора. Изначально нагрузка на ЦП составляла 100% во все время работы скрипта. Путем оптимизации кода и разбиения запросов на большее количество мелких (вместо небольшого количества больших) запросов удалось снизить нагрузку до 60–80%.
Оптимизация времени работы скрипта была достигнута путем использования
Memcached для хранения списка всех слов из словаря. Таким образом удалось убрать нагрузку на MySQL и ускорить время получения результата. Как альтернативу я перепроверил так же и файловый кеш FileCache, но здесь результаты были хуже, нежели Memcached.
Результаты оптимизации
На локальном сервере (четырехядерный процессор) время перебора всех комбинаций для слова из 10-ти букв составляет около 22 секунд. При этом два ядра загружены на 60% — 80% постоянно. Eщё 10–11 секунд требуется на проверку всех этих комбинаций в словаре (при использовании Memcached).
Итого (для слова из 10 символов): 22 сек. (генерация вариантов) + 10 секунд (проверка слов) = 32 секунды (общее время работы).
Рост времени линейный: 9 символьное слово проверяется примерно за 3 секунды, 10 символов — за 32 секунды, 11 символов — 350 секунд.
Т.е. слова из 11-ти букв уже недоступны (за разумное время) для перебора вариантов (для данного алгоритма, при данном железе); 10 символов — более-менее терпимо, предел; 9 и менее — достаточно быстро, незаметно для пользователя.
2. Фронтэнд
Я решил написать два фронтенда (исходя из поставленных целей). Один на PHP (YII2) — основной рабочий вариант игры «Угадай слова» с полным пользовательским функционалом; второй на React JS — то же самое клиентское приложение, но с сокращенным функционалом (учебный проект для изучения JS).
Реализовывать функционал игры на PHP (YII2) + верстка Bootstrap было просто, быстро и приятно. Программирование в удовольствие, творческое занятие: создавай (и придумывай, дорабатывай на ходу) интерфейсы взаимодействия с пользователем, диалоговые окна, элементы меню, кнопки; наполняй страницы контентом, выводи информационные сообщения; делай для всего этого дизайн; продумывай редиректы и т. п.
А вот с React JS у меня было все не так просто. Вылезли пробелы в знаниях, пришлось заново повторять и проходить основы JavaScript (помимо изучения особенностей самой библиотеки React JS). Иногда приходилось по несколько часов искать как сделать простейшее действие: скачать файл, вывести блок текста. Но так и планировалось изначально: знаниями HTML + Jquery сейчас уже не отделаешься. В результате получился собранный билд статического сайта для выгрузки на хостинг.
Пользователю игры доступны следующие варианты взаимодействия:
- Игра в слова — загадывается большое длинное слово, можно придумывать варианты и проверять их. Найденные слова сохраняются, ведется подсчет статистики, выдаются информационные сообщения (слово найдено/не найдено, ошибка, комбинация уже отгадана и т. п.). Игру можно отложить и продолжить в другое время. Игру можно завершить или начать заново.
- Поиск слов — просто показываются все возможные комбинации слов, которые можно составить из исходных букв. Некий вариант «подсказки» для игры или отдельный сервис.
- Значение слова — показывается толкование отгаданного или сгенерированного слова. Онлайн вариант электронного словаря.
3. Хостинг
Ничего особо нового здесь не напишу, надо подбирать хостинг под конкретный проект, исходя из требований и возможностей. Из того что удивило — почти у всех компаний качественная техподдержка: отвечают быстро и по сути, помогают решить возникшие затруднения. На собственном опыте убедился, что работа сисадмина и девопса нужна и важна.
Возможные доработки и идеи
Можно двинуться в двух направлениях: оптимизировать бекэнд (сделать работу АПИ более быстрой) и фронтэнд (расширять и «шлифовать» интерфейсы работы с пользователями). Оба варианта являются перспективными.
Бекэнд — наверное, здесь возможностей PHP для быстрой обработки большого объема цифровых данных будет недостаточно. Возможно подойдет написание некого отдельного быстрого модуля или скрипта на ином языке программирования, который бы быстро делал все расчеты. Может, что-то из результатов можно закешировать?! Для быстрой переборки словаря скорее всего стоит посмотреть в сторону NoSQL баз данных. Так же уместным видится увеличение сервисов (возможностей) системы.
По пользовательскому интерфейсу — здесь уместным будет привлечение специалистов по игровому дизайну в качестве консультантов (или сесть самому и пару вечеров подумать, что можно быстро и просто реализовать, все мы играли за свою жизнь в сотни разных компьютерных игр): продумывание игровых интерфейсов, расширение сервисов, добавление регистрации пользователя, сбор статистики, таблицы рекордов, сохраненные игры и т. п.
Не лишним будет, наверное, покрытие кода тестами (приемочными на фронтэнде и юнит-тестами на бекенде). Чтобы не тестировать все вручную снова и снова при обновлениях и расширении функционала.
Заключение
Вообще лингвистика и филология, оказывается, это очень интересно само по себе. Узнал много нового об русском языке в процессе работы над проектом.
Приведу ссылки на исходные коды в репозиториях и ссылки на рабочий сайт (хостинг — базовый VPS, возможно «падение» сайта под «Хабраэффектом»).
Множество багов и неточностей удалось найти и исправить в процессе разработки. Но, некоторые, наверняка остались. Прошу не судить строго, если вы с ними столкнетесь.
Сайт с игрой
Репозиторий с бекэндом (АПИ) и фронтэндом (PHP)
Репозиторий с фронтендом на React JS
