Abstract

Content

• Introduction
• 1. Theme urgency
• 2. Goal and tasks of the research
• 3. Overview of current methods for procedural generation of rooms in video games
• Conclusion
• References

Introduction

Procedural content generation is one of the most rapidly developing areas in the development of computer games. Procedural generation involves the automatic creation of the content of the game world, which can include all sorts of game objects, such as levels, rooms, objects, opponents, player's tools. With the help of generation algorithms, both the appearance and properties of these objects, and their location and even behavior can be specified. In addition, procedurally generated can be textures, music, game events, and even storylines.

Around the principle of procedural generation, entire genres of computer games were formed, and every year their popularity only increases. This is due to the fact that games with such an approach can permanently captivate the player with their diversity and uniqueness, because they allow each time to create new game situations. In addition, procedural generation can significantly reduce the cost of producing games, as it can replace the work of a large number of artists and designers.

1. Theme urgency

At this moment there are many approaches to procedural generation of environments in games. They include various methods and algorithms. The choice of certain of them depends on the tasks that are set during the use of procedural generation, but even for similar tasks various options may be optimal. This is determined by many criteria that the developer exposes - the user of the generation algorithm.

It follows the current tasks in the field of procedural content generation - the creation of universal methods that are able to satisfy a wide range of criteria and have flexible options for setting parameters for various situations, as well as finding and applying the most optimal methods for specific developer goals.

2. Goal and tasks of the research

The aim of the work is the design and development of a procedural content generation system for gaming applications, ensuring the achievement of optimal results through flexible adjustment of input parameters.

The main tasks of the work:

1. Research available methods and algorithms for procedural content generation, their basic principles and areas of application.
2. Selection of the most versatile and flexible methods that are widely used and convenient to use
3. Improving selected methods, including more parameters in their work to get more accurate results
4. Implementing methods based on universal input / output data
5. Developing an interface for interacting with the resulting method library

3. Overview of current methods for procedural generation of rooms in video games

Procedural generation involves the automatic creation of the content of the game world, which can include all sorts of game objects, such as levels, rooms, objects, opponents, player's tools. With the help of generation algorithms, both the appearance and properties of these objects, and their location and even behavior can be specified. In addition, textures, background music, and subject lines can be procedurally generated.

Procedural content generation can significantly reduce the cost of developing computer games, allowing you to create an unlimited number of different objects using one procedure. In addition, the generation can occur dynamically during the gameplay, creating for each player unique situations and unique experience with each new attempt, greatly increasing interest in the game.

However, this approach to development requires precision and detailed elaboration of procedural generation algorithms. Content created in this way should be a little different from manual content, so as not to cause negative impressions.

One of the first tasks that algorithms for procedural generation of content do well in solving is building the game level and the location of the rooms [1]. The concept of game level and rooms is widely used in computer games of various genres. Particularly relevant is the task of procedural generation of levels in games of those genres in which the peculiarity is that the player will have to restart the game many times over, starting from the first level. To prevent this process from becoming monotonous, it was proposed to create a new type of level each time, changing the location of rooms, objects and opponents. Thus, the player could never be sure of what lies ahead, even after several attempts.

The procedural level generation algorithm sets the following tasks:

• create unique sets of rooms;
• the level obtained should be balanced and passable;
• Rooms should be arranged in a natural, intuitive way.

Rooms in each individual game will have their own set of properties that will determine its uniqueness. Among them may be its structure, appearance, content. However, among all the games in the rooms, one can distinguish such generalized features: shape, size, location on the map, connection with other rooms.

Each procedural generation algorithm will include the creation of a set of properties from this list, and further vary depending on the features of the game [10]. Different algorithms allow you to create rooms that are more or less suitable for the given conditions of the game. For example, the level structure, which takes place in underground caves, should differ significantly from the level located in the urban environment. Thus, for different purposes different algorithms will be appropriate, which better cope with the construction of levels, the structure of which is closer to certain game realities.

Binary partitioning method

The method of binary partitioning of space is based on a structure called a BSP tree.

Binary space partitioning is a method for recursively partitioning Euclidean space into convex sets and hyperplanes. As a result, objects get a representation in the form of a data structure called a BSP-tree [3].

The input to the algorithm is the overall size of the level and the minimum size of the expected rooms. The entire area of ??the level is taken as one sheet of BSP-tree, which is randomly divided into two parts. These parts become leaves in the next level of the tree (see fig. 1). The algorithm is executed recursively for each new sheet until its size is below the specified minimum threshold.

Binary partitioning method is simple and convenient to implement. It allows you to quickly break the given initially figure on necessary the number of evenly distributed smaller figures without leaving between them empty spaces and creating geometrically strict rooms.

Level obtained using such an algorithm well suited where necessary portray artificially created landscape. This may be an urban environment. or the floor of a separate room (see fig. 2).

Basic the algorithm does not involve creating corridors - transitions between rooms. This task can be performed manually or supplement the generation algorithm.

Drunkard walk method

Drunkard Walk method - one of the variations method of "random walk". is he got its name for the corresponding chaotic pattern that is formed in result of his work.

Method based on moving the cursor which covers the area of ??the room moving in a random direction [11]. is he described by the following steps:

1. Each the point of the level is declared “wall” - impassable area

2. On the square the level is chosen random point - starting point. It is marked as "gender" - passable area

3. Is chosen random direction of movement.

4. Cursor takes a step in the chosen direction, his new point location is marked as "sex"

5. Steps 3-4 repeat until filled the specified number of points.

The Walk method guarantees the absence of isolated empty areas - from each point of the room will be get to any other point on the map.

To create more natural room structures the algorithm involves several improvements. So, for every possible driving directions are set weighting factors in this way to move the cursor to the center of the level and did not run into borders. In addition, on the next iteration you can set a larger coefficient for the previous direction - so between the rooms will appear more pronounced corridors.

This the algorithm transmits education well natural, natural structures. is he good for creating levels in caves or jungles (see fig. 3).

Cellular automatic

Cellular automaton - a set of cells forming some periodic lattice with set transition rules defining cell state next moment time through the state of the cells, being from her not more than some currently of time. Generally considered automata where the state is determined the cell itself and its closest neighbors [13].

Algorithm which is based on cellular machine starts its work with that randomly announces each point level "wall" or "floor". Thus it turns out starting state of the cellular automaton. Neighbors each point counts 8 adjacent to it points. After this begins it iterative process that is defined following rules:

- point remains a wall if it was a wall and its four adjacent points are walls;

- point becomes a wall if it was a floor and its five neighbors are walls.

So, after several iterations, are formed rooms.

As a result algorithm work can be formed isolated areas, their processing must be carried out manually either separate algorithm.

Final the result contains empty areas with gentle, natural looking walls, without strict division into "rooms" and "corridors". This kind of level is good reflects the natural landscape (see fig. 4).

Conclusion

Algorithms procedural content generation allow create unlimited diverse and high-quality structures levels and rooms. Flexible settings generation, after adjustments, allow achieve the desired developer appearance level. For different types the environment that passes the game world, different algorithms will be appropriate and generation parameters. Awareness and reasonable use of various methods generation allow you to create high quality video game content with minimal resources. However, generalized algorithms are not enough. to create competitive products, and every algorithm needs in completions to achieve the best results. Information of this article can be used to create more highly specialized algorithms procedural content generation.

References

1. Procedural Content Generation Wiki [Electronic resource]/ Интернет-ресурс. – Режим доступа : www/ URL: http://www.pcg.wikidot.com. – Загл. с экрана
2. The Death of the Level Designer: Procedural Content Generation in Games [Electronic resource]/ Интернет-ресурс. – Режим доступа : www/ URL: http://roguelikedeveloper.blogspot.com/2008/01/death-of-level-designer-procedural.html - Загл. с экрана
3. Procedural Content Generation in Games [Electronic resource]/ Интернет-ресурс. – Режим доступа : www/ URL: http://pcgbook.com/ - Загл. с экрана
4. Procedural Generation of Villages on Arbitrary Terrain [Electronic resource]/ Интернет-ресурс. – Режим доступа : www/ URL: https://link.springer.com/article/10.1007%2Fs00371-012-0699-7- Загл. с экрана
5. Меженин М.Г. Обзор систем процедурной генерации игр / М.Г. Меженин / Вестн. ЮУрГУ. Сер. Выч. матем. информ., 2015, том 4, выпуск 1, с. 5–20
6. Процедурная генерация уровней [Electronic resource]/ Интернет-ресурс. – Режим доступа : www/ URL: https://habr.com/post/418685/- Загл. с экрана
7. Процедурная генерация в Distrust [Electronic resource]/ Интернет-ресурс. – Режим доступа : www/ URL: https://habr.com/post/333692/- Загл. с экрана
8. 7 примеров использования процедурной генерации в играх [Electronic resource]/ Интернет-ресурс. – Режим доступа : www/ URL: https://habr.com/company/ua-hosting/blog/275195/- Загл. с экрана
9. Средства разработки динамического игрового окружения для mmorpg игр [Electronic resource]/ Интернет-ресурс. – Режим доступа : www/ URL: http://masters.donntu.ru/2015/fknt/luntovskaya/diss/index.htm- Загл. с экрана
10. Procedural Map Generation [Electronic resource]/ Интернет-ресурс. – Режим доступа : www/ URL: https://www.gridsagegames.com/blog/2014/06/procedural-map-generation. - Загл. с экрана.
11. How to use BSP trees to generate game maps [Electronic resource]/ Интернет-ресурс. – Режим доступа : www/ URL: https://gamedevelopment.tutsplus.com/tutorials/how-to-use-bsp-trees-to-generate-game-maps--gamedev-12268. - Загл. с экрана.
12. Drunken Master cave generation [Electronic resource]/ Интернет-ресурс. – Режим доступа : www/ URL: https://forums.roguetemple.com//index.php?topic=4128.0. - Загл. с экрана.
13. Generate random cave levels using cellular automata [Electronic resource]/ Интернет-ресурс. – Режим доступа : www/ URL: https://gamedevelopment.tutsplus.com/tutorials/generate-random-cave-levels-using-cellular-automata--gamedev-9664. - Загл. с экрана.