background
Recently, I was implementing a 3D sandbox game. The basic function is to build buildings in a 3D plane. Buildings can be added or edited in the scene.
When realizing the character’s walking function, we naturally thought of taking the coordinates of the end point and the starting point, and then connecting them into a straight line to walk. This idea is really good when there are no buildings, but once the buildings appear in the map, we will find: The character is wearing a model!
At this point, the search for obstacle avoidance scheme journey began.
Use the obstacle avoidance feature that comes with babiel.js
Since our project was developed using the babibin. js framework, our first idea was to use the built-in obstacle avoidance function of babibin. js in line with the principle of “if we can’t write by ourselves, we must not write by ourselves”.
introduce
A brief introduction to the obstacleavoidance feature in Babyl.js, which is an extension of the framework and needs to be used in conjunction with RecastJS dependencies.
RecastJS is used to generate Navigation Mesh. Then the Crowd Agents module in RecastJS is used for automatic path finding and obstacle avoidance.
A Navigation Mesh, also known as a walking surface, is a polygonal Mesh data structure used to navigate through a complex space and to mark where it is walkable.
A navigation grid is made up of many convex polygons. In plain English, the map is cut into N parts, each of which is a convex polygon. We call each polygon a Poly.
Then, when the character walks in the navigation grid, it will judge whether the starting point and ending point are in the same Poly. If so, it will directly connect the starting point and ending point into a straight line, which is the walking route of the character. Otherwise, it is necessary to use the corresponding pathfinding algorithm to calculate the path, calculate which Poly the character needs to pass, and then use these Poly to calculate the specific path.
application
I was overjoyed when I realized that Babylu.js had such a function, so I clicked on the keyboard, refreshed the page, added a new building, clicked on the map, and expected the character model to automatically bypass the building.
What happened?
My experience tells me that the navigation grid is not generated properly, but luckily RecastJS provides a variety of parameters that allow me to tweak the navigation grid generation rules.
So, after almost a full day of tweaking the parameters, it turned out that I was naive and nothing had changed at all. Only when the volume of the added obstacle is very small, the character’s obstacle avoidance function can be successfully effective. When the volume of the obstacle is a little bigger, the character will walk straight through the building to reach the end.
I thought: ok, since the callback doesn’t work, I’ll look at the source code for RecastJS and see how it generates the navigation grid and what’s causing it to generate the wrong navigation grid.
So I switched to Github. I was surprised to find that RecastJS was originally a library developed by C language. Later, I don’t know who converted it into a Javascript version and sent it to NPM. That is to say, we can’t see the Javascript version of Recast source code.
Well, using babyl.js to avoid obstacles is a dead end.
Build your own navigation grid and search algorithm
Since the built-in functionality didn’t work, and there wasn’t a better solution in the babyl.js community ecosystem, it was up to you to build a navigation grid and search algorithm for your current scene.
Let’s take a look at the overall thinking and process:
- Capture map data to generate an appropriate navigation grid
- Gets the start and end of the character’s walk
- Search algorithm is used to find the shortest path from the starting point to the end point in the navigation grid
- The operator follows the shortest path
Choose the appropriate search algorithm
Let’s talk about the search algorithm, speaking of the search algorithm for the path, the first people think of should be the well-known breadth-first search algorithm.
Breadth-first search
Breadth-first search algorithm is a very common path finding algorithm, which is widely used in various computer scenes, such as Windows sketchpad doodle function, which is realized by breadth-first algorithm.
We can simply divide the entire map into N 1X1 squares. The basic principle of the breadth-first algorithm is very simple: starting from the starting grid, we can move up, down, left, and right each time. The green marker in the figure below is the starting point and the red marker is the ending point.
At the end of each round of exploration, the squares explored in that round are marked as Frontier, which is the green square shown in the image below.
The algorithm then starts with the boundary squares and continues to explore one by one until it finds the end squares.
In each exploration, we need to keep track of the path direction, that is, form a structure like a linked list. After reaching the end point, we can find the corresponding shortest path according to this path record.
In addition, the path lattice explored in each round should be marked before the next round of exploration to let the algorithm know that this lattice has been traversed. If a marked lattice is encountered in the subsequent exploration process, it will be directly skipped and not included in the subsequent exploration rounds. The gray grids in the image below are the ones marked no longer to be explored.
The breadth-first algorithm is simple to implement and can be used in a wide range of scenarios, but it also has the obvious drawback that it is stupid and, at worst, requires traversing the entire map to find the target point, so it is easy to cause performance problems due to too many moves.
A – Star algorithm
In order to solve the breadth-first algorithm performance problems, so we introduced A – Star of heuristic search algorithm, and breadth-first algorithm is different, we are in each round of search, not to explore all of the boundary squares, but will choose the direction of the current price (cost) the lowest exploration, so it has certain direction, The direction it goes depends on the location of the lowest-cost square in the current bounding square.
The cost is divided into two parts, one is the cost of the current journey, or the current cost (F-cost), which represents the number of paths you have traveled so far. For example, if you need to take three steps to reach the current cell, the current cost is 3.
The other part of the cost is the estimated cost (G-cost), which represents the approximate number of steps from the current square to the end square. Since it is called the estimated cost, it is not an exact value, but is mainly used to guide the algorithm to preferentially search the more promising path.
Here are two commonly used estimated costs:
- SQRT ((x1 – x2)^2 + (y1-y2)^2) SQRT ((x1 – x2)^2 + (y1-y2)^2)
- Manhattan Distance (Manhattan short) : refers to the current grid and end Distance of two points in the vertical direction and horizontal direction, is expressed in a mathematical formula to | x1 – x2 + | | y1, y2 |, Manhattan Distance calculation does not need to prescribe, quick speed, high performance
When we know the current and estimated cost of a bounding square, we can get its total cost by adding the two values, i.e. :
Total cost = current cost + estimated cost
In each round of pathfinding, we find the square with the lowest total cost in the current boundary to explore, and record its direction and mark itself similar to the breadth-first algorithm. Until the end of the exploration, we can obtain the corresponding shortest path through the A-Star algorithm.
Compared with the breadth-first algorithm, the A-Star algorithm has A certain directionality, so it generally has fewer useless explorations than the breadth-first algorithm, and the number of map cells traversed is much less. Therefore, the overall performance of the A-Star algorithm is generally better than the breadth-first algorithm.
Now that we have a suitable search algorithm, the next step is to see how to generate our navigation map.
Build your own navigation grid
Before we talk about how to build our own navigation grid, we need to understand the concept that models in 3D scenes are made up of one triangle after another, so we need to follow this principle when building navigation grids.
Principle of navigation grid generation in Recast
What steps are required to build a navigation grid in Recast? In short, there are six steps.
- Voxelization, or “Rasterization,” of scene models. In simple terms, the triangular data is converted into pixel information (also called voxel information), which can be understood as converting from one triangular surface to one lattice information.
- Filter out Walkable Suface, that is, calculate the data of Walkable Suface at the top of voxel through the voxel information obtained in the first step.
- Region generation. After obtaining the walking surface, we use some algorithms to cut the surface into as large as possible, continuous, non-repeating regions with no holes in the middle, and these regions become regions.
- Generate Simplified Contours. Calculate the edge information of each Region based on the Region information obtained in the previous step, and then simplify the edge contour through some simplification algorithms. We call this Simplified contour as Simplified Contours.
- To generate the Poly Mesh, we divide the simplified contour into multiple convex polygons. Each convex polygon can be called a Poly, which is the basic unit of the pathfinding algorithm.
- Detailed Mesh is generated. Finally, we triangulate each Poly and divide it into multiple triangles to generate the navigation Mesh required by our final search algorithm.
It is worth mentioning here that after generating Region in the third step of the scene model, the THREE-DIMENSIONAL scene has been simplified into a two-dimensional existence, which facilitates some subsequent calculations and operations. But at the same time, this step also caused the model to be unable to move completely perpendicular to the ground, only to remain perpendicular to the xOz coordinate plane.
Combined with the actual situation of the navigation grid generation
In our sandbox game, in fact, the map and the building are quite simple, the map can be simply seen as a 64*64 square plane, and the building can also be simplified into a simple cube.
Refer to the Recast grid navigation generation steps above, and the result is a non-overlapping grid data.
Since our sandbox map is not particularly large, our navigation grid generation is actually very simple, in a nutshell: The vertex data of 64*64 square plane is directly used as the original navigation grid data, and then the vertex data in contact with the square projection of the building on the ground is excluded. Finally, the mesh formed by the remaining vertex data is the navigation grid we need.
We’ll cover this in more detail later in this article, but here you have a basic idea.
Combination of A-Star search algorithm and navigation grid
Now that we have A basic understanding of how the A-Star search algorithm works and how the navigation grid is generated, it’s time to put them together.
First of all, when we talked about the A-Star search algorithm, we assumed that the map was composed of 1X1 square grids, but in reality, since objects in the 3D scene were all composed of triangles, our navigation grid was also composed of triangles. Therefore, some calculations in our A-Star algorithm also need to be adjusted accordingly.
When calculating the value of the total cost, we divide the total cost into the current cost and the estimated cost, as mentioned above. In the current cost, we still calculate the total cost according to the number of paths we have taken so far.
And estimate the cost to use euler distance calculation, the calculation will be from a square grid computing into triangle surface, the distance between the distance between the calculation, so we need to calculate the center of each triangular faces, the distance between the grid we will instead of using the distance between the center point to the value of the euler distance for the midpoint of the boundary triangle to the finish line midpoint of triangle surface distance.
Next we need to process the map vertex data. Filter out the vertices that intersect with the projection of the building. Then we need to find the central points of each triangle composed of the filtered vertex data, as well as the list of neighbouring triangles (Geographically) and their adjacency data (portals).
Finally, we pass in starting point and ending point data, a-Star algorithm will find the corresponding triangular surface data of this point according to the starting point and ending point data, and then start from the starting point triangle and find the path according to the corresponding generation value of its adjacent triangles until the end point triangle is found, and then return the path data.
Finally, we can achieve the corresponding obstacle avoidance effect by making the character move along the returned path data.
Optimization under practical application
But so far, we have basically achieved the sandbox game pathfinding algorithm, but we found that, in the process of testing by triangle nodes so much, after the path leading to excess characters appeared in the process of walking the inflection point, and some of the paths between triangle apparent can be represented by a straight line, But it actually goes through the midpoints of many triangles.
Therefore, we introduced the pull rope algorithm, through the pull rope algorithm to solve the problem of too many inflection points in the path, here is not more than the introduction of the pull rope algorithm, interested in the article can be understood by the funnel algorithm of the pull rope algorithm.
By adding the pull rope algorithm, the path of the character walking has also been optimized, and the final actual effect is basically consistent with the ideal effect.
Subsequent items to be optimized
Our current pathfinding algorithm is actually not the optimal solution in my mind. In the process of generating navigation grid, we abstracted the whole map into a grid form, resulting in too many nodes in the map, which would be very inefficient to traverse in the case of a large map.
Therefore, we need to simplify the grid map into Waypoints with fewer nodes to delete and merge some unnecessary points and surfaces in the navigation grid.
Plus, we can join inoctreeIn the three-dimensional space, the x, Y and Z axes are used to divide the space into 8 parts to optimize the search efficiency.
In view of the length of the article, here will not carry on too much expansion of these contents, I hope that readers hold a studious state of mind, after reading their own continue to carry out in-depth research.
Refer to the link
- Description of Navigation Mesh
- Pathfinding game 1: Navigation grid
- Shortest path search: A* pathfinding algorithm explained
- A* Pathfinding algorithm in detail #A star # heuristic search