Algorithm to generate a segment maze

Question

I want to generate a maze that looks like this:

That is, it consists of paths in one direction that are then connected. I have looked for an algorithm to generate mazes like this without success.

Specifically, I don't want a maze like this:

because it doesn't "run" in only one direction.

Also, it would be nice if the solution of this maze required the player to "backtrack" -- i.e. not just move upwards all the time.

Latticed

Can you clarify the distinction between the maze you want and the maze you don't want? Other than density, and the fact that the first maze has multiple solutions, it's not clear. What do you mean by "paths in one direction that are then connected"? – Satin

do you mean something like this? (compiled(.net) that I created), pages.videotron.com/spirch/FredGames/Fred-Games.zip by default the maze is scrambled, look at the menu to change the behavior – Addend

@Adrian: The maze on top has long horizontal lines and short vertical lines. The maze on the bottom has no directional bias. – Latticed

Then can you use a traditional maze algorithm with a bias to prefer horizontal moves when choose random directions? – Satin

the first maze appears to be missing? – Perbunan

Answer 1

1. create a random path between point A and B
2. randomly add walls as long as it doesn't lie on the path until you're satisfied

Fetter

I think that you would want to check each wall before you add it to make sure that it doesn't seal off areas of the maze. – Odor

while (!user.IsSatisfied) { add random wall; } ? – Ese

Answer 2

Well that was fun! Complete with ASCII art output I present ...

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



    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();
            }
        }

Ese

Answer 3

Just use A* Search to make sure that you can always find a path to the end and then for every row add twenty randomly placed walls. If the A* cannot reach the end after you have placed a new row down then use backtracking to regenerate a new set of walls until it works. Maybe not the most efficient method but I think it will work reasonably well most of the time.

Heirship

There are much, much better maze-generating algorithms out there. – Dimphia

Answer 4

Here's another one:

1. Add walls to the borders of the room.
2. Pick several random spots at the borders and in the middle of the room. For each spot:
3. If from that spot there are directions to where there is no wall yet, pick a random free direction and "grow" a wall to there. Otherwise remove this spot from the list.
4. Give it a 20% chance to sprout a bud, and if it's a yes, then add that spot to the list.
5. If there's more spots in the list, pick the next one and goto #2. Otherwise got #5.
6. If there are left over free spots, put all of them into the list. For each free spot:
7. "Build" a wall towards the nearest wall so that they meet.

Tauro

Answer 5

If I understand you correctly, you want to have your solution to never have to go down (when the entrance is on the bottom and exit is on the top).

I think a simple way is to generate a simple horizontal map first, picking one random hole in each layer, like this:

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

You've now defined where the solution path goes. Now just do some jumbling: remove a random horizontal edge somewhere, then add a vertical edge that prevents its use, on either the row above or below the new hole, randomly selected between the hole and where the real solution goes. (You would need to make sure you don't remove a horizontal edge between two sections of the solution path.)

I think this would work pretty well. It might not generate large (multi-row) false paths too easily, though.

Champagne

Answer 6

Use Eller's algorithm and introduce a bias in the horizontal-direction.

Tegantegmen