Идея игры и ее особенности

Наверное, все играли в какие-то игры, где нужно составлять слова. Кто не знает, что такое кроссворды? А Города.? Еще популярная игра (не помню названия) — дается длинное слово (мне почему-то запомнилось "электрификация"), и из него составляются всевозможные слова ("электрик", "фикция") и т.д. В общем, таких игр есть множество — как и классических (настолки, листок и ручка), так и электронных.

Но нам же всегда мало, мы хотим больше и лучше, не так ли?

На Западе есть популярная настольная игра, где тоже нужно составлять слова. Называется Scrabble, здесь больше информации. Правила просты — на квадратном игровом поле изначально есть одно слово. Каждый игрок имеет определенные фишки с буквами. В свой ход он должен выложить одну фишку так, чтобы получилось новое слово (или несколько слов). Каждая буква имеет свою ценность (в баллах), поэтому некоторые слова более ценные, чем другие. Редкие буквы (например, "Ф") дают больше баллов.

Мой друг много игрался в Скрэббл, и у него возникла идея — а почему бы не изменить правила игры, чтобы она стала динамичней? Вкратце это звучит так — добавь одну любую букву и собери новое слово.

Сказано — сделано.

Пример: есть игровое поле, где есть слово "ЛАЗ". Добавляем букву "К" — получаем слово "ЛАК". Весьма просто, не так ли?

Некоторые игровые ограничения: можно составлять лишь существительные, убраны собственные имена, географические названия, имена, и т.д. Слова, которые можно использовать лишь в множественном числе, оставлены (например, "очки").

Я сделал прототип игры за пару дней, и она меня увлекла. С ужасным дизайном, с неполным словарем, с тупым ИИ — но это было играбельно и затягивающе.

И я взялся серьезно за разработку.

Железный противник

С чего начинается разработка игры? В нашем случае — с играбельного ядра, которое можно расширить. У нас — это игра с компьютером.

Вообще мы планировали несколько режимов игры. Но первый режим, который должен быть в любом случае — это игра против компьютера. Живых противников может не быть рядом, и здесь компьютер наш выручит. Поэтому я начал написание игры с написания искусственного интеллекта (ИИ).

Как вообще работает ИИ в нашей игре, когда ему переходит ход?

Первый этап — это поиск крайних клеток. Крайней клеткой я обозвал такую клетку, в которой есть буква, и у которой по вертикали или горизонтали есть хотя бы одна свободная ячейка. На картинке ниже такие клетки выделены красными точками.

Зачем нам нужны такие клетки? А потому что мы можем доставить букву в пустую клетку (желтая точка), и получить новое слово. Обратите внимание, что слово собрать можно двумя способами. Можно поставить букву, начать с нее же, и собрать слово ГАЗ (Г первая). Или же поставить букву последней, и собрать слово ЗАД (Д последняя).

Второй этап — после того, как мы нашли все крайние клетки. Задача следующая — составить всевозможные цепочки, и проверить, можем ли мы составить новое слово добавив спереди или позади новую букву. Например, для примера на картинке выше возможны следующие цепочки:

• Л
• ЛА
• ЛАЗ
• А
• ЛА
• АЗ
• З
• ЗА
• ЗАЛ

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

Третий этап — проверить, какие цепочки являются валидными (то есть, можно составить новое слово). Я думаю, вы догадались, какая проблема кажется очевидной — мы не можем использовать тупой поиск, не хватит никаких ресурсов сравнивать миллионы раз строки (если искать, просто перебирая последовательно элементы). На ум сразу приходит использовать бинарный поиск — благо это словарь, и мы можем сравнивать слова.

В общем, так я и сделал. Правда, я это все еще оптимизировал. В чем суть — я хитро отсортировал словарь. Например, у нас есть цепочка длиной в 5 символов. Очевидно, что новое слово будет длиной ровно в 6 символов. То есть, по длине цепочки мы точно знаем длину слова. Поэтому словарь отсортирован сначала по длине слова, а внутри — еще по алфавиту.

Вот пример. У нас есть цепочка СА. Если мы допишем в конец букву Д — получится слово САД, и это очень хорошо. Поэтому что мы делаем:

• ищем в словаре все слова, длиной в 3 буквы (длина цепочки + 1)
• среди этих слов ищем все, что начинаются на СА

Внимательные заметили, что так мы можем найти лишь те слова, которые можно составить методом дописывания буквы к цепочке в конце. А как же те слова, которые можно составить, дописав букву в начале цепочки? Ведь мы можем составить слово, и добавив спереди букву — например, ОСА. Получается, нам нужно искать трехбуквенные слова, которые кончаются на СА -а словарь у нас на такое не заточен.

Выходом стал еще один словарь, который отсортирован также сначала по длине слов, а дальше — по ВТОРОЙ букве слова. Вот выдержка из нашего словаря:

…
ярд
орк
ёрш
оса
иск
ось
дуб
зуб
куб
…

Получается, в обеих случаях мы ищем не полное слово, а подстроку (цепочку).

И, наконец, финальный этап — это сортировка полученных слов по их цене (а цена считается как сумма баллов, умноженная на длину слова), и выдача результата в зависимости от сложности.

Про сложность. Есть хорошая фраза — задача ИИ не выиграть, а красиво сдаться. В данном случае эта фраза себя полностью оправдывает. Дать ИИ играть на полную — означает крах человека, бинарный поиск и современные смартфоны делают перебор вариантов быстро. Поэтому у компьютера есть определенные рамки — он должен держаться от человека +- опреленное количество баллов. Там есть еще дополнительные моменты — например, он не может собирать слова, которые меньше определенной стоимости.

Кстати, в режиме сложности "Ультра" все ограничения с компьютера сняты. Если кто-то знает много длинных слов с буквами Ь, Ф, Ъ — сыграйте, это будет интересный поединок.

Еще один лайфхак, доступный человеку, но недоступный машине. Можно составить слово, и добавив букву в средину этого слова. Например, у нас есть цепочка М*МА (звездочка — это пустая клетка). Если мы добавим вместо звездочки А — получим слово МАМА. Так вот, компьютер так не ищет — пользуйтесь этим, обманывайте железяку (я так делаю постоянно).

Как завершение, хочу сказать следующее. Я боялся, что ИИ будет тормозить — и изначально взялся оптимизировать его по максимуму — никаких строк, массивы char-ов, бинарный поиск с оптимизациями под конкретную задачу. Но ничего не тормозило — вообще. То есть, даже мой древний android-смартфон без задержек отрабатывает задачи перебора даже на поле большого размера. Вывод — не такое уж и слабое железо на смартфонах.

Игровая модель. Работа со словарями

Первое, что нужно в играх такого рода — это словарь. Чем более полный он будет, тем меньше проблем будет от гневных пользователей. Причем если не будет какого-то редкого слова, это не большая проблема. А если не будет слова "кот" — это очень плохо. Поэтому первый этап — составление словаря. Ах да, два словаря — игра-то и на русском, и на английском есть.

Сначала я прошерстил интернет, нашел базу на 37 тысяч слов. Я обрадовался. Но рано. Эта база был результат парсера, написанного автором давным-давно. Как результат, многих слов не имелось, а многие были неподходящие (были имена собственные, и — о ужас — прилагательные). Это было плохо. Мой друг скинул мне еще пару файликов со словами — там дело было еще хуже — попадались цифры, и все в таком роде.

Я написал утилитку на java, которой на вход я даю "мусорный" файл со всеми словами, и даю список допустимых символов. А она выкидывает из словаря повторы, убирает слова, в которых есть неправильные буквы, отрезает слишком длинные слова (вряд ли кто-то составит в такой игре слово больше 15 букв), и сортирует их в алфавитном порядке (не совсем алфавитном, но про это позже). После этого жизнь стала легче. Появилась новая порция слов — добавил их в конец "мусорного" файла, запустил утилитку — на выходе готовые к употреблению слова.

Хочу сказать, что сколько мы не искали словарей, всех слов мы не нашли (да и наверное не найдем никогда). Мы много играли в игру сами, и постоянно выписывали на листик слова, которые потом я вручную добавлял в игру. Этот процесс продолжается и сейчас — хоть новые слова мы находим уже реже и реже. Я подозреваю, что просто у нас словарный запас ограничен 🙂

Следующий этап — у нас был словарь, где было много-много слов, и были такие слова, про которые мы ничего не знали (вы знаете, что такое ТРОТ? А это такой вариант аллюра, лошадь так скачет. Я не знал лично, увы). Что делать с такими словами? Просто выбросить не вариант, потому что есть люди, которые умнее меня и моего друга, и знают, что такое этот зверь ТРОТ. Поэтому я накидал за пару часов утилитку, которая слева список слов, а справа браузер для выделенного слова:

Особенная фишка — это английский язык. Половина слов там одновременно и существительные, и еще половина частей речи. А поскольку ни я, ни мой друг не являемся носителями языка, нам сложно было работать с таким словарем. Мы ограничились тем, что короткие слова (до 5 букв включительно) проверили на en.wiktionary, чтобы там было noun. В общем, подход не очень, но самые плохие слова (типо uivag) мы выбросили. Сразу на вопрос, где взялось такое слово — это не я, это парсер так напарсил, а мы потом расхлебывали :).

Мы прекрасно осознаем, что в словарях есть неправильные слова, и мы потихоньку чистим словари. Но как быть с теми словами, которые не попали в словарь, а люди вводят их? Решение было на поверхности — если человек собирает слово, которого нет в словаре, я отправляю его на Google Analytics. План простой — экспортируем данные как csv, я пишу софт, который вычленит уникальные слова из этого потока. Этот же софт ведет базу, где мы будем помечать слова как просмотренные (если нам отправят 768 раз слово ПОЛКА, я задолбусь 768 раз его добавлять). И потихоньку мы будем усовершенствовать свой словарь.

Также в ближайшем обновлении мы добавим возможность вести пользовательський словарь. Если пользователь точно уверен, что такое слово есть в словаре, а вот у нас его нет — он сможет добавить это слово.

Я еще хотел взять готовые словари (в формате dict), и какие-то библиотеки для работы с ними. Возможно, для других языков мы так и сделаем. Но, боюсь, даже в этом случае мы не покроем на 100% все нужные нам слова языка.

В общем, словари — это очень непросто. Точнее, плохой словарь — это вообще несложно, а вот хороший словарь — это вообще сложно. Сделать с первого раза его не выйдет, и мы сейчас на стадии постоянного их улучшения.

Дизайн

Дизайн — это сложно. Дизайн — это не мое.

У друга есть художник, который нарисовал нам то, что вы видите на скриншотах. Это не тот глянец, которые вы видите в Candy Crush. С другой стороны, текущий стиль приятный глазу, и подходит игре такого типа. Дизайном я доволен.

Как и положено, между дизайном и его размером есть некоторые проблемы. Большие бэкграунды я максимально пережал, сохранил в jpeg — я сохранил размер apk, но ничего не улучшил видеокарте. А вот элементы интерфейса я максимально делал 9patch. Так я добился примерно одинакового отображения на разных экранах.

Если вы откроете игру, и откроете любой диалоговое окно — это 9patch. И синий бэкграунд, и кнопки — это 9patch. Для себя я понял, что я буду максимально настаивать на 9patch там, где это возможно.

А вот картинка для тех, кто не может открыть игру:

Судя по всему, мы выиграли.

Первая версия — Unity3d

Начал я писать на Unity3d. У меня и маленький опыт был (перед этим мы выпустили другую игрушку на Unity3d, но это уже другая история), и 5-я версия бесплатная, и классная система UI с коробки… В общем, соблазнился я.

Что сказать. Игра тормозила. На компьютере все ок, но на телефоне — постоянно были мелкие лаги, хоть я и ничего не делал. Поначалу я грешил на неоптимизированность, но ближе к релизу я заволновался — вроде бы и играбельно все, но мелкие такие лаги портили всю малину. И я начал копать материалы по оптимизации.

Изначально я замерил FPS. Он был плохой — он прыгал. От 10 до 60. Когда он был 10 — играть было плохо, скроллинг панели с буквами был нечеткий и рывками. Я расстроился, и начал применять все советы с интернета. Я ухудшил качество текстур, повырубал V-sync, установил пониже настройки качества. Я принудительно выставил совместимость лишь с OpenGL 2 (писали, что это помогает). В общем, я перепробовал все, что мог.

Потом я сделал следующее — я создал новую пустую сцену. Туда поместил счетчик FPS. И запустил игру. FPS был порядка 50 — я немного расстроился, потому что пустая сцена почему-то отьедает уже 10 кадров — но еще не очень, потому что он (FPS) почти не прыгал. После этого я добавил на сцену Canvas, добавил Image (полноэкранный бэкграунд 480*800, из самым примитивным шейдером — кажется, Vertex Unlit) — и запустил снова. FPS упал до 40. Я вообще расстроился.

У меня не было проблем с архитектурой игры, C# похож на java, кое-где даже покомфортней (привет, свойства), а кое-где — похуже (нет такой свободы в работе с enums). Я написал без проблем весь код, сделал весь UI. Но я ничего не мог сделать с тормозами. Я порылся в интернете, и нашел кучу похожих проблем в других людей. Они писали, что после появления 5-й версии Unity3d их проекты начали ужасно тормозить. Судя по всему, я еще одна жертва. Я пробовал ставить Unity 5.2 (изначально у меня была 5.3), пробовал и бету 5.4. Безрезультатно.

Я разочаровался в Unity3d, надежда зарелизить игру через день-два рухнула. Я не мог выпустить тормозящую пазл-игру, внутренний кто-то во мне не давал это сделать. Я решил вернуться к истокам.

Переход на libgdx

Я создал новый libgdx-проект, и начал портирование игры. libgdx — это то, что меня не подводило. Некоторые вещи там делать дольше (потому что все ручками), но вот к производительности вопросов у меня не возникало никогда.

Архитектура получилась, конечно, совсем другая, чем на Unity3d. Единственная часть, которую я перенес без изменений — это работа со словарями и ИИ. Я тупо скопировал файлы из Unity3d, сменил расширение из .cs на .java, и поправил код. И это нормально работало. Это доказывает, что язык не важен — важен алгоритм и идея.

Главный класс я сделал синглтоном, и обозвал его Core:

private SpriteBatch batch; private Assets assets; private Localize localize;  private WordDict dict; private PlatformInteraction platformInteraction;  private SolutionSearcher searcher;  private float appTimeInSeconds = 0f;  private Core() {}  public static Core getInstance() {     return instance; }  public void setPlatformInteraction(PlatformInteraction platformInteraction) {     this.platformInteraction = platformInteraction; }  public PlatformInteraction getPlatformInteraction() {     return platformInteraction; }  @Override public void create () {     batch = new SpriteBatch();      assets = new Assets();     assets.loadAll();      localize = new Localize();     localize.loadLanguage(Settings.getInstance().getLanguage());      dict = new WordDict();     dict.load("en");      searcher = new SolutionSearcher();     searcher.setDict(dict);      Gdx.input.setCatchBackKey(true);      setScreen(new SplashScreen(batch)); }  public SpriteBatch getSpriteBatch() {     return batch; }  public TextureRegion getRegion(String regionName) {     return assets.getRegion(regionName); }  public BitmapFont getFont(int size) {     return assets.getFont(size); }  public String text(String tag) {     return localize.text(tag); }  public Localize localize() {     return localize; }  public WordDict getDict() {     return dict; }  public Assets assets() {     return assets; }  public SolutionSearcher getSearcher() {     return searcher; }  @Override public void render() {     appTimeInSeconds += Gdx.graphics.getDeltaTime();     super.render(); }  @Override public void dispose() {     platformInteraction.reportGameEvent("app-session-length: " + (int) appTimeInSeconds + " sec");     super.dispose(); }

Написал базовый класс для всех экранов:

class BackPressListener extends InputListener {     @Override     public boolean keyDown(InputEvent event, int keycode) {         if (keycode == Keys.ESCAPE || keycode == Keys.BACK) {             onBackOrEscapePressed();             return true;         }         return false;     } }  public BaseScreen(SpriteBatch batch) {     if (batch == null) {         batch = new SpriteBatch();     }     stage = new Stage(new ScreenViewport(), batch);     stage.addListener(new BackPressListener()); }  @Override public void render(float delta) {     Gdx.gl.glClear( GL20.GL_COLOR_BUFFER_BIT | GL20.GL_DEPTH_BUFFER_BIT );      stage.act(delta);     stage.draw(); }  @Override public void show() {     Gdx.input.setInputProcessor(stage); }  public void addActor(Actor actor) {     stage.addActor(actor); }  public void onBackOrEscapePressed() { }  public Stage getStage() {     return stage; }  public SpriteBatch getBatch() {     return batch; }  public void postTask(float delay, Runnable task) {     stage.addAction(Actions.sequence(Actions.delay(delay), Actions.run(task))); }  public void repeatTask(float interval, Runnable task) {     stage.addAction(Actions.forever(Actions.sequence(Actions.run(task), Actions.delay(interval)))); }  public float getHeightPixels(float percent) {     return stage.getHeight() * percent; }  public float getWidthPixels(float percent) {     return stage.getWidth() * percent; }

Еще сделал несколько вспомогательных классов — типо AssetManager, LocalizeManager. Это тривиальные вещи, их нет смысла описывать даже. Локализацию я беру из json файлов. Хотелось бы отметить, что последние libgdx версии позволяют делать текст цветным, размечая его тегами [COLOR]. Нам как раз это нужно было (в одном Label сделать несколько цветов), и эта возможность пришлась очень кстати.

Игра логически разделена на 4 экрана (сплеш, изначальный выбор языка, меню, игровой экран). Каждый экран — это отдельный package, по возможности элементы экран — отдельные классы (например, есть есть экран меню, и там есть верхняя панель — я эту панель делаю отдельным классом). Потом проще править игрушку.

По возможности логика вынесена в класс Model. Она хранит состояние поля, список слов, которые уже были использованы. Модель же отсылает сообщения, если в ней происходят какие-то изменения. Получился примерно паттерн Model-Presenter. Presenter — это GameScreen, который и показывает картинку, и обрабатывает ввод пользователя.

Для поддержки мультиэкранности я использовал Table. Кто не знает — это менеджер раскладки для UI-елементов. Раскладка называется TableLayout. Можно расставить элементы в ячейках виртуальной таблицы, и настроить каждую ячейку. В общем, довольно удобно, и иногда получается сделать то, что ручками в unity3d сделать затруднительно.

Все картинки в игре я запаковал в один текстурный атлас — 1024*1024. Часть места в атласе осталась еще свободной — это приятно. Это, кстати, один из бонусов libgdx (да и вообще низкоуровневых движков) — можно точно контролировать, какие ресурсы сколько места занимают. Unity3d сама пакует картинки в атласы, но я так до конца и не понял, как она это делает, и главное — как посмотреть финальный результат, сколько атласов и какого размера вышло.

Звуки и музыка. У нас их нет. Баба с возу — кобыле легче 🙂

Текстовые ресурсы — словари, локализация. Локализация — json. Json вообще отличный формат, если размер данных не слишком большой.
Словари — plain text. Как может кто-то заметил выше, словарей у нас по два одинаковых на каждый язык, но по разному отсортированных. Можно сортировать, конечно, и при запуске приложения — но лучше пожертвовать несколькими сотнями килобайт размера приложения, чем тормозами во время запуска.

Шрифты я использовал TrueType, ttf. В libgdx есть библиотека для работы с ними, и она хорошо работает. Памяти такие шрифты едят больше, конечно, чем просто текстура, но и результ получше визуально намного.

Что хочу сказать. Версию на Unity3d я писал около месяца. Переписал же за три дня на libgdx. Сравнение нечестное, потому что уже были подготовленные ассеты, и основная часть логики была написана. Но по моим ощущениям, мне на libgdx нужно было бы все равно меньше времени, чем на Unity3d.

Свою роль сыграли несколько факторов. Первый — я хорошо знаю libgdx, и не очень — Unity3d. Во вторых — идея игры и все что нужно, у меня было. Главное результат. А он такой — вместо 16 мегабайт тормозного APK (это я в Unity3d вырезал поддержку Android x86, чтобы добиться такого размера, а иначе — 20 +) — я получил APK у 8 мегабайт, и быстрый при этом (стабильных 60 FPS в с полноэкранными полупрозрачными бэкграундами). Плюс возможность легко взаимодействовать с android-кодом. Минус — портирование на ios будет сложнее, особенно в свете последних новостей про libgdx. Но портирование на ios непонятно когда будет, и будет ли вообще, а стабильная android версия нужна уже сейчас.

Для себя я сделал вывод — для своих проектов я буду использовать libgdx, и развивать свой движок, построенный поверх него. Это позволит мне не вздрагивать, когда Unity3d обновится до очередной версии, и не думать, как теперь пройдет сборка на Android, не будет ли тормозить приложение. С другой стороны, я буду периодически щупать очередные версии Unity3d — может, ситуация улучшится, кто знает. Мне вообще кажется, что Unity3d идут больше в сторону десктопной разработки, и поэтому не особо заботятся о производительности на мобильных устройствах.

Монетизация

Первая версия полнофункциональная и бесплатная, нет никаких дополнительных возможностей, которые можно купить за деньги. Но есть реклама — баннер в игровом поле внизу, и полноэкранная при завершении игры. В будущем мы планируем ввести некоторые бонусы, которые можно купить за in-app — добавить букву, сменить букву и т.д. Больше пока не задумывались про это. Сначала нужно довести его до ума (словарь и остальные режимы игры), а дальше можно думать про монетизацию.

Планы по апдейтам

Планов масса. Хотим добавить пользовательський словарь. Хочется добавить игру по сети (я планирую набросать сервер на Netty, есть некоторый опыт). Добавим ачивки. Добавим новые языки. Идей очень много, а времени мало 🙂 Но в ближайшее обновление точно войдет пользовательський словарь — это нужная фишка.

Итоги

Эта игра стала второй, которую я написал, и в которую я сам с удовольствием играю. Если спросите, какая первая — она не моя, фриланс, и она еще не вышла. И мне кажется, это верный путь — писать игры, в которые сам с удовольствием играешься. А писать их, такие игры, нужно с удовольствием 🙂

P.S. Если есть какие-то нюансы по вопросам игровой логики или libgdx — пишите в комментариях. Я понимаю, что я не могу охватить всю тему, и что-то мог пропустить, поэтому с удовольствием отвечу на любые вопросы

ссылка на оригинал статьи https://habrahabr.ru/post/282491/