Background Information: I'm building a 2D maze generator. I have tried Prim's algorithm, Wilson's algorithm, and a recursive backtracker algorithm for generating my maze, however was not satisfied with the difficulty of any. I have decided to create my own. I decided that two things make a maze hard. First, mazes can have lots of intersections and choices to make. Second, they can be disorienting and cause you to lose your way. I decided to create a tree to represent the intersections and dead ends in a maze and connect each node in the tree with a randomly generated path to disorient users.
The problem: If I begin to generate the cells in the maze for the tree, I may find that a node doesn't have the room it needs to connect to or create its children. How do I fix or avoid this problem?
My Thoughts: There seems like there might be a way to do this by dividing the maze into sections and subdividing them, but that still doesn't guarantee enough room at the end of the division. I could also try to start small and work my way up, sectioning off smaller areas and then creating connections between them, but that could still run into pathing issues with not having enough room to connect the sections together or even creating really long paths between sections.
I am using a hexagonal grid, but any solution you guys come up for rectangular grids should be easy to transfer to a hexagonal one.
I wasn't sure if this should be posted in the theoretical computer science section or here, and opted for the more general one.