Experience in developing an Unity asset for finding a path in 3D space
Welcome to the Graceful Algorithms Team!
As an experiment, we made a decision to keep “diaries” of developers, in which we will share our experience and highlight some interesting results of our experiments. This is our debut article on the project “Pathfinder 3D” - an asset for the Unity game engine, which allows you to search for a path in three-dimensional space. In it, we will talk about the path from the inception of the idea to the full-fledged product and about some of the problems we encountered. This material will be useful for people who want to start their project and support it in the future, as well as for those who want to realize the search for a path in space.
The team of two people began work on the asset. The first one had some groundwork to speed up the process of finding the shortest path on complex graphs sufficiently for real-time work and the desire to find practical application for them, the second one had some experience with Unity and was looking for an idea for a startup. Since they often communicated with each other, it is not surprising that at a certain point an idea arose about the possibility of creating an asset for finding a path in three-dimensional space.
When studying the Unity asset directory, a number of solutions were found for finding a path in two-dimensional space, but none in three-dimensional. It became obvious that this is a great opportunity to enter the market for software add-ins for Unity, especially given the visibility and spectacularity of the expected result.
')
The goal was to implement directly search for a path in three-dimensional space and the typical capabilities of existing solutions for finding a path in a two-dimensional space. We started to work: one developed directly the path finding mechanism, the second classes and methods for managing the path finding process, configuration interfaces, test scenes, documentation, the project website, and also registered and configured service accounts for selling assets.
Shortly after the start of work, it became clear that a common resource is needed for the team to keep notes: a list of tasks and problems that need to be solved, information about the decisions made, interesting ideas in the future, and research results. After analyzing the existing solutions, we stopped at the Trello , because of its functionality, simplicity, convenience and pleasant appearance. As practice has shown, this service is very convenient for small teams. If the team has more than 5 people, we would advise using a full-fledged project management system.
Next, we describe the decisions taken during the development of the first version of the asset, and the logic that we followed when making them. People who have experience with Unity and are familiar with path finding algorithms will immediately understand where problems will arise in the future. In these places, we took advantage of a simple solution in favor of reducing the development time before getting the first working version of an asset, so as not to get bogged down, because the enthusiasm is a limited and inconstant piece. Thus, we coped with one of the most common reasons for the closure of such startups, because of which many projects die without being born. All problem areas were corrected after the publication of the asset.
For the search of the path, the algorithm A * (A star) was chosen because of its high speed in large open spaces. Most path finding algorithms work on graphs represented by a discrete matrix. It would be possible to build this matrix in advance, but the one-time process of its construction along three-dimensional space with obstacles looked at that moment as a rather difficult task. In addition, it was not clear how this could be done without sacrificing performance, since at the time we started working on the asset, there was no experience with background processes and multithreading in Unity. The graph was formed in real time by probing the space with physical rays (Physics.BoxCast) in the search direction. The found trajectories were reduced to broken lines, with a smaller number of intermediate points, and then smoothed by splines.
The main difficulty was the impossibility of asynchronous use of the physical methods of the engine, since they can work exclusively in the main thread. On not too complicated scenes, the use of the search function at the same time by no more than twenty agents did not strongly influence the frame rate. To get rid of the rare strong FPS drawdowns, the computational load was separated in time using corutines. This slowed down the search, but only slightly.
Before submitting an asset for moderation, you need to put the code in order and compile detailed documentation, in accordance with the requirements , register and set up support mail. It is also desirable to create a project site where development news and demo examples will be conveniently displayed. This will be a big plus as with the passage of moderation, and when examining your asset by the user before purchase. Hosting and postal services were ordered by us from BeGet , as it offered the most advantageous offers at that time, and cost us 1000r / year.
The asset moderation lasted 22 days and passed the first time, since we very carefully approached the documentation and design of the asset page in the Unity store. After the publication, the asset immediately hit the top places in the Scripting / AI category. From this point on, letters began to come to the support mail asking for help in solving various problems. Sometimes several per day, sometimes none per month. If we average, then in a month 2 people turned to questions, the correspondence with which took a total of 2-3 hours. Not so much, but keep in mind that regardless of your current workload, you need to respond very promptly, so that angry users do not write bad reviews about the product, but, on the contrary, enthusiastic with quality support, left positive. Also, quite a lot of questions come to the mail like “will your asset work if ...”. Such letters should not be ignored either, because this is a potential buyer who can leave.
As we received complaints from the first customers, it became clear that many users use an asset on complex scenes that have a maze or other connected cavity configuration. In such projects, the path finding scheme we used, based on collision checking, and even in the main stream, was not effective enough. Therefore, we started to implement the early construction of the graph in order to make it possible to search for a path in the sidestream without using physics and referring to objects in the scene.
Discretization of three-dimensional space breaks it into cubes. Storing information about all cubes of the partition is redundant and is very expensive in memory. Therefore, it is logical to store only the coordinates of impassable cells, which was done.
Game obstacles are polygonal shapes and consist of triangles. To take into account the obstacles in the search graph, it is necessary to find all the cubes of the partition intersecting a triangle of any obstacle. Already at this stage, the possibility of dynamically removing and adding obstacles on the stage was laid, and not only the coordinates of the occupied cubes were saved, but also the identifiers of the obstacles that were in them. Now it became possible to build a navigation graph before the start of the game process and, by eliminating a large number of complex calculations during the search for a path, more than two hundred agents could perform it simultaneously without sacrificing performance.
Another problem known to us also manifested itself: the A * algorithm and its modifications work extremely poorly in closed spaces on high-power graphs. Since their algorithm gives preference to the direction of the route in the direction of approaching the target point, any impasse leading to the target slowed down the search for a path, because, before choosing another direction of “germination,” the algorithm first “fills” all the space inside the impasse.
In such situations, the wave search algorithm (Lie algorithm) shows itself to be very effective due to the smaller number of operations required to “fill” the space. Therefore, it was added to the asset as an alternative. When testing on a stage that is a labyrinth, the time to search for a path has been reduced by more than 30 times.
To speed up the pre-processing of the scene and search for the path into the asset, the possibility of parallel execution of processes was added, but the efficiency of parallelism was extremely low, because when working with a container that stores the coordinates of occupied cells, it is necessary to synchronize the flows, which was performed using mutexes, since competitive collections and many other means to ensure effective synchronization were implemented only in the .NET Framework 4.5 standard, and the .NE version was used in Unity until the 2018 release T Framework 3.5. We tried to solve this problem with the help of available means, but they had a very mediocre speed, and we got the desired result only after switching to the 2018 release of Unity. The use of competitive collections also opened up the possibility of implementing dynamic change of obstacles on the stage.
At a certain stage, a team began to disagree about the distribution of profits, and a third person joined the team, who introduced a system for evaluating the time investments of each team member, and also began to do code inspection and testing, which markedly improved the quality of the product.
The time evaluation system is currently implemented in the form of an Excel spreadsheet and is an automated system, in which once a month you need to enter information about sales and tasks completed over the past month. Team members need to estimate how much time they would need to complete a task. Thus, when evaluating the time complexity of tasks, the speed of each participant is taken into account. Anomalous overestimation or underestimation by any of the participants immediately becomes apparent from the accumulated statistics of his previous assessments. And, in the absence of a satisfactory explanation, this issue is resolved by the whole team. This approach showed itself well in six months of use and allowed us to collect interesting statistics. We did not find a ready-made free solution that would provide the described opportunities. Therefore, at the moment for small teams, the implementation in the form of Excel tables seems to be optimal. For relatively large teams, you will most likely have to design your database, develop the server part and the client, or implement an extension for one of the existing project management systems.
Let's sum up. Since the start of development to the first version with the minimum necessary functionality and sufficient performance for use in real projects, a year has passed. Another half a year was spent on improving the speed and implementation of multi-threaded asset work. At the moment, the time spent on this project was estimated by us at 1065 man-hours (this is quite an optimistic estimate), and the average monthly profit is 9.5 tr. It is easy to calculate that the average cost of an hour of work at the moment is about 160 rubles, which is not so much. However, the main thing in this event is the experience gained by each participant. Including teamwork experience and software product support experience. The project can be considered successful.
Now our team has started implementation of additional useful functionality: algorithmic accessibility check; the ability to assign game objects portals; support for dynamic obstacles; local navigation between agents, for collision avoidance and local route planning.
We hope this material will help someone to bring their project to the finish line.
As an experiment, we made a decision to keep “diaries” of developers, in which we will share our experience and highlight some interesting results of our experiments. This is our debut article on the project “Pathfinder 3D” - an asset for the Unity game engine, which allows you to search for a path in three-dimensional space. In it, we will talk about the path from the inception of the idea to the full-fledged product and about some of the problems we encountered. This material will be useful for people who want to start their project and support it in the future, as well as for those who want to realize the search for a path in space.
The team of two people began work on the asset. The first one had some groundwork to speed up the process of finding the shortest path on complex graphs sufficiently for real-time work and the desire to find practical application for them, the second one had some experience with Unity and was looking for an idea for a startup. Since they often communicated with each other, it is not surprising that at a certain point an idea arose about the possibility of creating an asset for finding a path in three-dimensional space.
When studying the Unity asset directory, a number of solutions were found for finding a path in two-dimensional space, but none in three-dimensional. It became obvious that this is a great opportunity to enter the market for software add-ins for Unity, especially given the visibility and spectacularity of the expected result.
')
The goal was to implement directly search for a path in three-dimensional space and the typical capabilities of existing solutions for finding a path in a two-dimensional space. We started to work: one developed directly the path finding mechanism, the second classes and methods for managing the path finding process, configuration interfaces, test scenes, documentation, the project website, and also registered and configured service accounts for selling assets.
Shortly after the start of work, it became clear that a common resource is needed for the team to keep notes: a list of tasks and problems that need to be solved, information about the decisions made, interesting ideas in the future, and research results. After analyzing the existing solutions, we stopped at the Trello , because of its functionality, simplicity, convenience and pleasant appearance. As practice has shown, this service is very convenient for small teams. If the team has more than 5 people, we would advise using a full-fledged project management system.
Next, we describe the decisions taken during the development of the first version of the asset, and the logic that we followed when making them. People who have experience with Unity and are familiar with path finding algorithms will immediately understand where problems will arise in the future. In these places, we took advantage of a simple solution in favor of reducing the development time before getting the first working version of an asset, so as not to get bogged down, because the enthusiasm is a limited and inconstant piece. Thus, we coped with one of the most common reasons for the closure of such startups, because of which many projects die without being born. All problem areas were corrected after the publication of the asset.
For the search of the path, the algorithm A * (A star) was chosen because of its high speed in large open spaces. Most path finding algorithms work on graphs represented by a discrete matrix. It would be possible to build this matrix in advance, but the one-time process of its construction along three-dimensional space with obstacles looked at that moment as a rather difficult task. In addition, it was not clear how this could be done without sacrificing performance, since at the time we started working on the asset, there was no experience with background processes and multithreading in Unity. The graph was formed in real time by probing the space with physical rays (Physics.BoxCast) in the search direction. The found trajectories were reduced to broken lines, with a smaller number of intermediate points, and then smoothed by splines.
The main difficulty was the impossibility of asynchronous use of the physical methods of the engine, since they can work exclusively in the main thread. On not too complicated scenes, the use of the search function at the same time by no more than twenty agents did not strongly influence the frame rate. To get rid of the rare strong FPS drawdowns, the computational load was separated in time using corutines. This slowed down the search, but only slightly.
Before submitting an asset for moderation, you need to put the code in order and compile detailed documentation, in accordance with the requirements , register and set up support mail. It is also desirable to create a project site where development news and demo examples will be conveniently displayed. This will be a big plus as with the passage of moderation, and when examining your asset by the user before purchase. Hosting and postal services were ordered by us from BeGet , as it offered the most advantageous offers at that time, and cost us 1000r / year.
The asset moderation lasted 22 days and passed the first time, since we very carefully approached the documentation and design of the asset page in the Unity store. After the publication, the asset immediately hit the top places in the Scripting / AI category. From this point on, letters began to come to the support mail asking for help in solving various problems. Sometimes several per day, sometimes none per month. If we average, then in a month 2 people turned to questions, the correspondence with which took a total of 2-3 hours. Not so much, but keep in mind that regardless of your current workload, you need to respond very promptly, so that angry users do not write bad reviews about the product, but, on the contrary, enthusiastic with quality support, left positive. Also, quite a lot of questions come to the mail like “will your asset work if ...”. Such letters should not be ignored either, because this is a potential buyer who can leave.
As we received complaints from the first customers, it became clear that many users use an asset on complex scenes that have a maze or other connected cavity configuration. In such projects, the path finding scheme we used, based on collision checking, and even in the main stream, was not effective enough. Therefore, we started to implement the early construction of the graph in order to make it possible to search for a path in the sidestream without using physics and referring to objects in the scene.
Discretization of three-dimensional space breaks it into cubes. Storing information about all cubes of the partition is redundant and is very expensive in memory. Therefore, it is logical to store only the coordinates of impassable cells, which was done.
Game obstacles are polygonal shapes and consist of triangles. To take into account the obstacles in the search graph, it is necessary to find all the cubes of the partition intersecting a triangle of any obstacle. Already at this stage, the possibility of dynamically removing and adding obstacles on the stage was laid, and not only the coordinates of the occupied cubes were saved, but also the identifiers of the obstacles that were in them. Now it became possible to build a navigation graph before the start of the game process and, by eliminating a large number of complex calculations during the search for a path, more than two hundred agents could perform it simultaneously without sacrificing performance.
Another problem known to us also manifested itself: the A * algorithm and its modifications work extremely poorly in closed spaces on high-power graphs. Since their algorithm gives preference to the direction of the route in the direction of approaching the target point, any impasse leading to the target slowed down the search for a path, because, before choosing another direction of “germination,” the algorithm first “fills” all the space inside the impasse.
In such situations, the wave search algorithm (Lie algorithm) shows itself to be very effective due to the smaller number of operations required to “fill” the space. Therefore, it was added to the asset as an alternative. When testing on a stage that is a labyrinth, the time to search for a path has been reduced by more than 30 times.
To speed up the pre-processing of the scene and search for the path into the asset, the possibility of parallel execution of processes was added, but the efficiency of parallelism was extremely low, because when working with a container that stores the coordinates of occupied cells, it is necessary to synchronize the flows, which was performed using mutexes, since competitive collections and many other means to ensure effective synchronization were implemented only in the .NET Framework 4.5 standard, and the .NE version was used in Unity until the 2018 release T Framework 3.5. We tried to solve this problem with the help of available means, but they had a very mediocre speed, and we got the desired result only after switching to the 2018 release of Unity. The use of competitive collections also opened up the possibility of implementing dynamic change of obstacles on the stage.
At a certain stage, a team began to disagree about the distribution of profits, and a third person joined the team, who introduced a system for evaluating the time investments of each team member, and also began to do code inspection and testing, which markedly improved the quality of the product.
The time evaluation system is currently implemented in the form of an Excel spreadsheet and is an automated system, in which once a month you need to enter information about sales and tasks completed over the past month. Team members need to estimate how much time they would need to complete a task. Thus, when evaluating the time complexity of tasks, the speed of each participant is taken into account. Anomalous overestimation or underestimation by any of the participants immediately becomes apparent from the accumulated statistics of his previous assessments. And, in the absence of a satisfactory explanation, this issue is resolved by the whole team. This approach showed itself well in six months of use and allowed us to collect interesting statistics. We did not find a ready-made free solution that would provide the described opportunities. Therefore, at the moment for small teams, the implementation in the form of Excel tables seems to be optimal. For relatively large teams, you will most likely have to design your database, develop the server part and the client, or implement an extension for one of the existing project management systems.
Let's sum up. Since the start of development to the first version with the minimum necessary functionality and sufficient performance for use in real projects, a year has passed. Another half a year was spent on improving the speed and implementation of multi-threaded asset work. At the moment, the time spent on this project was estimated by us at 1065 man-hours (this is quite an optimistic estimate), and the average monthly profit is 9.5 tr. It is easy to calculate that the average cost of an hour of work at the moment is about 160 rubles, which is not so much. However, the main thing in this event is the experience gained by each participant. Including teamwork experience and software product support experience. The project can be considered successful.
Now our team has started implementation of additional useful functionality: algorithmic accessibility check; the ability to assign game objects portals; support for dynamic obstacles; local navigation between agents, for collision avoidance and local route planning.
We hope this material will help someone to bring their project to the finish line.
Source: https://habr.com/ru/post/450854/
All Articles