1 /*********************************************************************** 2 * 3 * Copyright (C) 2007, 2008, 2012, 2014 Graeme Gott <graeme@gottcode.org> 4 * 5 * This program is free software: you can redistribute it and/or modify 6 * it under the terms of the GNU General Public License as published by 7 * the Free Software Foundation, either version 3 of the License, or 8 * (at your option) any later version. 9 * 10 * This program is distributed in the hope that it will be useful, 11 * but WITHOUT ANY WARRANTY; without even the implied warranty of 12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13 * GNU General Public License for more details. 14 * 15 * You should have received a copy of the GNU General Public License 16 * along with this program. If not, see <http://www.gnu.org/licenses/>. 17 * 18 ***********************************************************************/ 19 20 #ifndef MAZE_H 21 #define MAZE_H 22 23 #include "cell.h" 24 25 #include <QList> 26 #include <QLinkedList> 27 #include <QPoint> 28 #include <QVector> 29 30 #include <random> 31 32 class Maze 33 { 34 public: ~Maze()35 virtual ~Maze() 36 { } 37 columns()38 int columns() const 39 { return m_columns; } rows()40 int rows() const 41 { return m_rows; } cell(int column,int row)42 const Cell& cell(int column, int row) const 43 { return m_cells.at(column).at(row); } cellMutable(int column,int row)44 Cell& cellMutable(int column, int row) 45 { return m_cells[column][row]; } 46 47 void generate(int columns, int row, std::mt19937& random); 48 bool load(); 49 void save() const; 50 51 protected: 52 void mergeCells(const QPoint& cell1, const QPoint& cell2); 53 randomInt(std::uint_fast32_t max)54 std::uint_fast32_t randomInt(std::uint_fast32_t max) 55 { 56 std::uniform_int_distribution<std::uint_fast32_t> gen(0, max - 1); 57 return gen(m_random); 58 } 59 60 QPoint randomNeighbor(QVector<QVector<bool>>& visited, const QPoint& cell); 61 62 private: 63 virtual void generate() = 0; 64 65 std::mt19937 m_random; 66 int m_columns; 67 int m_rows; 68 QVector< QVector<Cell> > m_cells; 69 }; 70 71 72 class HuntAndKillMaze : public Maze 73 { 74 private: 75 virtual void generate(); 76 QPoint hunt(); 77 78 QVector< QVector<bool> > m_visited; 79 int m_unvisited; 80 }; 81 82 83 class KruskalMaze : public Maze 84 { 85 private: 86 virtual void generate(); 87 88 typedef QList<QPoint> Set; 89 QLinkedList<Set> m_sets; 90 QVector< QVector<Set*> > m_set_ids; 91 }; 92 93 94 class PrimMaze : public Maze 95 { 96 private: 97 virtual void generate(); 98 void moveNeighbors(const QPoint& cell); 99 void mergeRandomNeighbor(const QPoint& cell); 100 QList<QPoint> neighbors(const QPoint& cell); 101 102 QList<QPoint> m_frontier; 103 QVector< QVector<int> > m_regions; 104 }; 105 106 107 class RecursiveBacktrackerMaze : public Maze 108 { 109 private: 110 virtual void generate(); 111 void makePath(const QPoint& current); 112 113 QVector< QVector<bool> > m_visited; 114 }; 115 116 117 class StackMaze : public Maze 118 { 119 private: 120 virtual void generate(); 121 virtual int nextActive(int size); 122 123 QVector< QVector<bool> > m_visited; 124 }; 125 126 127 class Stack2Maze : public StackMaze 128 { 129 private: 130 virtual int nextActive(int size); 131 }; 132 133 134 class Stack3Maze : public StackMaze 135 { 136 private: 137 virtual int nextActive(int size); 138 }; 139 140 141 class Stack4Maze : public StackMaze 142 { 143 private: 144 virtual int nextActive(int size); 145 }; 146 147 148 class Stack5Maze : public StackMaze 149 { 150 private: 151 virtual int nextActive(int size); 152 }; 153 154 #endif // MAZE_H 155