По следам черного самурая, или делаем игру «Sokoban» своими руками.



Эпиграф.
«В последнее время плохо летаю во сне Неужто старею ?!
Или в подушке моей Недостаточно перьев?»
(японская поэзия)

Предыстория.
Я уже неоднократно упоминал в своих статьях о своем знакомом (молодой человек 14 лет отроду), которого я всячески пытался заинтересовать радиоэлектроникой (в общем) и Ардуиной (в частности). Так вот. Прямо беда с моим подопечным. Игры. В голове только игры. Везде и всегда. На даче, в гостях, за праздничным столом, в школе, на улице, ВЕЗДЕ. Причем, если родители запретят (заблокируют-запаролят) компьютер — он играет в планшете. Отнимут планшет — он в телефоне. Выгонят проветриться на улицу (предварительно заставив оставить дома всякие электронные гаджеты) — смотрю, а он уже с своим корешом в PSP на лавочке играет. И так до бесконечности. Как борьба с ветряными мельницами. Интересно, в таком режиме живут все современные подростки? По его словам:»Да».

И вот так сошлись звезды, что разгребая свои старые завалы, я случайно нашел старую тетрадь с моими робкими попытками (наверно в далеком 1993 году) программирования на ассемблере для ПЭВМ “ZX Speccy”.

Даже немного прослезился 🙂 Оказывается я тоже в молодости интересовался играми, правда их написанием. Любопытно, что тогдашние мои друзья по компьютерным делам (Саня и Петр) и сейчас плотно занимаются программированием.
И у меня появилась любопытная идея: “Раз уж игры так плотно засели у ребенка в голове, то может мне удастся перетащить его на другую сторону баррикады, а именно заинтересовать написанием игр”. Маловероятно конечно, но чем черт не шутит… Проявлял же он интерес к Ардуине. Думаю это будет хороший шаг от мигания светодиодами и управления моторчиками к процессу создания (так им обожаемых) игр.

Но, какую же выбрать игру для написания, чтобы раскрыть игровой потенциал платформы Ардуино?
Простых и увлекательных игр существует огромное множество. Навскидку могу вспомнить: Морской бой, Пятнашки, Тетрис, Сапер, Волк ловит яйца, всякие “стрелялки” монстров и так далее. Как говорится, на любой вкус.
Но мой уровень, как программиста, пока оставляет желать лучшего. Поэтому сложные игры с интеллектуальной составляющей (типа шахмат) я РЕАЛЬНО не осилю… Однако и совсем примитив (типа крестиков-ноликов) тоже не вариант, а ударить в грязь лицом перед своим подопечным не хотелось…
Короче, после долгих терзаний я выбрал в качестве конечной цели замечательную японскую игру Sokoban (отсюда, кстати, и несколько странное название этой статьи).
Подробнее об этой увлекательной игре на смекалку и логику можно почитать ТУТ.

Почему же я остановил свой выбор именно на этой игре:
-> Простота реализации. По сути дела, программа должна только контролировать игровую ситуацию;
-> Для создания игровой атмосферы не требуется высокая графика;
-> Игра (как игра) не является примитивной, а я бы сказал, зачастую требующая хорошенько “пошевелить серым веществом”;
-> Простое наполнение игры уровнями (интернет просто кишит вариантами разной степени сложности);
-> И еще. Оказывается, автору игры (некто Хироюки Имабаяси) и его компании принадлежат права непосредственно на программу как на конечный продукт, а не на идею. А учитывая, что в России с 1 мая 2015 года начинает работать “Антипиратский закон”, этот факт тоже немаловажен :). Даже не сомневаюсь, что и у нас в Республике Беларусь вскорости примут что-то подобное.

Немного об этой игре и ее правилах.
Правила игры просты и изящны, как все гениальное. Есть некий склад, зачастую весьма сложной конфигурации (его обычно называют «лабиринтом») и в нем находится кладовщик (в переводе с японского, Soko-Ban — и есть “Кладовщик”) и ящики. Все ящики необходимо поставить на конечные позиции (обычно они обозначаются крестиками). Ящики можно только толкать, но нельзя тянуть. Кроме того, нельзя толкать больше одного ящика. Запрешь ящик в угол — уже никогда его оттуда не вытащишь — придется начинать все с начала. Придвинешь один ящик вплотную к другому — и сдвинуть его сможешь только подойдя к нему сбоку. Если, конечно, не помешают стенки или другие ящики.

Осталось обсудить с пацаном что и как мы будем делать для реализации задумки.
Удивительно, но мой ярый “игроман” впервые слышал об этой замечательной игре. На кубиках LEGO пришлось разъяснить основные моменты.
Слава Богу, вроде заинтересовался. Уже хорошо, идем дальше.
Мы долго с ним пытались (точнее я подталкивал его из всех сил) выработать и нарисовать подобие некого алгоритма будущей программы.
Параллельно заметил, что ребенку очень сложно переходить к “атомарным” представлениям процессов. Ну, например, наш диалог:
Я — Ну и что дальше делать?
П — Проверить, можно ли туда походить.
Я — А как проверить?
П — Посмотреть, что находиться в этой клетке
Я — Минутку, у нас есть только цифры и набор четких команд. Как это сделать?
ну и т.д.

Честно говоря, благодаря этому “объяснению”, а так же уловкам и хитростям типа: “Нет, я знаю как это сделать, НО я ХОЧУ услышать твои варианты решения этого вопроса.”, у меня у самого НАКОНЕЦ-ТО появился “четкий план” написания кода :).
В конце концов, испортив кучу бумаги, мы все же что-то нарисовали. Я позже немного облагородил эту картинку:

Общая концепция программной части игры.
Есть рабочий массив (12х8 клеток) — это игровое поле. Размер игрового поля может быть абсолютно любым (в разумных пределах, конечно же), но огромные поля требуют большого количества тупых перемещений. И это может оттолкнуть игрока от прохождения такого уровня.

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

#define EMPTY 0
#define WALL 1
#define BOX 2
#define PLACE 3
#define BOX_IN_PLACE 4

Ниже пример “оцифровки” одного уровня:

Получилось, что один уровень можно описать так: 96 байт- это непосредственно лабиринт и 4 байта начальная позиция человечка. Итого 100 байт.
В ходе игры мы будем просто изменять нужные значения в нужном месте массива. Например, если коробка сдвинулась, то в ее старой ячейке массива запишем значение EMPTY (0), а в новом месте — код соответствующий BOX (2).
На этом этапе обсуждения стало понятно, что хранить текущие координаты человечка лучше в отдельных переменных, а не в массиве. Вполне возможна ситуация, когда человечек станет на клетку “Место под коробку”. И тогда нужно будет каким-то образом учесть этот момент.

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

Пример. Для получения информации о том, что располагается в ячейке с координатами X=3, Y=2 — нам нужно прочитать значение в массиве с номером (2*12)+3=27.

Как вы могли заметить, для отслеживания положения человечка (X,Y) расточительно выбран тип int (2 байта), хотя вполне хватило бы и byte, но… для расчета его смещения мы решили использовать следующий принцип: если мы смещаемся влево, то это move_x=-1. Соответственно, вправо — move_x=1.

Таким образом, очень удобно проверять что находится через “клетку” по направлению движения, просто прибавив к координатам человека два раза заданное смещение.

tmp_step1=(player_y+move_y)*12+(player_x+move_x);
tmp_step2=((player_y+move_y+move_y))*12+(player_x + move_x) + move_x;

Получается, что используя отрицательные числа, мы упрощаем себе задачу по контролю содержимого клетки “через одну”. На все про все — одна формула. Удобно.

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

Управление
Просто читаем из ком-порта команду на перемещение человечка. Согласно введенной команде задаем смещение (это переменные move_x или move_y).

Анализатор возможности хода.
По полученному смещению высчитываем “возможное будущее положение” человечка.
Смотрим что находится в этой клеточке и что в следующей по этому направлению. Если там пусто или место под коробку — присваиваем человечку новые координаты. Если же в предполагаемой позиции находится коробка, то дальше анализируем что за коробкой. Тут уже вариантов побогаче: там может быть другая коробка, стена или место под коробку. И так далее. В ходе проверки мы меняем значения в соответствующем месте массива.

Отображение игровой ситуации.
Пока все просто. Реализовано двумя циклами (по количеству строк и столбцов игрового поля). И вывод строки символов, которые (при должном уровне фантазии) отображают каждый элемент игрового мира.

Проверка на завершение уровня.
Уровень считается пройденным, если все коробки на своих местах. Т.е., в игровом массиве не осталось значений “Место под коробку” (или можно проверять на наличие значения “Коробка”).

Так это выглядит этот безобраз игровой процесс на экране:

Ниже код того, что у нас получилось 🙂 Пока всего один уровень и рестарт по кнопке ресет.
Даа-а-а, пока как-то не очень (и это мягко сказано)!

/*
0 - пусто
1 - стена
2 - коробка
3 - место под коробку
4 - коробка на месте
5 - игрок
*/

#define EMPTY 0
#define WALL 1
#define BOX 2
#define PLACE 3
#define BOX_IN_PLACE 4
#define MAN 5

// Готовый уровень 1
//карту уровня проще написать цифрами :)
byte labirint[]={
0,0,0,1,1,1,0,0,0,0,0,0,
0,0,0,1,3,1,0,0,0,0,0,0,
0,0,0,1,0,1,1,1,1,0,0,0,
0,1,1,1,2,0,2,3,1,0,0,0,
0,1,3,2,0,0,1,1,1,0,0,0,
0,1,1,1,1,2,1,0,0,0,0,0,
0,0,0,0,1,3,1,0,0,0,0,0,
0,0,0,0,1,1,1,0,0,0,0,0
};

//начальные координаты грузчика
//естественно лучше было бы использовать byte, но из-за
// применения "смещения" (+,-), пришлось использовать int
int player_x=5;
int player_y=4;
void setup()
{
  Serial.begin(9600);
  show_level(); //вывод игрового поля
}

void loop()
{
  byte incByte;//байт, считываемый из СОМ-порта
  //относительное смещение грузчика, тоже int (см. выше)
  int move_x=0;
  int move_y=0;
  int tmp_step1=0;
  int tmp_step2=0;

  if (Serial.available() > 0) //если ввели команду
    {
       // read the incoming byte:
        incByte = Serial.read();
        switch (incByte)
        {
          case '0': //refresh screen
          show_level();
          break;

          case '1': //move left
          move_x=-1;
          break;

          case '2': //move up
          move_y=-1;
          break;

          case '3':
          move_y=1; //move down
          break;

          case '4': //move right
          move_x=1;
          break;
        }//end switch


  Serial.print("move1 :"); Serial.print(tmp_step1);Serial.print(" next:"); Serial.println(tmp_step2);

  if (check_move(move_x,move_y)) show_level();

  } //end if

if (CheckLevel()) //проверяем уровень пройден?
  {
    Serial.println("********************");
    Serial.println("* Level Complete!!! *");
    Serial.println("********************");
    delay(10000);
   }
} //end main loop

//==========================================
// Check move
// Проверка возможности хода, с соответствующей корректировкой
// значений рабочего массива
//==========================================
boolean check_move (int move_x, int move_y)
{
  boolean step_ok=false; //
  int tmp_step1=0;
  int tmp_step2=0;
   //смотрим что в следующей клетке, куда немерены походить ну и след. за ней
  tmp_step1=(player_y+move_y)*12+(player_x+move_x);//работает правильно
  tmp_step2=((player_y+move_y+move_y))*12+(player_x + move_x + move_x);

 //если это пустая клетка, то и туда переходим
  if (labirint[tmp_step1]==EMPTY)
  {
    player_x=player_x+move_x;
    player_y=player_y+move_y;
    step_ok=true;
  }

  //так же можно двигаться по местам для коробок
  if (labirint[tmp_step1]==PLACE)
  {
    player_x=player_x+move_x;
    player_y=player_y+move_y;
    step_ok=true;
  }

  //уперся в коробку?
  if (labirint[tmp_step1]==BOX)
  {
    //проверим, что за коробкой. Если пусто - сдвигаем и коробку и человечка
    if (labirint[tmp_step2]==EMPTY)
      {
        labirint[tmp_step2]=BOX;
        labirint[tmp_step1]=EMPTY;
        player_x=player_x+move_x;
        player_y=player_y+move_y;
        step_ok=true;
      }
      //тоже самое, если там место для коробок
      if (labirint[tmp_step2]==PLACE)
      {
        labirint[tmp_step2]=BOX_IN_PLACE;
        labirint[tmp_step1]=EMPTY;
        player_x=player_x+move_x;
        player_y=player_y+move_y;
        step_ok=true;
      }

  }//end if (первого) где уперлись в коробку

//коробку стоящую на СВОЕМ месте тоже можно сдвинуть :)
if (labirint[tmp_step1]==BOX_IN_PLACE)
  {
    //проверим, что за коробкой. Если пусто - сдвигаем и коробку и человечка
    if (labirint[tmp_step2]==EMPTY)
      {
        labirint[tmp_step2]=BOX;
        labirint[tmp_step1]=PLACE;
        player_x=player_x+move_x;
        player_y=player_y+move_y;
        step_ok=true;
      }
      //тоже самое, если там еще одно место для коробок
      if (labirint[tmp_step2]==PLACE)
      {
        labirint[tmp_step2]=BOX_IN_PLACE;
        labirint[tmp_step1]=PLACE;
        player_x=player_x+move_x;
        player_y=player_y+move_y;
        step_ok=true;
      }
  }//end if (первого) где уперлись в коробку стоящую на своем месте
 return step_ok;
}// end check_move

//======================================
// проверка на завершение уровня
// Если в массиве есть места под коробку => уровень не пройден
//=====================================
boolean CheckLevel()
{
boolean complete=true;
  for (byte y=0;y<96;y++)
  {
    if (labirint[y]==PLACE) complete=false;
  }//end y
  return complete;
}

//==========================================
// процедура отображения на экран игровой ситуации
void show_level()
{
  char tmp_pic;
  for (byte y=0;y<8;y++)
  {
    for (byte x=0;x<12;x++)
    {
      if (labirint[y*12+x]==WALL) tmp_pic='#';
      if (labirint[y*12+x]==EMPTY) tmp_pic=' ';
      if (labirint[y*12+x]==PLACE) tmp_pic='X';
      if (labirint[y*12+x]==BOX) tmp_pic='o';
      if (labirint[y*12+x]==BOX_IN_PLACE) tmp_pic='+';
      if ((x==player_x)&&(y==player_y)) tmp_pic='R';

       Serial.print(tmp_pic);
    }//end x
   Serial.println(); //перевод строки
  }//end y
  Serial.println("= 0-refresh 1-left  2-up  3-down  4-right  ="); //так сказать, hint
  Serial.print("P X:"); Serial.print(player_x);Serial.print(" Y:"); Serial.println(player_y);

}//end show_level

Выводы.
Кто-то скажет, что эта часть статьи - “полное фуфло”, ничего нового и интересного. Не буду спорить. Может быть.

Но, с моей точки зрения, она не так уж бесполезна:

1) Оказывается, есть люди, которые абсолютно ничего не знают про эту замечательную игру;
2) Дает некое представление о принципах написания программного продукта;
3) Некоторые теоретические выкладки из этой части могут пригодиться в других разработках;
4) У нас на данном этапе появился (какой-никакой) скелет-основа будущей игры.

Далее довольно легко будет адаптировать этот код под любые “хотелки”: под другие микроконтроллеры, под принципиально другую платформу, под другие аппаратные решения и т.д. Для этого достаточно будет просто заменить соответствующие процедуры. Например, вывод не в сом-порт, а на маленький экранчик (того или иного типа) или вообще на TV (реально есть такие шилды). Или как вариант - чтение указаний не с ком-порта, а с кнопок или некого другого устройства ввода, например “перчатки виртуальной реальности”.

Все? Как говорил персонаж одного советского фильма: “НЕТ, не все! Против бритвы - пиджак и брюки!”

P.S.
Дело было на весенних каникулах у школьников. И Владислав (так зовут моего "ученика" по Arduino) остался очень доволен своим участием в этом проекте и клятвенно заверил, что в свободное от учебы время САМОСТОЯТЕЛЬНО придумает и нарисует несколько хороших и оригинальных уровней для НАШЕЙ игры.


0 комментариев на «“По следам черного самурая, или делаем игру «Sokoban» своими руками.”»

Добавить комментарий

Arduino

Что такое Arduino?
Зачем мне Arduino?
Начало работы с Arduino
Для начинающих ардуинщиков
Радиодетали (точка входа для начинающих ардуинщиков)
Первые шаги с Arduino

Разделы

  1. Преимуществ нет, за исключением читабельности: тип bool обычно имеет размер 1 байт, как и uint8_t. Думаю, компилятор в обоих случаях…

  2. Добрый день! Я недавно начал изучать программирование под STM32 и ваши уроки просто бесценны! Хотел узнать зачем использовать переменную типа…

3D-печать AI Android Arduino Bluetooth CraftDuino DIY IDE iRobot Kinect LEGO OpenCV Open Source Python Raspberry Pi RoboCraft ROS swarm ИК автоматизация андроид балансировать бионика версия видео военный датчик дрон интерфейс камера кибервесна манипулятор машинное обучение наше нейронная сеть подводный пылесос работа распознавание робот робототехника светодиод сервомашинка собака управление ходить шаг за шагом шаговый двигатель шилд юмор

OpenCV
Робототехника
Будущее за бионическими роботами?
Нейронная сеть - введение