You essential want a maze with no dead ends, sometimes also known as a unicursal maze or a labyrinth.
Jamis Buck describes a way to build rectangular unicursal maze as follows:
- Generate a maze first of half the desired final size.
- Remove the exit so only the entrance remains.
- Bisect each passage with a wall.
This makes dead-ends into u-turns, and will give you a unicursal labyrinth that is twice the size of the original maze. Here's an illustration of his process using a very small maze:
One drawback to this approach is that the resulting entrance & the exit are right next to each other. Here is a simple modification that will allow for an arbitrary entrance & exit:
- Pad the existing maze out with a wall thick enough to contain a tunnel.
- Pick an entrance & dig a tunnel to the nearest opening.
- Pick an exit & dig a tunnel to the remaining opening.
Here's an illustration that applies the modification to the previous example:
This isn't the only adaptation to fix the entrance & exit. Another somewhat more complex modification involves combining mulitple labyrinths. A more complex solution would be to partition & reconnect portions of the labyrinth.
Finally, note that while the illustrations I've used have varying wall thickness to illustrate the steps of the algorithm, all mazes are essentially (mathematical) graphs & you can adjust the representation (visual output) of the graph according to the needs of your game.