Лабораторная работа 6: двумерные массивы II

Кувшинов Д.Р.

2016

Общее оглавление

“Игра”

Введение

Экран
Экран

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

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

Дополнительные элементы con1

Библиотека con1 предоставляет ряд простых функций для управления вводом-выводом в консоли Windows и состоит из двух файлов: con1.hpp и con1.cpp (ссылки даны на ревизии, доступные на момент написания данного текста). По умолчанию библиотека сконфигурирована для использования в режиме header-only (достаточно включить файл con1.hpp в свою программу и положить con1.cpp “рядом” с ним).

Приведённая ниже программа использует дополнительные элементы con1, которые не были описаны в соответствующем разделе работы 5. Основным из них является тип данных Achar (от “attribute-character”), значение которого содержит как код символа, так и цвета (“атрибут”) тона (ink) и фона (paper). Функция draw позволяет выводить прямоугольный массив Achar в текущую позицию экрана (выбираемую функцией at).

Программа

Зададим несколько констант типа Achar, которые определяют “вид” различных клеток:

const Achar
  EMPTY  {' ', color::grey,   color::black},     // пустая клетка
  WALL   {'#', color::grey,   color::black},     // стена
  PLAYER {'@', color::yellow, color::black},     // игрок
  FLOOD  {'~', color::blue,   color::dark_blue}; // "затопленная клетка"

Глобальное состояние задаётся следующими целочисленными переменными:

int maze_width = 9, maze_height = 9;
int maze_total_size;
int player_x, player_y;

Переменная maze_total_size используется для удобства и хранит произведение maze_width * maze_height.

Переменные

Achar *maze_packed, *maze_packed_image;
Achar **maze, **maze_image;

используются для управления двумя динамическими двумерными массивами (способ 3). Массив maze содержит собственно описание лабиринта, а массив maze_image содержит “вид” лабиринта, отображаемый на экране. Использование двух массивов вместо одного позволяет упростить ряд операций.

Рисование лабиринта выполняется функцией draw_maze (функция draw определена в библиотеке con1):

void draw_maze()
{
  at(0, 0);
  draw(maze_packed_image, maze_height, maze_width);
}

Движение игрока обрабатывается функцией move_player:

void move_player()
{
  int nx = player_x + is_pressed(key::right) - is_pressed(key::left);
  int ny = player_y + is_pressed(key::down)  - is_pressed(key::up);
  if (maze[ny][nx] == EMPTY)
  {
    maze_image[player_y][player_x] = maze[player_y][player_x];
    maze_image[ny][nx] = PLAYER;
    player_y = ny;
    player_x = nx;
  }
}

Игрок не может проходить сквозь стены. Проходимость определяется через обращение к “мастер-копии” лабиринта — массиву maze. При этом символ игрока существует только в “образе лабиринта” — массиве maze_image.

Вызов функции new_game вызывает функцию new_maze, создающую новый лабиринт, которую мы рассмотрим ниже.

void new_game()
{
  new_maze();

  // Place the player.
  player_x = player_y = 1;
  maze_image[player_y][player_x] = PLAYER;
  maze[player_y][player_x] = EMPTY;
}

Все перечисленные выше функции вызываются функцией main, которая содержит цикл обработки ввода и вывода изображения (“game loop”):

int main()
{
  seconds(); // initialize the clock
  set_input_mode(mode::sync_input);
  new_game();

  while (!is_pressed(key::escape))
  {
    sync_input();
    if (is_pressed('r'))
    {
      reset_key('r');
      new_game();
    }

    if (is_pressed('f'))
    {
      maze_image[player_y][player_x] = EMPTY;
      flood_fill(player_x, player_y);
      maze_image[player_y][player_x] = PLAYER;
    }

    move_player();
    draw_maze();
    sleep(50);
  }

  return 0;
}

В коде main можно заметить ещё не описанную функцию flood_fill, которая вызывается при нажатии кнопки с литерой F. Эта функция вызывает “затопление” лабиринта, начиная с заданной позиции, которое заменяет пустые клетки в maze_image на затопленные, используя алгоритм поиска в глубину:

bool passable(int x, int y)
{
  return x >= 0 && y >= 0
    && x < maze_width && y < maze_height
    && maze_image[y][x] == EMPTY;
}

void flood_fill(int x, int y)
{
  if (passable(x, y))
  {
    maze_image[y][x] = FLOOD;
    flood_fill(x-1, y);
    flood_fill(x+1, y);
    flood_fill(x, y-1);
    flood_fill(x, y+1);
  }
}

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

Функция new_maze выполняет следующую последовательность действий:

  1. Удаление предыдущего лабиринта.
void new_maze()
{
  // Delete the old one.
  delete[] maze;
  delete[] maze_image;
  delete[] maze_packed;
  delete[] maze_packed_image;
  1. Запрос у пользователя размеров нового лабиринта.
  cls();
  input_echo(true);
  cursor_visible(true);

  cout << "Enter maze width and height: ";
  cin >> maze_width >> maze_height;

  input_echo(false);
  cursor_visible(false);
  cls();
  1. Обеспечение размеров лабиринта не меньше, чем 3 на 3. (А что если введены слишком большие значения?)
  if (maze_width < 3)
    maze_width = 3;
  if (maze_height < 3)
    maze_height = 3;
  1. Выделение памяти под новый лабиринт.
  maze_total_size = maze_width * maze_height;
  make_maze(maze_packed, maze);
  make_maze(maze_packed_image, maze_image);

Функция make_maze определена следующим образом:

void make_maze(Achar *&packed, Achar **&rows)
{
  packed = new Achar[maze_total_size];
  rows = new Achar*[maze_height];

  rows[0] = packed;
  for (int row = 1; row < maze_height; ++row)
    rows[row] = rows[row - 1] + maze_width;
}
  1. Инициализация псевдослучайной последовательности чисел.

Простейшим встроенным в Стандартную библиотеку C(++) средством генерации псевдослучайных чисел является функция rand(), возвращающая целое число в диапазоне от 0 до RAND_MAX (обычно 32767). Начальное “зерно” seed (номер последовательности) задаётся с помощью вызова функции srand(зерно). Распространённым способом “простого” вычисления как бы случайного зерна является использование текущего времени. Con1 определяет функцию seconds, которой мы здесь и воспользуемся.

  std::srand((unsigned)(3e+6 * seconds()));

Обычные реализации rand имеют довольно посредственное качество с точки зрения симуляции действительно случайных последовательностей с равномерным распределением. Стандартная библиотека C++11 содержит более развитые и качественные средства, определённые в заголовочном файле <random>.

Использование времени для генерации зерна также не является “качественным” с точки зрения симуляции истинной случайности и не подходит для “чувствительных” применений (например, криптографии).

  1. Заполнение массива сплошной “стеной”, в которой будем потом проделывать ходы:
  for (int i = 0; i < maze_total_size; ++i)
    maze_packed[i] = WALL;
  1. Собственно генерация лабиринта выполняется функцией recursive_trace, которую и надо будет запрограммировать (алгоритм описан ниже).
  int stx = maze_width/2, sty = maze_height/2;
  stx += (stx & 1) == 0;
  sty += (sty & 1) == 0;

  recursive_trace(stx, sty);
  1. После того как создана “мастер-копия” лабиринта, мы можем скопировать её в “образ”. Одним вызовом стандартной функции memcpy.
  std::memcpy(maze_packed_image, maze_packed, maze_total_size * sizeof(Achar));

Код целиком.


Задание

Воплотить в виде функции recursive_trace описанный ниже алгоритм (поиск в глубину со случайным выбором направлений). Функция изменяет массив maze.

Пример. Допустим выбрано направление “восток”. Тогда “соседняя с (x, y) в выбранном направлении клетка” имеет координаты (x+1, y), а “следующая в выбранном направлении клетка” — координаты (x+2, y).

Функция traceable вычисляет предикат “можно идти через клетку (x, y)”.

bool traceable(int x, int y)
{
  return x > 0 && y > 0
    && x < maze_width-1 && y < maze_height-1
    && maze[y][x] == WALL;
}

Таким образом, “можно идти через две клетки в выбранном направлении” означает, что traceable(x+1, y) и traceable(x+2, y) возвращают “истину”.


Приложение

Код программы

// maze_gen.cpp
#include "con1.hpp"
#include <cstdlib>
#include <cstring>
#include <utility>
using namespace con1;
using std::swap;

////////////////////////////////////////////////////////////////////////////////
// Global constants.
////////////////////////////////////////////////////////////////////////////////
const Achar
  EMPTY  {' ', color::grey,   color::black},
  WALL   {'#', color::grey,   color::black},
  PLAYER {'@', color::yellow, color::black},
  FLOOD  {'~', color::blue,   color::dark_blue};

////////////////////////////////////////////////////////////////////////////////
// Global state.
////////////////////////////////////////////////////////////////////////////////
int maze_width = 9, maze_height = 9;
int maze_total_size;
int player_x, player_y;

Achar *maze_packed, *maze_packed_image;
Achar **maze, **maze_image;

////////////////////////////////////////////////////////////////////////////////
// Procedures.
////////////////////////////////////////////////////////////////////////////////
void make_maze(Achar *&packed, Achar **&rows)
{
  packed = new Achar[maze_total_size];
  rows = new Achar*[maze_height];

  rows[0] = packed;
  for (int row = 1; row < maze_height; ++row)
    rows[row] = rows[row - 1] + maze_width;
}


bool passable(int x, int y)
{
  return x >= 0 && y >= 0
    && x < maze_width && y < maze_height
    && maze_image[y][x] == EMPTY;
}

void flood_fill(int x, int y)
{
  if (passable(x, y))
  {
    maze_image[y][x] = FLOOD;
    flood_fill(x-1, y);
    flood_fill(x+1, y);
    flood_fill(x, y-1);
    flood_fill(x, y+1);
  }
}


bool traceable(int x, int y)
{
  return x > 0 && y > 0
    && x < maze_width-1 && y < maze_height-1
    && maze[y][x] == WALL;
}

void recursive_trace(int x, int y)
{
  // ???
}

void new_maze()
{
  // Delete the old one.
  delete[] maze;
  delete[] maze_image;
  delete[] maze_packed;
  delete[] maze_packed_image;

  // Enter new maze sizes.
  cls();
  input_echo(true);
  cursor_visible(true);

  cout << "Enter maze width and height: ";
  cin >> maze_width >> maze_height;

  input_echo(false);
  cursor_visible(false);
  cls();

  if (maze_width < 3)
    maze_width = 3;
  if (maze_height < 3)
    maze_height = 3;

  // Allocate memory for the new maze.
  maze_total_size = maze_width * maze_height;
  make_maze(maze_packed, maze);
  make_maze(maze_packed_image, maze_image);

  // Randomize.
  std::srand((unsigned)(3e+6 * seconds()));

  ////////////////////////////
  // Generate maze.

  // Part 1. All is WALL.
  for (int i = 0; i < maze_total_size; ++i)
    maze_packed[i] = WALL;

  // Part 2. The Inner Maze.
  int stx = maze_width/2, sty = maze_height/2;
  stx += (stx & 1) == 0;
  sty += (sty & 1) == 0;

  recursive_trace(stx, sty);

  // Initialize the maze image.
  std::memcpy(maze_packed_image, maze_packed, maze_total_size * sizeof(Achar));
}

void new_game()
{
  new_maze();

  // Place the player.
  player_x = player_y = 1;
  maze_image[player_y][player_x] = PLAYER;
  maze[player_y][player_x] = EMPTY;
}

void draw_maze()
{
  at(0, 0);
  draw(maze_packed_image, maze_height, maze_width);
}

void move_player()
{
  int nx = player_x + is_pressed(key::right) - is_pressed(key::left);
  int ny = player_y + is_pressed(key::down)  - is_pressed(key::up);
  if (maze[ny][nx] == EMPTY)
  {
    maze_image[player_y][player_x] = maze[player_y][player_x];
    maze_image[ny][nx] = PLAYER;
    player_y = ny;
    player_x = nx;
  }
}

////////////////////////////////////////////////////////////////////////////////
// Game loop.
////////////////////////////////////////////////////////////////////////////////
int main()
{
  seconds(); // initialize the clock
  set_input_mode(mode::sync_input);
  new_game();

  while (!is_pressed(key::escape))
  {
    sync_input();
    if (is_pressed('r'))
    {
      reset_key('r');
      new_game();
    }

    if (is_pressed('f'))
    {
      maze_image[player_y][player_x] = EMPTY;
      flood_fill(player_x, player_y);
      maze_image[player_y][player_x] = PLAYER;
    }

    move_player();
    draw_maze();
    sleep(50);
  }

  return 0;
}

Общее оглавление

Кувшинов Д.Р. © 2016