Как понять, возможно ли пройти лабиринт / пройти лабиринт
Я сделал класс, который генерирует лабиринты, алгоритм придумал сам, есть проблемы:
- Понять, возможно ли пройти лабиринт
- Найти начало и конец лабиринта (Где его можно пройти от начальной точки до конечной)
- Пройти его (Я бы хотел написать это сам, но остановился, на понимании, возможно ли его вообще пройти, мне как минимум нужно указать начальную точку и конец)
Вот вид лабиринта:
Код генерации:
public class Info
{
public Info(string name, Size size, int strange)
{
Name = name;
Size = size;
Strange = strange;
}
public Info(Size size, int strange) : this( "TEST-" + (DateTime.Now.Ticks % 99), size, strange) { }
public string Name { get; set; }
public Size Size { get; set; }
public int Strange { get; set; }
}
public abstract class BaseMaze
{
protected BaseMaze(Info info)
{
this.info = info;
}
public Random Random = new Random();
protected Info info;
public Info Info { get => info; set => info = value; }
public bool[,] Maze { get; set; }
public List<Point> Complited { get; set; }
public List<Point> ComplitedESP { get; set; }
public abstract void Gen();
public abstract void Complite();
public void Render(Panel panel)
{
panel.SuspendLayout();
Graphics g = panel.CreateGraphics();
g.Clear(Color.FromArgb(49, 49, 49));
Size ps = new Size(panel.Width / info.Size.Width, panel.Height / info.Size.Height);
for (int x = 0; x < info.Size.Width; x += 1)
{
for (int y = 0; y < info.Size.Height; y += 1)
{
bool block = Maze[x, y];
g.FillRectangle(new SolidBrush(block ? Color.Black : Color.White), new Rectangle(x * ps.Width, y * ps.Height, ps.Width, ps.Height));
}
}
panel.ResumeLayout();
}
public List<Point> GetNear(Point coord) => new (int, int)[8] { ( 1, 0 ), ( 0, 1 ), ( -1, 0), ( 0, -1), ( 1, 1), (1, -1), (-1, 1), (-1, -1) }.Select(z => (coord.X + z.Item1, coord.Y + z.Item2)).Where(z => z.Item1 > 0 && z.Item1 < info.Size.Width && z.Item2 > 0 && z.Item2 < info.Size.Height).Where(z => Maze[z.Item1, z.Item2]).Select(z => new Point(z.Item1, z.Item2)).ToList();
public int GetNearCount(Point coord) => GetNear(coord).Count;
}
public class RoundMaze : BaseMaze
{
public bool unique;
public RoundMaze() : base(new Info("Round", new Size(32, 32), 2)) { }
public override void Gen()
{
Maze = new bool[Info.Size.Width, Info.Size.Height];
List<Point> blocks = new List<Point>();
for (int w = 0; w < Info.Size.Width; w += 1)
{
for (int h = 0; h < Info.Size.Height; h += 1)
{
Point coord = GetBlock();
int count = GetNearCount(new Point(coord.X, coord.Y));
if(count <= info.Strange)
{
Maze[coord.X, coord.Y] = true;
}
}
}
Point GetBlock()
{
while (true)
{
Point coord = new Point(Random.Next(0, Info.Size.Width), Random.Next(0, Info.Size.Height));
if (unique)
{
if (!blocks.Contains(new Point(coord.X, coord.Y)))
{
blocks.Add(new Point(coord.X, coord.Y));
return new Point(coord.X, coord.Y);
}
}
else
return new Point(coord.X, coord.Y);
}
}
}
public override void Complite()
{
}
}
Ответы (1 шт):
Автор решения: Kromster
→ Ссылка
Делаете Flood Fill от точки входа и смотрите, залилась ли точка выхода.
Можете сделать заливку т.н. Connected Components Labeling чтобы получить все несвязанные области, далее выбираете самую большую область касающуюся краев и ставите в любых двух местах на ней "вход" и "выход".
Пример как это может выглядеть:
Пройти можно простым алгоритмом поиска пути, например, A-star.

