Сегодня я поделюсь своей наработкой игры «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() { 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(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(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(); }
Генерация работает, теперь дело за малым: найти в таком лабиринте выход. Рисуем выход тем же способом, что и рисовали лабиринт. Но все упрощается, так как не надо удалять стенки. На этом у меня все, в следующей статье будет описан способ поиска выхода.
ссылка на оригинал статьи http://habrahabr.ru/post/265307/
Добавить комментарий