Время на прочтение
6 мин
Количество просмотров 13K
Сегодня я поделюсь своей наработкой игры «Maze». В этой игре реализован алгоритм DFS. На днях мне поручили сделать курсовую работу по Алгоритмам, а именно по DFS в лабиринтах. Отказываться было нельзя. Пришел домой, выпил чашечку крепкого кофе и начал творить.
Перед тем как открыть Visual Studio, я решил поискать готовые лабиринты. Как я и думал, я нашел кучу материала. Все лабиринты (искал я только разные и интересные) были написаны на разных языках, платформах, но у них было что-то общее, а именно — все они были C-подобными.
Тяжело было определиться между рядом платформ, на которых можно разрабатывать такую идею (для первокурсника). Все ниже перечисленные платформы обладают своими достоинствами и недостатками.
- Windows Form
- WPF
- Direct X
- XNA
Windows Form
Открыл студию, кинул на панель кнопку и думаю: ” А где я буду рисовать свой лабиринт и как он будет выглядеть?”. Найдя в интернете необходимый материал, я понял, что должна быть какая-то матрица, которая хранит в себе координаты ячеек и их типы.
В WF я решил пойти ламерским способом и создал сетку компонентов. Далее начал создавать (динамически) обычные панели. Сперва все было классно, пока не столкнулся с проблемой: при большом расширении лабиринта программа просто зависала. Тут я решил отступить от своей идеи и найти новую платформу.
WPF
WPF Мне всегда нравился своим функционалом. Способов рисования лабиринта WPF предоставлял кучу — все не перепробовать. Решил рисовать массив клеток используя Path. Но напоролся на грабли: проект опять получался затратным по ресурсам. И способа обратиться к нарисованной клетке я не нашел. Время поджимало, а найти платформу для рисования так и не получалось.
Direct X
Технологии Direct X невероятно огромные, и я бы 100% нашел способ как сотворить свой лабиринт и алгоритм для его создания. Но узнав, что
в основном с DX ты будешь работать с языком с++, я был сильно огорчен. Работать и создавать программы на языке с++ мне не доводилось, так что отбросил и эту идею.
XNA
О технологии XNA мне рассказал одногруппник и представил свою созданную змейку. И тут я понял: это то, что мне нужно. Посмотрев пару уроков о том как работать с XNA, я принялся создавать свою игру! Наткнувшись на эту статью, я решил пойти по плану mersinvald.
Набросав план, я бросился в бой!
- Создать матрицу
- Реализовать алгоритм DFS
- Рисовать лабиринт
Создание матрицы я выделил в отдельный класс.
class Matrix
{
private struct Size // Использование структур поможет убрать большое кол-во переменных и значительно упростит жизнь при обмене информацией между функциями.
public int Width { get; set; }
public int Height { get; set; }
}
readonly Size _size; // Размер лабиринта
readonly Texture2D[,] _maze; // Массив текстур клеток массива
public Matrix(Maze.Cells size , Texture2D[,] cell2D)
{
_maze = cell2D;
_size.Width = size.X;
_size.Height = size.Y;
}
public void Draw(SpriteBatch spriteBatch) // Начинаем рисовать начальную матрицу
{
for (var i = 0; i < _size.Height; i++)
{
for (var j = 0; j < _size.Width; j++)
{
if ((i % 2 != 0 && j % 2 != 0) && (i < _size.Height - 1 && j < _size.Width - 1)) //если ячейка нечетная по x и y, и не выходит за границы лабиринта
{
spriteBatch.Draw(_maze[i, j], new Rectangle(i * 10, j * 10, 10, 10), Color.White); // То это клетка
}
else
{
spriteBatch.Draw(_maze[i, j], new Rectangle(i * 10, j * 10, 10, 10), Color.White); // в остальных случаях это стена
}
}
}
}
}
Матрица сгенерирована, точнее создан массив клеток. Теперь каждой клетке (стене и полу) нужно задать свою текстуру. Переходим в основной класс и создаем все необходимые переменные.
Начало основного проекта
public struct Cells
{
public int X;
public int Y;
public Cells(int newX, int newY)
{
X = newX;
Y = newY;
}
}
private SpriteBatch _spriteBatch;
private readonly Texture2D[,] _maze; // Массив клеток
private Cells _size; // Размер лабиринта
private readonly Cells _start;
private readonly Cells _finish;
private int _cell; // Клетка
private int _wall; // Стена
private int _visited; // Посещенная клетка
private readonly List<Cells> _neighbours; // Список соседей
private readonly Stack<Cells> _path; // Стэк путей лабиринта
private int _status; // Статус готовности лабиринта
public Maze(List<Cells> neighbours, Stack<Cells> path)
{
_neighbours = neighbours;
_path = path;
var graphics = new GraphicsDeviceManager(this);
Content.RootDirectory = "Content";
var winWidth = graphics.PreferredBackBufferWidth = 210;
var winHeight = graphics.PreferredBackBufferHeight = 210;
_size = new Cells(winWidth/10, winHeight/10);
_start = new Cells(1, 1);
_finish = new Cells(_size.X - 2, _size.Y - 2);
_maze = new Texture2D[_size.X, _size.Y];
_path.Push(_start);
IsMouseVisible = true;
}
Загрузка текстур
protected override void LoadContent()
{
_spriteBatch = new SpriteBatch(GraphicsDevice);
for (var i = 0; i < _size.Y; i++)
{
for (var j = 0; j < _size.X; j++)
{
if ((i%2 != 0 && j%2 != 0) && (i < _size.Y - 1 && j < _size.X - 1)) // Способ анологичен с генерацией матрицы. Если ячейка нечетная по x и y, и находится в пределах размера лабиринта
{
_maze[i, j] = Content.Load<Texture2D>("flat"); // Загружаем пол
_cell = _maze[i, j].GetHashCode(); // Нужно для распознавания типа клетки.
}
else
{
_maze[i, j] = Content.Load<Texture2D>("wall");// Загружаем стену
_wall = _maze[i, j].GetHashCode();
}
}
}
}
Не найдя способа распознования типа клетки и перешел на хитрость. Загружал в переменную Hash Code ресурсов клетки.
_wall = _maze[i, j].GetHashCode();
_cell = _maze[i, j].GetHashCode();
Наша матрица готова и отображается на экране. Теперь дело за малым, создание ветвей лабиринта. Создадим 3 VOID:
- DrawMaze — Рисуем лабиринт
- GetNeighbours — Получаем соседей текущей клетки
- RemoteWall — Убираем стены
private void DrawMaze()
private void DrawMaze()
{
if (_path.Count != 0) // Если стек не пуст , есть непосещенные клетки
{
GetNeighbours(_path.Peek()); // Получаем соседей Верхнего элемента стека, текущей клетки
if (_neighbours.Count != 0) // Проверяем список соседий , если есть сосед(и)
{
var a = _neighbours[new Random().Next(0, _neighbours.Count)]; // Получаем случайног ососеда
RemoteWall(_path.Peek(), a); // Убираем стену между текущей клеткой и соседом
_path.Push(a); // Продвигаем соседа в стек и делаем его активной клеткой
_neighbours.Clear(); // очищаем список соседий
}
else
{
_path.Pop(); // если нет соседий , перейти на предыдущую клетку
}
}
else // Если стек пуст и нет непосещенных клеток
{
MainPoint(); // Рисуем точки старт и финиш
_status = 1; // Передаем статус созданного лабиринта
}
}
private void GetNeighbours()
private void GetNeighbours(Cells localcell) // Получаем соседа текущей клетки
{
var x = localcell.X;
var y = localcell.Y;
const int distance = 2;
var d = new[] // Список всех возможных соседий
{
new Cells(x, y - distance), // Up
new Cells(x + distance, y), // Right
new Cells(x, y + distance), // Down
new Cells(x - distance, y) // Left
};
for (var i = 0; i < 4; i++) // Проверяем все 4 направления
{
var s = d[i];
if (s.X <= 0 || s.X >= _size.X || s.Y <= 0 || s.Y >= _size.Y) continue; // Если сосед не выходит за стенки лабиринта
if (_maze[s.X, s.Y].GetHashCode() == _wall || _maze[s.X, s.Y].GetHashCode() == _visited) continue; // И не является стеной или уже посещенной клеткой
_neighbours.Add(s); // добовляем соседа в Лист соседей
}
}
private void RemoteWall()
private void RemoteWall(Cells first, Cells second) // Убираем стену между 2 клетками
{
var xDiff = second.X - first.X;
var yDiff = second.Y - first.Y;
Cells target;
Cells newCells;
var addX = (xDiff != 0) ? xDiff/Math.Abs(xDiff) : 0; // Узнаем направление удаления стены
var addY = (yDiff != 0) ? yDiff/Math.Abs(yDiff) : 0;
target.X = first.X + addX; // Координаты удаленной стены
target.Y = first.Y + addY;
_maze[target.X, target.Y] = Content.Load<Texture2D>("visited"); // Загружаем в клетку соседней стены - посещенную клетку
_maze[_path.Peek().X, _path.Peek().Y] = Content.Load<Texture2D>("visited"); // Загружаем в текущую клетку - посещенную клетку
_visited = _maze[target.X, target.Y].GetHashCode(); // Получаем Hash Code посещенной стены
newCells.X = first.X + 2*addX;
newCells.Y = first.Y + 2*addY;
_path.Push(newCells); // Загружаем в стек новую клетку
_maze[_path.Peek().X, _path.Peek().Y] = Content.Load<Texture2D>("visited"); // Загружаем в новую клетку - посещенную клетку
}
Ну и код для отрисовки начальных точек:
private void MainPoint()
{
_maze[_start.X, _start.Y] = Content.Load<Texture2D>("start");
_starter = _maze[1, 1].GetHashCode();
_maze[_finish.X, _finish.Y] = Content.Load<Texture2D>("finish");
_finisher = _maze[_finish.X, _finish.Y].GetHashCode();
}
Dowload
Генерация работает, теперь дело за малым: найти в таком лабиринте выход. Рисуем выход тем же способом, что и рисовали лабиринт. Но все упрощается, так как не надо удалять стенки. На этом у меня все, в следующей статье будет описан способ поиска выхода.
Задача
Создать игру с лабиринтом который нужно пройти не коснувшись стенок
При касании стенок лабиринта мы возвращаемся назад
Задания
Создаем фон
Уменьшаем персонажа под размеры лабиринта
Создаем 1 вариант управления персонажем
Касается цвета настраиваем с помощью пипетки
2 Способ управления
Обучающие игры в виде небольшого путешествия с участием игровых персонажей достаточно часто встречаются в педагогической практике.
Такая интерактивная игра может использоваться:
- в качестве самостоятельного ЭОР для освоения понятия, темы и даже раздела учебного предмета;
- как элемент более обширной темы, урока, мероприятия;
- в качестве занятия или его части (введения, объяснения, закрепления, упражнения, контроля).
Для создания таких игр можно воспользоваться обычным офисным приложением PowerPoint. Возможностей этого приложения достаточно для педагога, который не знаком с программированием и просто является пользователем программы для создания презентаций.
Рассмотрим порядок создания игры “Лабиринт”.
Идея игры взята из курса по робототехнике «Робокласс». Игровые персонажи — инфики: ВсеЗнайка, Самоделкин, Кибернетик. Графические объекты — элементы LEGO Mindstorms. Школьнику необходимо преодолеть лабиринт, отвечая на вопросы, которые ему задают инфики. В случае правильного ответа на все вопросы лабиринт будет пройден.
1. Разберем подробно этап создания игры в программе PowerPoint.
А. Формируем лабиринт с помощью каких-либо графических фигур и рисунков. Это может быть множество колес или иные объекты. Добавим фоновое изображение — шестерёнку.
В игре будет предусмотрено три вопроса и три героя, которые будут озвучивать эти вопросы играющему. Для демонстрации вопросов можно использовать изображение электронного табло. Для движения по лабиринту используем изображение робота.
Б. Добавляем текстовое сообщение о том, что для начала игры необходимо кликнуть мышкой по роботу. Для перехода к следующему вопросу игры используем стрелку. Эта стрелка будет появляться только в случае правильного ответа.
Игровое поле готово. Оно понадобится нам для всех трех вопросов. Поэтому можно этот слайд продублировать дважды. По ходу игры будем убирать героев, которые уже задали свои вопросы. А робота будем перемещать по лабиринту.
В. Приступаем к созданию анимационных эффектов для графических изображений и текстового содержимого.
Итак, все слайды готовы. Не забудьте похвалить школьника, успешно прошедшего лабиринт.
2. Публикуем созданную интерактивную игру с помощью программных продуктов iSpring. Теперь эту игру можно разместить в интернете или использовать на занятии в компьютерном классе.
Пример игры доступен здесь.
Если вам понравилась статья, дайте нам знать — нажмите кнопку Поделиться.
А если у вас есть идеи для полезных статей на тему электронного обучения — напишите нам в комментариях, и мы будем рады поработать над новым материалом.
Приступаем
к работе.
Запускаем
программу Kodu Game Lab, в
открывшимся окне выбираем вкладку «NEW WORLD».
Рис. 3 – Создание пустого мира
После
нажатия на «NEW WORLD»
открылась рабочая плоскость. В нижней части находится панель взаимодействия с
миром.
Рис. 4 – Рабочая плоскость
Нижняя
панель имеет следующие компоненты:
·
Главное меню
·
Играть
·
Перемещает камеру
·
Объект
·
Путь
·
Кисть для земли
·
Вверх/вниз
·
Сглаживание
·
Неровности
·
Вода
·
Удалить
·
Изменяет параметры мира
Создание компьютерной игры «Лабиринт» состоит из
нескольких пунктов:
1.
Создание лабиринта;
2.
Создание «Байкеров»;
3.
Программирование «Байкеров»;
4.
Тестирование игры.
Так как, по умолчанию при создании игры рабочая
плоскость имеет зеленый цвет, мы ее изменим. Для этого в панели инструментов
выберем «Кисть».
Кисть – для
земли. Рисует, добавляет или удаляет землю.
Рис. 5 – Кисть для земли
В левой части над «Кистью», располагаются
четыре квадрата, нажав на которые появляется возможность выбрать цвет рабочей
плоскости, на которой мы работаем.
Рис. 6 – Выбор цвета рабочей области
Наводим
мышку с мерцающим квадратом на рабочую плоскость и нажимаем один раз.
Рис. 7 – Смена цвета рабочей плоскости
Далее мы выбираем новый цвет, тем
же способом, каким ранее изменили цвет рабочей плоскости. – Рис 8.
В панели задач, над «Кистью»
располагается с левой стороны выбор цвета для рабочей плоскости, а справа
выбор способа нанесения цвета на рабочую плоскость. – Рис 9.
Выбрав цвет
и способ нанесения чертежа «Длинная прямая кисть» – предназначенный
для создания прямых линий на плоскости, создаем набросок лабиринта.
Рис. 8 – Чертеж
Лабиринта
Рис. 9 –
Выбор элемента «Длинная прямая кисть» для черчения Лабиринта
Далее выбираем «Вверх/вниз – создает холмы и
долины». – Рис 10. Над элементом «Вверх/вниз» находятся четыре фигуры,
нажимаем на них и выбираем «Волшебная кисть» – Рис. 11. После, правой
кнопкой мыши нажимаем на нарисованный вторым цветом чертеж и держим, до
нужного нам увеличения стен.
Рис. 10 – Вверх/вниз
Рис. 11 – «Вверх/вниз» Волшебная кисть
Рис. 12 – Создание возвышения №1
Рис. 13 – Создание возвышения №2
Для создания новых объектов, на панели задач
воспользуемся элементом «Объект» – элемент с помощью которого
происходит создание и добавление различных персонажей и новых объектов.
Рис. 14 – Объект
Выбрав «Объект» нажимаем правой кнопкой мыши
на рабочей плоскости и выбираем «Добавить объект».
Рис. 15 – Добавление объекта «Байкер» №1
В
появившимся круглом меню, находим «Байкера».
Рис. 16 – Добавление объекта «Байкер» №2
Рис. 17 – Добавление объекта «Байкер» №3
После добавления и появления объекта «Байкер» на
плоскости, он имеет большой размер. – Рис 18.
Рис. 18 – Байкер
Для изменения размера Байкера, нажимаем на него
правой кнопкой мыши – «Изменить размер».
Рис. 19 – Изменение размера Байкера №1
В
появившийся шкале «Размера» уменьшаем наше значение до 0,2.
Рис. 20 –
Изменение размера Байкера №2
Динамическая пауза
https://www.youtube.com/watch?v=Wcr4ZB_4Iqo
Продолжаем нашу работу. Правой кнопкой мыши нажимаем
на нашего Байкера и выбираем «Программа».
Рис. 21 – Программа
В чем будет заключаться суть нашей игры:
У нас есть лабиринт в конце которого находится
яблоко. Мы играем за Красного Байкера (Доброго), которому нужно преодолеть лабиринт
и не столкнуться со «Злыми Байкерами» – докоснувшись до которых «Игра
закончена» и мы проиграли.
Если же нам удалось пройти лабиринт, увернуться и
уехать от всех «Злых Байкеров», а также найти и докоснуться до яблока, то
тогда мы победили.
Программа
для «Злых Байкеров».
Рис. 22 – Программа для «Злых Байкеров»
Программа
для «Доброго Байкера».
Рис. 23 – Программа для «Доброго Байкера»
Схема
расположения Байкеров:
«Злые
Байкеры» – красные кружки – 7 штук.
«Добрый
Байкер» – желтый кружок, представлена на Рис. 24.
Для того, чтобы в программа различала байкеров между
собой, Главного Байкера, за которого будем играть мы, сделаем красным цветом.
– Рис. 25.
Рис. 24 – Схема расположения Байкеров
Рис. 25 – Выбор цвета Главного байкера
Добавим в конец лабиринта «Яблоко» – которое и будет
символизировать победу в случае если главный байкер докоснется до него.
Правой кнопкой мыши на рабочей плоскости, где хотим,
чтобы появилось «Яблоко». Далее «Добавить объект», находим «Яблоко».
Рис. 26 – Создание Яблока
Если
«Злые Байкера» дотронутся до «Главного байкера» появится окно о поражении. 
Рис. 27 – Game over
Если все же «Главный байкер» сумел добраться до
Яблока и коснуться его, появится окно, о победе.
Рис. 28 – Winner
Не секрет, что все дети любят играть в компьютерные и мобильные игры, а также что многие из них хоть раз да задумывались над созданием собственной игры. Но для создания собственной игры нужно знать, как минимум, основы программирования на одном из языков, владеть навыками 3D-моделирования и работой с игровым движком.
В качестве языка программирования для создания их первых простейших игр мы используем Scratch. Scratch — это визуальный язык программирования, специально разработанный для детей. Во-первых, он доступен онлайн и не требует установки чего-либо.
Во-вторых, это интегрированная среда, рисуешь код и сразу его исполняешь, сразу же видно результат.
В-третьих, он заточен на создание игр, в нем уже существует библиотека спрайтов и фонов, а также специальные “игровые” операторы, вроде “Повернуть, если врезался в стену”.
После данного занятия ученики станут ближе к воплощению своей идеи в проектировании и программировании первой игры. На занятии ребята создадут игру с главным героем, задачей которого будет добраться до выхода из лабиринта.
Текстовая версия:
Начнем мы с выбора фона в виде двухмерного лабиринта. Лабиринт мы можем нарисовать свой или использовать готовый. Для того, чтобы нарисовать свой лабиринт необходимо навести курсор мыши на кнопку “Выбрать фон”, а затем во всплывшем меню нажать кнопку “Нарисовать”.
После этого в открывшемся окне для рисования с помощью инструментов нарисовать лабиринт.
Если же мы хотим использовать уже готовое изображение лабиринта, взятое из интернета или нарисованное в другом графическом редакторе, то нам опять же нужно навести курсор на кнопку “Выбрать фон”, а во всплывшем меню нажать кнопку “Загрузить фон”. После этого в открывшемся окне найти уже готовое изображение.
Следующая наша задача – это добавить спрайт, которым игрок должен пройти лабиринт, а также спрайт, который будет ожидать нас в конце лабиринта. Чтобы добавить спрайта нужно нажать кнопку “Выбрать спрайт” в правом нижнем углу экрана. Откроется библиотека спрайтов. Для того, чтобы добавить понравившийся спрайт в проект достаточно кликнуть по нему левой кнопкой мыши.
Для данного проекта лучшего всего использовать спрайт “Ball” в виде главного действующего лица, поскольку он симметричен и у игрока не будет проблем, связанных с тем, что при повороте спрайт задевает стенки лабиринт. В качестве конечной точки лабиринта воспользуемся спрайтом “Cake”. Вы можете использовать любые спрайты.
На текущем этапе у нас есть изображение лабиринта и два спрайта. Следующим этапом будет добавление блоков для движения спрайта “Ball” по лабиринту для этого нужно выбрать спрайт в списке снизу левым кликом. Например, на рисунке выше у нас выбран спрайт “Cake”. Это можно понять по синему выделению и корзинке правее и чуть выше значка спрайта. Сейчас нам нужно выбрать спрайт “Ball”. Движение мы будем осуществлять с помощью стрелок. Для этого из вкладки “События” мы выбираем блок “Когда клавиша пробел нажата” и вытаскиваем его в рабочее поле. После этого кликаем левым щелчком мыши по блоку и выбираем “Стрелка вверх”, вместо “Пробел”.
Поскольку по умолчанию все спрайты после добавление в Scratch повернуты в направлении 90 (вправо), то нам нужно, чтобы спрайт при нажатии поворачивался в соответствии со стрелкой. Делаем это с помощью блока “Повернуться в направлении” из вкладки “Движение”. После этого мы кликаем левым щелчком по цифрам, принадлежащим этим блокам. Откроется окно, с выбором направления. Здесь нам нужно просто перетащить стрелку в соответствующем направлении.
Следующим этапом будет добавление условия, чтобы при касании стенки лабиринта наш возвращался в начальное положение. Для этого мы будем использовать блок “Если-то” из кладки управление. В качестве условия мы воспользуемся блоком “Касается цвета” из вкладки “Сенсоры”. А в качестве команды, если условие оказывается верным будет блок “перейти” из вкладки “движение”. Чтобы задать координаты начала уровня достаточно расположить спрайт “Ball” в нужной позиции и тогда при перетаскивании блока “Перейти” он перетащится с нужными координатами.
После этого с помощью дублирования делаем аналогичные команды для остальных стрелок и добавляем условие, что при касании спрайта “Cake” нас нужно уведомить о выигрыше, а уровень начался заново. Таким образом будет выглядеть наш итоговый вариант кода.
В дальнейшем проект можно дополнять. Например, сделать так, чтобы при
касании стенки лабиринта мы от нее отталкивались, а не начинали уровень заново,
добавить различные бонусы или телепорты, добавить негативных персонажей,
создать несколько сменяющих друг друга уровней.
