The internal layouts of buildings in video games are usually designed by hand, but the increasingly expansive and realistic nature of virtual worlds introduces scalability issues which make manual design methods impractical. We present a new methodology that uses a multi- objective evolutionary algorithm to automatically generate building lay- outs. The method accepts highly versatile input constraints, encoding layouts using a flexible binary tree representation and evaluating them on a range of criteria to ensure authentic results. Tests demonstrate that the method works well for a variety of problem instances representing an apartment, a family house, and an office floor; the ability to generate so- lutions for different types of buildings and to incorporate non-rectangular spaces shows greater versatility than many previous methods.