views:

1019

answers:

5

I want to generate a maze that looks like this: alt text

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:

alt text

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.

+4  A: 
  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
Kornel Kisielewicz
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.
Justin Peel
while (!user.IsSatisfied) { add random wall; } ?
Hightechrider
A: 

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.

Robert Massaioli
There are much, much better maze-generating algorithms out there.
LarsH
A: 

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.
sbi
A: 

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.

Keith Randall
+3  A: 

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