How to generate a maze with walls so that there is always a path in this maze?

Question

Algorithms

A simple maze is generated from tiles.


The generation of the labyrinth with walls has differences. There are theoretically two solutions, but which are problematic to apply in practice.
The programming language is not important.
The decision itself is important ....... The task is to build a generated labyrinth with walls where there is always an entrance and exit ...
You have tiles vertical and perpendicular.


the problem is that you will have a dead end ....
How to avoid this and ensure the rotation of the tile?

We need a theoretical solution that is implemented in software, with a step-by-step explanation of the theory

Answer 1

There is a fairly simple and understandable algorithm:
1) We get to the starting point adjacent to the entrance.
2) We generate a random tile (r, -, +, m, ...) in such a way that it has an entrance connected and at least one exit is not blocked (by walls of the labyrinth and other tiles).
3) If there is no such exit, we generate a new tile so that there is one. If still not, then go to step 5.
4) Move to the exit of the current tile. Now the empty space is our current point.
5) We repeat until we hit a dead end, i.e. there will be no free exit from the current tile.
6) We go back to the first branch and repeat the algorithm.
7) If again there are dead ends in all branches, then we return even further back.
8) If we nevertheless returned to the entrance to the labyrinth, then we erase everything and start the algorithm over again.

Answer 2

At the time, it was pretty straight forward. On the maze, I first generated a path from point A to point B randomly and marked these cells as checkpoints. And only then around randomly generated the rest of the maze.

Answer 3

There are many such articles.

Answer 4

This is a task, not a question.