Wandering monster: how to get rid of problems on the map

Already in the process of creating The Witness has become one of my favorite games. I started to play it from the moment when Jonathan Blow began its development, and could not wait for its release.

Unlike John Braid’s previous game, The Witness’s resources and programming were much closer to AAA projects than to indie games. Everyone who works on such projects, it is known that the amount of work when choosing such a path increases significantly. More people worked on The Witness than on Braid , but as is the case with any project of this level, there are many aspects that require more attention than the project management can afford.

So I always wanted to find some free time to help create The Witness when it came to the release of the game. Therefore, one day at Thanksgiving, John and I sat down and looked at the list of things in the code base that would benefit from the extra effort of another programmer. Having decided on the relative importance of the list items, we decided that the gameplay would benefit the most if we make improvements to the player’s movement code.

Walkmonster in wall

In the context of The Witness , the task of the player’s movement code is to be as unobtrusive as possible. The player must fully immerse himself in an alternate reality, and in this gaming experience every detail is important. The last thing we wanted was for the player to notice that he was sitting at the computer and moving the virtual camera.
')
Therefore, the movement code of the player must be absolutely reliable. If a player clings to corners, gets stuck in the walls, falls through the floor, descends a hill without being able to go back, etc., this will instantly destroy the illusion of immersion and remind the player that he is inside an artificial gameplay, which is hampered by an unreliable system. displacements. In some circumstances, this can even lead to disastrous consequences for the player if he does not have the opportunity to solve the problem by restarting the game or reloading (probably very old) “saved”. If you often play games, you must have encountered problems of this type, and you know what I mean.

After our discussion, I began to work on this task. First of all, I decided to write integrated tools for working with the player’s movement code, so that we could analyze it and observe its current behavior. Having opened the project, I ran into a serious problem already known to me: how to name the first file of the source code? This is always the most important part of any project ( as Bob Pollard once said about the names of bands and albums ). If you give the source file a suitable name, then further work will be clear and smooth. Choose the wrong - you can destroy the whole project.

But how to call a system to ensure the quality of the player’s movement code? I have never had to write such code before. When I thought about it, I realized that I personally saw an example of such a code only once: when playing in the early Quake beta. It contained bugs with the location of monsters, and in the console window you could see error messages saying that monsters, instead of being created on the surface of the earth, are created, partially intersecting with the geometry of the levels. Each debugging message began with the phrase "walkmonster in wall at ..."

Bingo! It’s hard to pick a better name for the code file than “walk_monster.cpp”. And I was almost sure that from now on, the code will be created without problems.

Movement to the point

When you want to test a system, the most important thing is to actually test the system . Although this rule looks simple, people who write tests often fail to observe it.

In our particular case, it is very easy to imagine that we are testing the player’s movement code without actually testing it. Here is one example: you can perform an analysis of the volume of collisions and surfaces along which you can move in the game, look for small surfaces, gaps, etc. By eliminating all these problems, you can say that the player is now able to safely move and walk around the world.

But in fact, we tested the data, not the code. It is very likely that there will be bugs in the movement code that lead to bad behavior even with quality data.

To avoid such a trap, I wanted the testing system to be as close as possible to the behavior of the person actually controlling the movement of the character in the game. I began by writing two procedures that would become the building blocks of such testing.

The first procedure is closest to the real actions of a person. This is an update call that connects to The Witness input processing system and sends synthesized keyboard and mouse events to it. It is capable of simple things that a person can do: look around, go towards a point, look at a point, and so on. The procedure performs these actions with a simple emulation of user interaction with the keyboard and mouse, so I was sure that when processing input from The Witness, everything would be done exactly the same way as during testing. In the following articles I will discuss in more detail about this system and its use.

The second procedure is one step that is not used at this level. This is a function called DriveTowardPoint , which receives two points of the world and, causing an already existing system of player collisions, tries to seamlessly move from one point to another. By returning, she transmits information about the attempt: what obstacles did she encounter on the way and whether she managed to reach the end point.

This function is not as reliable as the method of testing with synthesized input, because it eliminates from testing a part of the player’s movement system. For example, any erroneous condition related to the player’s location in case of problems with the collision system will not affect testing with this feature. Nevertheless, I considered this level of testing valuable, because it can test vast areas much faster, because it does not require the execution of the entire game cycle, that is, it can be used more often and throughout the world, and not just in individual test runs .

It is also worth noting that the physical input data is not transferred to this function; for example, no speeds are indicated for the starting point. This is done because The Witness is not an action game, so the player has few significant physical properties. Players can not jump, run on the walls, include "bullet time". You can support such behaviors with the help of systems that I will describe later, but they add levels of complexity that were not required in our project.

Anyway, after implementing DriveTowardPoint, I could begin to solve the first task of the system: determining where the player can move on The Witness Island.

Rapidly Exploring Random Trees

Where can players move? It seems that this is a simple question, but you will be surprised to know how many games were released when the development team did not know the real answer. If this is possible, then I wanted The Witness to be one of those few games in which the developers knew exactly where the player could and could not get to before the release - no surprises.

This makes problem statement (but probably not its solution) very simple: with the DriveTowardPoint function, which reliably determines whether a player can move in a straight line between two points, create a coverage map that shows where the player can be.

For some reason, I, without having written a single line of code, for some reason thought that it would be best to use Rapidly Exploring Random Tree . For those who are unfamiliar with this algorithm, I will explain: this is a very simple process in which we record all the points we visited with reference to the point from which we came. To add a point to the tree, we take a random target point anywhere in the world, select the point closest to it, which is already in the tree, and try to get from this point to the target. The place where we ended up becoming the next sampling point.

Usually, this algorithm is used to search for paths: alternately for random points, we always select the same point as the target. This inclines the exploration of space towards the target point, and this is what is required when our only task is to reach the goal. But in this case, I wanted to create a complete map of the places that a player can fall into, so I use only random samples.

After the implementation of this algorithm (fortunately, it is very simple and didn’t take much time), I saw that it did quite a good job of exploring the space (the white paths show the paths studied, and the vertical red lines indicate the places where the algorithm collided with an obstacle) :


However, after observing his behavior, I realized that in fact I didn’t need such an algorithm. For example, even after many iterations, he is barely able to explore similar to the rooms shown below, despite the dense coverage of the areas outside of them. This is because it is simply not able to select fairly random points inside the rooms:


If I thought about this before starting work, I would understand that the advantage of algorithms like the Rapidly Exploring Random Tree is that they efficiently explore high-dimensional spaces. In fact, this is usually the main reason for using them. But there are no high spaces in The Witness . We have a two-dimensional space (yes, distributed over a complex manifold, but this is still a two-dimensional space).

In this low-dimensional space, the advantages of the Rapidly Exploring Random Tree manifest weakly, and its disadvantage is crucial for my task: the algorithm is designed for finding the most efficient paths to connected pairs of points in space, and not for effectively finding all the achievable points of this space. If you have such a task, then in fact Rapidly Exploring Random Tree will take a huge amount of time to solve it.

Therefore, I quickly realized that I need to look for an algorithm that effectively completely covers low-dimensional spaces.

3D Flood Filling

When I really thought about choosing an algorithm, it became obvious that in fact I needed something like the good old two-dimensional fill that is used to populate areas of a bitmap. For any starting point, I just had to fill in the entire space, exhaustively checking every possible path. Unfortunately, for many reasons, the decision for The Witness will be much more difficult than for a two-dimensional bitmap.

Firstly, we do not have a clear concept of a finite connectivity of a point. All space is continuous. This is for a pixel, we can easily list 4 possible places that can be reached from a given point, and check each of them in turn.

Secondly, there is no fixed size position in space, like a pixel on a bitmap. The surfaces on which the player moves, and obstacles can be anywhere, they do not have a maximum or minimum topological size, as there is no binding to any external grid.

Thirdly, although movement through the space of The Witness can be locally considered as moving along a plane, space itself is in fact a deeply interconnected and changing variety, in which the areas passed for the player are directly above other areas (sometimes there are several levels located one above the other) . In addition, there are connections that vary depending on the states of the world (open / closed doors, ascending / descending elevators, etc.).

Taking into account the described difficulties, it is very easy to come up with your own implementation variant for the fill, which as a result will turn out to be filled with intersecting areas, missing important routes, erroneous information about connections in difficult places of diversity. In the end, the algorithm will be too cumbersome to use, because to take into account changes in the state of the world, it must be restarted.

Immediately I did not think of any good solution, so I decided to start with simple experiments. Using the Rapidly Exploring Random Tree code I wrote, I changed the choice of target points from random to very controlled. Each time I added a new point to the tree, I indicated that the points are at a unit distance along the main directions from the point that will be considered the future target point, as is the case in simple two-dimensional filling.

But of course, if you are not careful, it will create a useless sampling cycle. The point will branch into the neighboring 8 points around it, but these 8 points will then try again to return to the starting point, and this will continue forever. Therefore, in addition to the controlled selection of target points, I need a simple constraint: any target point that is not within a certain minimum useful distance from an existing target point will not be taken into account. To my surprise, these two simple rules create a fairly successful fill:


Not bad for a fairly simple experiment. But the algorithm suffers from what I call the “boundary echo”. This effect can be seen in the following screenshot taken during the map exploration process:


In areas without obstacles, the algorithm works well, performing samples at relatively equal distances. But when they hit the intersection border, they create points that are “outside the grid”, that is, not aligned in accordance with the sampling pattern, according to which the algorithm fills the adjacent open area. The reason why the points “in the grid” do not create excessively dense tessellation is that each new point trying to return to one of the previous ones finds the previous point there and refuses to recalculate it again. But when creating new points on the border, they are not aligned at all, so nothing can prevent them from returning to the already explored space. This leads to the creation of a wave of displaced samples, which continues until it reaches a random line of points somewhere else, which will be close enough for the algorithm to find it coinciding with the moving front of points.

Although this does not seem to be a serious problem, in fact it is critical. The whole point of such algorithms is to concentrate the samples in areas where they are most likely to produce productive results. The more time we spend on sampling and resampling vast open areas, the less time we spend on marking the very edges of this area, which are the information we need. Since we are dealing with continuous space, and its true form can only be described by an infinite number of samples, the ratio of significant to insignificant samples is literally a measure of the efficiency of the algorithm in creating the surface passed for the player.

However, there is a simple solution to this particular problem: you need to expand the distance at which the two points are considered “close enough.” By doing this, we will reduce the sampling density in places that are not important to us, but will also lose sampling density in places that are important to us, for example, the areas around the borders, which we want to carefully check for the presence of “holes”.

Localized directional sampling

Probably because I started with the Rapidly Exploring Random Tree, my brain ousted all other ideas except the idea of ​​proximity. All previous algorithms for completing their task used proximity, for example, in order to determine a new point that needs to be considered next, or to choose a point from which to start in order to get to a new target point.

But after reflecting on the task for a while, I came to the realization that everything becomes more logical if we think not only about proximity, but also about directionality . Then it becomes obvious, but if you worked on similar tasks, you know that it is easy to fall into the trap of narrowly focused thinking and not see the big picture, even if it turns out to be simpler. That is exactly what happened to me.

When I changed my view of things, the right approach to sampling seemed obvious. Every time I wanted to expand the study of space from a point, I made a request for the existence of the nearest points in the local environment. However, instead of using the distance to these points for research, I will classify them according to their directions (before that, I used only eight main directions, but I wanted to experiment with other cores).

In any direction in which I do not “see” a point, I travel a given distance and add a point at any place where I stopped (regardless of whether I ran into something or not). If I see a point in one of the directions, then I move there and check if I can get there. If I can, then I simply add a visible edge so that the user can easily see that the points are connected. If I can not, then I add a new point at the point of collision, defining the boundary of the obstacle.

This sampling method worked just fine. It allows us to control sampling very precisely with the help of convenient adjustable parameters, to save all the necessary points and to avoid unnecessary tessellation, which leads to a very fast fill of space:


Since the algorithm performs a search along directions, rather than simply using proximity, it is protected from boundary echo and limits over-sampling only to the boundaries we need:


Moreover, the algorithm is completely unaffected by state transitions or problems with complex manifolds. It deals only with points, and these points can be anywhere, and new ones can be added at any time. If you have already mapped an area with the door closed, then after opening the door, you simply place a single point of investigation on the other side of the door and order the algorithm to continue expanding this map, after which it will correctly connect and properly examine the entire area behind the door.

You can also change the basic parameters at any time, and the system will continue to work. Want to sample the area with higher density? Just lower the default distance value. This can be done already in the process of building a map, and the algorithm will begin sampling with greater density without having to reset previous results (which may take some time).

Rudimentary rib check

By default, the algorithm carefully samples the boundaries, because the intersections create additional points that are not included in the sampling pattern, but it does not necessarily check them with the care I need, because it does not perform any special actions when encountering obstacles. I realized that since I knew which of the points were created during collisions, the two detected points of collisions are connected by an edge and we can call for additional sampling in order to try to find more boundary points in the neighborhood.

I didn’t actively investigate this approach, but I created a rudimentary method for testing this theory, and it seemed promising to me. Taking any two points of collision connected by an edge, I move to the midpoint of the edge and try to conduct the outward-facing perpendicular to the edge. If it does not intersect with the border at a very short distance, then I assume that the border is more complicated, and add a new target point to continue the search in this area.

Even this simple scheme creates very high-quality dense sampling along the border without undue sampling of neighboring open areas. Here is an area with several borders, but without edge checking:


But the same area with the verification of the edges:


No matter how satisfied I am with this result, I was surprised at the lack of significantly better algorithms for sampling the boundary, and I will try to select a few more methods in the future.

Quick wins

Even by investing just a little time in the development and creating a fairly simple code, I achieved that Walk Monster was already creating quite useful output data that could detect real problems in the game. Here are examples of problems that I found during the development of the algorithm:


The slopes on the sides of this platform should not be passable, but the player can walk on them. This happened because the pathology of the player’s movement has a pathological poor way to handle oblique geometry. Now I know that he is there, and I will correct him when it comes to ensuring his reliability.


The Witness was supposed to be a contemplative game, but wondering why it seems that there is a stone, although it does not exist, was not one of its koans. As you can guess, this problem arose because someone left in the game the amount of collision after removing the geometry that indicates it. This can easily happen, and it’s very good that we have a tool that can quickly recognize such mistakes so that people don’t have to do it.



These objects were supposed to become impassable rocks, but Walk Monster discovered that this did not happen. Worse, Walk Monster found that for some reason we only walk the path in one direction (in the screenshot, from left to right), but this should not happen. I made sure that the player can really do it (I managed). It is very interesting to observe the occurrence of such errors!

Open questions

When you see good results that can be developed further, it is inspiring. As I said, if you select the appropriate name for the source files, then everything will go like clockwork! But all this work was done in just a few days, so it is far from exhaustive, and a lot has been done completely improvised. If I have enough time to further develop these systems, then it is worth answering a few questions.

First, what kind of post-processing needs to be done with the data to make it easier to visualize? It will be difficult for people to understand the raw network of points and edges, but if we improve the description of the data, then this may make it difficult at first glance to assess the complex traversed areas.

Secondly, how can sampling patterns be improved around borders to ensure that the maximum number of “holes” is found? Are there any good ways to characterize the information of the figures in the lattice, and are there any qualitative tessellation schemes that maximize the probability of crossing and passing through these figures?

Third, which sampling patterns are better for filling spaces — regular or randomized? I can easily change the criteria for selecting target points to create more randomized patterns, but it’s not very clear if you should do this, and if so, which types of randomized patterns will be better.

Fourth, what other information we want to get from the maps of passable areas, if we have already learned how to build them? For example, it is very easy to expand an existing system with functions such as searching for paths or distance maps so that the user can select a point and request the shortest path between it and some other point, or see the heat map of the distance between the point and other points of the map. Would such queries be helpful? What other queries can I use?

At the moment, visualizations of passable areas obtained with the help of Walk Monster are more than enough to show that the player’s movement code is rather bad. I planned to go over to creating a system for nightly testing cards using the method of simulating user input, but it is obvious that we already have enough problems without this step to solve. Therefore, the next step is to increase the reliability of the player’s movement code. , , - , Walk Monster .