I was imagining a few limitations to help with consistency: all scenes have the same number of edges (say, 10) ensuring there's a limited set of scenes you can navigate to from the current one and previously generated scenes can get reused, and no flying, that way we can only worry about generating prism-shaped rooms with a single ceiling and floor edge.

I suppose this is the easy part, actually; for me the real trouble might be collision based on the non-deterministic thing that was generated, i.e. how to decide which scene edges the player should be able to travel through, interact with, be stopped by, burned by, etc.