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