Игра Snake в 93 байта

    image

    История создания


    «Змейка» (Питон, Удав) как ее называют в народе — одна из первых игр цифровой (компьютерной) середины 1970-х годов.

    В то время игры выпускались на отдельном игровом автомате, например, известны такие игры как «Space Invaders», «Pac-Man», «Arkanoid» и другие. Обычно, на аркадных автоматах того времени была предустановленна всего одна игра, а сам автомат был стилизован под эту игру.

    «Змейка» имеет незамысловатый геймплей, в котором игрок управляет движущейся линией, изображающей змею. Игрок может изменять направление движения змеи «поворачивая» на 90 градусов. Цель игры — «наезжать» змеёй на точки изображающие кроликов. Каждый съеденный «кролик» увеличивает длину змейки. Сложность заключается в том, что змея не может пересекать саму себя.

    С момента своего появления, «Змейка» пережила множество воплощений на разных устройствах. Например, на некоторых устройствах, вместо линии змея могла отображаться в виде строки символов из-за технических ограничений. В других, более современных компьютерах, змея могла поворачивать на произвольный угол, а не только на 90 градусов.

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

    Идея «Змейки» популярна и сейчас — недавний «бум» пришелся на реинкарнацию в виде многопользовательской сетевой игры «slither.io».

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

    Я, в свою очередь, тоже практиковался в написании этой игры на разных языках и платформах. Однажды, читая электронный журнал на «ZX-Spectrum», я наткнулся на статью, автор которой уложился в 256 байт запрограммировав «Змейку». В конце статьи автор заявил, что вряд ли кому-то удастся написать игру короче, чем 256 байт на платформе «ZX-Spectrum». Но через некоторое время появилась версия в 121 байт от другого автора. Правда при уменьшении размера кода, пострадал геймплей.

    Через какое-то время, общаясь с одним начинающим программистом, я посоветовал ему написать хоть какой-то законченный проект. Тогда речь зашла про «Змейку». Я вспомнил про то, что это может иметь соревновательный характер и решил подогреть интерес своего собеседника сказав ему, что напишу свою реализацию игры с упором на минимальный размер кода. Для усложнения задачи я решил использовать всё ту же платформу «ZX-Spectrum» и Ассемблер процессора «Z80».

    Первую версию игры я написал за пару часов и «весила» она чуть больше 150 байт. Тут я вспомнил про статью в электронном журнале, и решил побить рекорд в 121 байт. Итак моя следующая версия уже весила 100 байт. Написание заняло уже 6 часов. После этого я долгое время не возвращался к этой игре.

    Позже, разбирая папку со своими проектами и исходниками, я наткнулся на исходный код своей «Змейки» и понял, что код можно модифицировать и сократить ещё на пару байт. Процесс оптимизации занял целый день, а код сократился всего лишь на 5 байт. Но тем не менее код игры стал «весить» рекордные 93 байт.

    Технические подробности


    Технические подробности игры snake в 93 байт

    • 58 строчек кода без комментариев
    • Полная релоцируемость программы (размещение в любой адрес без перекомпиляции)
    • Не используется стек
    • Используется только основной набор регистров: a,b,c,d,e,h,l и r как генератор случайности
    • Без использования процедур ПЗУ
    • Честная инициализация экрана и бордера
    • Классическое управление клавишами: 6,7,8,9 (Sinclair Joystick)
    • Каждую инициализацию псевдослучайным образом расставляться кролики

    Код состоит из 3 блоков

    • Инициализация переменных и экрана
    • Опрос клавиш на нажатие и изменение направления движения
    • Обработка игровых событий

    Регистры используются в основном как именные переменные, так:

    • Регистр a – используется по как промежуточный результат и манипулятор с отдельными битами
    • Регистровая пара bc – это направление движения принимает всего 4 значения за весь игровой процесс: #ffe0, #0020, #0001, #ffff
    • Регистровая пара de – это текущий индекс обработки массива (атрибут)
    • Регистровая пара hl – это текущие координаты головы змейки в адресном пространстве атрибут

    В блоке инициализации de и hl, поменяны местами для сокращения логической операции распределения кроликов

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

    Код игры


    begin	ld de,#598f;snake xy
    	ld hl,#5aff
    	ld b,l
    	ld c,l
    ;---
    rabbit1	ld (hl),b
    	ld a,r
    	cp l
    	jr z,rabbit2
    	inc (hl)
    rabbit2 dec hl
    	bit 3,h
    	jr nz,rabbit1
    	ex hl,de
    ;---
    l1	xor a
    	out (#fe),a
    clr	ld (de),a
    	dec de
    	bit 6,d
    	jr nz,clr
    ;---
    ;	xor a
    	in a,(#fe)
    	rra
    	rra
    	jr c,$+5
    	ld bc,#ffe0
    	rra
    	jr c,$+5
    	ld bc,#0020
    	rra
    	jr c,$+5
    	ld bc,#0001
    	rra
    	jr c,$+4
    	ld b,e;ld bc,#ffff
    	ld c,e
    ;---
    	ld (hl),33
    	ld d,#5a
    move1	ld a,(de)
    	dec a
    	cp 254
    	jr nc,move2
    	ld (de),a
    move2	jr nz,move3
    	dec (hl)
    move3	dec de
    	bit 3,d
    	jr nz,move1
    ;---
    	ld a,(hl)
    	and %00100000
    	add hl,bc
    	or (hl)
    	inc a
    	cp 7
    	jr nc,begin
    	ld a,h
    	inc a
    	and %00000011
    	jr z,begin
    	jr l1
    


    Алгоритм


    Изображение на экране в данном случае доступно в памяти как одномерный массив 32*24. Каждая ячейка занимает один байт памяти. Меняя значения этих ячеек можно задавать цвет каждого «квадратика» на экране. Формат в битах %FBPPPIII где: F-Flash бит «мигания» раз в секунду (обмен ink на paper), B-Bright повышенная яркость, PPP-Paper 0 до 7, III-INK 0 до 7.

    • 0 000 Чёрный
    • 1 001 Синий
    • 2 010 Красный
    • 3 011 Пурпурный
    • 4 100 Зелёный
    • 5 101 Голубой
    • 6 110 Жёлтый
    • 7 111 Белый

    Таким образом «Кролики» кодируются значением 255 (мигающий, яркий, белый фон, белый цвет), пустое пространство кодируется значением ноль (черный фон, черный цвет)

    В отличие от других реализаций, под хранение «змейки» не выделено отдельного массива в памяти, и она сразу находится в «экранной» памяти. Длина змеи и количество «съеденных кроликов» хранится в виде цвета головы, так как большее значение выглядит «ярче», происходит простая арифметика, пробегается весь массив и складывается значение количество кроликов к базовому цвету головы. Движение же всего тела змеи происходит обработкой всего массива где, каждое значение просто уменьшается на один до черного цвета.

    Обработка игровых событий — это всего несколько логических ветвлений «IF», при перемещении головы в следующий индекс массива, проверятся предыдущее значение, если там не кролик и не пустое пространство, то змея «наехала» сама на себя. Ещё один «IF» если голова змеи имеет максимальный цвет после проверки массива, то все кролики съедены.

    UPD Обновил исходники, так как смог оптимизировать с 95 байт до 93 байт, без потери функциональности.
    UPD2 Добавил раздел Алгоритм.
    Поделиться публикацией
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 25

      +4
      А есть какой-нибудь онлайн-компилятор, чтобы не ставить инструменты локально?
        0
        Я нашел вот этот, но он ругается много на этот код :(

        clrhome.org/asm
        –7
        языке Ассемблер

        зануда mode on
        Ассемблер — это не язык, это программа. «Язык ассемблера» — так правильно.
        зануда mode off

        А вообще круто. Помню, видел исходники вирусов на 30-40 байт, само собой простейшие COM-оверрайтеры.
          –1
          Хоть бы намекнули, за что минусуете :)
            0
            Мне кажется, открытое голосование оптимально, как сделано в disqus.
              0
              ИМХО достаточно, чтобы при минусовании нужно было выбрать причину (в select'е, из вариантов типа «оффтопик» (как вот этот мой коммент), «нецензурщина», ну и т.д. — так хоть обжаловать бы можно было, если причина указана неадекватно) и опционально дополнить текстом. P.S. Мне еще и карму до -4 за тот коммент снизили. Вот не понимаю же, что я такого плохого написал.
          0
          А релоцируемость за счёт чего взята? в i80 такого нет, чисто средствами Z80?
            +1
            JR — короткий относительный переход, этого достаточно.
              0
              Как это «такого нету в i80»? Условные переходы и в 8080 и в 8086 относительные, так что если у вас нет процедур (а их тут нету), то релоцируемость не так сложно сделать…
                +1

                у 8080 — только абсолютные адреса (как для jmp так и для call).
                http://demin.ws/projects/radio86/info/kr580/i8080.html#cmdlist

                  +1
                  Да, правда ваша. Это у z80 и 8086 есть относительные переходы, у 8080 нету…
              +1
              Кто-нибудь знает сообщества, которые вот так соревнуются в минимизации или оптимальности?
                +1
                Тут есть пара ссылок: en.wikipedia.org/wiki/Code_golf
                  0
                  Спасибо, никогда бы не догадался искать по такому сочетанию.
                  +1
                  Ещё можете посмотреть box-256.com (это правда не совсем сообщество, но игра интересная и похоже на то, что вы ищите)
                  Суть игры в том, что надо нарисовать на экране определённую картинку используя ассемблер. Можно соревноваться как в компактности кода (наименьшее количество инструкций в памяти), так и в быстроте программы (количество тактов необходимых для построения картинки).
                    0
                    Демосцена же
                      0
                      Разве в демосцене всеобщими усилиями уменьшают один ассемблерный код?
                        0
                        Если работать в команде, то несомненно. А так какие-нибудь профильные каналы на reddit
                    0
                    Люблю «змейку»; помнится, когда-то много в неё наиграл (была в начале девяностых популярна томская версия — «Червяк», там еще уровни были с препятствиями, а червяк на зеленом поле собирал красные яблоки и периодически гадил, в какашки врезаться тоже было нельзя).
                      +5

                      Ассемблер z80. Сколько вечеров… Слезы на глазах, грусть, настольгия. Спасибо большое за воспоминания детства.

                        0
                        Можно общее описание алгоритма?
                        Как хранится и обрабатывается сама змейка?
                          0
                          Добавил описание алгоритма в новый раздел статьи.
                          0
                          Помнится, в моей змейке размером меньше сектора на диске TR-DOS больше всего занимал хороший генератор ПСЧ и драйвер экрана, т.к. я работал с пикселями, а не аттрибутами. Звуки тоже были и эффект заливки и очистки экрана случайными точками (процедурой печати кроликов в цикле). Было это в 90-у, интернета не было, и я был уверен, что единственный интересовался таким. А оно вот как получается. Ещё чего доброго окажется, что я не единственный «создавал» новые уровни змейки на китайских клонах brick-game («Тетрис») методом circuit bending…
                            0
                            Отличный результат!!!
                            PS: Не помню уже досконально систему команд, а в гугль подглядывать нечестно, но разве нельзя
                            LD BC, nn
                            вместо
                            LD B, 1
                            LD C, 1

                            ?

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

                            Самое читаемое