This study introduces a new representation landscape automata for encoding heightmaps that may be used for terrain generation or other procedural content generation. Landscape automata are evolvable state-conditioned quadtrees with embedded decay parameters. Landscape automata are used to both match idealized landforms and to generate a heightmap with controllable connectivity for agents using the height map as terrain. Parameter studies on both mutation rate and number of states in the automata are performed. Mutation rate is found to have a modest impact on performance while the number of states used both has a large impact on fitness and a different type of impact for each of two types of fitness functions. Landscape automata are demonstrated to be well able to match idealized landforms, providing a palette of varied approximations with a variety of secondary features. They are also able to generate heightmaps that, viewed as terrain, form challenging mazes.