A lazy, lightweight algorithm for generating very large navigable terrains
Bruce Johnson · 2011
A virtual, interactive 3-D environment is exemplified by the so-called "first person shooter" (FPS) genre found in many video games. One of the limiting factors in the creation of a 3-D interactive environment is content production. A key component of the content produced is the virtual terrain upon which the interactive participants (or avatars) navigate. Typically, terrains are constructed by overlaying a texture map (called a height map) upon a patch of polygons and have each of the height map's colors or shades get mapped to a polygon's elevation. A terrain's size is typically limited by the size of the patch of polygons the height map is placed upon. Once an avatar's position has exceeded the dimensions of the terrain, further movement might not be allowed within the terrain. It is therefore beneficial to have available a very large terrain. A lazy, lightweight algorithm is presented. It is based upon using a just-in-time method of updating a set of available height maps for the automatic production of very large 3-D terrains. This just-in-time update algorithm requires only 0.47 second of landscape-generation and landscape-update time and provides a smooth 44 frames-per-second display using modern hardware. These performance numbers ensure that the user is kept unaware of the update procedure and is thus provided with a seamless depiction of a very large terrain. Furthermore, the algorithm presented only requires a small amount of on-device memory and thus can make it useful for small Internet-connected computing devices.