I made a new world not long before the "Arts and Crafts" Beta update (I'm in the beta), but it took a while till I realised that some parts were missing. In the upper world I didn't have the Moon Stone, so I could not get the Mooncaller's Staff, and in the caves the Labyrinth (and of course the Ancient Guardian) were missing. I lived more than 200 days and fully explored both maps, but didn't found these, even not using "c_gonext".
However I found a place in the ruins, which looks like the beginning of the Labyrinth (wants to be), like as if the game choose a place for it but couldn't create it at the end. I have a picture of the map of it.
World settings were: Start: Plus, Long Autumn and short winter, spring, summer, the caves are "huge", with less rain and monkeys, more treeguards, cave bananas, failed surviors and touch stones and slower disease. The world was generated a few days before the "Arts and Crafts" update.