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.

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

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