Using QuadTree for Procedural Generation

Question

so I've been trying to start a new project that focuses on procedural room generation similar to what is seen in Binding of Isaac.

I plan to have the code use a QuadTree to help determine where rooms should be placed. Each node in the quad tree represents any of the possible 4 directions the next room can be placed.

The problem is this. I'm not sure where to start when trying to implement the QTree and haven't found good resources on the topic. Most implementations of QuadTrees in a procedural generation context use them for partitioning spaces and placing rooms within the partitioned spaces. Not sure if that's what I want to achieve. I'm also unsure of weather I should be going in this direction or if there's a more optimal solution?

Answer 1

As already stated in others comments I think you might be using the quadtree concept to solve the wrong problem.

I spend most of my time managing massive amounts of data working with voxels and even I don't touch quad trees for anything related to generating my world data.

The purpose of the quad tree is to help manage and work with your rendered world so it really has no place when thinking about generating your world.

The concept of building dungeons in the way you mention though is well known ...

http://www.roguebasin.com/index.php?title=Dungeon-Building_Algorithm

http://journal.stuffwithstuff.com/2014/12/21/rooms-and-mazes/

...

Once you have your algorithm implemented for generating the raw data that represents your maze you can start to think about rendering it, for that you may or may not need to a quad tree.

If it's a typical rogue like you could get away with not using one at all and avoid the complication of it altogether, most I've seen building these sorts of games simply uses an array of cells that they move around in a grid loading and unloading the edges as needed.

My advice: Go back to basics and only use a qudtree if you absolutely need it.

Answer 2

It seams like the world is not big. The benefits of qadtrees is not really what you need if it's not a big world and you want to do fast search. I would recommend using a 2D array instead. If you want it to be dynamic use a dictionary of dictionaries of rooms using x and y indexes as keys.