Looking for advice on procedural mapping an infinite dungeon.

[LostTemplar]

The trick is connecting rooms to already explored areas.

This is exactly what is solved by using features not limited to be inside some kind of chunks. E.g. you want 100x100 area somewhere, so you generate (100+n)x(100+n) array of features (n will be double maximum size of a feature, quite large for e.g. greater vault), and then place them using any deterministic algorythm, so, e.g. large and important features like greater vaults allways trample over small features if they are nearby, when connect rooms, etc. Well you can of course again introduce chunks and write a function, that generates 3x3 or 5x5 chunk array.