The maze landscape generation system with improved visual realism [Jinmo Kim]

Hi, Habr!

In this post, I’ll talk about the article by the author of Jinmo Kim: "The Maze Terrain Authoring for New Visual Realism". It was published on 04/04/2019. The full text of the article can be found here .

Brief system description

The article proposed the author's system for creating labyrinth landscapes, with which the user can automatically generate various complex patterns in a simple and intuitive system. Using the maze information calculated in the program, the three-dimensional maze landscape is generated quickly and efficiently.

The proposed maze landscape generation system consists of three main functions:

• the function of automatic generation of a grid of a labyrinth of various sizes and patterns, implemented using the classical algorithm for generating a labyrinth;
• circular maze generation function;
• a maze transformation function from a hand sketch to a 3D object using an image processing algorithm.

With the help of the proposed system consisting of these three functions, it is possible to effectively create various labyrinths, from homogeneous to irregular. This development will allow to generate labyrinth landscapes of various concepts directly from the calculations made through the same system. In addition, this paper analyzes the improvement of the effect of presence and immersion into virtual reality, i.e. visual realism. Also, in this paper, an analysis was conducted of the suitability of the proposed authoring system using a survey.

Why virtual reality?

To get some realistic experience, you need to interact with the human senses. Virtual reality allows a person to get this experience, due to the interaction with visual, auditory and tactile feelings. In virtual reality, the effect of presence is important, due to which the user can get a realistic experience based on sensations, regarding where he is and with whom and what actions he performs.

To increase the effect of presence in virtual reality, it is important how the user interacts with the virtual environment, but it is equally important how diverse the virtual scenes are provided for the visual satisfaction of the user.

In studies of hardware-oriented systems of virtual reality (tactile systems, motion platforms, etc.), for realistic display of actions and movements of users in virtual reality, only experimental scenes were used, where the space in them was limited, and the structure of the scenes was simple. most cases. Since VR technology is used in various fields, such as visual arts and architectural design, as well as in games, special studies are needed to create a complex virtual space in accordance with VR. To this end, this work has investigated the methods of automatically creating virtual scenes, such as urban spaces and virtual landscapes, which have complex structures and various characteristics.

Virtual reality immersion

Virtual reality immersion (or immersive virtual reality) - this is a reality that is born in the mind of man in the process of its interaction with complex technical systems, such as virtual reality systems. It has its own unique chronotope, logic, it exists only as relevant as long as the user is "present" in this reality, has interactivity, as the ability to respond to user actions.

Studies of virtual reality immersion were carried out using various approaches:

• a display that transmits three-dimensional visual information to provide a realistic user experience in a virtual environment based on the five senses
• sound processing to provide enhanced spatial perception using surround sound
• a method of interaction with the virtual environment, as well as a tactile system and a platform of movement that direct physical responses back to the human body (arms, legs, etc.).

To achieve the effect of presence in virtual reality, there must be a visual user satisfaction. For this reason, there is a growing interest in multimodal research, which deals with visual and auditory sensations or visual and tactile sensations, as well as studies of pseudo-tactile systems that combine visual experience and tactile systems.

Improving visual realism

A virtual scene generation method that can provide an enhanced presence effect, along with new visual experiences for the user in a virtual environment, is necessary for a variety of VR applications. In the future, virtual reality scenes will free themselves from small and limited spaces, such as interiors, and create vast open landscapes, such as cities and virtual worlds, to provide users with a wider choice.

To create virtual scenes of labyrinths that can provide new experiences and improve the effect of the presence of users in virtual reality, an optimized authoring system is proposed in this paper. It is based on traditional research and can generate more diverse virtual scenes of labyrinths in a simple, intuitive and user-oriented structure.

Labyrinth terrain creation system

The proposed system creates a virtual labyrinth landscape, with the effect of enhancing visual realism for users in virtual reality, using various visual effects. It contains three main functions that automatically generate various maze patterns and convert them into information needed to create a three-dimensional maze surface.

Generate a straight maze pattern

The first function of the maze landscape creation system is to automatically generate maze patterns using the classic maze generation algorithm. An important factor is the need to create a final maze. There must be different paths or one absolute path so that the user is not trapped inside the maze. This helps prevent users from having the disease VR, which is a serious problem in the field of virtual reality. This function is based on the Lee et al. Algorithm, which creates a maze pattern using the Prima algorithm.

The algorithm for the final generation of the labyrinth of Lee, and others, is a method that begins with the processes of: (1) setting the starting position and (2) randomly installing a road cell from the surrounding cells. Then (3) the algorithm explores four cells around the direction (defining the structure of the cell layers, after adding these four surrounding cells to the collection as cell walls). The algorithm then repeats the processes (4, 5) to find one of the recorded cells of the wall, and then creates a road.

The pictures below show the process of building a rectilinear maze pattern. The user sets the size of the maze pattern, and when the “Maze” button is clicked, the maze pattern is automatically calculated and generated.

If the user wants to edit the template of an automatically created maze, then the “Edit” mode is selected. The user edits the mouse in the view field of the maze pattern by clicking on a cell, after which it is automatically converted from the wall to the road or from the road to the wall. After the maze pattern has been generated, the user has the opportunity to view the maze in 3D format.

View the maze in 3D

The method of creating a circular maze

The second function of the proposed authoring system for creating a landscape of a labyrinth is the method of generating a circular labyrinth. This method automatically creates circular labyrinths of various sizes and patterns and is a good addition to the function of generating labyrinth patterns in the form of a rectangular grid. Thus, this method extends the visual experience of users in virtual reality. The process of creating and installing walls and road cells is basically identical. But for a circular maze, the input characteristics are the radius of the maze and the number of entrances to the maze.

First of all, when the user enters the desired radius of the labyrinth, the cells of the walls of the circular labyrinth are automatically calculated using the algorithm for drawing a circle from a central point. Then the wall of the circular labyrinth is repeatedly duplicated with a certain interval (ns) from the outer circle. Based on the number of inputs entered by the user, the passages are created by rotating the wall cells as many times as the entrances should be from the outermost circle.

The cells that will be the starting points for entering the outer circle are chosen arbitrarily as many times as there are turns of maze entries. Then, in the selected cell, the cell of the wall is chosen, whose length coincides with the interval (ns) between the circular walls, and it rotates just enough to touch the inner circular wall.
Finally, when a cell of the wall is encountered in the position in which it is turned and touches the inner circular wall, the above algorithm is repeated.

1: nr ←   . 2: ne ←    . 3: procedure     (nr, ne) 4: ns ←       . 5: while nr > ns do 6:         . 7: nr = nr - ns. 8: end while 9: nc ←    . 10: Arre[ne] ←  ,  ne      . 11: for i = nc, 0 do:     . 12: for j = 0, ne do 13:     ns    (Arre[j]). 14:   . 15:  Arre[j],  ,      . 16: end for 17: end for 18: end procedure 

 nr ← radius of the circular maze. ne ← number of maze entrances. procedure CIRCULAR MAZE GENERATION PROCESS(nr, ne) ns ← interval between maze for user road. while nr > ns do define wall cell by using Bresenham's circle drawing algorithm. nr = nr - ns. end while nc ← number of drawing circles. Arre[ne] ← as many entrance cells as ne are selected from wall cell of the outermost circle. for i = nc, 0 do: generate passages in every circle. for j = 0, ne do select cells with length of ns in entrance cell (Arre[j]). rotate selected cells. renew Arre[j] by finding a cell that meets the inner circle after rotation. end for end for end procedure 

The above is an algorithm for this process based on the input parameters of the radius of the circular labyrinth and the number of inputs entered by the user. Also, the figure below shows the process of creating a circular maze.

Labyrinth based sketch

The last function of the labyrinth creation system in this work is the generation of a maze based on a sketch. Patterns of rectilinear and circular labyrinths are homogeneous labyrinths. However, in most cases, the labyrinth park that we may encounter in everyday life has an irregular shape. Therefore, in this work, a function is proposed that, from a hand-drawn sketch of a user, can easily create a natural maze surface, as well as a maze pattern in electronic form. This feature allows you to use labyrinth areas in various applications, such as path finding systems or virtual parks.

The proposed maze generation function allows the user to use a maze drawing drawn with graphics software such as Photoshop or a scanned sketch drawn by hand on a piece of paper. The image is loaded into the system in which the image processing algorithm is applied, due to which the image is converted into a maze texture map. This process is carried out in three stages.

• The first step is the process of obtaining a thumbnail image in the system. To make calculations of subsequent processes, a sketch image is converted into a single-channel image in grayscale.
• The second step is the process of partitioning walls and roads using binarization. Here the threshold is an important element for determining walls and roads. The system has the ability to edit the input threshold value through the interface.
• The third stage is the process of filling holes arising in the process of binarization.

Due to these steps, a natural maze is created. The system also has a menu item that allows the user to control the number of iterations of the fill operation.
The figure below shows the process of generating a maze texture map in a step-by-step mode from a user-drawn sketch of a maze.

Generating a maze from a user sketch

Experimental results and analysis

The proposed maze terrain creation system was implemented using Microsoft Visual Studio 2013, OpenCV 2.4.11 and DirectX SDK 9.0c. In addition, the Unity 2017.3.1f1 (64-bit) engine was used to create a labyrinth landscape, refined using graphic work, based on a maze texture map, automatically generated using the maze authoring system. To test this landscape and view the results in virtual reality, the system was integrated using the Oculus Rift CV1 HMD and Oculus SDK (ovr_unity_utilities 1.22.0) devices with the Unity3D engine. Finally, the PC used for the experiment and implementation had the characteristics of an Intel Core i7-6700, 16 GB of RAM (random access memory) and a Geforce 1080 graphics processor.

The figure below shows the three virtual terraces of the maze. These are the results of the terrain generation from maze patterns calculated using the considered functions of this development system. In addition, you can see that the various maze virtual environments are created by adding graphical factors according to the concept.

In addition, an experimental survey was conducted targeting general participants. First, with regard to system performance, using comparative tests with the function of creating landscapes of commercial game engines, it was confirmed that the proposed system allows users (developers) to easily and intuitively edit the desired parts of the maze. This reduced the time required and led to a high degree of user satisfaction with the system.

Using a survey on the feeling of presence, it was confirmed that the labyrinth landscapes in virtual reality can offer users a new visual experience. Using statistical analysis, it was also confirmed that all the plots obtained using the proposed three functions were satisfactory without any significant differences between them. In the future, the system will be refined to provide a large-scale virtual maze environment, such as a maze park or a theme park, where several users can experience the maze space together in virtual reality.