Graph-based Terrain Generation

Abstract

This thesis introduces a technique for procedurally generating terrains for strategy video games. In our approach, we use graphs to represent regions and corridors in the terrain. We implemented a tool that a game designer can use to define a terrain graph with geometric properties that the maps should have, such as the connectivity structure and physical dimensions of the regions and corridors. Our terrain generator uses a graph layout algorithm to find a terrain graph layout that meets the specifications, and generates a heightmap based on that layout. We tested the effectiveness of our method with various test cases in different experiments, and found that the generated terrains match the designer's intent quite well.