Пишем Лабиринт на XNA 4.0 C#

от автора

image
Сегодня я поделюсь своей наработкой игры «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();         } 

Генерация работает, теперь дело за малым: найти в таком лабиринте выход. Рисуем выход тем же способом, что и рисовали лабиринт. Но все упрощается, так как не надо удалять стенки. На этом у меня все, в следующей статье будет описан способ поиска выхода.

ссылка на оригинал статьи http://habrahabr.ru/post/265307/


Комментарии

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

Ваш адрес email не будет опубликован. Обязательные поля помечены *