Как я провёл милых два дня в погоне за random()'ом.



Вчера выложил свою игру «Time Hotel» на Kongregate. И тамошняя публика быстро нашла интересный баг. Суть в том, что курсор-призрак иногда не делает тех действий, которые делал игрок ранее. Не держит кнопку, не убивает зомби и так далее. Об этом мне говорил один из игроков на DevGAMM:Moscow, но мне тогда показалось, что в спешке он мог просто не понять как что работает. Ну и просто иногда тяжело уследить за всеми своими воплощениями. Но сейчас, когда на Kong'е народ валом сообщает о том же, я хочу сказать тому тестеру: «Прости, что не воспринял тебя всерьез сразу! Буду доверчивей в следующий раз».

Давно я рассказывал об эффекте перемотки. Сегодня буду о баге, который вывел меня из себя.
Вчера вечером и сегодня полдня я пытался пофиксить этот баг. Если коротко, то дело было в random()'ном стартовом кадре анимации зомби. В разные заходы его голова могла быть немного в разных положениях и из-за этого курсор-призрак промахивается. Казалось бы проблема легко-находящаяся, почему я долго не мог ее отследить?



По пунктам:
  • Код настолько ужасен, что найти логическую цепочку действий иногда безумно сложно :) Цена быстрой разработки — ужасная читабельность кода и архитектура проекта. Такие дела...
  • Ошибка была наслоенной — во-первых стартовый random(), во вторых анимация зомби обновлялась и на стартовом экране с названием, в-третьих стартовый заход и последующие отличались по инициации объектов. Вероятно, это следствие первого пункта.
  • Воспроизвести ошибку было крайне сложно — нужно выстрелить в голову зомби в уникальные 5 кадров, когда сама голова наиболее сильно наклонена. Я несколько часов потратил только, чтобы понять, что ошибка в принципе связана с зомби.

Хотелось сделать так:



Но перфекционизм взял верх, и я принялся за дело.
Как я искал баг:
  • Сначала долго пытался воспроизвести. Много играл, пробовал разное.
  • Затем понял, что проблема с зомби. Иногда предыдущий успешный выстрел заканчивается промахом. Какого черта?
  • Я убил очень много времени, думая, что ошибка в округлении координат, в переходе из экранных координат в мировые, и так далее.
  • Пришла идея о рандоме. Но починить так просто не получалось — в первый день я пофиксил только несколько наслоений ошибки, оставив без внимания последний. Он давал разницу в два кадра анимации. Воспроизвести ошибку стало крайне сложно.
  • Еще была проблема с тем, что Math.random() я заменил на детерминированный, но зерно из-за разной инициации было разным при первом и последующих заходах. Как бы я вернул одно из наслоений бага, но только уже новым, детерминированным рандомом.
  • Чтобы не пытаться воспроизвести баг каждый раз, пришлось разобрать игру, убрать произвольное распределение объектов на уровнях, а сделать их положения определенными и сохранять положения мышки в SharedObject.
  • Как только баг воспроизвелся, я разобрал игру еще сильнее, загружая курсор из SharedObject, и убрав геймплей с отматыванием времени. Я просто смотрел, как ведет себя курсор и все объекты.
  • Методичность дала свое — сдвиг анимации дал о себе знать. Оставалось только найти, почему кадры зомби инициируются по-разному для стартового курсора и его дальнейшего призрака.

Где-то с мая я делал новую idle-defense-игру, основанную на заходах. То есть зашли, поиграли, добыли кристаллов, погибли и по новой. Так как там очень много всего завязано на произвольном спавне, вероятности критического выстрела и так далее, то создавалось неприятное впечатление из-за того, что в разные заходы, с одинаковой экипировкой, игрок зарабатывал разное количество кристаллов. Поэтому я практически на старте разработки отказался от любых Math.random(), влияющих на геймплей. Перешел на детерминированный рандом, с набором из сотни «красивых» сидов. Немного арта новой игры:



Это помогло мне отловить текущий баг. Сложность была в том, что базовый рандом в Time Hotel у меня использовался везде — как для геймплейных элементов, так и для эффектов и прочего. Это дополнительно затруднило правильное понимание и замену вызова этой функции в нужных местах. Мораль, которую я постараюсь сохранить и в последующих проектах — не использовать Math.random(), и прокидывать такие значения через собственные функции, и, при необходимости, быстро подменить их на детерминированный или нет, рандом.

Это было сложно, но баг я починил. Как-то так…

Играем здесь:
Time Hotel на Конге.
Буду рад пятеркам :)

Всем только хороших случайностей!

Комментарии (15)

0
Как быстрофикс можно было использовать одну область для коллизий зомби.
Только проверить, чтобы не сильно бросалось в глаза, ну был бы небольшой подыгрыш игроку.
0
Не хотел сильно код менять, ибо там и так всё на костылях держится… но в целом — да, что-то такое можно было накрутить, чтобы точно не беспокоиться о зомби!
0
Дружище, надо делать pseudoRandom. Я напоролся на это N лет назад, делая симуляцию прохождения игры в SWF (вместо видео-прохождения на ютубе). Оригинальная идея принадлежала Жене Каратаеву.
0
ну вроде как Math.random() — это тоже псевдо рандом. разве нет? или ты имеешь ввиду детерминированный генератор? если так — то да, теперь я полностью согласен! про симулятор прохождения — это очень круто! снимаю шляпу.
0
Симулятор прохождения не сложнее перемотки времени:) Да, я имею ввиду массив заранее подготовленных значений. При записи и воспроизведении прохождения обнуляется индекс в массиве. И будет праведный рандом.
0
Да, интересная идея. Возьму на заметку такой оригинальный ход, спасибо!
+3
Блоги, живите!
+1
Где-то с мая я делал новую idle-defense-игру, основанную на заходах… Перешел на детерминированный рандом, с набором из сотни «красивых» сидов.

А чем не устроил дефолтный флешевый PRN?
Вроде неплохо справляется на примере твоей игры (если я правильно понял механику):

if (Math.random() * 100 < chance) 
{
    ...
}

Крит. удар - 15%
- Итараций: 100
- Успешно: 16 
- Порядок: 3, 5, 11, 21, 22, 38, 44, 48, 49, 52, 53, 54, 58, 67, 87, 90
-----------------------
Кристаллы - 30%
- Итараций: 100
- Успешно: 32
- Порядок: 0, 8, 10, 15, 23, 24, 29, 33, 35, 36, 38, 40, 41, 42, 43, 50, 53,
		56, 60, 63, 67, 70, 71, 72, 83, 85, 88, 89, 90, 93, 98, 99
-----------------------
Итем - 0.1%
- Итараций: 1000
- Успешно: 1
- Порядок: 842
0
Тоже использую подобную конструкцию, но думал что результат у неё не особо точный и вообще считал что так делать плохо (не шибко разбираюсь в рандомах и думал что процент фактических срабатываний будет довольно сильно отличатся от указанного). Но проверить не додумался (небыло нужды в точности). А оказалось довольно точная штука :) для большинства задач вполне подойдет. При проверке на 100000 итераций погрешность редко переваливала за одну десятую процента.
Спасибо ReMind!
0
считал что так делать плохо
Так же думал. Мол «алгоритм слишком короткий для хорошего результата» :)
Потом увидел эту конструкцию в java-серверах lineage2. Играют люди уже около 10 лет. И от официальных серверов вроде бы отличий в этом плане нет.

погрешность редко переваливала за одну десятую процента
Это не совсем погрешность, а опять же random. Шанс в 50% (по теория вероятности) может выглядеть и так: 0,1,0,0 (25% в итоге).
Поэтому входной и выходные шансы редко будут строго равны. В этом и смысл случайности с равномерным распределением.
Например 20% шанс на 1 млрд итераций у меня сработал 199 984 722 раз (19.99%), а на 10 итераций может вообще ни разу не выпасть.
0
Обожаю вероятности, они такие уютные и непредсказуемые…
Любая вероятность — это значение на бесконечных итерациях.

Люблю такой пример: доктор говорит пациенту, что шанс умереть от операции 1%.
И теперь два случая:
— Доктор сообщает, что последние 99 операций прошли успешно. Должно ли это нас насторожить? Как бы пациент станет сотым… один процент.
— Вариант второй, доктор сообщает, что последний пациент умер от этой операции. Вроде как это должно нас обрадовать — шанс второй неудачи подряд довольно низок.
Как быть?
0
Попробую коротко… штука в том, что враги спавнятся, к примеру, каждую секунду в диапазоне 10-15 метров от базы, и идут к ней. При чистом PRN иногда выходят такие случаи:
1. Спав в 15 метрах, затем через секунду спавн в 12 метрах, а затем в 10… в итоге эти три врага сбиваются в кучку трех идущих рядом, что делает их непобедимыми. И это нормально на самом деле, но ведь в этом же месте при другом заходе может быть такая ситуация:
2. Спав в 10 метрах, затем в 12, затем в 15… и эти три врага в итоге растягиваются в длинную легко побеждаемую цепочку.
Так как при PRN с произвольным сидом эти две ситуации вполне себе могут уживаться, то при старте игры, когда юзер пытается своими действиями повлиять на ход сражения, то очень сильно впечатление, вроде «какого черта они так заспавнились рядом? компьютер — читер!» с точки зрения гейм-дизайна хочется более предсказуемых спавнов, чтобы игрок своими действиями реально влиял на ход сражения.
В итоге я генерю разные сиды, запускаю автоматические битвы и затем выбираю нужные мне. Найти сотню годных сидов можно за час. Для игрока все также будет выглядеть рандомным, но для меня он будет абсолютно предсказуемым и известным, до какого уровня дойдет игрок.
Если говорить с точки зрения рандома, то мне важно не только количество выпадов на N итераций, но и номера успешных итераций. Возможно, не стоит такие задачи изначально перекладывать на рандом, но многие именно так и делают…
0
Если честно, то я ничего не понял. Но очень интересно. Можно немного подробнее о реализации этих сидов?
+1
Да, с утра я туго соображаю, сорри…
1. По поводу спавна. Идея в том, что я не хочу, чтобы каждый отдельный спавн был независимым от других. В этом случае реально бывают случаи, когда обычный рандом спавнит врагов рядом. Из-за этого их невозможно победить. Это плохо.
2. По поводу рандома с сидом. Я использую вот этот код. Задаешь начальное число — сид, зерно (seed). Это просто число. Все дальнейшие генерируемые числа будут выглядеть рандомными, с одним «но» — если мы снова дадим тот же сид, то последовательность полностью повторится. На самом деле Math.random() делает так же, просто у нас нет доступа к сидам, из-за этого мы не можем повторить последовательность.
3. Как я это использую. В итоге я запускаю игру с произвольным сидом, ставлю, чтобы все действия компьютер выполнял сам, за игрока. Далее, при поражении смотрится до какого уровня смогли дойти, если он тот, что нужно — сид запоминается и игра рестартится. Запоминаются двести-триста хороших сидов. При которых игрок точно сможет дойти до нужного мне уровня. Теперь я точно (!) знаю, что игрок может дойти до этого уровня, что, хоть спавн и остальное выглядит рандомным, но я с уверенностью могу сказать, что игра проходима.
0
Я понял. У тебя задача при рестарте повторять предыдущий красивый рандомный спавн, чтобы у игрока опыт накапливался. Тогда да, тут или записывать значения предыдущих красивых спавнов, либо использовать твой метод. Это уже как левел дизайн получается. Затратно ведь по времени. Особенно если что-то поменяется в геймплее. Можно просто при спавне проверять enemyInRange() и при true искать другие координаты/выдавать «рандомные» незанятые. Но еще логичнее просто сделать очереди для монстров, будет очень удобно настраивать.

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