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();
        }

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

Комментарии (11)


  1. Anvol
    24.08.2015 10:51
    +4

    Не найдя способа распознования типа клетки и перешел на хитрость

    Добавить в struct Cells еще одно поле с типом перечисления CellType, в котором перечислить все возможные типы клеток. В том числе и вход/выход, телепорт, подземелье и клад :)
    И стоит именовать структуру — Cell, она отражает одну клетку.


    1. cool_grass
      30.08.2015 18:16

      Вы правы, я сперва так и сделал, но запутался и решил все сделать по быстрому, т.к. очень спешил. Теперь я буду делать «красивый» код.


  1. perfectdaemon
    24.08.2015 12:43
    +2

    Но узнав, что в основном с DX ты будешь работать с языком с++,

    Вы неправы совершенно. Одних только хедеров и врапперов к C# не счесть: Managed DirectX, SharpDX, SlimDX…
    Даже выбранный вами XNA рисует через DirectX


    1. cool_grass
      30.08.2015 18:04

      Поэтому я и выбрал XNA так как люблю C#


  1. AWE64
    24.08.2015 14:03

    Совет на будущее: используйте поменьше магических чисел в коде, а то попытка разобраться в нем —.сама по себе этакий лабиринт.


    1. redmanmale
      24.08.2015 20:34

      Да и код можно было на гитхаб выложить.


  1. kekekeks
    24.08.2015 16:35
    +1

    Относительно сравнения в начале статьи. XNA вне конкуренции просто потому, что работает на iOS/Android/Linux/Mac OS/PS4.


  1. imbeat
    25.08.2015 10:13

    cool_grass, если не трудно, выложите, пожалуйста, код в какой-нибудь (например, GitHub) публичный репозиторий, чтобы можно было скачать, открыть, запустить,… ну или даже форкнуть, если захочется. Спасибо.


    1. cool_grass
      30.08.2015 18:21

      Сейчас сделал и прохождение, в понедельник обновлю статью, перепишу ее, и оновлю. Вот ссылка на проект.


  1. mersinvald
    03.09.2015 17:31

    Неожиданно, у меня уже учатся. Приятно, главное не зазнаться)


    1. cool_grass
      03.09.2015 18:17

      Я скажу больше, такого больше нигде я не увидел. Решение классное, мне понравилось, решил взять и переписать под XNA. Сегодня наверное статью перепишу.