Labyrinth descriptions, their characteristics and algorithms can be described Sooner or later, you're stumbling into a dead end, then it starts moving back and looking for new unattended cells. In the end, after such manipulations, you'll get a network of walks that'll be in the labyrinth. There's only one thing left to make holes for start or end or to use cells at his own discretion.Unfortunately, I've already forgotten the C++, so there may be some mistakes and I can't make a quick visual on it. Therefore, the implementation of WPF + rendering in Canvas with pictures has been added to the response [C+++]#include <iostream>
#include <cstdlib>
#include <time.h>
#include <stack>
#include <vector>
using namespace std;
enum CellState { Close, Open };
class Cell
{
public:
int x;
int y;
CellState Left;
CellState Right;
CellState Top;
CellState Bottom;
bool Visited;
};
int main(int argc, char **argv)
{
const int width = 5,
height = 5;
Cell labyrinth[width][height];
//заполняем начальные данные для ячеек
for (int y = 0; y < height; y++)
for (int x = 0; x < width; x++)
{
labyrinth[x][y].x = x;
labyrinth[x][y].y = y;
labyrinth[x][y].Visited = false;
}
//Выбираем первую ячейку откуда начнем движение
srand(time(NULL));
int startX = rand() % width;
int startY = rand() % height;
labyrinth[startX][startY].Visited = true;
//Заносим нашу ячейке в path и начинаем строить путь
stack<Cell> path;
path.push(labyrinth[startX][startY]);
while (!path.empty())
{
Cell _cell = path.top();
//смотрим варианты, в какую сторону можно пойти
vector<Cell> nextStep;
if (_cell.x > 0 && (labyrinth[_cell.x - 1][_cell.y].Visited == false))
nextStep.push_back(labyrinth[_cell.x - 1][_cell.y]);
if (_cell.x < width - 1 && (labyrinth[_cell.x + 1][_cell.y].Visited == false))
nextStep.push_back(labyrinth[_cell.x + 1][_cell.y]);
if (_cell.y > 0 && (labyrinth[_cell.x][_cell.y - 1].Visited == false))
nextStep.push_back(labyrinth[_cell.x][_cell.y - 1]);
if (_cell.y < height - 1 && (labyrinth[_cell.x][_cell.y + 1].Visited == false))
nextStep.push_back(labyrinth[_cell.x][_cell.y + 1]);
if (!nextStep.empty())
{
//выбираем сторону из возможных вариантов
Cell next = nextStep[rand() % nextStep.size()];
//Открываем сторону, в которую пошли на ячейках
if (next.x != _cell.x)
{
if (_cell.x - next.x > 0)
{
labyrinth[_cell.x][_cell.y].Left = Open;
labyrinth[next.x][next.y].Right = Open;
}
else
{
labyrinth[_cell.x][_cell.y].Right = Open;
labyrinth[next.x][next.y].Left = Open;
}
}
if (next.y != _cell.y)
{
if (_cell.y - next.y > 0)
{
labyrinth[_cell.x][_cell.y].Top = Open;
labyrinth[next.x][next.y].Bottom = Open;
}
else
{
labyrinth[_cell.x][_cell.y].Bottom = Open;
labyrinth[next.x][next.y].Top = Open;
}
}
labyrinth[next.x][next.y].Visited = true;
path.push(next);
}
else
{
//если пойти никуда нельзя, возвращаемся к предыдущему узлу
path.pop();
}
}
//... где-то тут визуализируем labyrinth...
return 0;
}
[C# WPF] public partial class MainWindow : Window
{
enum CellState { Close, Open };
class Cell
{
public Cell(Point currentPosition)
{
Visited = false;
Position = currentPosition;
}
public CellState Left { get; set; }
public CellState Right { get; set; }
public CellState Bottom { get; set; }
public CellState Top { get; set; }
public Boolean Visited { get; set; }
public Point Position { get; set; }
}
private Int32 _Width, _Height;
private Cell[,] Cells;
public MainWindow()
{
InitializeComponent();
}
protected override void OnInitialized(EventArgs e)
{
base.OnInitialized(e);
_Width = 10;
_Height = 10;
Cells = new Cell[_Width, _Height];
for (int y = 0; y < _Height; y++)
for (int x = 0; x < _Width; x++)
Cells[x, y] = new Cell(new Point(x, y));
Random rand = new Random();
Int32 startX = rand.Next(_Width);
Int32 startY = rand.Next(_Height);
Stack<Cell> path = new Stack<Cell>();
Cells[startX, startY].Visited = true;
path.Push(Cells[startX, startY]);
while (path.Count > 0)
{
Cell _cell = path.Peek();
List<Cell> nextStep = new List<Cell>();
if (_cell.Position.X > 0 && !Cells[Convert.ToInt32(_cell.Position.X - 1), Convert.ToInt32(_cell.Position.Y)].Visited)
nextStep.Add(Cells[Convert.ToInt32(_cell.Position.X) - 1, Convert.ToInt32(_cell.Position.Y)]);
if (_cell.Position.X < _Width - 1 && !Cells[Convert.ToInt32(_cell.Position.X) + 1, Convert.ToInt32(_cell.Position.Y)].Visited)
nextStep.Add(Cells[Convert.ToInt32(_cell.Position.X) + 1, Convert.ToInt32(_cell.Position.Y)]);
if (_cell.Position.Y > 0 && !Cells[Convert.ToInt32(_cell.Position.X), Convert.ToInt32(_cell.Position.Y) - 1].Visited)
nextStep.Add(Cells[Convert.ToInt32(_cell.Position.X), Convert.ToInt32(_cell.Position.Y) - 1]);
if (_cell.Position.Y < _Height - 1 && !Cells[Convert.ToInt32(_cell.Position.X), Convert.ToInt32(_cell.Position.Y) + 1].Visited)
nextStep.Add(Cells[Convert.ToInt32(_cell.Position.X), Convert.ToInt32(_cell.Position.Y) + 1]);
if (nextStep.Count() > 0)
{
Cell next = nextStep[rand.Next(nextStep.Count())];
if (next.Position.X != _cell.Position.X)
{
if (_cell.Position.X - next.Position.X > 0)
{
_cell.Left = CellState.Open;
next.Right = CellState.Open;
}
else
{
_cell.Right = CellState.Open;
next.Left = CellState.Open;
}
}
if (next.Position.Y != _cell.Position.Y)
{
if (_cell.Position.Y - next.Position.Y > 0)
{
_cell.Top = CellState.Open;
next.Bottom = CellState.Open;
}
else
{
_cell.Bottom = CellState.Open;
next.Top = CellState.Open;
}
}
next.Visited = true;
path.Push(next);
}
else
{
path.Pop();
}
}
renderCells();
}
private void renderCells()
{
for (int y = 0; y < _Height; y++)
for (int x = 0; x < _Width; x++)
{
if (Cells[x, y].Top == CellState.Close)
mCanvas.Children.Add(new Line()
{
Stroke = Brushes.Black,
StrokeThickness = 1,
X1 = 20 * x,
Y1 = 20 * y,
X2 = 20 * x + 20,
Y2 = 20 * y
});
if (Cells[x, y].Left == CellState.Close)
mCanvas.Children.Add(new Line()
{
Stroke = Brushes.Black,
StrokeThickness = 1,
X1 = 20 * x,
Y1 = 20 * y,
X2 = 20 * x,
Y2 = 20 * y + 20
});
if (Cells[x, y].Right == CellState.Close)
mCanvas.Children.Add(new Line()
{
Stroke = Brushes.Black,
StrokeThickness = 1,
X1 = 20 * x + 20,
Y1 = 20 * y,
X2 = 20 * x + 20,
Y2 = 20 * y + 20
});
if (Cells[x, y].Bottom == CellState.Close)
mCanvas.Children.Add(new Line()
{
Stroke = Brushes.Black,
StrokeThickness = 1,
X1 = 20 * x,
Y1 = 20 * y + 20,
X2 = 20 * x + 20,
Y2 = 20 * y + 20
});
}
}
}
Examples of rendering:
