Dynamic maze mutation

I have an idea of creating yet another maze game. However, there is a key difference: maze changes on-the-fly during the game. When I think of the problem the following restrictions come into my mind:

1. there is main route in the maze which never changes
2. the main route is the only route which leads to the finish
3. maze mutation should not block paths back to the main route

It also would be nice to control (affect game difficulty):

1. how much of the maze gets changed during a single mutation
2. opt开发者_运维百科ionally disable restriction #3 (i.e. player can get blocked in the maze for a while)

EDIT: The question is: can you suggest an algorithm (or give your ideas) for described maze generation/mutation, which will not violate given restrictions?

You could:

1. Block a path at random (or using some sneaky criteria).

2. Scan the maze to see if it has been partitioned into 2 regions that are no longer connected.

3. If disconnected, you can knock down a wall at random so long as it neighbors both regions.

If your maze has only one path between any two points, step 2 will always split the maze and so #3 will always be needed.

Make a graph connecting all the cells of the maze and the walkable connections between them. To modify the maze, first pick a random wall to knock down, which generates a new edge in the graph. Then find a cycle in the graph that contains that edge, and delete a random, non-main-path edge in that cycle, which will erect an edge somewhere else.

This algorithm ensures that if all cells were reachable at the start, they will remain so. You probably want that feature so you can't ever get trapped.

This is probably quite straightforward. Generate the maze using the standard depth-first-search algorithm. Store the list of cells that form the (only) path from start to exit in a list. When you decide you want to mutate the maze, do the following:

1. Reset the entire maze to the default state (all walls in place), with the exception of any cell along the critical path, and optionally, a few cells within line-of-sight of the player's current location.
2. Re-execute the breadth-first search algorithm from the start, with one modification: when choosing which unvisited neighbour to explore, prefer edges that already have the wall removed.

The modification in the second step will ensure that the algorithm first explores the existing paths, then adds on side-passages and so forth from there. It's not even strictly necessary to preserve the critical path if you don't want to - you can regenerate the entire maze except where the user's standing, and it'll remain valid.

I think this ought to always produce a valid tree in the same way the original algorithm would, but I'm not 100% sure about the implications of preserving the cells around the user, which may not be on the critical path. I'm positive the reconfigured maze will always be solvable from where the user is standing, though.

This is a pretty neat idea, too. I love the idea of the maze rearranging itself substantially wherever the user isn't looking. If you're doing this in first-person, you could even use the camera view to change the walls behind the user when they're not looking!