Visually Improved Erosion Algorithm for the Procedural Generation of Tile-Based Terrain Fong Yuan Lim Yu Wei Tan and Anand Bhojan

2025-05-06 0 0 2.99MB 12 页 10玖币

侵权投诉

Visually Improved Erosion Algorithm for the Procedural Generation of

Tile-Based Terrain

Fong Yuan Lim, Yu Wei Tan and Anand Bhojan a

Department of Computer Science, National University of Singapore, Singapore

e0169576@u.nus.edu, yuwei@u.nus.edu), banand@comp.nus.edu.sg

Keywords: pcg, procedural, terrain, generation, modelling, games, virtual world, erosion, natural

Abstract: Procedural terrain generation is the process of generating a digital representation of terrain using a computer

program or procedure, with little to no human guidance. This paper proposes a procedural terrain genera-

tion algorithm based on a graph representation of ﬂuvial erosion that offers several novel improvements over

existing algorithms. Namely, the use of a height constraint map with two types of locally deﬁned constraint

strengths; the ability to specify a realistic erosion strength via level of rainfall; and the ability to carve real-

istic gorges. These novelties allow it to generate more varied and realistic terrain by integrating additional

parameters and simulation processes, while being faster and offering more ﬂexibility and ease of use to terrain

designers due to the nature and intuitiveness of these new parameters and processes. This paper additionally

reviews some common metrics used to evaluate terrain generators, and suggests a completely new one that

contributes to a more holistic evaluation.

1 INTRODUCTION

Terrain graphics are integral to many applications in

the real world, primarily in the entertainment indus-

try such as games and movies, but also holding value

in various other industries such as education, train-

ing and engineering. Capturing and rendering real ter-

rain has several drawbacks, such as requiring a large

amount of storage space, losing detail at high zoom

levels, and covering a ﬁnite area.

Procedural terrain generation (PTG) is the gener-

ation of terrain by an automated process with limited

to no human input, which overcomes the limitations

of using only hard terrain data. Due to its automated

nature, it is a scalable method for generating large

amounts of content with minimal costs in time and

human labour. There are professional PTG tools such

as Terragen,World Creator and E-on Vue in the in-

dustry today, and many successful movies and games

have utilized PTG in their production as well, such

as Pirates of the Caribbean: Dead Man’s Chest,The

Golden Compass,Far Cry 5, and Minecraft.

Despite the beneﬁts of PTG, there remain limita-

tions and room for further improvement in various as-

pects, such as efﬁciency, variety and realism. This

paper proposes an erosion-based PTG algorithm that

ahttps://orcid.org/0000-0001-8105-1739

offers improvements in several visual and technical

aspects over current solutions. A teaser output of the

algorithm is shown in Figure 1. The contributions of

this work are as follows:

1. A new way to specify terrain constraints in terms

of a constraint map with local value and gradient

constraint strengths empowers the terrain designer

with greater ﬂexibility, accuracy and intuition in

controlling the output, along with making the sim-

ulation converge faster.

2. The additional moisture parameter is a powerful

dictator of how much erosion should occur at a

particular region of terrain, and thus provides a

high degree of controllability to the terrain de-

signer over the distribution of ﬂat vs mountainous

areas, as well as greater variety and realism.

3. The algorithm’s ability to generate convincing

gorges improves the realism of the output terrain.

4. Proposal of a set of metrics, including an original

metric, to evaluate terrain generators with. Mod-

ern terrain generators and the new proposed gen-

erator are compared using these metrics.

The rest of this paper is structured as follows: Sec-

tion 2 brieﬂy discusses related work. Section 3 ex-

plains the proposed algorithm. Section 4 analyzes the

algorithm and compares it to existing solutions. Sec-

arXiv:2210.14496v1 [cs.GR] 26 Oct 2022

Figure 1: Sample output of the algorithm, rendered in Terragen 4.

tion 5 concludes this paper and highlights some po-

tential areas for future research.

2 RELATED WORK

In this section, we discuss the current PCG algo-

rithms in four categories, Stochastic Algorithms, Ero-

sion Simulation Algorithms, Graph-based Algorithms

and Machine Learning.

2.1 Stochastic Algorithms

The most common method to automatically gener-

ate terrain by far has been with fractal noise. This

method originated in (Perlin, 1985), and is explained

in (Shaker et al., 2016) chapters 4.2-3, as well as var-

ious online tutorials.

This approach has been further improved in (Per-

lin, 2002). An alternative noise generation algorithm

called simplex noise that improved upon the short-

comings of Perlin noise was also presented in (Perlin,

2001).

The diamond-square algorithm (Miller, 1986) is

an alternative approach to this method that produces a

similar result, albeit with more axis-aligned artifacts.

(Belhadj, 2007) constrains the diamond square al-

gorithm to be of a certain height at user-speciﬁed

points, thus demonstrating that the method is control-

lable. This method was successfully used to increase

the resolution of satellite DEMs.

(Bangay, 2017) attempts to avoid some common

pitfalls of other methods, such as visible seams and

repetitive elements, by working with gradient maps

instead of height-maps. A variant of Wang tiling is

used to generate the gradient maps, and the height-

map is reconstructed from there by solving a re-

lated Poisson equation. The designer has the free-

dom to specify what the Wang tiles are, which cre-

ates overlap with an example-based methodology, but

the algorithm otherwise pieces the Wang tiles together

stochastically with no designer input. The resulting

terrain has a messy, crumpled appearance, which is

somewhat unrealistic especially at lower elevations.

(Gasch et al., 2020) presents a noise-based method

that allows procedural terrains creation with elevation

constraints.

2.2 Erosion Simulation Algorithms

The effects of rivers and erosion have been recog-

nized as the most important contributing factor to the

shape of terrain as early as (Kelley et al., 1988) and

(Musgrave et al., 1989) respectively. Erosion simu-

lation algorithms excel at producing realistic terrain,

particularly the generation of creases on hillsides that

strongly imply water erosion. However, their main

drawback is a slow generation speed.

(Benes and Forsbach, 2002) elaborates on hy-

draulic erosion and its basis in the real world. (Beneˇ

et al., 2006) and (Beneˇ

s, 2006) base hydraulic erosion

on the Navier-Stokes equations that describe viscous

ﬂuid dynamics in real world physics. (Neidhold et al.,

2005) augments the standard algorithm with interac-

tive terrain manipulation tools such as painting water

or water sources directly onto the terrain as the simu-

lation is running.

(Musgrave et al., 1989) is an early paper that sim-

ulates both thermal weathering and hydraulic erosion.

For hydraulic erosion, the terrain height as well as

amount of water and sediment are tracked for each

pixel. As water ﬂows out of a pixel into neighbouring

pixels, a proportionate amount of sediment is trans-

ported as well. The ground is eroded or sediment is

deposited depending on the sediment carrying capac-

ity of the water. A ﬁxed amount of water is added

to every pixel at regular intervals to simulate rain.

(ˇ

St’ava et al., 2008) adopts the same approach for hy-

draulic erosion, and adds that water penetrates into

the ground and turns it into slushy regolith, which is

simulated as a slow-moving liquid.

(Hud´

ak and ˇ

Durikoviˇ

c, 2011) is able to simu-

late landslides by tracking the wetness of the soil.

However, the soil is represented as discrete particles,

which is unrealistic for large-scale terrain and compu-

tationally expensive as it involves particle collisions.

More recent papers focus on the efﬁciency of such

algorithms. (Anh et al., 2007) and (Mei et al., 2007)

propose to run the simulation on the GPU. (Vanek

et al., 2011) proposes to speed up hydraulic erosion

simulation by using a quadtree representation for the

terrain.

The standard way to simulate water, as used in

the majority of the papers cited above, is to track the

amount of water held by each tile, then distributing

that water to its neighbouring tiles. This mechanism

restricts water to ﬂow at a maximum of one tile per

simulation tick, which is highly unfeasible for simu-

lation at geological time and space scales.

2.3 Graph-based Algorithms

Graph-based algorithms attempt to draw a graph - typ-

ically a river network - onto a terrain, then use this

graph to ﬁll in the terrain height. This may be done

in either a stochastic or a simulation fashion. Graph-

based algorithms tend to be more structured and re-

alistic than the standard stochastic methods due to

their attention to the dendritic nature of real terrain

features, and they are generally faster than the stan-

dard simulation methods due to their efﬁcient way of

deﬁning rivers and water ﬂow.

(Kelley et al., 1988) deﬁnes an initial main river,

then generates a complete river network by recur-

sively generating branches along the river, calculates

the height at varying points on the river based on how

much erosive power that part of the river has, and ﬁ-

nally constructs the rest of the terrain from using the

heights of the points on the river. (G´

enevaux et al.,

2013) adopts the same general approach, with more

developed geological theories. (Zhang et al., 2016)

also uses the same general approach, but they gener-

ate the terrain between rivers using the midpoint dis-

placement algorithm, and their usage of an L-system

to generate the river network results in distinct regions

of terrain with regular hills.

(Gaillard et al., 2019) generates a random den-

dritic fractal shape that can be explicitly used as

mountain ridges. The height of the terrain at any point

is proportionate to its distance from the closest branch

of the fractal. The fractal can be controlled to take on

a particular shape.

(Cordonnier et al., 2016) implements erosion sim-

ulation on a graph-based terrain. The underlying phi-

losophy of the algorithm is that terrain is shaped by

two processes: tectonic uplift and river erosion. Up-

lift raises the terrain, while erosion lowers the terrain.

The simulation runs until the terrain reaches a stable

state where the uplift balances out the erosion at every

pixel.

Every pixel of the height-map is given a point with

a random position within it. Each point is also asso-

ciated a ﬁxed drainage area - representing the area of

locality from which it collects water, and thus how

much water has to be drained from it. Finally, each

pixel also keeps track of an uplift value - how much

the terrain (rock) at that point is raised every tick.

Within a simulation tick, uplift is applied every

pixel, then erosion. For the erosion step, every pixel

ﬁrst identiﬁes its neighbour with the lowest height.

This represents the neighbour that all its collected wa-

ter is going to ﬂow to. If all its neighbours are higher

than it, it aborts the erosion step. Once every pixel

determines its lowest neighbour, the total drainage A

of each pixel is calculated. The total drainage is the

total sum of the current pixel’s drainage area and the

drainage areas of everything upstream of it. Simulta-

neously, the slope sof each pixel is calculated to be

the gradient between its own point and the point of the

neighbour that it is emptying into. Finally, erosion is

calculated as ks√A, where kis an experimentally de-

rived erosion constant. Every pixel’s terrain height is

reduced by this erosion value for this tick.

2.4 Machine Learning

Machine learning (ML) has in recent years found

many applications throughout the ﬁeld of informa-

tion technology and beyond, and terrain generation is

no exception. When one regards terrain height-maps

as images, it is clear that existing ML techniques are

highly compatible with height-map generation, given

a large enough database of existing terrain samples to

learn from. (Summerville et al., 2018) is a survey on

ML techniques being used for PCG for functional el-

ements in games.

(Yeu et al., 2006) is an early attempt at generat-

ing terrain using ML techniques - in this case, an ex-

treme learning machine (ELM). (Gu´

erin et al., 2017)

proposes to use a Conditional Generative Adversarial

Network (cGAN) that has been trained on real terrain

in order to generate new terrain. (Wulff-Abramsson

et al., 2018) uses a Deep cGAN to generate alpine

height-maps. (Spick and Walker, 2019) uses a GAN

to generate both a height-map and a corresponding

satellite image.

ML techniques have the capability to produce

high-quality terrain output with fast speed and sim-

ple inputs. However, they can only do so with the

help of many auxiliary resources: First of all, there

needs to be a database of realistic and properly for-

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

VisuallyImprovedErosionAlgorithmfortheProceduralGenerationofTile-BasedTerrainFongYuanLim,YuWeiTanandAnandBhojanaDepartmentofComputerScience,NationalUniversityofSingapore,Singaporee0169576@u.nus.edu,yuwei@u.nus.edu),banand@comp.nus.edu.sgKeywords:pcg,procedural,terrain,generation,modelling,games,virt...

展开>> 收起<<

Visually Improved Erosion Algorithm for the Procedural Generation of Tile-Based Terrain Fong Yuan Lim Yu Wei Tan and Anand Bhojan.pdf

共12页,预览3页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Visually Improved Erosion Algorithm for the Procedural Generation of Tile-Based Terrain Fong Yuan Lim Yu Wei Tan and Anand Bhojan

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: