Search Unity

  1. Unity 2019.1 is now released.
    Dismiss Notice

PathFinder 3D - pathfinding in three-dimensional space!

Discussion in 'Assets and Asset Store' started by SnigirevNikita, Oct 7, 2017.

  1. SnigirevNikita

    SnigirevNikita

    Joined:
    Jul 1, 2013
    Posts:
    19
    Hi there!

    This topic is dedicated to the PathFinder 3D asset. The last actual version is 0.4.1. Below we will talk about some of the features of this asset, as well as about the prospects for development.
    • Our asset allows you to search for paths in space on scenes of various configurations. It is perfect for any game scenarios where there must be flying or floating bots. For example, birds, spaceships, airplanes, fish, submarines or any other objects for which the path must be found in three-dimensional space, and not on surfaces.
    • The search for the path is very fast, even on rather complex scenes. Pathfinding is performed using one of two algorithms:
      • Modification of algorithm A *
      • Lie algorithm (it’s a wave algorithm)
    The first algorithm is suitable for use in open spaces, i.e. in most game scenes. The second will give an advantage in search speed compared to the first on cramped scenes with a maze configuration.​
    • All the major algorithms of our asset are implemented using multi-threading, so the frame rate should not be lost under any usage scenarios.
    • Obstacles can be any game objects of your choice. It is enough that the game object has a mesh of sufficient size and a special tag, or mesh collider. The obstacles of the scene are processed at the time of the start of the game. With the correct settings, this process does not last long and may well be included in the level loading process. But for procedurally-generated worlds, our asset is also suitable.
    • Any objects that appeared on the scene after the start of the game can also be asynchronously handled during the game and entered into the space graph. Deleting objects from a space graph in real time is also possible. Thus, the process of finding a path can be performed even on changing scenes.
    • Also in the asset there are built-in tools for smoothing and optimizing the found trajectories. These methods give the found trajectories a more natural look.
    • We also have a means to move along the paths found. So building game scripts with bots will not present any major difficulties. We even have a tool for smooth pursuit of moving targets. (without jerks and expectations when rebuilding the trajectory)
    In short, we have a lot of things :)
    More information about all the possibilities, as well as about the use of an asset, you can read in the user's guide.
    Thanks to everyone who read this post, we hope you were interested in learning about our product!
    If you are interested, you can go to the asset store page. If you have any questions - write us an email, or ask a question directly on the forum.
    Also, you can try PathFinder 3D in action! Demos availible here.

    Now we will tell a little about our plans for the future.
    • In the future, we want to introduce support for full-fledged dynamic obstacles, i.e. those obstacles that move, change size, shape, and so on.
    • We also want to introduce a local avoidance mechanism. What would a large number of agents could search for paths and move without colliding and without intersecting with each other.
    • Since the asset provides pathfinding possibility, it would be advisable to also provide users with the ability to build full-fledged AI. In order to use our product to create complex behavioral scenarios, as well as to customize the logic of interaction between bots and the player. Thus, there is an idea to create a full-fledged AI system with advanced settings for behavior and interaction.







     
    Last edited: Mar 9, 2019
    Korindian likes this.
  2. LennartJohansen

    LennartJohansen

    Joined:
    Dec 1, 2014
    Posts:
    2,110
    Looks nice :)

    how do you feed the system with obstacles? Physics colliders?
     
  3. SnigirevNikita

    SnigirevNikita

    Joined:
    Jul 1, 2013
    Posts:
    19
    Yes, so it is implemented :)
     
  4. LennartJohansen

    LennartJohansen

    Joined:
    Dec 1, 2014
    Posts:
    2,110
    Nice.

    What is the speed like? calculating a route. Like in one if the example images here?
     
  5. SnigirevNikita

    SnigirevNikita

    Joined:
    Jul 1, 2013
    Posts:
    19
    The speed of calculating the route depends on the size of the space and the degree of detail in which the search is performed.
    The examples shown on the website show it is slower than it really is.
    In any case, there is a choice between the search speed and the quality of the route.
     
  6. LennartJohansen

    LennartJohansen

    Joined:
    Dec 1, 2014
    Posts:
    2,110
    just within a order of magnitude? is it 1 ms or 100 for a path like this? Any problem to split over frames? I assume it needs to be in main thread as you access physics.
     
  7. SnigirevNikita

    SnigirevNikita

    Joined:
    Jul 1, 2013
    Posts:
    19
    The search algorithm is implemented as a coroutine. So measuring the speed of search is an incorrect question. Delays between frames are insignificant when the search parameters are correctly configured.

    If the search is too difficult, the delay will be visible.

    But we have implemented a state machine, this allows you to mask the search process, for example by adding some wait animation.
     
  8. dgoyette

    dgoyette

    Joined:
    Jul 1, 2016
    Posts:
    1,429
    This looks just like what I've been looking for. Impressive work.

    Question: In my game, I have flying objects that have attached rigidbodies. I move them around using physics forces, rather than just changing the transform. (That is, using PID controllers). With Unity's NavMesh system, it's possible to just use the data provided by an Agent to get a path, without using the Agent to actually move the gameobject around. Does your system do something similar? That is, can I use your package to determine the path to take, while handling the movement on my own?
     
  9. SnigirevNikita

    SnigirevNikita

    Joined:
    Jul 1, 2013
    Posts:
    19
    Hi, Dan!
    Of course, this possibility is present. You can only get the path without moving along it. We can also help you with setting up a package for this purpose.
     
  10. RendCycle

    RendCycle

    Joined:
    Apr 24, 2016
    Posts:
    329
    Is this compatible with Unity 2018.1? Can this be used for swimming NPCs? This still does not support colliders?
     
  11. SnigirevNikita

    SnigirevNikita

    Joined:
    Jul 1, 2013
    Posts:
    19
    Hi!

    1)The asset has been assembled and tested on Unity v 2017.1.1. So, there is no reason to believe that there may be problems when used with version 2018.1. In any case, we'll help you to solve any problems, if it appear.

    2)What do you mean by swimming NPCs? If this is NPCs, for which the movement is planned in space, then yes, the asset is suitable for this.

    3)At the moment asset support any obstacles, provided by mesh collider, or mesh with special tags. More details can be found in the documentation for the Asset on our website - https://gracefulalgs.com/portfolio/pathfinder/
     
    Last edited: Jun 23, 2018
  12. RendCycle

    RendCycle

    Joined:
    Apr 24, 2016
    Posts:
    329
    Thanks for the reply. Yup, that's NPCs (Non-Player Characters). Planning to use it for animals/creatures. Can the GameObjects that has the Pursuer script have colliders? Also, can the distance between an obstacle and a Pursuer be adjusted? I noticed in the EXE demo that the planes are very close to the mountains and some move jerkily.
     
  13. SnigirevNikita

    SnigirevNikita

    Joined:
    Jul 1, 2013
    Posts:
    19
    Indeed, according to our idea, objects that have a component of Pursuer can have colliders. And they should not be regarded as obstacles in finding a way. But recently one of our users encountered some problem. More details can be found in the last review on the page of our Asset in Assetstore. Therefore, I can not fully guarantee the fulfillment of this requirement. But I can assure you that the next update will solve the problem.

    Concerning the jerking of the pursuers and the approaching of the passage to the obstacles - yes, such a problem exists, and we also reflect on it. We hope that we will manage to solve it. Now the problem of approaching obstacles can be solved by increasing the dimension of cells in the search graph. I suggest you do not hurry with the purchase of the asset and wait for the next update (it is expected by early August). Then you can try new demos, which will be published on our website.
     
    Mohamed-Anis likes this.
  14. RendCycle

    RendCycle

    Joined:
    Apr 24, 2016
    Posts:
    329
    Thank you very much for your honesty. Will just watch this asset for updates. All the best to you and your team! :)
     
  15. JamesMillsTunacorn

    JamesMillsTunacorn

    Joined:
    Mar 21, 2018
    Posts:
    3
    Hello,

    I am attempting to use this asset in UWP and it looks like it won't work at all due to the asset using System.Threading, of which UWP doesn't have access to. Is there any way around this?
     
  16. SnigirevNikita

    SnigirevNikita

    Joined:
    Jul 1, 2013
    Posts:
    19
    Hello, James! In the update to version 0.3 we have implemented several code elements that should solve this problem by providing Windows.System.Threading namespace(which supports at UWP) instead of System.Treading. Unfortunately, we can not guarantee working capacity, because we do not have the opportunity to test our asset on this platform. (This update is currently not released, but is pending review at Asset Store.)
     
  17. ivanbolcina

    ivanbolcina

    Joined:
    Oct 27, 2013
    Posts:
    41
    Hi.
    I am having a problem.
    I need to restart SpaceManager, but I'am not able to do so. The closest I came is this:

    public void RestartImpl()
    {
    markrestart = true;
    }
    bool markrestart;
    void Update()
    {
    if (markrestart)
    {
    if (!isPrimaryProcessingCompleted) return;
    markrestart = false;
    isPrimaryProcessingCompleted = false;
    Start();

    }
    ......

    But it doest work always. I guess some async thread issue?
     
  18. SnigirevNikita

    SnigirevNikita

    Joined:
    Jul 1, 2013
    Posts:
    19
    Hi, Ivan!
    Could you describe your purpose in more details? Maybe, we could suggest a way for solving this problem.
    What is mean "restart SpaceManager"? Your want to reinitialise class instance, or just clear spatial graph (occupied cells dictionary), or abort obstacles handeling process and the restart it?
     
  19. ivanbolcina

    ivanbolcina

    Joined:
    Oct 27, 2013
    Posts:
    41
    Hi.
    I have this situation:
    on scene, I have several "waypoints gameobject": Waypoint1, Waypoint2, Waypoint3.
    Each waypoint contains several obstacles and other game objects.
    On scene start, waypoint1 is active.
    When player finishes with waypoint1, game activates waypoint2 and deactivates waypoint1.

    Only obstacles in Waypoint1 are detected, and nothing happens when Waypoint2 is activated.

    I need to "rescan" scene when game activates waypoint2.

    Also,similar problem, if I move obstacle around, how to synchronize with SpaceManager?
    Thx!
     
  20. ivanbolcina

    ivanbolcina

    Joined:
    Oct 27, 2013
    Posts:
    41
    Tried this, doesnt work:
    Code (CSharp):
    1.  
    2. using System.Collections;
    3. using System.Collections.Generic;
    4. using UnityEngine;
    5.  
    6. public class NotifySpaceManager : MonoBehaviour
    7. {
    8.     // Start is called before the first frame update
    9.     void Start()
    10.     {
    11.         var sm = GameObject.Find("SpaceManagerGO").GetComponent<SpaceManager>();
    12.         sm.HandleAnObstacle(gameObject);
    13.      
    14.     }
    15.  
    16. }
    17.  
     
  21. ivanbolcina

    ivanbolcina

    Joined:
    Oct 27, 2013
    Posts:
    41
    Update....If I have a clone of object, that is visible at begging, then code above works (for another object).


    gameobject1 has the same mesh as gameobject2
    gameobject2 has NotifySpaceManager attached
    gameobject2 is not enabled at scene start


    OK SCENARIO:
    //////////////////////////////////////////////////////////
    gameobject1 ---enabled < detected
    gameobject2 ---disabled < not detected

    then enable gameobject2, which has NotifySpaceManager behaviour

    gameobject1 ---enabled < detected
    gameobject2 ---enabled < detected by spacemanager



    ERROR SCENARIO:
    //////////////////////////////////////////////////////////
    gameobject2 ---disabled < not detected

    then enable gameobject2, which has NotifySpaceManager behaviour

    gameobject2 ---enabled < not detected by spacemanager (ERROR!!!)



    It seems, that UpdateGraphForObstacle doesn't work, if there is not a GameObject with the same mesh available at the start of scene.

    I guess method should have functionality to automatically add mesh, if it is not present.
     
  22. SnigirevNikita

    SnigirevNikita

    Joined:
    Jul 1, 2013
    Posts:
    19
    Hi again.

    I checked the performance of the obstacle handling functions. SpaceHandler really had a bug. We have already fixed it and it will be fixed in a new update coming soon. So that you can resolve this error in your home space, replace the line at number 255 "if (staticObstacleTags.Contains(obstacleGOToUpdate.tag) && meshFilterInst && meshFilterInst.sharedMesh)" in the SpaceHandler class with this "if (meshFilterInst && meshFilterInst.sharedMesh)".

    I also created a test scene to test the processing of new obstacles and remove existing ones. I attached a link for downloading. In the project, you need to import the asset file into project and add the SpaceManager script to the scene.

    Thank you for noticing the problem and letting us know!
     
    Last edited: Dec 16, 2018
  23. ivanbolcina

    ivanbolcina

    Joined:
    Oct 27, 2013
    Posts:
    41
    Thanks.
    It worked, I can now see boxes around meshes.

    I have however another problem:

    SpaceHandler never calls NotifyRediness.

    And then, I cannon find path. Even if I force calling it, path doesnt return.
    I guess something gets stuck in working queue?
     
  24. SnigirevNikita

    SnigirevNikita

    Joined:
    Jul 1, 2013
    Posts:
    19
    The setting "Graph obtaining at scene start" in the inspector SpaceManager set to true? If not, then when you start the scene, you must manually make a call to SpaceManager.HandleAllObstaclesOnScene ().

    And we also found an error that could prevent the correct call of NotifyRediness
    To fix it, please replace the function HandleAllObstaclesOnScene () with the following code:
    Code (CSharp):
    1. public bool HandleAllObstaclesOnScene()
    2.         {
    3.             //selection all GameObjects at scene
    4.             List<GameObject> generalGOList = GameObject.FindObjectsOfType(typeof(GameObject))
    5.                 .Select(item => (GameObject)item).ToList();
    6.  
    7.             //selection of objects, having mesh collider,terrain, or prohibited tag
    8.             generalGOList = generalGOList.Where(go =>
    9.                 !go.GetComponent<Pursuer>() && go.activeInHierarchy && (
    10.                     go.GetComponent<MeshCollider>() && go.GetComponent<MeshCollider>().sharedMesh &&
    11.                     go.GetComponent<MeshCollider>().enabled == true ||
    12.                     staticObstacleTags.Contains(go.tag) && go.GetComponent<MeshFilter>() &&
    13.                     go.GetComponent<MeshFilter>().sharedMesh ||
    14.                     go.GetComponent<Terrain>() && go.GetComponent<Terrain>().enabled == true
    15.                 )).ToList();
    16.  
    17.             if (generalGOList.Count == 0)
    18.             {
    19.                 NotifyRediness();
    20.                 return false;
    21.             }
    22.  
    23.             totalTrisCount = CountTheTotalNumOfTris(generalGOList);
    24.             foreach (GameObject go in generalGOList)
    25.                 UpdateGraphForObstacle(go, broadcastCancToken);
    26.             return true;
    27.         }
    A correction of this error will also be included in the nearest update. We apologize for such flaws in the asset code. The update will be released very soon.
     
  25. ivanbolcina

    ivanbolcina

    Joined:
    Oct 27, 2013
    Posts:
    41
    No problem.
    However, the your fix didnt do it. I figured out what is the problem: you count of all triangles and count the number of processed. It never reaches target count.
    I changed to count just game objects, that way it finishes. When i look at scene mode, i see boxes around my objects, which is fine.

    But then I do:


    Code (CSharp):
    1.  persuer.StopAllAsyncTasks();
    2.                 foundRoute.Clear();
    3.                 persuer.FindWay(Ship.transform.position, pos,
    4.                     persuer.pathfindingLevel, foundRoute,
    5.                     persuer.selectedPFAlg,
    6.                     new Action(() => { state = Mode.Exit; }),
    7.                     new Action(() => { state = Mode.MovingToBall; }),
    8.                     persuer.trajectoryOptimization, persuer.trajectorySmoothing);
    and it never finds path.
    I dont know if request for path doesnt get processed or what is wrong....
     
  26. ivanbolcina

    ivanbolcina

    Joined:
    Oct 27, 2013
    Posts:
    41
    I have quite complex meshes with lots of hierarchy, maybe that was the problem with triangle count....
     
  27. SnigirevNikita

    SnigirevNikita

    Joined:
    Jul 1, 2013
    Posts:
    19
    I think it would be useful for me to look at your scene. If you are allowed to do this, please send us your scene by mail : support@gracefulalgs.com. We would like to investigate it and find out the cause of the error.
    I think it will solve the problem faster than the correspondence on the forum :)
     
  28. ivanbolcina

    ivanbolcina

    Joined:
    Oct 27, 2013
    Posts:
    41
    Thanks. I will try to prepare something, but for now, I found that complex gameobjects hierarchy (hundreds of object in 4 or more level hierarchy) can cause this. I added tag to ignore them (they are contained in larger gameobject, so it is the same effect)

    Feature request. Add tag for ignoring objects when doing HandleAllObstaclesOnScene
     
  29. SnigirevNikita

    SnigirevNikita

    Joined:
    Jul 1, 2013
    Posts:
    19
    Thanks for the feature idea! Honestly, you anticipated our intention. Ignore tags are already being developed and will also be released very soon.
     
  30. DankP3

    DankP3

    Joined:
    Jul 17, 2017
    Posts:
    44
    @SnigirevNikita
    This looks like a nice asset I have a few questions, apologies for number, but I am potentially interested.
    1. Would this be a good asset to create at a 'random' point in a world, on demand at runtime, a 3d navmesh, for example a 20m cube in the middle of a furnished house, so that any flying AI that entered that zone could path around furniture etc. Then, when finished, delete the mesh and make another elsewhere at another time?
    2. Could you have more than one such mesh in a world at any time?
    3. If 2, could the meshes overlap (assuming my AI are programmed to discriminate), or could you add two meshes together to make one? Or would I delete one and make anew bigger one.
    4. Can I have the navmesh only navigate around assets if they are on a specific layer?
    5. If 4, if meshes are moved between layers is it easy to update the navmesh/is it automatic.
    Lastly, do you have a planned timeline estimate for implementation of local avoidance? And dynamic obstacles?
    Thanks for the help.
     
  31. SnigirevNikita

    SnigirevNikita

    Joined:
    Jul 1, 2013
    Posts:
    19
    Hi, DankP3!
    Thanks for the questions, I will try to answer them exhaustively.

    1)As I understand it, the first three questions relate to the construction of a navigation graph, which will be used later for pathfinding.

    So here, the navigation graph implemented in such a way, that it hasn't any coordinate constraints. It's size is not restricted. It's storages only occupied cells of the space. The cells, that couldnt be finden at graph, are considered as free.

    Navigation graph obtaining once at the start of the scene. So, in any time after obtaining a graph, you can serach for a path in any coordinate of the scene space. And all obstacles will be taken into account.

    So, the patfinding area is extends over all space of the scene. So no need to rebuild navigation mesh in specific areas of the space.

    The obstacles, that appeared after the navigation graph calculation, can be handeled separately and merged to an already constructed graph. The same goes for their disappearing.
    2) To define obstacles among all the game object of the scene, special tags are used. So, your conception of the layers may be realised by using of tags groups, that mark gameobjects, that are mmust be taken into account as obstacles.

    In-game tag changing will not cause automatic graph updating. It's need to be executed by manual call of the specific update function.

    3)As for local avoidance and dynamic obstacles, currently we are working at this fetures. Theirs release is expected for the end of january or the beginning of the february.

    Hope, I understood your questions correctly, and my answers has satisfied you.

    If you have any more questions, please ask it.
     
  32. DankP3

    DankP3

    Joined:
    Jul 17, 2017
    Posts:
    44
    Thank you very much. I guess i was wondering in a large and complex map if small graphs could be built when needed in specific locations rather than mapping the whole world at the beginning. However, i think you answered my question, a single graph is built for all at the start.
    Thanks again,
     
  33. Mohamed-Anis

    Mohamed-Anis

    Joined:
    Jun 14, 2013
    Posts:
    71
    @SnigirevNikita may I suggest linking Pathfinder 3D asset store page having a link to this forums? It'll be useful for potential buyers to know that you are active here and that they're assured in getting great support here :) thanks!
     
  34. SnigirevNikita

    SnigirevNikita

    Joined:
    Jul 1, 2013
    Posts:
    19
    Hi, Mohamed-Anis!
    Thanks for the great idea :)
    Honestly, I was sure that the description contained a link to the forum thread. But, apparently, we still forgot to insert it.
     
    Mohamed-Anis likes this.
  35. Mohamed-Anis

    Mohamed-Anis

    Joined:
    Jun 14, 2013
    Posts:
    71
    @SnigirevNikita may I know how is local avoidance and dynamic obstacles coming along? Is there an ETA on that?

    Thank you!
     
  36. SnigirevNikita

    SnigirevNikita

    Joined:
    Jul 1, 2013
    Posts:
    19
    This feature are currently under development. I do not want to give any exact dates, but according to our estimates, the development will be completed by the end of February - the beginning of March.
     
  37. Mohamed-Anis

    Mohamed-Anis

    Joined:
    Jun 14, 2013
    Posts:
    71
    Ok! Thank you!
     
  38. Mohamed-Anis

    Mohamed-Anis

    Joined:
    Jun 14, 2013
    Posts:
    71
    @SnigirevNikita will your asset support multiple navgraph equivalents? Say I have large airplane that can't go through narrow corridors while I also have smaller planes that can go through it?
     
  39. SnigirevNikita

    SnigirevNikita

    Joined:
    Jul 1, 2013
    Posts:
    19
    Yes, we have this feature.
    Spatial graph, that uses for pathfinding, consist of multiple levels. Each level keeps cells of i's own size.
    The size of the cells at each level is equal to the size of the cells at the previous level plus the size of the cells at zero level multiplied by 0.33. Thus, for a graph with five levels and with a cell size of 1 on the zero level, we obtain the following sequence of cell sizes. 0: 1, 1: 1.33, 2: 1.66, 3: 1.99, 4: 2.32.

    The maximum possible number of levels is 15.

    Each pursuer can search for a path at any level you wish.
     
  40. Mohamed-Anis

    Mohamed-Anis

    Joined:
    Jun 14, 2013
    Posts:
    71
    Also can I configure the areas where different objects can move? E.g. Unity's navmesh allows baking of each navmesh independent of other navmeshes. Do you have such a functionality?
     
  41. SnigirevNikita

    SnigirevNikita

    Joined:
    Jul 1, 2013
    Posts:
    19
    In our asset, the search space is considered a little differently. It is assumed that the entire space of the scene is discrete, and those discretes that are occupied by obstacles are considered impassable. So the search space is unlimited and is common to all searchers.
    In Navmesh, as I understand it, some geometry is built, within which a pathfinding is possible. We do not have this. Pathfinding is possible everywhere there are no obstacles.
     
    Mohamed-Anis likes this.
  42. Mohamed-Anis

    Mohamed-Anis

    Joined:
    Jun 14, 2013
    Posts:
    71
    @SnigirevNikita just to share what I'm thinking of:
    I have two types of dragons (both same size): ice and fire dragons. Ice dragon can't traverse the hot regions of the map (they'll melt) while fire dragons can't traverse the cold regions of the map (they'll freeze).

    One solution using Unity's navmesh will be to have two different navmeshes. However I'm guessing that's not possible here?
     
  43. SnigirevNikita

    SnigirevNikita

    Joined:
    Jul 1, 2013
    Posts:
    19
    Unfortunately, at the moment this feature is not supported in our asset. But maybe we will implement it later.
     
  44. Mohamed-Anis

    Mohamed-Anis

    Joined:
    Jun 14, 2013
    Posts:
    71
    Sure.. no worries. Looking forward to the future changes thank you!