This paper presents a search-based method for generating maps for the popular real-time strategy (RTS) game StarCraft. We devise a representation of StarCraft maps suitable for evolutionary search, along with a set of fitness functions based on predicted entertainment value of those maps, as derived from theories of player experience. A multiobjective evolutionary algorithm is then used to evolve complete Star- Craft maps based on the representation and selected fitness functions. The output of this algorithm is a Pareto front approximation visualizing the tradeoff between the several fitness functions used, and where each point on the front represents a viable map. We argue that this method is useful for both automatic and machine-assisted map generation, and in particular that the Pareto fronts are excellent design support tools for human map designers.