На чем написан тетрис

Тетрис: как советский программист придумал игру, которая покорила детей и взрослых

Получайте на почту один раз в сутки одну самую читаемую статью. Присоединяйтесь к нам в Facebook и ВКонтакте.

Как появился тетрис

Компьютерную игру изобрел программист из СССР Алексей Пажитнов. 6 июня 1984 года головоломку выпустили на советских микроЭВМ «Электроника-60». А в 1987 году фирма из США Spectrum HoloByte запустила продажу игры.

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

Головоломка завоевывает мир

Параллельно с этим американские компании запустили собственную версию тетриса, но уже со звуком и усовершенствованной графикой. А главной «фишкой» стала заставка, на которой появлялись советский космонавт Юрий Гагарин и немецкий пилот Матиас Руст. Тетрис стал настоящей сенсацией, как первая игра, проникшая из закрытого Союза. Однако Стейну так и не удалось договориться о правах, а благодаря журналистам CBS весь мир узнал, что изобретателем игры является Алексей Пажитнов, а не американские разработчики.

Борьба за права

После этого начались длительные разбирательства и суды, чтобы выяснить, кому же «Электроноргтехника» готова передать лицензию. В конечном итоге права достались японской компании-разработчице Nintendo. Пока весь мир играл в головоломку, Пажитнов получил первые дивиденды лишь в 1996 году, когда завершился срок действия лицензии. В это же время программист объединяет силы с Хенком Роджерсом, руководителем Bullet-Proof Software, и вместе они основывают фирмы The Tetris Company LLC и Blue Planet Software. Тетрис становится торговой маркой, поэтому теперь компаниям приходится покупать лицензию из первых рук.

Геймдев, как бы сейчас назвали Пажитнова, переехал в Штаты и получил должность в Microsoft. Там он занялся созданием головоломок Pandora’s Box. В 2005 году Алексей покинул Microsoft, а сегодня работает в «Яндексе». По данным портала Engadget, всего в мире продано свыше 170 млн копий тетриса. А в 2007 году головоломка вошла в топ-10 легендарных компьютерных игр. Само устройство разместили как артефакт в Библиотеке Конгресса США. Сегодня тетрис адаптирован для различных платформ и ничуть не утратил своей популярности.

Понравилась статья? Тогда поддержи нас, жми:

Источник

История алгоритмов рандомизации «Тетриса»

Tetris (прибл. 1985 год)

Первая и оригинальная версия «Тетриса» имела рандомизатор без смещения. На выбор следующей фигуры ничто не влияло, она просто выбиралась и показывалась игроку.

При использовании рандомизатора без смещения возникают ситуации, в которых игрок получает последовательность из одной фигуры (называемую «потопом», flood) или последовательность, в которой отсутствует определённая фигура (называемую «засухой», drought). Мы увидим, как дизайнеры разных версий «Тетриса» пытались слегка сгладить эту проблему.

Хотя рандомизатор без смещения создаёт для игроков самую большую сложность головоломок, он нестабилен и может привести к непобедимой последовательности (PDF). Однако в реальной игре такого не случается, потому что в компьютерах нет генераторов истинных случайных чисел. Генераторы псевдослучайных чисел (ГПСЧ) пытаются имитировать истинную случайность, но не имеют свойств, способных сгенерировать подряд 70 тысяч фигур Z.

Истинная псевдослучайность

Сложность головоломки: 4/5

Предотвращение потопов: 0/5

Предотвращение засух: 0/5

Tetris, Nintendo (1989 год)

Четыре года спустя была выпущена ставшая необычно популярной версия «Тетриса» для NES.

Чтобы снизить количество потопов (повторения) фигур, в рандомизатор была добавлена проверка истории. Эта простая проверка делала следующее:

Запоминание истории на 1 фигуру вглубь и с 1 броском

Сложность головоломки: 5/5

Предотвращение потопов: 2/5

Предотвращение засух: 0/5

Tetris: The Grand Master (1998 год)

Хоть Tetris для NES и улучшил алгоритм по сравнению с рандомизацией без смещения, засухи в нём по-прежнему были часты. В Tetris: The Grand Master (TGM) по сути использовалась та же система, но с более долгой историей и бОльшим количеством бросков.

Благодаря увеличению этих значений не только снизилось количество потопов, но улучшилась ситуация с засухами. В истории сохранялись четыре фигуры, а это значило, что повышалась вероятность получить фигуру, которой уже давно не было. Несмотря на это, в игре по-прежнему отсутствовало строгое правило для предотвращения засух и они всё равно возникали, хоть и намного реже, чем в Tetris для NES.

Запоминание истории на 4 фигуры и с 4 бросками

Сложность головоломки: 4/5

Предотвращение потопов: 4/5

Предотвращение засух: 2/5

Tetris Worlds и далее (2001 год)

Tetris Worlds познакомил широкие массы с генератором случайности. Сейчас он является официальным рандомайзером, в большинстве официальных версий игры после Tetris Worlds и по сей день используется он.

Рандомизаторы на основе истории помогали избавиться от потопов (или, по крайней мере, минимизировать их), но не останавливали засухи. В определённых условиях по-прежнему существовала вероятность получения смертоносной последовательности фигур.

Генератор случайности (Random Generator) решает эти проблемы благодаря использованию новой системы «мешков» (bags). В этой системе список фигур помещается в «мешок», после чего фигуры одна за другой случайным образом извлекаются из него, пока «мешок» не опустеет. Когда он опустеет, фигуры возвращаются в него и процесс повторяется. Random Generator имеет «мешок» размером 7 (7-bag), то есть «мешок» заполненный каждой из 7 тетрамино. Возможны и другие типы «мешков», например 14-bag, в который кладутся по две фигуры каждого типа тетрамино.

Из-за отсутствия у «мешков» истории на их стыках могут возникать потопы длительностью 2 фигуры и «змейки» из 4 фигур (, и т.п.). То есть в каком-то смысле это шаг назад по сравнению с традиционным Tetris для NES.

Фигуры выпадают из 7-bag стабильно, из-за чего он более предсказуем. Легко понять, в какой части «мешка» вы находитесь, и когда может прийти нужная вам фигура. Из-за предсказуемости этого генератора случайности в игру на самом деле можно играть бесконечно. В целом это очень глупая система, и непонятно, как она вообще стала официальным рандомизатором.

Сложность головоломки: 3/5

Предотвращение потопов: 3/5

Предотвращение засух: 4/5

Tetris: The Grand Master 3 — Terror-Instinct (2005 год)

TGM3 сильно продвинула вперёд идею генерации случайности. Это уникальная система, не встречавшаяся ни в одной другой версии.

Вместо «мешка» или истории в TGM3 используется пул фигур. Изначально в нём по 5 фигур каждого типа, то есть всего 35 фигур. При вытягивании фигуры она не удаляется из пула, а заменяется фигурой с самой большой засухой (той, которую давно не вынимали). Постепенно пул всё больше заполняется этой фигурой, пока она наконец не будет вытащена. Это решает проблемы систем «мешков», а также систем с историей; она берёт лучшее от обоих типов рандомизации.

Пул из 35 фигур с 6 бросками

Сложность головоломки: 4/5

Предотвращение потопов: 4/5

Предотвращение засух: 4/5

Выводы

Сложно подвести какой-то определённый итог. Рандомизатор TGM3 кажется более предсказуемым и менее сложным для игрока. Неуклюжий 7-bag ощущается неестественным, но позволяет создавать множество стабильно жизнеспособных стратегий строительства. Недружелюбный рандомайзер, как, например в Tetris для NES, может испортить вам игру, или, что вероятнее, настроение играть.

Можем ли мы улучшить эти системы, делая их кажущимися более случайными, и накладывая жёсткие ограничения на засухи и потопы? Или такие жёсткие ограничения просто делают игру более предсказуемой?

Источник

Как написать свой Тетрис на Java за полчаса

Авторизуйтесь

Как написать свой Тетрис на Java за полчаса

В предыдущих статьях этой серии мы уже успели написать сапёра, змейку и десктопный клон игры 2048. Попробуем теперь написать свой Тетрис.

Нам, как обычно, понадобятся:

Прежде чем задавать вопрос в комментариях, не забудьте заглянуть в предыдущие статьи, возможно там на него уже давался ответ. Исходный код готового проекта традиционно можно найти на GitHub.

С чего начать?

Получение данных от пользователя

Код, честно говоря, достаточно капитанский:

Интерфейсы для клавиатурного и графического модулей

Так как многим не нравится, что я пишу эти модули на LWJGL, я решил в статье уделить время только интерфейсам этих классов. Каждый может написать их с помощью той GUI-библиотеки, которая ему нравится (или вообще сделать консольный вариант). Я же по старинке реализовал их на LWJGL, код можно посмотреть здесь в папках graphics/lwjglmodule и keyboard/lwjglmodule.

Интерфейсы же, после добавления в них всех упомянутых выше методов, будут выглядеть следующим образом:

Отлично, мы получили от пользователя данные. Что дальше?

А дальше мы должны эти данные обработать и что-то сделать с игровым полем. Если пользователь сказал сдвинуть фигуру куда-то, то передаём полю, что нужно сдвинуть фигуру в таком-то направлении. Если пользователь сказал, что нужно фигуру повернуть, поворачиваем, и так далее. Кроме этого нельзя забывать, что 1 раз в FRAMES_PER_MOVE (вы же открывали файл с константами?) итераций нам необходимо сдвигать падающую фигурку вниз.

Сюда же добавим проверку на переполнение поля (в Тетрисе игра завершается, когда фигурам некуда падать):

Так, а теперь мы напишем класс для того магического gameField, в который мы всё это передаём, да?

А инициализировать мы их будем так:

А вот теперь мы переходим к классу, который отвечает за хранение информации об игровом поле и её обновление.

Класс GameField

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

Хранить информацию о поле…

…и о падающей фигуре

TpReadableColor — простой enum, содержащий элементы с говорящими названиями (RED, ORANGE и т.п.) и метод, позволяющий получить случайным образом один из этих элементов. Ничего особенного в нём нет, код можно посмотреть тут.

Это все поля, которые нам понадобятся. Как известно, поля любят быть инициализированными.
Сделать это следует в конструкторе.

Конструктор и инициализация полей

А что это там за spawnNewFigure()? Почему инициализация фигуры вынесена в отдельный метод?

На этом с хранением данных мы закончили. Переходим к методам, которые отдают информацию о поле другим классам.

Методы, передающие информацию об игровом поле

Таких метода всего два. Первый возвращает цвет ячейки (для графического модуля):

А второй сообщает, переполнено ли поле (как это происходит, мы разобрали выше):

Методы, обновляющие фигуру и игровое поле

Сдвиг фигуры

Что мы сделали в этом методе? Мы запросили у фигуры ячейки, которые бы она заняла в случае сдвига. А затем для каждой из этих ячеек мы проверяем, не выходит ли она за пределы поля, и не находится ли по её координатам в сетке статичный блок. Если хоть одна ячейка фигуры выходит за пределы или пытается встать на место блока – сдвига не происходит. Coord здесь – класс-оболочка с двумя публичными числовыми полями (x и y координаты).

Поворот фигуры

Логика аналогична сдвигу:

Падение фигуры

Сначала код в точности повторяет предыдущие два метода:

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

Этот метод возвращает истину, если линию удалось уничтожить. После добавления всех кирпичиков фигуры в сетку (и удаления всех заполненных линий), мы, при необходимости, запускаем метод, который сдвигает на место пустых линий непустые:

Теперь GameField реализован почти полностью — за исключением геттера для фигуры. Её ведь графическому модулю тоже придётся отрисовывать:

Теперь нам нужно написать алгоритмы, по которым фигура определяет свои координаты в разных состояниях. Да и вообще весь класс фигуры.

Класс фигуры

Реализовать это всё я предлагаю следующим образом – хранить для фигуры (1) «мнимую» координату, такую, что все реальные блоки находятся ниже и правее неё, (2) состояние поворота (их всего 4, после 4-х поворотов фигура всегда возвращается в начальное положение) и (3) маску, которая по первым двум параметрам будет определять положение реальных блоков:

Rotation мод здесь будет выглядеть таким образом:

Соответственно, от самого класса Figure нам нужен только конструктор, инициализирующий поля:

И методы, которыми мы пользовались в GameField следующего вида:

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

Форма фигуры и маски координат

Чтобы не занимать лишнее место, здесь я приведу реализацию только для двух форм: I-образной и J-образной. Код для остальных фигур принципиально не отличается и выложен на GitHub.

Храним для каждой фигуры маску координат (которая определяет, насколько каждый реальный блок должен отстоять от «мнимой» координаты фигуры) и цвет:

Реализуем методы, которые использовали выше:

Ну а сами маски координат я предлагаю просто захардкодить следующим образом:

Т.е. для каждого объекта enum‘а мы передаём с помощью импровизированных (других в Java нет) делегатов метод, в котором в зависимости от переданного состояния поворота возвращаем разные реальные координаты блоков. В общем-то, можно обойтись и без делегатов, если хранить в каждом элементе отсупы для каждого из режимов поворота.

Источник

🎮Тетрис на JavaScript: разбираем возможности языка через геймификацию

furry.cat

Тетрис на JavaScript + изучение современных возможностей языка

Лучший способ узнавать новое и закреплять полученные знания – практика. Лучшая практика в программировании – создание игр. Лучшая игра в мире – Тетрис. Сегодня мы будем узнавать новое в процессе написания тетриса на javaScript.

В конце руководства у нас будет полностью функционирующая игра с уровнями сложности и системой очков. По ходу дела разберемся с важными игровыми концепциями, вроде графики и игрового цикла, а также научимся определять коллизии блоков и изучим возможности современного JavaScript (ES6):

Весь код проекта вы можете найти в github-репозитории.

Тетрис

Эта всемирно известная игра появилась в далеком 1984 году. Придумал ее русский программист Алексей Пажитнов. Правила очень просты и известны каждому. Сверху вниз падают фигурки разной формы, которые можно вращать и перемещать. Игрок должен складывать их внизу игрового поля. Если получается заполнить целый ряд, он пропадает. Игра заканчивается, когда башня из фигурок достигает верха игрового поля.

Тетрис – великолепный выбор для первого знакомства с гейм-разработкой. Он достаточно прост для программирования, но в то же время содержит все принципиальные игровые элементы. К тому же в нем максимально простая графика.

Структура проекта

Для удобства разобьем весь проект на отдельные файлы:

Сразу же подключим все нужное в index.html:

Создание каркаса

Для отрисовки графики будем использовать холст – элемент HTML5 canvas. Добавим его в html-файл с инфраструктурой будущей игры:

Теперь в главном скрипте проекта main.js нужно найти элемент холста и получить контекст 2D для рисования:

Здесь мы используем установленные ранее константные значения.

Метод scale используется, чтобы избежать постоянного умножения всех значений на BLOCK_SIZE и упростить код.

Оформление

Для оформления такой ретро-игры идеально подходит пиксельный стиль, поэтому мы будем использовать шрифт Press Start 2P. Подключите его в секции head :

Теперь добавим основные стили в style.css :

Для разметки используются системы CSS Grid и Flexbox.

Вот, что у нас получилось:

Пустое игровое поле

Игровое поле

Поле состоит из клеточек, у которых есть два состояния: занята и свободна. Можно было бы просто представить клетку булевым значением, но мы собираемся раскрасить каждую фигурку в свой цвет. Лучше использовать числа: пустая клетка – 0, а занятая – от 1 до 7, в зависимости от цвета.

Само поле будет представлено в виде двумерного массива (матрицы). Каждый ряд – массив клеток, а массив рядов – это, собственно, поле.

Для создания пустой матрицы поля и заполнения ее нулями используются методы массивов: Array.from() и Array.fill().

Теперь создадим экземпляр класса Board в основном файле игры.

Функция play будет вызвана при нажатии на кнопку Play. Она очистит игровое поле с помощью метода reset :

Для наглядного представления матрицы удобно использовать метод console.table:

Тетрамино

Каждая фигурка в тетрисе состоит из четырех блоков и называется тетрамино. Всего комбинаций семь – дадим каждой из них имя (I, J, L, O, S, T, Z) и свой цвет:

Для удобства вращения каждое тетрамино будет представлено в виде квадратной матрицы 3х3. Например, J-тетрамино выглядит так:

Для представления I-тетрамино потребуется матрица 4×4.

Заведем отдельный класс Piece для фигурок, чтобы отслеживать их положение на доске, а также хранить цвет и форму. Чтобы фигурки могли отрисовывать себя на поле, нужно передать им контекст рисования:

Итак, нарисуем первое тетрамино на поле:

Активная фигурка сохраняется в свойстве board.piece для удобного доступа.

Первое тетрамино на поле

Управление с клавиатуры

Передвигать фигурки по полю (влево, вправо и вниз) можно с помощью клавиш-стрелок.

Перечисления

Вычисляемые имена свойств

Теперь нужно сопоставить коды клавиш и действия, которые следует выполнить при их нажатии.

ES6 позволяет добавлять в объекты свойства с вычисляемыми именами. Другими словами, в имени свойства можно использовать переменные и даже выражения.

Для установки такого свойства нужны квадратные скобки:

Для перемещения тетрамино мы будем стирать старое отображение и копировать его в новых координатах. Чтобы получить эти новые координаты, сначала скопируем текущие, а затем изменим нужную ( x или y ) на единицу.

Так как координаты являются примитивными значениями, мы можем использовать spread-оператор, чтобы перенести их в новый объект. В ES6 существует еще один механизм копирования: Object.assign().

В объекте moves теперь хранятся функции вычисления новых координат для каждой клавиши. Получить их можно так:

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

Теперь добавим обработчик для события keydown:

Метод board.valid() будет реализован в следующем разделе. Его задача – определять допустимость новых координат на игровом поле.

board.js Управление с клавиатуры

Обнаружение столкновений

Если бы фигурки тетриса могли проходить сквозь друг друга, а также сквозь пол и стены игрового поля, игра не имела бы смысла. Важно проверить возможные столкновения элементов перед изменением их положения.

Возможные столкновения одного тетрамино:

Фигурки можно будет вращать, поэтому при вращении тоже нужно учитывать возможные столкновения.

Мы уже умеем вычислять новую позицию фигурки на поле при нажатии клавиш-стрелок. Теперь нужно добавить проверку на ее допустимость. Для этого мы должны проверить все клетки, которые будет занимать тетрамино в новом положении.

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

Пустые клетки матрицы тетрамино при этом не учитываются.

Если проверка прошла удачно, передвигаем фигурку в новое место.

Обнаружение столкновений

Теперь мы можем добавить возможность ускоренного падения (hard drop) фигурок при нажатии на пробел. Тетрамино при этом будет падать пока не столкнется с чем-нибудь.

Вращение

Фигурки можно вращать относительно их «центра масс»:

Вращение тетрамино относительно центра

Чтобы реализовать такую возможность, нам понадобятся базовые знания линейной алгебры. Мы должны транспонировать матрицу, а затем умножить ее на матрицу преобразования, которая изменит порядок столбцов.

Вращение тетрамино в двумерном пространстве

На JavaScript это выглядит так:

Эту функцию можно использовать для вращения фигурок, но перед началом манипуляций с матрицей, ее нужно скопировать, чтобы не допускать мутаций. Вместо spread-оператора, который работает лишь на один уровень в глубину, мы используем трюк с сериализацией – превратим матрицу в JSON-строку, а затем распарсим ее.

Теперь при нажатии на клавишу Вверх, активная фигурка будет вращаться:

constants.js main.js Вращение фигурки при нажатии на клавишу Вверх

Случайный выбор фигурок

Чтобы каждый раз появлялись разные фигурки, придется реализовать рандомизацию, следуя стандарту SRS (Super Rotation System).

Добавим цвета и формы фигурок в файл constants.js:

Теперь нужно случайным образом выбрать порядковый номер тетрамино:

На этом этапе мы можем выбирать тип фигурки случайным образом при создании.

Добавим в класс Piece метод spawn :

piece.js

Игровой цикл

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

RequestAnimationFrame

Для совершения циклических действий удобно использовать метод requestAnimationFrame. Он сообщает браузеру о том, что нужно сделать, а браузер выполняет это во время следующей перерисовки экрана.

Таймер

Нам также потребуется таймер, чтобы в каждом фрейме анимации «ронять» активное тетрамино вниз. Возьмем готовый пример с MDN и немного модифицируем его.

Для начала создадим объект для хранения нужной информации:

В цикле мы будем обновлять это состояние и отрисовывать текущее отображение:

main.js board.js

Заморозка состояния

При достижении активной фигуркой низа игрового поля, ее нужно «заморозить» в текущем положении и создать новое активное тетрамино.

Теперь при достижении фигуркой низа поля, мы увидим в консоли, что матрица самого поля изменилась:

Добавим метод для отрисовки целого поля (с уже «замороженными» тетрамино):

Обратите внимание, что теперь объекту игрового поля тоже нужен контекст рисования, не забудьте передать его:

main.js Отрисовка уже размещенных тетрамино

Очистка линий

Главная задача игры – собирать из блоков целые ряды, которые должны пропадать с поля, освобождая место для новых фигурок.

Добавим в класс Board метод для проверки, не собрана ли целая линия, которую можно удалить, и удаления всех таких линий:

Его нужно вызывать каждый раз после «заморозки» активного тетрамино при достижении низа игрового поля:

board.js Удаление собранных рядов

Система баллов

Чтобы сделать игру еще интереснее, нужно добавить баллы за сбор целых рядов.

Чем больше рядов собрано за один цикл, тем больше будет начислено очков.

При каждом изменении счета нужно обновлять данные на экране. Для этого мы обратимся к возможностям метапрограммирования в JavaScript – Proxy.

Прокси позволяет отслеживать обращение к свойствам объекта, например, для их чтения (get) или обновления (set) и реализовывать собственную логику:

Добавим логику начисления очков в обработчик события keydown :

и в метод очистки собранных рядов:

board.js

Уровни

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

Напишем отдельную функцию resetGame, в которую поместим всю логику для начала новой игры:

Теперь нужно немного обновить логику начисления очков за собранные линии. С каждым уровнем очков должно быть больше.

При сборке каждых десяти рядов, уровень будет повышаться, а скорость – увеличиваться.

Завершение игры

Игра завершается, когда пирамида фигурок достигает самого верха игрового поля.

main.js Сообщение об окончании игры

Следующая фигура

Для удобства игрока мы можем добавить подсказку – какая фигурка будет следующей. Для этого используем еще один холст меньшего размера:

Получим его контекст для рисования и установим размеры:

Осталось внести изменения в метод board.drop :

Теперь игрок знает, какое тетрамино будет следующим, и может выстраивать стратегию игры.

Подсказка о следующей фигурке

Источник