In game-based learning and in teaching using virtual worlds, designers creating the products and teachers providing them to students are both faced with a dualism between instruction and construction. Open-ended virtual worlds may provide authentic settings and inspire experimentation; on the other hand a lack of guidance may result in learners losing direction. The chapter conducts a narrative review of concepts across disciplines that describe the dilemma and imply certain instructional design strategies. Many authors advocate constructivist learning, but with instructional elements added. The authors collect their recommendations and apply and refine them in their own ideas: adaptivity inspired by Cognitive Apprenticeship, guidance on the basis of Cognitive Task Analysis, and immersive, interactive quest journals. Study setups and first results from ongoing projects illustrate the theoretical considerations.