Dynamic Map Generation in Ganked

I have been working on the dynamic map generation for Ganked. I have been prototyping it in python; though, the final implementation will likely live in C++. I currently have 4 phases of map generation:

Phase 1: Using a room placement strategy ( 2 strategies exist at the moment), place the rooms



Phase 2 : I create a navigation map with lines extending from the center of rooms, but terminating just before any other room it may run into. This will form the paths that hallway generation will use to create hallways in later steps.




Phase 3: Using a clustering algorithm based on distance between centers, I cluster the rooms to determine what will be connected to what. Rooms are initially turned into a cluster node and then cluster nodes are clustered into composite nodes based on distances between centers. This continues until there is only one node left in the list. In the graphic above, each clustering is outlined in its own color.



Phase 4: Using a depth first approach to the clustered nodes, begin connecting nodes to each other with a simple A* pathfinding hallway generator with all spaces blocked except those identified in phase 2 (the lines). Now we have hallways connecting all of our rooms!



In future iterations I hope to have hallway "diggers" widen out the hallways based on relationships to room sizes they connect to and potential space they have to dig in.