Хороший день для кодогенерации

            Давным-давно, еще на заре существования Вечности, где-то в 300-х Столетиях был изобретен дубликатор массы…
            Вечность приспособила дубликатор для своих нужд. В то время у нас было построено всего шестьсот или семьсот Секторов. Перед нами стояли грандиозные задачи по расширению зоны нашего влияния. «Десять новых Секторов за один биогод» — таков был ведущий лозунг тех лет.
            Дубликатор сделал эти огромные усилия ненужными. Мы построили один Сектор, снабдили его запасами продовольствия, воды, энергии, начинили самой совершенной автоматикой и запустили дубликатор. И вот сейчас мы имеем по Сектору на каждое Столетие.

                Айзек Азимов "Конец Вечности"


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

    Сделать Sokoban я хотел давно. Вернее, (как и многие другие) я уже делал его несколько раз, но это было задолго до моего знакомства с Zillions of Games. Что меня всегда напрягало — так это разработка уровней. Придумать хороший уровень, для игры-головоломки, совсем не просто, а ведь их надо ещё и закодировать! Поскольку в Sokoban-е количество уровней не менее важно чем их качество, работа грозила затянуться надолго.

    С другой стороны, возможно уровни и не стоило придумывать. В самом деле, ностальгировать всего лучше на старых уровнях, привычных с детства. Здраво рассудив, что за время, прошедшее с 80-ых годов прошлого века, кто нибудь обязательно должен был озадачиться той же проблемой (и не один раз, скорее всего), я решил поискать описание оригинальных уровней в Интернете. Искомое я быстро обнаружил на Хабре, за что, безусловно, хочу поблагодарить уважаемого begoon. Выдранный им, ещё из DOS-овой версии программы, листинг выглядит следующим образом:

    *************************************
    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          
    

    Всё просто и понятно! Осталось перевести это в форму, понятную Zillions of Games. Все шестьдесят уровней. Не знаю, кто как, но лично я, не настолько люблю работать руками. Проблема даже не в том, чтобы всё это набить, потом ведь придётся ещё и исправлять неизбежные ошибки! В общем, если кто-то искал подходящую задачу для кодогенерации, то это она и есть. Напомню, что кодогенерация — это такая «домашняя» разновидность метапрограммирования, чуть более дружественная к головному мозгу разработчика, чем другие разновидности.

    Сказано - сделано!
    open(my $f, '>', 'levels_1_10.zrf');
    
    my $n = 0;
    my $k = 0;
    my $x = 0;
    my $y = 0;
    my %p;
    my %b;
    
    while (<>) {
      chomp;
      my $s = $_;
      if (/^\s*X/) {
         $y++;
         my $i = 0;
         my @a = split(//, $s);
         foreach $c (@a) {
             $i++;
             if ($c ne ' ') {
                 my $p;
                 if ($i > 26) {
                     $p = chr(ord('A') + $i - 27);
                 } else {
                     $p = chr(ord('a') + $i - 1);
                 }
                 my $key = $p . $y;
                 $c =~ tr/X*.@/WBTY/;
                 $p{$key} = $c;
                 if ($i > $x) {
                     $x = $i;
                 }
             }
         }
      } else {
         if ($y) {
             $n++;
             if ($n > 10) {
                 $k++;
                 $n = 1;
                 close($f);
                 my $a = $k * 10 + 1;
                 my $b = ($k + 1) * 10;
                 open($f, '>', "levels_${a}_${b}.zrf");
             }
             my $l = $k * 10 + $n;
             if ($n > 1) {
                 printf $f "(variant\n";
             } else {
                 printf $f "(include \"sokoban.inc\")\n\n";
                 printf $f "(game\n";
             }
             printf $f "   (title \"Sokoban (Level $l)\")\n";
             if ($n == 1) {
                 printf $f "   (common-level)\n";
             }
             printf $f "   (board\n";
             printf $f "      (image \"images/sokoban/black-${x}x${y}.bmp\")\n";
             printf $f "      (grid\n";
             printf $f "         (common-grid)\n";
             printf $f "         (dimensions\n";
             printf $f "              (\"";
             for (my $i = 1; $i <= $x; $i++) {
                 if ($i > 1) {
                     printf $f "/";
                 }
                 my $p;
                 if ($i > 26) {
                     $p = chr(ord('A') + $i - 27);
                 } else {
                     $p = chr(ord('a') + $i - 1);
                 }
                 printf $f "$p";
             }
             printf $f "\" (25 0)) ; files\n";
             printf $f "              (\"";
             for (my $i = 1; $i <= $y; $i++) {
                 if ($i > 1) {
                     printf $f "/";
                 }
                 printf $f "$i";
             }
             printf $f "\" (0 25)) ; ranks\n";
             printf $f "         )\n";
             printf $f "      )\n";
             printf $f "   )\n";
             printf $f "   (board-setup\n";
             printf $f "      (You\n";
             printf $f "         (W";
             foreach $pos (keys %p) {
                 if ($p{$pos} eq 'W') {
                     printf $f " $pos";
                 }
             }
             printf $f ")\n";
             printf $f "         (B";
             foreach $pos (keys %p) {
                 if ($p{$pos} eq 'B') {
                     printf $f " $pos";
                 }
             }
             printf $f ")\n";
             printf $f "         (T";
             foreach $pos (keys %p) {
                 if ($p{$pos} eq 'T') {
                     printf $f " $pos";
                 }
             }
             printf $f ")\n";
             printf $f "         (Y";
             foreach $pos (keys %p) {
                 if ($p{$pos} eq 'Y') {
                     printf $f " $pos";
                 }
             }
             printf $f ")\n";
             printf $f "      )\n";
             printf $f "   )\n";
             printf $f ")\n\n";
             $b{"black-${x}x${y}.bmp"}->{x} = $x * 25;
             $b{"black-${x}x${y}.bmp"}->{y} = $y * 25;
             $x = 0;
             $y = 0;
             %p = ();
         }
      }
    }
    
    close($f);
    
    foreach $b (keys %b) {
      printf "$b - $b{$b}->{x} $b{$b}->{y}\n";
    }
    


    Лёгким движением руки, генерим уровни, файлами, по 10 уровней в каждом. Выглядит полученное следующим образом (нет, sokoban.inc, в самом начале файла — это не название компании, а просто подгружаемый файл, с необходимыми определениями, созданными вручную). Некоторые не любят язык Perl, а многие другие могут найти мой стиль программирования не слишком изящным (чего стоят только разбросанные по коду «магические» константы), но я думаю, что для программы, которая (возможно) будет запущена всего один раз — это вполне приемлемое решение.

    В любом случае, мы получили (почти даром) вожделенные уровни, но (пока) не можем их запустить. Для полного счастья, нам не хватает того самого "sokoban.inc" и графических ресурсов, конечно. Последние мы быстренько создаём в paint-е (не особенно заморачиваясь и рисуя разноцветные, однотонно закрашенные квадратики), а первый — содержит, пока, не так много полезного. Перемещение «погрузчика» будем программировать позже, сейчас мы хотим, всего лишь, полюбоваться на уровни!

    sokoban.inc - минималистическая версия
    (define common-grid
       (start-rectangle 0 0 25 25)
    )
    
    (define common-level
       (move-sound "Audio/Pickup.wav")
       (release-sound "Audio/Pickup.wav")
       (capture-sound "")
    
       (option "prevent flipping" true)
       (option "animate captures" false)
    
       (players    You)
       (turn-order You)
    
       (piece
          (name W)
          (image You "images/sokoban/w.bmp")
       )
       (piece
          (name B)
          (image You "images/sokoban/b.bmp")
       )
       (piece
          (name b)
          (image You "images/sokoban/b.bmp")
       )
       (piece
          (name T)
          (image You "images/sokoban/t.bmp")
       )
       (piece
          (name Y)
          (image You "images/sokoban/y.bmp")
       )
       (piece
          (name y)
          (image You "images/sokoban/g.bmp")
       )
    
       (win-condition (You) (pieces-remaining 0 B) )
    )
    


    Стены, ящики, места для размещения ящиков и, разумеется, сам «погрузчик» — всё это фигуры. Некоторые из них, потом, даже будут двигаться. Всё это прекрасно, но нас уже поджидает очередная засада! Возможно, вы обратили внимание на имена файлов вида black-NNxMM.bmp в описаниях уровней? Это «задники» уровней. Всё, что от них требуется — предоставить фон, для отображения на нём фигур. Проблема лишь в том, что все эти задники разного размера (спасибо разработчикам Sokoban) и размер этот очень важен для корректного отображения уровней (за это стоит поблагодарить разработчиков ZoG).

    Вновь вооружаемся paint-ом и, пытаясь посрамить Малевича, рисуем чёрные прямоугольники всевозможных форм и размеров. Конечно их не шестдесят штук. Их всего пятьдесят четыре, но от этого не сильно легче! Парадоксально, но факт — более 90% нашего дистрибутива займут пустые, радикально чёрные прямоугольники (если бы они не были монохромными, то вполне могли бы занять и все 99%). Теперь можно полюбоваться на сами уровни:


    Быстренько пробегаемся по всем уровням (просто чтобы убедиться, что нигде не напахали с кодогенератором), после чего нас охватывает дизайнерская лихорадка. Начинаем с жёлтых ящиков. Две диагональных линии делают их гораздо более привлекательными (а дорисованные по сторонам треугольники — вообще тянут на эксклюзив). Рисуя кирпичную кладку, начинаем понимать, что 25x25 — фиговый размер для тайла. 24 — гораздо более правильное значение (забавно, что простой перестановкой цифр из него можно легко получить универсальный ответ на никому не известный вопрос). Снова берём в руки paint и терпеливо ресайзим все чёрные прямоугольники (результат стоит затраченных усилий). Последним перерисовываем сам «погрузчик» (без градиентной заливки тоже дело не обходится).

    Далее всё совсем просто. Необходимо научить фигуры двигаться. Единственная техническая сложность (очень небольшая) в том, что места размещения ящиков — тоже являются фигурами. Это означает, что когда мы по ним ходим и двигаем ящики — они должны удаляться (а затем автоматически восстанавливаться, при выходе с соответствующего поля). Конечно, можно было бы их просто нарисовать на задниках, но после этого последние уже перестали бы быть монохромными (солидно увеличившись в размере) и, в любом случае, 54 задника всё же лучше, чем все 60. На этом, всё! Наслаждаемся результатом:



    P.S.
    Уже ближе к вечеру, Howard McCay прислал мне весьма неожиданное и очень элегантное дополнение к моей реализации Yonin Shogi, опубликованной в далёком уже 2014 году. Оглядываясь назад, я понимаю, что это был не самый худший день в моей жизни.
    • +20
    • 15,8k
    • 6
    Поделиться публикацией
    Реклама помогает поддерживать и развивать наши сервисы

    Подробнее
    Реклама
    Комментарии 6
    • +2
      Отличная история. В начале 90-ых все гики вытаскивали из классического грузинского сокобана 99 уровней и лепили своё, родное. По поводу видео — замечен черный мерцающий лаг при движении грузчика по зеленому полю.
      • 0
        Увы, это не лаг. Грузчик на пустом месте и грузчик на поле для ящика — это две разных фигуры (Y и y соответственно). Рисунок первого — «шарик» на прозрачном фоне (ZoG использует один из оттенков зелёного), рисунок второго — тот же шарик, но уже на зелёном фоне. При выходе с «зелёной» области анимируется именно этот «шарик на зелёном». От этого можно было бы избавиться, сделав пометку мест под ящики частью фона, но почему я не стал этого делать я написал в статье (дистрибутив стал бы намного толще).
      • 0
        Мне вот, кстати, всегда было интересно, как разрабатываются головоломки с перемещениями, точнее, сами уровни.
        Как авторы умудряются выдумать 20-30 и более уровней, с нарастающей сложностью и нетривиальными решениями? Они как, пишут с конца?

        Вот, к примеру, на хабре (гиктаймсе) была такая статья:
        habrahabr.ru/post/231297

        36 уровней (хотя, первые, конечно, скорее для обучения).
        • +1
          Я думаю просто делаются уровни на что фантазии хватит, а потом просто выставляются номера в порядке сложности…
          • +1
            Подтверждаю! (В далёком прошлом занимался мелкими играми на флеше.)
        • 0
          Совсем не давно я прошёл 50 уровней классического сокобана. Управление было не удобным, и было очень тягостно растаскивать последние ящики, когда уровень уже практически пройден.
          Я задался целью — написать свой движок сокобана, чтобы там были автоходы (кликнул мышкой — человечек сам туда побежал).
          Этого мне показалось мало :), и я добавил ещё алгоритм перемещения одного ящика с одного места на любое другое (только одного, не трогая другие).
          Потом я решил сделать ещё «Сокобан на двоих» — можно много других интересных уровней придумать, когда на поле могут работать сразу два участника.
          Если есть желание — могу записать и выложить видеообзор программы, которая у меня получилась.

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