In this paper we describe a hierarchical method for procedurally generating 2D game maps using multi-dimensional Markov chains (MdMCs). Our method takes a collection of 2D game maps, breaks them into small chunks and performs clustering to find a set of chunks that correspond to high-level structures (high-level tiles) in the training maps. This set of high-level tiles is then used to re-represent the training maps, and to fit two sets of MdMC models: a high-level model captures the distribution of high-level tiles in the map, and a set of low-level models capture the internal structure of each high-level tile. These two sets of models can then be used to hierarchically generate new maps. We test our approach using two classic games, Super Mario Bros. and Loderunner, and compare the results against other existing map generators.

Procedural content generation (PCG) has become a popular research topic in recent years, but not much work has been done in terms of generalized content generators,that is, methods that can generate content for a wide variety of games without requiring hand-tuning. Probabilistic approaches are a promising avenue for creating more general content generators, and specificially map generators. I am interested in exploring probabilistic techniques that could lead to generalized procedural level generators.

In this paper we describe a hierarchical method for procedurallygenerating maps using Markov chains. Ourmethod takes as input a collection of human-authoredtwo-dimensional maps, and splits them into high-leveltiles which capture large structures. Markov chains arethen learned from those maps to capture the structure ofboth the high-level tiles, as well as the low-level tiles.Then, the learned Markov chains are used to generatenew maps by first generating the high-level structure ofthe map using high-level tiles, and then generating thelow-level layout of the map. We validate our approachusing the game Super Mario Bros., by evaluating thequality of maps produced using different configurationsfor training and generation.

In this paper we outline a method of procedurally generating maps using Markov Chains. Our method attempts to learn what makes a "good" map from a set of given human-authored maps, and then uses those learned patterns to generate new maps. We present an empirical evaluation using the game "Super Mario Bros.," showing encouraging results.