Алгоритм для генерации лабиринта сегмента

Просто используйте A* Search, чтобы убедиться, что вы всегда сможете найти путь к концу, а затем для каждого ряда добавьте двадцать случайно расположенных стен. Если A* не может достичь конца после того, как вы поместили новый ряд вниз, используйте обратный путь, чтобы сгенерировать новый набор стен, пока он не сработает. Возможно, это не самый эффективный метод, но я думаю, что он будет работать достаточно хорошо большую часть времени.

1. создать случайный путь между точками A и B
2. случайным образом добавить стены, если они не лежат на пути, пока вы не будете удовлетворены

Ну, это было весело! В комплекте с выводами ASCII art, которые я представляю ...

█    ██████    █████████████████████    █
█    █                             █    █
█    █                             █    █
█    █    ██████████████████████████    █
█                                       █
█                                       █
██████    ██████    ███████████    ██████
█    █    █              █         █    █
█    █    █              █         █    █
███████████████████████████████    ██████
█                                       █
█                                       █
██████    █████████████████████    ██████
█                             █         █
█                             █         █
██████    ███████████    ███████████    █
█              █                   █    █
█              █                   █    █
█████████████████████    ██████    ██████
█         █              █              █
█         █              █              █
███████████████████████████████    ██████
█                                       █
█                                       █



    private struct Cell
    {
        public bool visited;
        public bool right;
        public bool top;
    }

    static void Main(string[] args)
    {
        Random Rand = new Random();

        int size = 8;

        var maze = new Cell[size,size];

        for (int x = 0; x < size; x++)
            for (int y = 0; y < size; y++)
            {
                maze[x, y] = new Cell() { right = true, top = true, visited = false };
            }

        int count = size * size;

        int positionX = Rand.Next(size);

        // mark space below (outside matrix)

        for (int y = 0; y < size; y++)
        {
            maze[positionX, y].top = false; maze[positionX, y].visited = true;
            count--;

            // move left or right n spaces
            int n = Rand.Next(size);                    // random left or right by an amount n
            int direction = (Rand.Next(2) == 0) ? 1 : -1; 
            while (positionX + direction > 0 && positionX + direction < size -1 && n-- > 0)
            {
                // moving sideways
                if (direction == -1)
                {
                    positionX += direction;
                    maze[positionX, y].right = false;
                    maze[positionX, y].visited = true;
                    count--;
                }
                else
                {
                    maze[positionX, y].right=false;
                    positionX += direction;
                    maze[positionX, y].visited = true;
                    count--;
                }
            }
        }


        // Now pick a random place we have visited and extend into new territory
        while (count > 0)
        {
            int x = Rand.Next(size);
            int y = Rand.Next(size);
            if (!maze[x, y].visited) continue;      // not visited yet

            // We are on a visited node, where can we go from here?

            // Pick a direction to break down a wall - favor left right
            if (Rand.Next(4) > 0)
            {
                if (Rand.Next(2) == 1 && x < size-1 && !maze[x+1,y].visited )
                    { maze[x,y].right = false; maze[x+1,y].visited = true; count--;}
                else if (x > 0 && !maze[x-1,y].visited)
                    {maze[x-1,y].right = false; maze[x-1,y].visited = true; count--;}
            }
            else
            {
                if (Rand.Next(2) == 1 && y < size - 1 && !maze[x, y + 1].visited)
                    { maze[x, y].top = false; maze[x, y+1].visited = true; count--; }
                else if (y > 0 && !maze[x, y-1].visited)
                    { maze[x, y-1].top = false; maze[x,y-1].visited = true; count--; }
            }
        }

        // Dump the maze
        for (int y = 0; y < size; y++)
        {
            Console.Write("█");
            for (int x = 0; x < size; x++)
                Console.Write((maze[x, y].top) ? "█████" : "    █");
            Console.WriteLine();

            for (int repeat = 0; repeat < 2; repeat++)
            {
                Console.Write("█");
                for (int x = 0; x < size; x++)
                {
                    Console.Write(maze[x, y].right ? "    █" : "     ");
                }
                Console.WriteLine();
            }
        }

Вот еще один:

1. Добавьте стены к границам комнаты.
2. Выберите несколько случайных мест по краям и в центре комнаты. Для каждой точки:
3. Если от этой точки есть направления туда, где еще нет стены, выберите случайное свободное направление и «вырастите» стену туда. В противном случае удалите это место из списка.
4. Дайте ему 20% шанс дать росток, и если да, то добавьте это место в список.
5. Если в списке есть еще места, выберите следующее и перейдите к пункту №2. В противном случае получил # 5.
6. Если остались свободные места, занесите их все в список. За каждое свободное место:
7. «Постройте» стену к ближайшей стене так, чтобы они встретились.

Если я правильно вас понял, вы хотите, чтобы ваше решение никогда не спускалось вниз (когда вход находится внизу, а выход - наверху).

Я думаю, что простой способ - это сначала сгенерировать простую горизонтальную карту, выбрав одно случайное отверстие в каждом слое, примерно так:

+--------------- +
+                +
+--- ------------+
+                +
+-------------- -+
+                +
+-------- -------+
+                +
+ ---------------+

Теперь вы определили, где проходит путь решения. Теперь просто сделайте некоторую перестановку: удалите где-нибудь случайную горизонтальную грань, затем добавьте вертикальную грань, которая препятствует ее использованию, в ряд выше или ниже новой дыры, случайно выбранный между дырой и местом, где проходит реальное решение. (Вам нужно будет убедиться, что вы не удалите горизонтальное ребро между двумя участками пути решения)

Я думаю, это будет работать довольно хорошо. Хотя, возможно, он не сможет легко генерировать большие (многорядные) ложные пути.