Уровни для Сокобана

    Во времена XTшек и ДОС был у меня вариант Сокобана, реализованный в виде махонького бинаря, размером менее десяти килобайт. Называлось это чудо pusher.exe и выглядело вот так:



    Это был простой уровень, но как насчет вот такого?



    Элементарно запускается через DOSEmu: DOSEmu -exit pusher.exe.

    Кому лень запускать можно посмотреть демку:



    И стало мне интересно, как шестьдесят уровней помещаются в столь небольшой бинарь. Поковырявшись немного IDA'ой, я написал программку, которая выдирает из бинаря `pusher.exe` все уровни и печатает их в текстовом виде:

    *************************************
    Maze: 1
    File offset: 148C, DS:00FC, table offset: 0000
    Size X: 22
    Size Y: 11
    End: 14BD
    Length: 50
    
        XXXXX
        X   X
        X*  X
      XXX  *XXX
      X  *  * X
    XXX X XXX X     XXXXXX
    X   X XXX XXXXXXX  ..X
    X *  *             ..X
    XXXXX XXXX X@XXXX  ..X
        X      XXX  XXXXXX
        XXXXXXXX
    
    *************************************

    Можно скачать сразу все уровни.

    Уровни сжаты чем-то вроде Хаффмана — битовыми цепочками переменной длины. Каждый уровень кодируется следующим образом:
    • Размер карты по X (1 байт).
    • Размер карты по Y (1 байт).
    • X*Y байт самой карты, которая представлена последовательностью пар
      [СЧЕТЧИК][КОД СИМВОЛА]. СЧЕТЧИК — это либо один бит 0, если символ
      только один, либо четыре бита «1 D3 D2 D1», и тогда количество повторений
      рассчитывается по формуле «N = 2 + D3*4 + D2*2 + D1», то есть от 2-х до
      9-и символов. КОД СИМВОЛА имеет пять разных значений: 00 — пустое место,
      01 — стена, 10 — бочка, 110 — место для бочки, 111 — бочка, уже стоящая
    • Начальная позиция игрока по X (1 байт).
    • Начальная позиция игрока по Y (1 байт).
    И так все 60 уровней.

    В файле pushermaps.c можно увидеть весь нехитрый декомпрессор.

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

    level_01        db 16h, 0Bh, 0A2h, 0DFh, 38h, 32h, 1Fh, 38h, 2Ah, 3, 0E6h
                    db 12h, 0C0h, 0A5h, 0F2h, 83h, 2, 81h, 3, 0E4h, 12h, 82h
                    db 25h, 6, 0CDh, 64h, 22h, 51h, 0ACh, 11h, 0A1h, 0Ah, 5
                    db 0E5h, 11h, 0B1h, 14h, 82h, 29h, 82h, 31h, 0A0h, 0E1h
                    db 2Ch, 18h, 0D1h, 0CFh, 80h, 0Ch, 8
    level_02        db 0Eh, 0Ah, 0F6h, 58h, 0Ch, 68h, 0Dh, 94h, 0C6h, 80h
                    db 85h, 2, 82h, 18h, 0D0h, 15h, 4Ch, 10h, 0C6h, 0C2h, 18h
                    db 21h, 8Dh, 1, 6, 4, 39h, 10h, 0A0h, 81h, 80h, 85h, 2
                    db 8, 20h, 60h, 34h, 1Bh, 0Ch, 1Eh, 0CAh, 7, 4
    level_03        db 11h, 0Ah, 0E3h, 9Fh, 0Eh, 7, 0C2h, 11h, 42h, 1Fh, 8
                    db 50h, 23h, 0E0h, 85h, 4, 0Ch, 1Eh, 84h, 8, 0A6h, 0B4h
                    db 10h, 85h, 2, 82h, 59h, 0D4h, 28h, 14h, 90h, 0D6h, 83h
                    db 0DFh, 7Ch, 0Eh, 1
    
    И т.д.

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

    Знаю, что в интернете полно уровней для Сокобана, и автоматические решалки имеются, но это совершенно не отменяет фан копания дизассемблером в бинаре более чем двадцати летней давности.

    Проект на GitHub'e — github.com/begoon/sokoban-maps, если кому интересно.
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 53

      +17
      Это RLE — Run Length Encoding. %)
        +7
        Это была первая игрушка которую я написал в конце далеких 80-х в рамках своих первых потуг программирования(не именно эта). И как выяснилось позже, таких людей кто писал свой собственный сокобан было не мало. Почти все мои друзья кто нынче является программистом написали по своему сокобану в начале програмерского пути.
        Много ли людей тут кто прошел такой же путь?
          +1
          Было такое. Тоже писал сокобан как минимум три раза на разных языках програмирования :)
            0
            Ох сколько людей писало сокобан! Впечатляет! И фраза изобрели еще один велосипед тут будет одновременно как уместна та и не уместна. :) Это скорее учебное пособие.
            +1
            Я начинал с сапера в текстовом режиме на basic'е, а потом заново начал, уже с пак-мэном на C++ в связке с голым OpenGL. Так что не все, не все… :)
              +1
              Я писал, в основном, тетрисы и пэкмэна. Над сокобаном думаю сейчас — ни разу не видел его трехмерного варианта, а значит, что-то в этом мире пропущено.
                +1
                Где-то мне попадалось нечто трехмерное, псевдо 3д еще на 486, но смутно помню. А в целом конечно затея хорошая, как минимум для развития собственных навыков в 3д графике.
                +1
                этих 3d-сокобанов уже тоже легион — только на андроиде с десяток вариаций встречалось
                  +1
                  Они действительно трехмерные, или это 3D-визуализация плоских уровней?
                    +1
                    А это классная мысль — вынести в 3D не только интерьер, но и склад сделать многоэтажным, с лифтами и штуками, которыми пользуются пожарники, чтобы быстро спускаться с верхнего этажа. Погрузчиками, чтобы на разные полки склада ставить.
                    И чтобы можно было грабить корованы

                    Такой себе симулятор кладовщика.
                      +2
                      Боюсь, что это разрушит математическую элегантность игрушки. Я думаю, скорее, над «космическим» складом, без гравитации. Где ящики можно толкать во всех 6 направлениях.
                        +2
                        А можно сразу в 4D.
                          +2
                          Это основная идея. Но без промежуточного 3D-этапа будет трудно понять, что там можно делать и что придумывать. Например, у того же сапера увеличивать число измерений большого смысла нет (если оставлять окрестность кубической). У пэкмэна, как выяснилось, и подавно — он для любого числа измерений будет казаться нам трехмерным.
                      +1
                      На андроиде мне понравился Psychoban 3D.
                      Он с сюжетом (подаётся между уровнями), проходить интересно.
                    +3
                    Так вот что мне нужно написать! :) Спасибо за идею!
                      0
                      Трехмерные варианты есть. Правда, сам геймплей классический — в 2х, а не в 3х измерениях. Есть один по iOS. Еще в блоге Emanuele Feronato был пост с прототипом на Unity. Кстати, прототип получился достаточно симпатичный.
                        0
                        Одна из OSS вариаций на тему сокобана, с православным Beastie: beastieworker.sourceforge.net/, написана хабраюзером anmartex.
                        +3
                        Я тоже начинал с сокобана. На ZX + Basic.
                          0
                          Та же фигня. Севастопольский ZX Spectrum на встроенном Васике
                            +1
                            Я писал сокобан в рамках программерского конкурса Caos Construction'09, но у организаторов на компе не оказалось требуемой версии дотнета, так что у меня вместо консольки был отображён диалог с ошибкой :-
                              +1
                              Один из первых подобных self-challenge проектов — Тетрис-клон под DOS на Quick C с некоторыми функциями (инициализация графического режима, вывод точки) на ASM. Это была первая курсовая работа в универе. Эх, ностальгия!
                                0
                                А сокобан писал не так давно с целью разобраться с AS3 — практически без документации :) Писал, как если бы писал под DOS, и возможности Флеша практически не заюзал. Но сокобан заколбасил :) С AS3 же так и не разобрался :) Разобрался уже позже…
                                0
                                Да, я первый раз написал сокобан на ZX Spectrum, по-моему. Там был всего один уровень.
                                  0
                                  Я писал, из «техники молодёжи» брал идею и для Правеца переписывал.
                                    +1
                                    Я писал раза три точно, на разных машинах и языках.

                                    Сокобан очень просто пишется, и при этом сама игра хорошая. В ту же кучу можно засунуть тетрис — тоже просто пишется и хорошо играется. Что-то даже не вспоминается чего-то еще с подобным сочетанием играбельности и простоты реализации.
                                      +3
                                      Змейка
                                        0
                                        Арканоид
                                          0
                                          Арканоид все-таки посложнее — там не такая простая физика. Шарик летает не по клеточкам, надо как-то считать пересечения. В общем да, довольно просто, но не настолько.
                                            –1
                                            Что змейка, что сокобан, что арканоид — игры из разряда тривиальных. Можно на скорость даже соревноваться.
                                            Один из мох знакомых как-то прототип быстренько писал по просьбе заказчика, за 4-е часа успели написать 80% логики финального продукта на удивление безглючную, более менее связную анимацию и с десяток уровней. Трудилось 2 человека в целом, этот знакомый и аниматор. Само собой за плечами был мощный внутренний фреймворк который позволял творить достаточно прилично выглядящие вещи в короткие сроки. Результат был впечатляющим. Сделка состоялась. Через месяц продукт бы отполирован до блеска и отдан заказчику.
                                        0
                                        Помнится, у нас в компьютерном классе были голые терминалы с доступом только к своему каталогу и компилятору.
                                        А игрушек хотелось, так что написал себе как раз сокобан и сапёра.
                                          +1
                                          Нет, я писал питона, писал тетрис. В рамках изучения ассемблера «цветной тетрис» aka Coloris. Сокобан никогда не писал, потому что там не было динамики :)
                                            +1
                                            И я, и я писал сокобан:
                                            • UFO just landed and posted this here
                                              0
                                              Будучи ещё совсем ребёнком — писал похожую игрушку (но не sokoban, а скорее больше — boulder dash) — у меня там было четыре бита на одну клетку, для поля 62x17.
                                              Спасибо за пост — ностальгия…
                                                +1
                                                boulder dash — совсем другое. Там надо выгрызать клетки и собирать алмазы, уворачиваясь от врагов и камней.
                                                  0
                                                  Я конечно понимаю, но «карта уровня» и там, и там примерно схожа. :)
                                                +4
                                                Для такой игрушки 10кб — не «небольшой бинарь» по тем временам :)
                                                А разновидность сокобана тоже писал, помнится, на асме.
                                                  0
                                                  Да, этот написан на Турбо Си.
                                                  +1
                                                  По мне самый симпатичный сокобан был с грузином в кепке. Если ты задумывался, грузин доставал беломорину и закуривал. Уровни были этажами в высотке. Все оттуда тащили расклады для своих поделок.
                                                    0
                                                    Да, да, еще у этой игры была классная функция — «Начальник идет», если ее включить, то игровое окно пряталось, и на весь экран появлялся ЯКОБЫ Norton Commander сильно занятый процессом копирования файлов.
                                                    +1
                                                    Как по мне, можно жать и гораздо плотнее, даже не привлекая тяжелую артиллерию. А тут просто на коленке сделанный RLE, наверняка без попыток особо его улучшить — как придумали, так и слепили.
                                                      +1
                                                      А как в данном конкретном случае можно сжать еще плотнее?
                                                        0
                                                        Например, воспользоваться тем, что статистика стен и ящиков сильно различается. Закодировать сначала битовую маску стен (тем же указанием длин отрезков — только придумать, как не тратить лишний бит на переключение между стеной и пустотой), а потом ящики и места для них — последовательностью разностей одномерных координат (его можно ужать, если каждый раз тратить на очередную разность число бит, соответствующих месту до конца массива). При этом не учитывается, что места для ящиков обычно идут плотно — но там можно нулем обозначать разность 1, а 1xxxx… — все остальные разности. Будет ли выигрыш, надо смотреть.
                                                          0
                                                          На первой картинке у меня выигрыш примерно 23% — 277 бит против 364. Так что «гораздо плотнее» не получилось.
                                                      +1
                                                      А мне сразу вспомнилось, как я в далёком 2003 закодировал фигурки для тетриса на Delphi

                                                       f:array [1..8,1..8] of byte=        {1'st type 2'nd num}
                                                         ((98,4, 192,6, 32,70, 96,3),
                                                          (100,2,96,12,64,38,48,6), 
                                                          (68,6,32,14,96,34,112,4), 
                                                          (34,6,224,2,96,68,64,7),   
                                                          (98,2,224,4,64,70,32,7),   
                                                          (100,4,64,14,98,2,224,4), 
                                                          (96,6,96,6,96,6,96,6),        
                                                          (34,34,240,0,68,68,0,15));
                                                      
                                                      

                                                        0
                                                        Пятая и шестая фигуры совпадают…
                                                          0
                                                          Не вижу совпадений.
                                                          Каждая строка — четыре варианта одной фигуры повернутой на 90°, по два байта на фигуру.
                                                          Первый байт — верхняя часть фигуры, второй — нижняя часть. Кроме того, каждый байт делится пополам, на две строки.
                                                          (Не самое понятное объяснение, могу исходник выложить)
                                                        +1
                                                        Спасибо, про формат я догадался (не считая ориентации верх-низ) :)

                                                        Пятая фигура:
                                                        ..x.
                                                        .xx.
                                                        ..x.
                                                        ....
                                                        

                                                        Шестая:
                                                        .x..
                                                        .xx.
                                                        .x..
                                                        ....
                                                        

                                                        По-моему, они одинаковые. Отличаются только положением в квадрате (одна при ориентации в виде T смещена влево, другая вправо).
                                                          0
                                                          Да, точно, так и есть. Фигур должно было быть 7
                                                          0
                                                          Неужели только я писал танчики?
                                                            0
                                                            Не только, но танчики это уже поближе к современности.
                                                              0
                                                              Я танчиков писал и на Делфи и на JS. Первая игра так сказать писанная. Правда до нормального состояния так и не разу не доводил, видимо сказывается то, что мне они не особо нравятся ))

                                                            Only users with full accounts can post comments. Log in, please.