[Cedec2019] Create a new game experience by devising terrain expressions on a map of 1 km square

What is the difference between art and design?If art is a creator's self -expression, design is an act that solves customer issues.The same is true for game development, and there are many solutions to various issues.If game designers provide new game experiences to users, the challenge of the game programmer is to give the game designer ideas.Various ideas are included so that you can maximize your hardware restrictions.

CEDEC2019, which was held in Pacifico Yokohama from September 4 to September 6, also shared various "solutions to issues" using game AI.This time, I will report on the content of the topographic expression and navigation AI in "Left Alive" by Square Enix Makoto Hasegawa.Mr. Hasegawa explained the devising various topographical expressions used in moving enemy soldiers on a vast map of one kilometer.

Numerous requests presented on the game design side

"Left Alive" is a survival action game that shares the world view with the company's science fiction simulation game "Front Mission" series.The game core mechanics are a third -person 3D cover shooting, and players confront humanoid weapons, Vanzer and enemy soldiers while manipulating three protagonists.Instead of assaulting enemy soldiers who beat the quantity from the front, it is characterized by high elements of the kakeki, thinking about how to survive while making various choices.

In developing this work, the issues presented by the game designer are "3D cover shooting", "On the map of one kilometer, the enemy soldiers can explore the players from end to end" "Fight anywhere on the map".I could do it. "In addition to simply moving and shooting enemy soldiers, you can do the same act as players, such as attacks using a cover (shielding), going through door, ladder, windows, jumping walls and cover.I also needed it.

In order to create a navigation AI that realizes these specifications, normal navigation (navigation) mesh alone was insufficient.If you do a long path search from the edges of the map to the end, the search load will be too high.In order for enemy soldiers to perform special actions using doors and ladders, it is also necessary to move outside the mesh by jumping links.You will also need a search function to get the right cover position.The most important thing is to automatically generate a huge amount of data on topographic expressions.

Therefore, Mr. Hasegawa decided to devise the topographic expression to solve the above issues.One of them is a way point that embeds various information on the map in addition to the normal navigation mesh.The upper graph added to divide the rough area also played a major role.Based on these, a mechanism to automatically generate information such as the list of shields and LOF (LINE OF FIRE) has been set up.

Navigation

Like many 3D games, the base of this work is a topographic expression by Navi Mesh.In the actual creation, a recast navigation that has been adopted in many titles and many titles has been adopted.Use this to make a flag that can pass from the initial arrangement of the player to the continuous polygon.However, this alone has a mesh in places where it cannot be moved directly, such as the rooftop of a building, so there is also a response to delete a specific mesh.

Way point and connection graph

Waypoint is the place to embed the necessary information on the game.The information stored in the waypoints is "XYZ position", "Navimesh polygon ID with a waypoint", "LOF", and "shooting coverlist".It is also the starting point of jump links used to bind each other.In this way, the way point in this work is the basis of terrain expression along with Navimesh.

Way points are automatically placed on navigation mesh (it is the base of the upper graph described later, so a certain amount of density is required) and thinned out randomly.However, there are some points on the map that should never be thinned, such as the "Way Point graph cut point".As a result of automatic detection and saving algorithms, we succeeded in deleting up to 64,286 hors points per maximum map.

LOF (LINE OF Fire)

The wave point after the tone is also the basic information for automatically generating LOF.LOF is a ray information in individual waypoints. It is required by flying a requast from the point position to the circle and calculating the depth.The calculated LOF is embedded in each way point and is used for shooting enemy soldiers.Without LOF, the enemy soldiers need to fly the ray casting to the surroundings and check the rays, so that the processing can be faster.

In this work, two types of LOFs are stored in one way point in one way point.As a result, a point that is out of the LOF occurs in the crouching posture in the standing posture (these points are effective for the cover).In addition, at the edge of the building, two types of LOFs are stored while the characters are hidden and laid out in the building.

Cover (shielding)

The cover is a 3D cover shooting, a topographic expression that greatly contributes to the game experience of this work.The edge of the three -dimensional structure is used for the creation without a adjacent polygon on the navigation mesh.It is a mechanism that hits the ray casting sideways while shifting the reference point in the vertical direction from the straight line corresponding to the edge part of each polygon, and is listed as a terrain that can be used for the cover if the height is within the reference value.As with LOF, there are two types of high and low in the cover.

The most suitable place for the cover changes in real time depending on the position of the character on the map.For this reason, in this work, all cover parts on the map are listed, and the list information of the cover suitable for that position is stored for each wave point.When your character reaches a specific wave point, a list of effective coverlists for that point is shared by surrounding enemy soldiers.The enemy soldiers move to the appropriate cover position according to that information.

Other than this, there are points on the map that can be moved through special actions, even in places where navigation is not directly connected.Cross over the shield, go up and down the ladder, open the door and enter the building.In order to enable such movements, a connection between howpoint was made.As a result, even if the navigation is interrupted in this work, if it is connected between the way points, enemy soldiers can be reached anywhere.

Upper layer graph based on Way Point

During the lecture, Hasegawa explained how to emphasize the most emphasis on how to make a higher -level graph based on the Way Point.A higher -level graph is a wider area created based on a waypoint.By using it with Navi Mesh when you move an enemy soldier, you can search for a pass at high speed even if you travel long distances.

However, simply dividing the map will create an upper graph that does not fit the shape of the building or terrain.Therefore, in this work, an algorithm that creates a higher -layer graph according to the size of the terrain (building, road, etc.) was adopted.

The base is the way point information before the pulling.Set the distance from the border (such as inner walls) of the terrain at each wave point, and attach the label to the farthest point (= center).After that, attach the same label to the adjacent wave point and repeat this until it comes into contact with a wePoint with another label.This creates a top -level node according to the terrain.After that, the node is integrated and divided, and the size is adjusted.

Along with these methods, the map has a maximum of 64286 hors points, and succeeded in reducing the number of nodes of the upper graph to 2174.The long -distance travel problem has been solved.Specifically, the enemy soldier moves by stepping on the steps of "by performing a path search with a higher -level graph, formulating a rough movement route, joining the way points of all nodes and moving to the destination".I will do it.In addition, a veven curve based on the wapoint is applied to formulating the mobile route.

However, specific actions may occur during the movement, such as when an enemy soldiers open the door or go up and down the ladder.In this case, the action is separated depending on whether the action straddles on a higher -level graph or on the way point (the door and ladder are upper -level graphs, and cross -over, etc.)In order to enable this, it was supplemented that the door, ladder, and windows need to be created on the node that corresponds to the border of the upper layer graph.

Dynamic terrain evaluation added based on additional requests

By the way, in this way, all terrain expressions were completed, so it was not possible to settle down.This is because a new issue was presented by the game designer during the development.Both were directly connected to the game experience, and could not be realized without improvement of navigation AI.It goes without saying that how far the programmer can respond to such an additional task (which can be said to be the unreasonable game designer) is the key to creating an interesting game.

One of the first tasks was "I want to make enemy soldiers traps in a good way."In this work, the traps set up by their characters play an important factor in exterminating enemies that are better than numbers.However, during the development stage, there was a problem that enemy soldiers did not approach the trap.Normally, players set traps in places that are invisible to enemy soldiers, such as shadows, and wait.However, since the enemy's algorithm was "attacking the position where the player was lost," he was out of time without approaching the trap.

Therefore, the idea of "preparing a" front line "at a moderate distance between the character and enemy soldier" was adopted.If you lose sight of the player during the battle, you will set the enemy soldier to the front line.Also, when a trap is installed, this front line will approach the player.With such a combination of logic, a series of experiences, when the player was trapped and waited, eventually the enemy soldiers walk and trap traps.

However, it was necessary to make this front line on the terrain.In addition, there was a problem that it was difficult to draw lines in the first place because enemy soldiers were distributed unevenly.For this reason, the front line is set by creating an influence map on a high -level graph with enemy soldiers as high temperatures and low -temperature heat sources.In addition, it has been adjusted so that the enemy soldier group goes straight to the player to some extent, so that the temperature difference is steep.

Peeling shooting / appearance of enemy soldiers ... Up -ranking graphs are active

The challenge of "I want Vanzer to shoot a character in the game and shoot a character."Simply searching and moving by searching for a pass tends to connect multiple Vanzers and cannot reproduce the situation in which their characters are surrounded.Therefore, the weight of the search was devised so that Vanzer set up a counter on the pass where he passed and perform a path search across the upper layer graph.As a result, we were able to reproduce the shooting situation naturally.

There was also a request that "I want to make enemy soldiers appear in the appropriate position on the map."In this work, the enemy soldiers in advance on the map are limited, and the enemy soldiers will automatically appear according to the location of their own characters.However, just by making enemy soldiers randomly appeared, there were problems that tend to fall apart until enemy soldiers reached the character point.This is because it is inevitable that it will appear in a place where you have to detour and approach with walls and fences.

Again, the existence of the upper graph that contributed to the solution.First, when moving your character, you will dynamically create a distance map on a higher -layer graph.Next, the number of times that crosses the upper layer node is regarded as the distance to the character, and automatically eliminates the distant place in the mobile route.On top of that, enemy soldiers appear randomly from the remaining places.

The game AI and the game design are the front and back of the coin

In addition, Mr. Hasegawa said that it contributed to the navigation AI by embedding various information on the upper graph.The recognition of the "floor" of the building, the list of listing from a certain upper -level node, the list of listing the upper node, and the entrance information of the building where the character is standing.

In this way, this session has become a sample of how the game AI programmer solves the issues in response to the request from the game designer.Conversely, during the development, he often provided new ideas from the perspective of game AI.In addition, we have supplemented that the promotion of automation by creating each terrain expression has contributed to improving quality.If the level designers do these tasks manually, it will take a lot of time and it's not realistic.

The point is that the game AI does not exist alone in the game development, and is used in the relationship with the game design.This may also have predicted the birth of a new position as a game AI designer that brokers game AI and game design in the future.

Writer: Kenji Ono