Сегодня я поделюсь своей наработкой игры «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;
}
Загрузка текстур
Не найдя способа распознования типа клетки и перешел на хитрость. Загружал в переменную Hash Code ресурсов клетки.
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
Генерация работает, теперь дело за малым: найти в таком лабиринте выход. Рисуем выход тем же способом, что и рисовали лабиринт. Но все упрощается, так как не надо удалять стенки. На этом у меня все, в следующей статье будет описан способ поиска выхода.
