Automatic evolution of programs for procedural generation of terrains for video games

Nowadays the video game industry is facing a big challenge to keep costs under control as games become bigger and more complex. Creation of game content, such as character models, maps, levels, textures, sound effects and so on, represent a big slice of total game production cost. Hence, the video game industry is increasingly turning to procedural content generation to amplify the cost-effectiveness of the efforts of video game designers. However, procedural methods for automated content generation are difficult to create and parametrize. In this work we study a genetic programming-based procedural content technique to generate procedural terrains that do not require parametrization, thus, allowing to save time and help reducing production costs. Generated procedural terrains present aesthetic appeal; however, unlike most techniques involving aesthetic, our approach does not require a human to perform the evaluation. Instead, the search is guided by the weighted sum of two morphological metrics: terrain accessibility and obstacle edge length. The combination of the two metrics allowed us to find a wide range of fit terrains that present more scattered obstacles in different locations than our previous approach with a single metric. Procedural terrains produced by this technique are already in use in a real video game.     

Arches: a Framework for Modeling Complex Terrains

In this paper, we present a framework for representing complex terrains with such features as overhangs, arches and caves and including different materials such as sand and rocks. Our hybrid model combines a volumetric discrete data structure that stores the different materials and an implicit representation for sculpting and reconstructing the surface of the terrain. Complex scenes can be edited and sculpted interactively with high level tools. We also propose an original rock generation technique that enables us to automatically generate complex rocky sceneries with piles of rocks without any computationally demanding physically-based simulation.     

Sparse representation of terrains for procedural modeling

In this paper, we present a simple and efficient method to represent terrains as elevation functions built from linear combinations of landform features (atoms). These features can be extracted either from real world data‐sets or procedural primitives, or from any combination of multiple terrain models. Our approach consists in representing the elevation function as a sparse combination of primitives, a concept which we call Sparse Construction Tree, which blends the different landform features stored in a dictionary. The sparse representation allows us to represent complex terrains using combinations of atoms from a small dictionary, yielding a powerful and compact terrain representation and synthesis tool. Moreover, we present a method for automatically learning the dictionary and generating the Sparse Construction Tree model. We demonstrate the efficiency of our method in several applications: inverse procedural modeling of terrains, terrain amplification and synthesis from a coarse sketch.     

Procedural generation of villages on arbitrary terrains

Although procedural modeling of cities has attracted a lot of attention for the past decade, populating arbitrary landscapes with non-urban settlements remains an open problem. In this work, we focus on the modeling of small, European villages that took benefit of terrain features to settle in safe, sunny or simply convenient places. We introduce a three step procedural generation method. First, an iterative process based on interest maps is used to progressively generate settlement seeds and the roads that connect them. The fact that a new road attracts settlers while a new house often leads to some extension of the road network is taken into account. Then, an anisotropic conquest method is introduced to segment the land into parcels around settlement seeds. Finally, we introduce open shape grammar to generate 3D geometry that adapts to the local slope. We demonstrate the effectiveness of our method by generating different kinds of village on arbitrary terrains, from a mountain hamlet to a fisherman village, and validate through comparison with real data.     

A Survey on Procedural Modelling for Virtual Worlds

Procedural modelling deals with (semi‐)automatic content generation by means of a program or procedure. Among other advantages, its data compression and the potential to generate a large variety of detailed content with reduced human intervention, have made procedural modelling attractive for creating virtual environments increasingly used in movies, games and simulations. We survey procedural methods that are useful to generate features of virtual worlds, including terrains, vegetation, rivers, roads, buildings and entire cities. In this survey, we focus particularly on the degree of intuitive control and of interactivity offered by each procedural method, because these properties are instrumental for their typical users: designers and artists. We identify the most promising research results that have been recently achieved, but we also realize that there is far from widespread acceptance of procedural methods among non‐technical, creative professionals. We conclude by discussing some of the most important challenges of procedural modelling.     

Terrain Modelling from Feature Primitives

We introduce a compact hierarchical procedural model that combines feature‐based primitives to describe complex terrains with varying level of detail. Our model is inspired by skeletal implicit surfaces and defines the terrain elevation function by using a construction tree. Leaves represent terrain features and they are generic parametrized skeletal primitives, such as mountains, ridges, valleys, rivers, lakes or roads. Inner nodes combine the leaves and subtrees by carving, blending or warping operators. The elevation of the terrain at a given point is evaluated by traversing the tree and by combining the contributions of the primitives. The definition of the tree leaves and operators guarantees that the resulting elevation function is Lipschitz, which speeds up the sphere tracing used to render the terrain. Our model is compact and allows for the creation of large terrains with a high level o detail using a reduced set of primitives. We show the creation of different kinds of landscapes and demonstrate that our model allows to efficiently control the shape and distribution of landform features.     

各向异性的分形地形生成方法研究

传统的分形地形生成方法得到的地形是各向同性的,为了使生成的分形地形具有各向异性特征,提出了一种新的分形地形生成方法,该方法利用组合分形布朗曲面模型,将具有不同特征的两种分形布朗曲面相融合,使得生成的地形具有各向异性特征.对组合分形布朗曲面算法进行了仿真实验,生成了最终的分形地形.对仿真结果的分析表明,生成的分彤地形的特征具有各向异性特征,和实际的自然地形特征相符合,从而证明了该算法的有效性.     

大规模地形漫游中的实时地形渲染技术

地形漫游已经被广泛应用于游戏、虚拟现实（VR）、飞行仿真和地理信息系统（GIS）等环境中。在传统的仿真中,地形采用艺术家手工建模,但是手工建模价格昂贵,而且不能产生连续的细节层次（Level of Detail,LOD）。大规模的地形渲染算法需要采用细节层次来减少实际需要绘制的地形数据。从产生地形角度入手,分析了几种经典的实时地形渲染技术,并对部分技术进行比较。最后提出对某些方法进行改进,以达到更好的效果,并通过PC机上的实验加以验证。     

Enhancing N-Gram Based Metrics with Semantics for Better Evaluation of Abstractive Text Summarization

Text summarization is an important task in natural language processing and it has been applied in many applications. Recently, abstractive summarization has attracted many attentions. However, the traditional evaluation metrics that consider little semantic information, are unsuitable for evaluating the quality of deep learning based abstractive summarization models, since these models may generate new words that do not exist in the original text. Moreover, the out-of-vocabulary (OOV) problem that affects the evaluation results, has not been well solved yet. To address these issues, we propose a novel model called ENMS, to enhance existing N-gram based evaluation metrics with semantics. To be specific, we present two types of methods: N-gram based Semantic Matching (NSM for short), and N-gram based Semantic Similarity (NSS for short), to improve several widely-used evaluation metrics including ROUGE (Recall-Oriented Understudy for Gisting Evaluation), BLEU (Bilingual Evaluation Understudy), etc. NSM and NSS work in different ways. The former calculates the matching degree directly, while the latter mainly improves the similarity measurement. Moreover we propose an N-gram representation mechanism to explore the vector representation of N-grams (including skip-grams). It serves as the basis of our ENMS model, in which we exploit some simple but effective integration methods to solve the OOV problem efficiently. Experimental results over the TAC AESOP dataset show that the metrics improved by our methods are well correlated with human judgements and can be used to better evaluate abstractive summarization methods.     

River Networks for Instant Procedural Planets

Realistic terrain models are required in many applications, especially in computer games. Commonly, procedural models are applied to generate the corresponding models and let users experience a wide variety of new environments. Existing algorithms generate landscapes immediately with view‐dependent resolution and without preprocessing. Unfortunately, landscapes generated by such algorithms lack river networks and therefore appear unnatural. Algorithms that integrate realistic river networks are computationally expensive and cannot be used to generate a locally adaptive high resolution landscape during a fly‐through. In this paper, we propose a novel algorithm to generate realistic river networks. Our procedural algorithm creates complete planets and landscapes with realistic river networks within seconds. It starts with a coarse base geometry of a planet without further preprocessing and user intervention. By exploiting current graphics hardware, the proposed algorithm is able to generate adaptively refined landscape geometry during fly‐throughs.     

Color texture analysis based on fractal descriptors

Color texture classification is an important step in image segmentation and recognition. The color information is especially important in textures of natural scenes, such as leaves surfaces, terrains models, etc. In this paper, we propose a novel approach based on the fractal dimension for color texture analysis. The proposed approach investigates the complexity in R, G and B color channels to characterize a texture sample. We also propose to study all channels in combination, taking into consideration the correlations between them. Both these approaches use the volumetric version of the Bouligand–Minkowski Fractal Dimension method. The results show a advantage of the proposed method over other color texture analysis methods.     

Fast approximate clearance evaluation for rovers with articulated suspension systems

We present a light‐weight body‐terrain clearance evaluation algorithm for the automated path planning of NASA's Mars 2020 rover. Extraterrestrial path planning is challenging due to the combination of terrain roughness and severe limitation in computational resources. Path planning on cluttered and/or uneven terrains requires repeated safety checks on all the candidate paths at a small interval. Predicting the future rover state requires simulating the vehicle settling on the terrain, which involves an inverse‐kinematics problem with iterative nonlinear optimization under geometric constraints. However, such expensive computation is intractable for slow spacecraft computers, such as RAD750, which is used by the Curiosity Mars rover and upcoming Mars 2020 rover. We propose the approximate clearance evaluation (ACE) algorithm, which obtains conservative bounds on vehicle clearance, attitude, and suspension angles without iterative computation. It obtains those bounds by estimating the lowest and highest heights that each wheel may reach given the underlying terrain, and calculating the worst‐case vehicle configuration associated with those extreme wheel heights. The bounds are guaranteed to be conservative, hence ensuring vehicle safety during autonomous navigation. ACE is planned to be used as part of the new onboard path planner of the Mars 2020 rover. This paper describes the algorithm in detail and validates our claim of conservatism and fast computation through experiments.     

Meta-metric for saliency detection evaluation metrics based on application preference

Existing saliency detection evaluation metrics often produce inconsistent evaluation results. Because of the widespread application of image saliency detection, we propose a meta-metric to evaluate the performance of these metrics based on the preference of an application that uses saliency maps as weighting maps. This study uses content-based image retrieval (CBIR) as the representative application. First, we perform CBIR using image features extracted from deep convolutional layers of convolutional neural networks as well as saliency maps computed by various saliency detection algorithms as the weighting maps over queries. Second, we establish the preference order of the saliency detection algorithms in the CBIR application by sorting the mean average precision. Third, we determine the preference order of these algorithms using existing saliency detection evaluation metrics. Finally, our meta-metric evaluates these metrics by correlating the preference order in the CBIR application with that determined by each evaluation metric. Experiments on three publicly available datasets show that, of 24 evaluation metrics, the traditional metric: area under receiver operating characteristic curve is the best metric for a CBIR application.     

A Semi-Procedural Convolutional Material Prior

Lightweight material capture methods require a material prior, defining the subspace of plausible textures within the large space of unconstrained texel grids. Previous work has either used deep neural networks (trained on large synthetic material datasets) or procedural node graphs (constructed by expert artists) as such priors. In this paper, we propose a semi-procedural differentiable material prior that represents materials as a set of (typically procedural) grayscale noises and patterns that are processed by a sequence of lightweight learnable convolutional filter operations. We demonstrate that the restricted structure of this architecture acts as an inductive bias on the space of material appearances, allowing us to optimize the weights of the convolutions per-material, with no need for pre-training on a large dataset. Combined with a differentiable rendering step and a perceptual loss, we enable single-image tileable material capture comparable with state of the art. Our approach does not target the pixel-perfect recovery of the material, but rather uses noises and patterns as input to match the target appearance. To achieve this, it does not require complex procedural graphs, and has a much lower complexity, computational cost and storage cost. We also enable control over the results, through changing the provided patterns and using guide maps to push the material properties towards a user-driven objective.     

Terrain surface classification with a control mode update rule using a 2D laser stripe-based structured light sensor

It is necessary for autonomous ground vehicles operating on outdoor terrains to identify and adapt to different terrains in order to improve their mobility and safety. This work presents a classification scheme to identify outdoor terrains and an update rule to reduce the possibility of implementing control modes based on classification inaccuracies. A laser stripe-based structured light sensor, which has a laser and infrared camera component, is used to sense terrains directly in front of the vehicle (). Use of this infrared vision system allows sensing at night, without external lighting, unlike many previous vision-based approaches that rely on stand-alone cameras. Also, unlike many previous results, the classification algorithm presented here does not rely on measures of color, which are subject to illumination and weather conditions. Instead, the method presented here relies on spatial relationships which are captured in two quantities: spatial frequency from range data and texture from camera data. The presented terrain classification scheme uses a probabilistic neural network classifier to exploit the spatial differences in four terrains: asphalt, grass, gravel and sand. This approach yields empirical results that report a greater than 97% classification accuracy when both spatial frequency and texture features are used. Color robustness and lighting robustness is then shown through additional experiments. Furthermore, instead of implementing control modes directly from the identified terrains, it is shown that the use of current and past terrain detections allows for the rejection of misclassifications with minimal effect on the rate at which a new control mode can be implemented.     

自然地形环境下移动机器人的一种路径规划方法

本文给出了一种规划移动机器人在自然地形中运动的新方法，该方法利用ＮＵＲＢＳ曲面模拟自然地形地貌，以ＴｒｉｍｍｅｄＮＵＲＢＳ曲面描述带有障碍物或不可逾越区域的地形，在综合考虑机器人动力学、地形及障碍描述和曲面特性等各方面因素的情形下，运用测地线的概念和计算方法以及Ａ＊搜索算法，获得了在自然地形环境下任意两点间的距离最短路径和时间最优路径，所有的路径均由ＮＵＲＢＳ曲线表示，实验结果表明，该方法在性能与效率上均十分令人满意．     

A Bayesian Inference Framework for Procedural Material Parameter Estimation

Procedural material models have been gaining traction in many applications thanks to their flexibility, compactness, and easy editability. We explore the inverse rendering problem of procedural material parameter estimation from photographs, presenting a unified view of the problem in a Bayesian framework. In addition to computing point estimates of the parameters by optimization, our framework uses a Markov Chain Monte Carlo approach to sample the space of plausible material parameters, providing a collection of plausible matches that a user can choose from, and efficiently handling both discrete and continuous model parameters. To demonstrate the effectiveness of our framework, we fit procedural models of a range of materials—wall plaster, leather, wood, anisotropic brushed metals and layered metallic paints—to both synthetic and real target images.     

非对称博弈的表示和求解

非对称博弈是一种普遍存在的博奔现象,现实中大量的博弈都呈现出非对称的特性.但是非对称博弈的表示问题在多-Agent影响图中是一个难以解决的问题,存在表示复杂和求解效率低的情况.针对该问题,借鉴了单-Agent决策系统中非对称性表示的方法,提出了一种新的博弈模型,有效的解决了非对称博弈的表示问题.给出了该模型详细的求解算...     

结合稀疏识别的自适应Wallis滤波在高分辨率影像控制点匹配中的应用

目的：随着国内遥感卫星的迅速发展,卫星图像的图幅越来越大,分辨率越来越高。在轨遥感图像的几何精度评价,要求从待评遥感图像和多源参考图像之间精确地提取出分布均匀的控制点信息。使用Wallis滤波对高分辨率影像进行增强时,会产生过增强和饱和现象,影响了控制点提取效果。为了克服上述缺陷,提出了一种基于稀疏识别的自适应Wallis图像增强算法。方法：首先计算图像子区域的辐射质量参数并构建分类特征;然后通过稀疏识别算法确定子区域的地物类型;最后根据子区域所属地物类型,选择不同的Wallis滤波参数,实现整幅图像的自适应增强,并在增强的遥感图像上提取控制点信息,实现遥感图像的几何精度自动化评价。结果：针对资源三号影像的实验结果表明,针对不同的子区域地物类型进行自适应Wallis增强,有效防止了基于全局统一参数的Wallis滤波带来的过增强和饱和现象,有效增强了高分辨率图像的纹理。结论：本文提出来一种新的高分辨率遥感影像增强策略,增强了高分辨率图像的纹理,提高了控制点的获取数目和准确率。