Как понять, возможно ли пройти лабиринт / пройти лабиринт

Я сделал класс, который генерирует лабиринты, алгоритм придумал сам, есть проблемы:

  1. Понять, возможно ли пройти лабиринт
  2. Найти начало и конец лабиринта (Где его можно пройти от начальной точки до конечной)
  3. Пройти его (Я бы хотел написать это сам, но остановился, на понимании, возможно ли его вообще пройти, мне как минимум нужно указать начальную точку и конец)

Вот вид лабиринта:

введите сюда описание изображения

Код генерации:

    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
  1. Делаете Flood Fill от точки входа и смотрите, залилась ли точка выхода.

  2. Можете сделать заливку т.н. Connected Components Labeling чтобы получить все несвязанные области, далее выбираете самую большую область касающуюся краев и ставите в любых двух местах на ней "вход" и "выход".

    Пример как это может выглядеть:

    введите сюда описание изображения

  3. Пройти можно простым алгоритмом поиска пути, например, A-star.

→ Ссылка