Is there an algorithm to dynamical generate a maze, ensuring that there is always more places to go?

Question

Let's suppose we have a maze. You start somewhere in it:

* - * - * 
    |   |
    *-here

Only a small part of the maze is generated (for example, a 10 by 10 square around you). As you move around, more of the maze is generated. Is there an algorithm that ensures that there is always a place for you to go?

For example:

 *-here  * - *
             |
             *

would not work because you have no paths.

I have a 'solution' for it, and that is to generate a finite maze, then force it to be connected to another finite maze, forming a mesh (ensuring that finite mazes are doable is easy).

Edit 1: The maze can't have a deterministic size; Parts of the map will be generated dynamically.

Edit 2: It has to generate the same maze no matter the order which you load it in (Moving up then left should generate the same maze as moving left then up)

My maze does not need to include all places

example image:

Answer 1

I like to generate mazes with variants of Kruskal's algorihtm:

http://weblog.jamisbuck.org/2011/1/3/maze-generation-kruskal-s-algorithm

https://mtimmerm.github.io/webStuff/maze.html

One way to think of using Kruskal's algorithm to generate mazes is:

1. Assign a random weight to every possible wall
2. Remove every wall if the cells on ether side of it are not connected by removing all walls of lesser weight.

If you divide the world into tiles, then you can turn this into an algorithm that you can evaluate locally as follows:

1. Assign a random weight to every possible wall. Use a different random number generator for the walls in each tile, and seed it with the tile's coordinates.
2. Remove every wall if the cells on either side of it are not connected by removing all walls of lesser weight in its tile and adjacent tiles.

This way, to generate any tile of the maze, you only need to consider the weights that would be assigned to walls in the 8 adjacent tiles. The procedure is just like doing the normal Kruskal's to make a 3 tile X 3 tile maze, and then cutting out the middle tile.

When you generate mazes this way, it's guaranteed that there will be a path from every place in the maze to every other place. Unlike "perfect" mazes, however, there may be more than one path between two places that are more than a tile apart. As long as your tiles are sufficiently large, though, there won't be any visible artifacts of the tiling, and it will still be difficult to find your way from one place to another.

Answer 2

There are many, of varying complexities. A good place to start is the Wikipedia page: https://en.wikipedia.org/wiki/Maze_generation_algorithm.

Often, it'll be easier to generate the whole maze in advance and reveal it bit by bit as it is explored than to incrementally generate the maze during exploration, but take a look at the link and decide what you think.

Also, if the maze doesn't completely fill space, you might look at the way old games like hack, nethack, or rogue generate room layouts on levels. I'm sorry I don't have a reference for how that was done.