Experience in developing a Unity asset for finding a path in 3D space
Welcome to the Graceful Algorithms Team!
As an experiment, we decided to keep “diaries” of developers in which we will share experience and highlight some interesting results of our experiments. This is our debut article on the "Pathfinder 3D" project - an asset for the Unity game engine, which allows you to search for paths in three-dimensional space. In it, we will talk about the path from the origin of the idea to a 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 implement a search for a path in space.
A team of two people started work on the asset. The first one had some developments allowing to speed up the process of finding the shortest path on complex graphs sufficiently to work in real time, and a desire to find practical application for them, the second had some experience working with Unity and was looking for an idea for a startup. Since they often communicated with each other, it is not surprising that at some point the idea arose of the possibility of creating an asset to search for a path in three-dimensional space.
When studying the Unity asset catalog, many solutions were found to find the path in two-dimensional space, but not one in three-dimensional. It became obvious that this was a great opportunity to enter the Unity software add-ons market, especially considering the visibility and entertainment of the expected result.
The goal was to implement directly the search for a path in three-dimensional space and the typical capabilities of existing solutions for finding a path in two-dimensional space. We started to work: one developed directly the path search mechanism, the second classes and methods for managing the path search process, configuration interfaces, test scenes, documentation, the project site, and also was involved in registering and setting up service accounts necessary for selling the asset.
Soon after the start of the work, it became clear that some kind of common resource was needed for the team to take notes: a list of tasks and problems that need to be solved, information about the decisions made, interesting ideas and research results in the future. Having analyzed the existing solutions, we settled on Trello, due to 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 recommend using a full-fledged project management system.
Next, we describe the decisions made 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 used a simple solution for the sake of reducing the development time until the first working version of the asset was received, so as not to get bogged down, because enthusiasm is limited and inconstant. Thus, we dealt with one of the most common reasons for closing such startups, because of which many projects die without being born. All problem areas were corrected after the publication of the asset.
To search for the path, the algorithm A * (A star) was chosendue to its high speed of operation in large open spaces. Most path search algorithms work on graphs represented by a discrete matrix. It would be possible to construct this matrix in advance, but the one-time process of its construction in three-dimensional space with obstacles looked at that time as a rather difficult task. In addition, it was not clear how to do this without sacrificing performance, since at the time of the beginning of work on the asset there was no experience with background processes and multithreading in Unity, as well as with multithreading in general. The graph was formed in real time by probing the space with physical rays (Physics.BoxCast) in the direction of the search. The found trajectories were reduced to broken ones with fewer intermediate points, and then smoothed by splines.
The main difficulty was the impossibility of using the engine’s physical methods asynchronously, since they can work exclusively in the main thread. On not too complex scenes, using the search function at the same time by no more than twenty agents did not significantly affect the frame rate. To get rid of rare strong drawdowns of FPS, the computational load was spaced in time using coroutines. This slowed down the search, but not significantly.
Before submitting an asset for moderation, you must bring the code in order and draw up detailed documentation, in accordance with the requirements, register and configure support mail. It is also advisable to create a project website where development news and demos will be conveniently displayed. This will be a big plus both during the passage of moderation, and when studying your asset by the user before buying. Hosting and mail services were ordered by us from BeGet , since at that time it offered the most advantageous offers, and cost us 1000r / year.
Asset moderation lasted 22 days and passed the first time, since we very carefully approached the documentation and the design of the asset page in the Unity store. After the publication, the asset immediately fell into first place in the Scripting / AI category. From that moment, letters began to come to the support mail asking for help in solving certain problems. Sometimes a few per day, sometimes not a month. If you average, then for a month 2 people asked questions, correspondence with which took a total of 2-3 hours. Not so much, but it should be borne in mind that regardless of your current workload, you need to respond very quickly so that angry users do not write bad reviews about the product, but, on the contrary, enthusiastic about quality support, leave positive ones. Also, quite a lot of questions come to the mail like “will your asset work if ...”. Such letters should also not be ignored, because this is a potential buyer who can leave.
As complaints from first buyers were received, it became clear that many users use assets on complex scenes that have the configuration of a labyrinth or other connected cavity. In such projects, our path-finding scheme, based on collision checking, and even in the main stream, was not effective enough. Therefore, we started implementing the early construction of the graph so that it would be possible to search for the path in the side stream without using physics and accessing scene objects.
Discretization of three-dimensional space breaks it into cubes. Storing information about all partition cubes is redundant and very memory intensive. Therefore, it is logical to store only the coordinates of impassable cells, which was done.
Game obstacles are polygonal figures and consist of triangles. To account for obstacles in the search graph, you must find all the cubes of the partition that intersect any triangle of any obstacle. Already at this stage, the possibility of dynamically removing and adding obstacles to 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 is possible to build a navigation graph before the start of the game process and, due to the elimination of a large number of complex calculations during the search for a path, more than two hundred agents could make it simultaneously without sacrificing performance.
Another problem known to us also made itself felt: the A * algorithm and its modifications work extremely poorly in confined spaces on high-power graphs. Since their algorithm prefers the direction of the route toward approaching the target point, any deadlock leading to the target greatly slowed down the search for the path, since before choosing a different direction of “germination”, the algorithm first “fills” the entire space inside the dead end.
In such situations, the wave search algorithm (Lee Algorithm) proves 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 maze, the search time for the path was reduced by more than 30 times.
To speed up the preliminary processing of the scene and find the path to the asset, the possibility of parallel execution of processes was added, but the parallelism efficiency was extremely low, due to the fact that 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 tools to ensure efficient synchronization were implementedonly in the .NET Framework 4.5 standard, and in Unity until the 2018 release version of the .NET Framework 3.5 was used. We tried to solve this problem using available tools, but they had very mediocre performance, and we only got the desired result after switching to the 2018 Unity release. The use of competitive collections also opened up the possibility of realizing the dynamic change of obstacles in the scene.
At a certain stage, disagreements began to arise in the team regarding the distribution of profits, and a third person joined the team, who introduced a system for assessing the time investment of each member of the team, and also began to engage in code inspection and testing, which significantly improved the quality of the product.
The system for estimating time costs at the moment is made in the form of an Excel table and is an automated system in which once a month it is necessary to enter information about sales and tasks completed over the past month. Team members need to evaluate how much time they would need to solve a particular problem. Thus, when assessing the time complexity of tasks, the speed of each participant is taken into account. An abnormal overestimation or understatement by one of the participants immediately becomes evident from the accumulated statistics of his previous assessments. And, in the absence of a satisfactory explanation, this issue is decided by the whole team. This approach proved to be good for six months of use and allowed to collect interesting statistics. A ready-made free solution that would provide the described features, we have not been found. Therefore, at the moment, for small teams, the implementation in the form of Excel tables seems to us optimal. For relatively large teams, you will most likely have to design your database, develop the server part and client, or implement an extension for one of the existing project management systems.
To summarize. A year has passed since the start of development to the first version with the minimum necessary functionality and sufficient performance for use in real projects. Another six months was spent on improving performance and implementing multi-threaded work of the asset. At the moment, we estimated the time costs for this project at 1065 man hours (this is a rather optimistic estimate), and the average profit for the month is 9.5t. 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 implementing additional useful functionality: algorithmic reachability verification; the ability to assign game objects to portals; dynamic obstacle support; Local navigation between agents to prevent collisions and plan local routes.
We hope this material helps someone bring their project to the finish line.
As an experiment, we decided to keep “diaries” of developers in which we will share experience and highlight some interesting results of our experiments. This is our debut article on the "Pathfinder 3D" project - an asset for the Unity game engine, which allows you to search for paths in three-dimensional space. In it, we will talk about the path from the origin of the idea to a 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 implement a search for a path in space.
A team of two people started work on the asset. The first one had some developments allowing to speed up the process of finding the shortest path on complex graphs sufficiently to work in real time, and a desire to find practical application for them, the second had some experience working with Unity and was looking for an idea for a startup. Since they often communicated with each other, it is not surprising that at some point the idea arose of the possibility of creating an asset to search for a path in three-dimensional space.
When studying the Unity asset catalog, many solutions were found to find the path in two-dimensional space, but not one in three-dimensional. It became obvious that this was a great opportunity to enter the Unity software add-ons market, especially considering the visibility and entertainment of the expected result.
The goal was to implement directly the search for a path in three-dimensional space and the typical capabilities of existing solutions for finding a path in two-dimensional space. We started to work: one developed directly the path search mechanism, the second classes and methods for managing the path search process, configuration interfaces, test scenes, documentation, the project site, and also was involved in registering and setting up service accounts necessary for selling the asset.
Soon after the start of the work, it became clear that some kind of common resource was needed for the team to take notes: a list of tasks and problems that need to be solved, information about the decisions made, interesting ideas and research results in the future. Having analyzed the existing solutions, we settled on Trello, due to 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 recommend using a full-fledged project management system.
Next, we describe the decisions made 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 used a simple solution for the sake of reducing the development time until the first working version of the asset was received, so as not to get bogged down, because enthusiasm is limited and inconstant. Thus, we dealt with one of the most common reasons for closing such startups, because of which many projects die without being born. All problem areas were corrected after the publication of the asset.
To search for the path, the algorithm A * (A star) was chosendue to its high speed of operation in large open spaces. Most path search algorithms work on graphs represented by a discrete matrix. It would be possible to construct this matrix in advance, but the one-time process of its construction in three-dimensional space with obstacles looked at that time as a rather difficult task. In addition, it was not clear how to do this without sacrificing performance, since at the time of the beginning of work on the asset there was no experience with background processes and multithreading in Unity, as well as with multithreading in general. The graph was formed in real time by probing the space with physical rays (Physics.BoxCast) in the direction of the search. The found trajectories were reduced to broken ones with fewer intermediate points, and then smoothed by splines.
The main difficulty was the impossibility of using the engine’s physical methods asynchronously, since they can work exclusively in the main thread. On not too complex scenes, using the search function at the same time by no more than twenty agents did not significantly affect the frame rate. To get rid of rare strong drawdowns of FPS, the computational load was spaced in time using coroutines. This slowed down the search, but not significantly.
Before submitting an asset for moderation, you must bring the code in order and draw up detailed documentation, in accordance with the requirements, register and configure support mail. It is also advisable to create a project website where development news and demos will be conveniently displayed. This will be a big plus both during the passage of moderation, and when studying your asset by the user before buying. Hosting and mail services were ordered by us from BeGet , since at that time it offered the most advantageous offers, and cost us 1000r / year.
Asset moderation lasted 22 days and passed the first time, since we very carefully approached the documentation and the design of the asset page in the Unity store. After the publication, the asset immediately fell into first place in the Scripting / AI category. From that moment, letters began to come to the support mail asking for help in solving certain problems. Sometimes a few per day, sometimes not a month. If you average, then for a month 2 people asked questions, correspondence with which took a total of 2-3 hours. Not so much, but it should be borne in mind that regardless of your current workload, you need to respond very quickly so that angry users do not write bad reviews about the product, but, on the contrary, enthusiastic about quality support, leave positive ones. Also, quite a lot of questions come to the mail like “will your asset work if ...”. Such letters should also not be ignored, because this is a potential buyer who can leave.
As complaints from first buyers were received, it became clear that many users use assets on complex scenes that have the configuration of a labyrinth or other connected cavity. In such projects, our path-finding scheme, based on collision checking, and even in the main stream, was not effective enough. Therefore, we started implementing the early construction of the graph so that it would be possible to search for the path in the side stream without using physics and accessing scene objects.
Discretization of three-dimensional space breaks it into cubes. Storing information about all partition cubes is redundant and very memory intensive. Therefore, it is logical to store only the coordinates of impassable cells, which was done.
Game obstacles are polygonal figures and consist of triangles. To account for obstacles in the search graph, you must find all the cubes of the partition that intersect any triangle of any obstacle. Already at this stage, the possibility of dynamically removing and adding obstacles to 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 is possible to build a navigation graph before the start of the game process and, due to the elimination of a large number of complex calculations during the search for a path, more than two hundred agents could make it simultaneously without sacrificing performance.
Another problem known to us also made itself felt: the A * algorithm and its modifications work extremely poorly in confined spaces on high-power graphs. Since their algorithm prefers the direction of the route toward approaching the target point, any deadlock leading to the target greatly slowed down the search for the path, since before choosing a different direction of “germination”, the algorithm first “fills” the entire space inside the dead end.
In such situations, the wave search algorithm (Lee Algorithm) proves 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 maze, the search time for the path was reduced by more than 30 times.
To speed up the preliminary processing of the scene and find the path to the asset, the possibility of parallel execution of processes was added, but the parallelism efficiency was extremely low, due to the fact that 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 tools to ensure efficient synchronization were implementedonly in the .NET Framework 4.5 standard, and in Unity until the 2018 release version of the .NET Framework 3.5 was used. We tried to solve this problem using available tools, but they had very mediocre performance, and we only got the desired result after switching to the 2018 Unity release. The use of competitive collections also opened up the possibility of realizing the dynamic change of obstacles in the scene.
At a certain stage, disagreements began to arise in the team regarding the distribution of profits, and a third person joined the team, who introduced a system for assessing the time investment of each member of the team, and also began to engage in code inspection and testing, which significantly improved the quality of the product.
The system for estimating time costs at the moment is made in the form of an Excel table and is an automated system in which once a month it is necessary to enter information about sales and tasks completed over the past month. Team members need to evaluate how much time they would need to solve a particular problem. Thus, when assessing the time complexity of tasks, the speed of each participant is taken into account. An abnormal overestimation or understatement by one of the participants immediately becomes evident from the accumulated statistics of his previous assessments. And, in the absence of a satisfactory explanation, this issue is decided by the whole team. This approach proved to be good for six months of use and allowed to collect interesting statistics. A ready-made free solution that would provide the described features, we have not been found. Therefore, at the moment, for small teams, the implementation in the form of Excel tables seems to us optimal. For relatively large teams, you will most likely have to design your database, develop the server part and client, or implement an extension for one of the existing project management systems.
To summarize. A year has passed since the start of development to the first version with the minimum necessary functionality and sufficient performance for use in real projects. Another six months was spent on improving performance and implementing multi-threaded work of the asset. At the moment, we estimated the time costs for this project at 1065 man hours (this is a rather optimistic estimate), and the average profit for the month is 9.5t. 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 implementing additional useful functionality: algorithmic reachability verification; the ability to assign game objects to portals; dynamic obstacle support; Local navigation between agents to prevent collisions and plan local routes.
We hope this material helps someone bring their project to the finish line.