CODEWITHSUNDEEP
c#unity-game-enginerecursionmaze
ryanhagz
ryanhagz

Reputation: 193

How to make a "Maze" with multiple paths and no dead ends?

How would I go about programming a Braid maze in C# (Unity in particular) with multiple solutions?

A Braid maze from what I understand in my brief research is a type of recursive maze which allows loops, meaning no dead ends.

The closest answer I've found is in this thread dealing with how to create more than one successful path, but I can't figure out to combine the two as the examples used in the thread are for "Perfect" mazes.

By these steps you can get multiple successful paths from start to finish:

  1. Subdivide the maze into three sets: Start (intially holding just the start cell), goal (initially holding just the goal cell), and undiscovered (all the rest).
  2. Randomly remove walls between cells in the start or the goal set and cells in the undiscovered set, and move the newly discovered cell to the respective set.
  3. Repeat until each cell is either in the start or the goal set.
  4. Remove as many walls between the two regions as you want paths from the start to the goal.

I need is a step 5. that goes back and deletes all dead ends to turn it into a braid maze and I would be set! (Assuming that the maze size is n * n).

Upvotes: 0

Views: 2002

Answers (1)

jon_simon
jon_simon

Reputation: 380

How about the simplest approach: keep track of dead-ends as the maze is being constructed, and then after the maze is completed, for each dead-end remove one of its three walls so that it connects to some other part of the maze. It's possible that there may be some configuration of dead-ends for which this isn't possible to do without breaking the maze in some way, but I haven't been able to come up with such an example.

Upvotes: 1

Related Questions