Search Unity

  1. Unity 2019.1 is now released.
    Dismiss Notice

Assets K-PathFinder

Discussion in 'Works In Progress' started by Krokozor, Dec 25, 2016.

?

What do you think is best option?

  1. Expand documentation and make videos

    7 vote(s)
    25.0%
  2. Fix bugs and make features

    14 vote(s)
    50.0%
  3. A bit of everything in small chunks

    2 vote(s)
    7.1%
  4. Do all. Whatever time it takes

    5 vote(s)
    17.9%
  1. itsnottme

    itsnottme

    Joined:
    Mar 8, 2017
    Posts:
    72
    The raycast and the other issues are working fine, good job. Just one thing, there wasn't an example about "PathFinderAgent.position" in the example scene. Do I set it to transform.position before SetGoalMoveHere or nextPoint?

    I also have a suggestion, instead of being forced to have a AgentProperties for every different character (just because of height and radius differences); it would be great if all the values are set by default in PathFinderAgent, but can be changed if needed be, like radius and height for example. Or leave the AgentProperties, but have height and radius separate in PathFinderAgent.
     
    Last edited: Aug 11, 2017
  2. Krokozor

    Krokozor

    Joined:
    Sep 27, 2014
    Posts:
    63
    Next patch i will probably wount implement new triangulation either. Need to finish next stage of my main project before that. After that i will get big site to test PathFinder so it will be easier for me to catch bugs.
    But i will happy to fix reported bugs. And probably fix in some degree current triangulation cause i have some neat idea.

    Hi CorvOrc!
    Well thats a actualy a bit big topic. You actualy can see used data if you use debuger i build in navmesh.

    Firstly for each chunk i create templates for it work. It contains information like size, resolution, colliders. Next stages are happening in not main thread. Then using some tricks i place mesh into collider shape (for terrain i generate mesh from heightmap and for trees reading tree instances data).
    In this stage we can tell wich triangle are walkable by cheking it inclanation.
    Unity 2017-08-12 12-01-20-58.png

    Then this mesh are rasterized. I my case this mesh converted into set of two images that represent top and bottom. Green for walkable area, purple are overinclined area, black for bottom. Then this sets if images are combined into one chunk where in proces of combining cheked intersections of added volumes. Removed obstructed voxels, applied flags based on agent height. Cause on this stage we can tell wich voxels have enough space to fit agent above them. That generate red unwalkable voxels.
    Unity 2017-08-12 12-46-08-23.png

    After that stage there are multiple stages of refining that set of images. Firstly builded connectivity data so we know wich voxel connected to wich, in that stage used "step height" value. Then when we know neighbours of each voxels we also know borders for each voxel groups. Then applyed agent radius in voxels using connectivity data. And some extra steps in some stages like combining small volumes into one to reduce amount of work. Or optional work. "Battle grid" are generated in that stage, cover map generated in that stage.
    Unity 2017-08-12 12-01-59-51.png

    Then to this map siquentialy for each volume are applyed "marching squares" algorithm (left image). Nodes share information so we know where nodes have connections to more than 2 nodes. Result of that algorithm splited into set of points between nodes with 3 connections, or just closed sets where end and begin are one node. And simplify this sets using Ramer-Douglas-Peuker algorithm.
    Unity 2017-08-12 12-02-32-16.png
    And now we have contour. This contour are triangulated.
    Unity 2017-08-12 12-02-53-29.png

    Then navmesh builded from this data with some little tricks based on previos steps. Cause we know connection order of contour and wich lines are generated from triangulation. And then navmesh are finally ready. It contain information it get in voxels stage, it offseted from borders. And it have graph to search path on it. At this stage PathFinder exit from thread and connect this chunk of navmesh to whole grid.


    Oh i forgot. PathFinderAgent are actualy have "public virtual Vector3 position" assessor in case you want to inherit from PathFinderAgent and overload it. By default it returns "get { return transform.position; }" so if you dont want to change agent position it will be it transform position.
    There is now also two functions to order path in PathFinderAgent:
    SetGoalMoveHere(Vector3 destination, bool snapToNavMesh = false, bool applyRaycastBeforeFunnel = false, int maxRaycastIterations = 100)
    SetGoalMoveHere(Vector3 start, Vector3 destination, bool snapToNavMesh = false, bool applyRaycastBeforeFunnel = false, int maxRaycastIterations = 100)

    So you can also specify start position here. For example you can store current path as backup, and check paths in some other cases. For example if you building AI wich think in multiple steps and you need to check move cost from one step to another. Or if you just want to check if some path are even exist.

    I planning to expand PathFinderAgent in future and make sort of "service" version of it. For example to build sort of squad commander who actualy build paths and check information for multiple agents. To simplify some cool tactical orders like "surround target but stay in cover". It's long way from it though. For now you can separate navigation and actual agent position using that.


    This will be bad decision actually. Radius and height are used deep inside of process navmesh generation to tell where borders of navmesh are. I actually tried to make navmesh with dynamic agent radius but it need some special type of triangulation to make pathfinding take into account agent radius. It cant really be done when navmesh in grid pattern. At least i cant thought any good way to do that. (Can share my thoughs how it can be done if you want)
    So there was two options:
    A) Make agent sizes constant but implement grid where navmeshes can be disconnected from grid. So changes in world can be applyed without rebuilding navmesh for entire level
    B) Make agent radius dynamic.
    Think dynamic world with more limited types of agents are more viable option so i impement it in that way.
    If you want i actualy can reimplement making small offsets from navmesh so agent will take little extraspace from border but cant guarantee it will be precise.

    AgentProperties are to differentiate agent archetypes really. Though most games dont have much of it. If you want to do such bizarre thing as building navmesh for 10-20 or more types you can overload PathFinderAgent, make so on start it tries to generate AgentProperties for it sizes itself or take existed properties if already generated and use them. I mean you dont need to store AgentProperties in file if you want to.
     
    Last edited: Aug 12, 2017
    CorvOrk and itsnottme like this.
  3. itsnottme

    itsnottme

    Joined:
    Mar 8, 2017
    Posts:
    72
    Actually what I meant is not to make them dynamic, but make it possible to set them in the Start method right with AgentProperties. So instead of having radius and height in AgentProperties, it can be set somehow in the Start method of PathFinderAgent.
     
    Krokozor likes this.
  4. Krokozor

    Krokozor

    Joined:
    Sep 27, 2014
    Posts:
    63
    Well. Then i dont have good idea how you imagine that. I mean. Radius and Height of AgentProperties are data to generate navmesh with expected height and radius. If i apply this data to PathFinderAgent it's mean now NavMesh will be generated for every PathFinderAgent? That not seems reasonable.
    Though you suggest to somehow make one navmesh but extract data from it differently.

    Or you mean just add some GUI to PathFinderAgent component? To edit it's AgentProperties from it so you dont need to move back and forth to make small changes in it's properties if they exist?
     
    Last edited: Aug 12, 2017
    CorvOrk likes this.
  5. itsnottme

    itsnottme

    Joined:
    Mar 8, 2017
    Posts:
    72
    Doesn't each PathFinderAgent (can) have a different AgentProperties, which then will be used to generate the whole NavMesh?
    What I am trying to say is, instead of having the radius and height be saved into file, it would be better (if possible) to be set as a variable (in whatever class, my example was PathFinderAgent) before the NavMesh is generated. It would save memory and the hassle of using multiple AgentProperties files just for different sizes.

    So instead of making them dynamic variables to be changed in run-time, they would be "static" variables that are just set at the beginning.
     
    Krokozor likes this.
  6. Krokozor

    Krokozor

    Joined:
    Sep 27, 2014
    Posts:
    63
    Nope. Navmesh are generated per AgentProperties. Not PathFinderAgent.
    For example if you have 3 types of soldiers wich uses one AgentProperties then they all will use one navmesh and it will be generated only once. Or if you have for example 3 types of soldiers wich uses Soldier_AgentProperties and have big tank wich uses Tank_AgentProperties then 2 navmeshes will be generated. One for Soldier_AgentProperties and one for Tank_AgentProperties.
    AgentProperties are serve as key to NavMesh dictionary. If no navmesh exist then it serve as instruction to generate navmesh.
    And PathFinderAgent are serve only as reciever to requested information and as holder of AgentProperties. PathFinder are know that PathFinderAgent can recieve information and it have AgentProperties. It's not participate in navmesh generation in any way. (Actualy i can separate it entirely AgentProperties from PathFinderAgent and only tell PathFinder "give stuff to that Agent and use that Properties" and dont check if this Agent even have this Properties at all)

    But of course you CAN have AgentProperties for every PathFinderAgent so navmesh will generated also for every PathFinderAgent. If you have good causes to do that.
    For example if you have story about three good guys. One is big, one is small and one something in between. And they need separate navmeshes for navigation cause of big size differences. But some generic enemy probably need to have just one navmesh type. And it probably just reuse navmesh from middle good guy.

    Well sizes are mean a lot for navmesh generation.
    I can implement something like checkbox in PathFinderAgent "make properties" so for example it check some static dictionary if it contains already target AgentProperties then it takes it and if not then it firstly creates it and then takes it. So navmeshes are not generated per agent and you have lowest possible navmesh types count. But really this is bad design.
     
    itsnottme likes this.
  7. itsnottme

    itsnottme

    Joined:
    Mar 8, 2017
    Posts:
    72
    Oh I see that makes sense, thanks for clarifying.
     
    Krokozor likes this.
  8. Krokozor

    Krokozor

    Joined:
    Sep 27, 2014
    Posts:
    63
    You are welcome! Will put it in manual in more obvious way.
     
    itsnottme likes this.
  9. julienc

    julienc

    Joined:
    Nov 26, 2012
    Posts:
    2
    Hi,
    thanks for the nice asset. I am comparing different approach to navmesh for my game. Could you explain how to implement dynamic obstacles (e.g. moving NPC) with your?
    thanks!
     
  10. Krokozor

    Krokozor

    Joined:
    Sep 27, 2014
    Posts:
    63
    Hello!
    Well. Currently dynamic obstacles are object to implement. (will do this. this feature requested multiple times and actualy i need on my own. but right now i have really busy times) Obstacles are can be only static. But parts of navmesh can be disconnected and redone while playing so if some parts of level was changes there is no need to generate all navmesh from zero. Guess it's can be pretty good for small tactical games with destructible/procedural levels.

    If your main concern is obstacle avoidance then guess right now it's not siuted for your needs.
    Though it have some other cool features like sampling points in reachable proximity, jump spots generation, cover spots generation. Also you can paint areas on terrain.
     
  11. itsnottme

    itsnottme

    Joined:
    Mar 8, 2017
    Posts:
    72
    Hey, how's it going? it's been a while.
    How's the progress going with the PathFinder?

    Also, I was wondering, if patrolling using sets of points on the terrain would be possible to implement in the future?
     
  12. Krokozor

    Krokozor

    Joined:
    Sep 27, 2014
    Posts:
    63
    Hello! Long time no see. Spend lots of time on some distant stuff and experiment with triangulation. Actualy i submitted small update to asset store 3 days ago so it will be there soon. Will make big navmesh chunks generation somewhat faster, fix compatability with unity 2017.2 and small bug related to covers generation. Will make post about whats going on later.

    Actualy i was planned to fix old bug related to navmesh triangulation but for now i dont have good example of that bug. Spend couple days trying to recreate it but it's not that simple.
    Basically when pathfinder generate navmesh from it's hull it trying to connect pointy nodes to nearest any visible node in target angle and direction. So result are always covex. Issue is: testing visibility.
    1.png
    In 1 example node "a" search connection and node "b" are viable connection but it's on edge of possible connections. Graph connected and no issue here.
    issue is when condition on 2 example occure. "a" search for connection and "b" still only possible connection but due to some number rounding and other problems "c" is not viable connection and it's edges are dont overlap when testing visibility. So edge are placed exactly on another node in that case.
    And when node "c" trying to search nearest node to connect. It either connect through "a-b" edge to some other edge or connect to "a" and "b". Both cases are bad. "a-b-c" triangle can be solved on later stage but when "c" connect to another node then it's can't be helped.

    So. I can avoid that issue if i check all nodes. If node laying on another line or close enough then it should subdivide line. But nodes and lines are many and it's taking too much time already.
    I planned to limit scope of tested lines. So i redone some math related to line rasterization
    2.png
    Now it much faster. And also limits scope for testing.
    Also now testing node visibility are done using that. So pathfinder dont test visibility for all lines, just one which close enough to test area. And it was around 40% of work for triangulation so now it's next to nothing.
    End up with still existing bug (cause dont have good eample of it) but boost of perfomance.

    Also was trying to scrap triangulation altogether and implement limited delaunay triangulation.
    Unity 2017-12-05 08-24-12-46.png
    But it's some hairy stuff. Spend to much time on that and need to spend much more to make it viable. So i return after some time to original triangulation and tried to fix it.


    And thats kinda it. Also spend some time with my main project, create some cool node based terrain generator which will probably end up on asset store at some point. Tested pathfinder on it.
    Also spend lots of time with UNET and procedural animations. But it's not related.

    Well. AI need for that :) pathfinder are really just about finding path and stuff in the world.
    I will add soon enough related to AI stuff like "escape away from point" and also planing to add interface for searching stuff. So for example something will be registered on navmesh as it's content and user just ask "find nearest thing with that condition" like it's happening with covers. But also can happen to items in world or something like that.

    Will probably add AI at some point to pathfinder like RAIN does. But different kind of AI. I have somewhat cool and working AI in my main project and lot's of people asked me to also share it. But currently it's too badly writen and i dont expect anyone will figure out how it can be changed for their needs.
     
    itsnottme likes this.
  13. itsnottme

    itsnottme

    Joined:
    Mar 8, 2017
    Posts:
    72
    Nice, good job.
    About the patrolling, it was just a suggestion, but since I don't have any experience with adding points on terrain that can be used, but I have an idea of an implementation in code of using the points in an AI point of view. I can write the code and give it to you, to use in this project, if you are willing to implement this later :).
     
  14. Krokozor

    Krokozor

    Joined:
    Sep 27, 2014
    Posts:
    63
    Changelog 0.38 => 0.39:

    Whats new:
    * Added option to add extra voxels into sampling covers.
    You can find in on agent properties. 0 by default. If your agent is too thin then it fixes issue with fragmented covers
    CoverFix.png
    * PathFinderAgent now have "bool ignoreCrouchCost" as public variable
    if it true then generated path and search for nearest cover will set crouch areas cost as normal moving cost.
    userful if your agent swich state to permament crouching

    Whats Fixed:
    * compatability with Unity 2017.2
    * some conditions for allerts. less false alarm

    Whats changed:
    * triangulation now around 40% faster. more noticible on large graphs
    * some UI tweaks
    * lots of small internal changes. less garbage generation, calling struct constructors etc
    * some important parts of code are better commented

    Also i added version for unity 5.6 on asset store. Some people tells me some bizzare story about unity licensing. So if they buy unity 5.X so they cant download this asset. I cant check it but here it is.
     
    Last edited: Dec 6, 2017
    itsnottme and WinterboltGames like this.
  15. WinterboltGames

    WinterboltGames

    Joined:
    Jul 27, 2016
    Posts:
    123
    The 40% faster triangulation greatly improved the fps on my 512x512 terrain getting stable 60 fps now. thanks for making this amazing *free* plugin!
     
  16. itsnottme

    itsnottme

    Joined:
    Mar 8, 2017
    Posts:
    72
    I finished a simple and modifiable code for patrolling (using any objects on scene, best to just use empty game objects); if anyone want's me to share the code, just let me know :)
     
  17. WinterboltGames

    WinterboltGames

    Joined:
    Jul 27, 2016
    Posts:
    123
    I many find a use of patrol code in my game...can you show me it please?
     
  18. itsnottme

    itsnottme

    Joined:
    Mar 8, 2017
    Posts:
    72
    Let me know if you find any bugs. Also, please read the comments, there are some things that might need implementing.
     

    Attached Files:

  19. WinterboltGames

    WinterboltGames

    Joined:
    Jul 27, 2016
    Posts:
    123
    Thanks very much! Will test it soon.
     
    itsnottme likes this.
  20. shahzaib

    shahzaib

    Joined:
    Dec 14, 2013
    Posts:
    19
    Looks cool! does it also support spherical navigation?
     
  21. itsnottme

    itsnottme

    Joined:
    Mar 8, 2017
    Posts:
    72
    I forgot to add:
    patrolTimer.Reset(); under patrolTimer.Stop();
    To actually reset the stopwatch each time.
     
  22. itsnottme

    itsnottme

    Joined:
    Mar 8, 2017
    Posts:
    72
    Hey how is everything going?

    I was wondering if there is a sure way to check if the goal was reached after SetGoalMoveHere?
    haveNextPoint would be perfect, but it's not set automatically to true after calling SetGoalMoveHere. It takes a few frames (2 or so) to update and set to true.
    I could always hardcode the checker to wait few frames, but that wouldn't always work on all computers/processors the same.

    I also found some bugs:
    ArgumentException in line 86 in PathFinderMenu, when clicking on the colour in area editor.

    There is also a MissingReferenceException in line 245 in PFDDebugger, when closing (sometimes opening and using) the Menu. But it got fixed after the settings got updated when running the game.
     
  23. Krokozor

    Krokozor

    Joined:
    Sep 27, 2014
    Posts:
    63
    A bit strange implementation. Will add to this post simple example of patroll.

    Planing to make it faster in next update. Current other half of hard work is find all viable nodes to connect. Before previous update it was way to reduce work where now it dont need to be reduced.

    currently not.
    will add this at some point in future actualy. it's not that hard at this point.

    A bit sad for me :( Spend amost 2 weeks in hospital before new year. So i have only little progress. Before that i spend time to dive into multiple agents collision avoidance.

    A bit unclear question. Cant see what scenario did i miss.
    You mean store "move goal" and check is agent reach it in first couple frames?

    Amost all code in PathFinderAgent related to just Path stored in it. So if it dont have path then obviously haveNextPoint will be false.
    To check path length best place is delegates that fired when path recieved.


    Oh this one. Yeah i think i know this bug. Think it's related to adding and removing areas.
    It's only UI related and will fix itself after unity reload. Will try to fix it in next update.

    Well and this one i dont know yet. Will check this.
     

    Attached Files:

    Last edited: Jan 5, 2018
  24. shahzaib

    shahzaib

    Joined:
    Dec 14, 2013
    Posts:
    19
    Cool! Hope to see it sooner. All the best, Krokozor.
     
  25. itsnottme

    itsnottme

    Joined:
    Mar 8, 2017
    Posts:
    72
    I didn't check all of your example yet, but just wondering what you found strange :) just to improve my programming skills if needed :).
    Hopefully you are doing better now :)
    Lets say I want to check if the ai reached its goal, haveNextPoint would work, but it gives a false positive for few frames after SetGoalMoveHere.
    So usually haveNextPoint (after SetGoalMoveHere) would be true if the goal wasn't reached and false if the goal was reached, but not for the first few frames, before the path is updated.
    I know it's not a bug and it's correct. I was just wondering how to get a sure way to check if the goal was reached without false positives, since checking distance between ai and goal wouldn't work because of the removed points smaller than properties radius.
     
  26. Krokozor

    Krokozor

    Joined:
    Sep 27, 2014
    Posts:
    63
    Well. Im talking about handling conditions mostly. Only thing in patrol case need to get another path is reach end of current path. And you can check if you reach it where you remove points from path.
    Also in example i am also overcomplicate a bit :) With fresh head i changed it slightly to make sure agent wount skip patrol points.

    Kinda not that much:( Probably will spend some more time in hospital before full recovery. But will be more prepared this time.

    Eh? But cheking is AI reach goal best place are where points are removed.
    Lets say you check it by distance. Then if you want to see if it was end of path then just look if there points left in path.
    Code (CSharp):
    1.      
    2. if (Vector2.Distance(agentPositionVector2, agent.nextPoint.positionV2) < agent.properties.radius) {
    3.     agent.RemoveNextPoint();
    4.     if(agent.haveNextPoint == false) {
    5.     //We reach end of current path
    6.     }
    7. }
    8.  
    If you want to check if AI are already there then you probably just need to compare distance to goal point before you try to get path there.
    So best place to check if AI reach goal point is AI itself. Cause it's know it's move goal before it tell it to navigation.

    In next update i will store goal point in Agent cause it's kinda handy for many reasons.
     
  27. itsnottme

    itsnottme

    Joined:
    Mar 8, 2017
    Posts:
    72
    Well there is usually a difference of 0.5-1.5 in distance between ai and goal when "it reaches the goal", so its hard to check. I presume it's because some points are removed; if not let me know, that would mean there is a problem.

    An example of what I meant:
    Code (CSharp):
    1.    //Didn't reach goal
    2. if (pathAgent.haveNextPoint)
    3.         {
    4.         }
    5. //reached goal
    6. else{
    7.     }
    In the above example, let's say I called SetGoalMoveHere.
    Since the path is still updating, else will be chosen for 2 or so frames instead of if. Then after the path is updated, if will be called normally until the path is reached.
    Also, I know in the above code there are workarounds, but in some cases knowing that the goal is reaches is needed.
     
  28. zenGarden

    zenGarden

    Joined:
    Mar 30, 2013
    Posts:
    4,536
    Hi @Krokozor
    I didn't looked at code, but could the cover finding system work without navmesh components ?
    I got some performance spikes, when navmesh is generated in realtime , or testing the scene with the other Navmesh Agent using covers. It is some specific settings to lower performance spikes ?

    Would it be possible to store save all cover data in the map navmesh ?
    This could become usefull to automatically bake covers and get covers on the grid based on character position/

    Some idea i got is to have decals throw on terrain alter the navmesh cost like terrain splat textures costs.
    Anyway, this is a great plugin with interesting new functionnalities.
     
    Last edited: Jan 9, 2018
  29. Krokozor

    Krokozor

    Joined:
    Sep 27, 2014
    Posts:
    63
    I dived to collision avoidance for some time. It somewhat working but i need some more time to solve issues like deadlock or when where is no optimal velocity at all. It a bit bizzare topic. There is bazillion research articles on it but it all mostly too fragmented to be userful.


    Well. It kinda hard to imagine how you made your AI in this case. For example i have AI that can take some items. It remove next points in 0.5 radius and take items in 1 radius. So firstly i check if item already can be reached by radius. if true then i test by raycast item visibility. If false then AI try to get path. If no path yet then it start to move towards item until it get path.

    But if you want i can add main thread path search for that case. Like i did with raycasting. Assume current state of navmesh are good enough and you really want to get path instantly.

    Also yeah. I need to expand path search and make it also faster. Also add different modes like "escape from there to safe distance" or "find nearest union with another agent"'. After next update it probably will be main goal.

    Hello zenGarden!
    It depend what you mean by "cover finding".
    Actual searching nearest cover done on navmesh. Because it referenced on navmesh cells as it content.
    But you can just generate covers if you want to. Pathfinder currently generates 3 things - navmesh, covers and grid. you can enable/disable generation any of it in Agent Properties.
    It's in AgentProperties file:
    Options.png
    It not that userful cause i still dont wrote proper code to extract this information in that case :) Will add it in next update.
    But you can take this information on your own right now.
    In K_PathFinder.PathFinder there is private static Dictionary<GeneralXZData, Graph> _chunkData
    and there is all current navmesh stored chunk by chunk.
    You can lock this dictionary and iterate through stored graphs. In graph there is just public List<Cover> covers where all covers of that graph stored. So you can take all covers from it.
    I can explain how PathFinder collect this information if you intrested. It's a bit dumb idea but seems to work fine.

    Perfomance spikes i have no clue where you get them. Since amost all done in threads i dont have noticeable spikes even on my android tablet i bought ~8 years ago.
    Is multithread enabled? (this options exist purely for troubleshooting) Also to reduce performance spikes you can use CPU version of terrain and collider collection since it all done in threads.
    This options are in PathFinder menu:
    Options.png
    Not threaded in that case are only collecting world information and connecting new chunks to navmesh grid. And it not that big operation to get large spikes from it.
    If you already enable multithread and use CPU version of collection information then you probably should use unity profiler and then tell me where spikes come from.

    Decals is cool idea and also thought about it. But right now i think unity dont have any good build in decal systems and im not that good to make it on my own with in short time. Later on i will add some gizmos to alter cost at sellected areas and also plan to add option to also use detail maps to alter move cost. So for example there will be layer with lower priority generated by splatmaps and layer with higher prioity generated by grass.
     
    Last edited: May 1, 2018
    christoph_r and itsnottme like this.
  30. itsnottme

    itsnottme

    Joined:
    Mar 8, 2017
    Posts:
    72
    Not sure if this is a known bug, but applyRaycastBeforeFunnel from time to time will have the ai slightly move in irregular movement, slightly to the left or right when nothing is in front. It is a huge improvement using the Raycast though.
     
  31. WinterboltGames

    WinterboltGames

    Joined:
    Jul 27, 2016
    Posts:
    123
    I have been using a very bad way of doing the pathfinding with this *Amazing* plugin, I won't lie it makes the game run at full 60 fps with no spikes but sometimes agents stop moving, the game crashes so, I wanted to ask what's the simplest way to make agents find a path and move on it also the simplest way to generate a navmesh in the scene on terrains.

    Thanks.

    code samples would be greatly appreciated too :)
     
  32. starikcetin

    starikcetin

    Joined:
    Dec 7, 2017
    Posts:
    218
    Are you planning to put this on GitHub?
     
  33. itsnottme

    itsnottme

    Joined:
    Mar 8, 2017
    Posts:
    72
    Hope you are doing okay with your second hospital visit.
     
  34. Arina_29

    Arina_29

    Joined:
    Apr 18, 2017
    Posts:
    5
    Hi, did it work with a navMeshAgent, for example, if you want to use SetDestination() function and did it work on android?
     
    Last edited: Apr 3, 2018
  35. itsnottme

    itsnottme

    Joined:
    Mar 8, 2017
    Posts:
    72
    By navMeshAgent, you mean the one by Unity? You don't need to use it, everything is in this asset.
    Also, yes it works in all devices.
    Check the example scripts for more info on how to get it to work.
     
  36. Arina_29

    Arina_29

    Joined:
    Apr 18, 2017
    Posts:
    5
    Thank you! ))
     
  37. Arina_29

    Arina_29

    Joined:
    Apr 18, 2017
    Posts:
    5
    How can I set the character controller to follow the path it finds. Because I am using:
    Code (CSharp):
    1. if (_agents [0].haveNextPoint) {
    2.                 _agents [0].GetComponent<CharacterController> ().SimpleMove (new Vector3 (_agents [0].nextPoint.x - position.x, 0, _agents [0].nextPoint.z - position.z).normalized * 0.5f);
    but it gets stuck when reaches the first point position, not the target position
     
  38. itsnottme

    itsnottme

    Joined:
    Mar 8, 2017
    Posts:
    72
    Please post your full movement code if possible.

    This is how I use it (slightly different from example)

    Code (CSharp):
    1. //set the target position to anything you need
    2.                             pathAgent.SetGoalMoveHere(player.position, true, true);
    3.                             if (pathAgent.haveNextPoint && Vector3.Distance(transform.position, pathAgent.nextPoint.positionV3)  < pathAgent.properties.radius)
    4.                             {
    5.                                 pathAgent.RemoveNextPoint();
    6.                             }
    7.  
    8.                             //have to check again incase a point was removed
    9.                             if (pathAgent.haveNextPoint)
    10.                             {
    11.                      //GetComponent<CharacterController>().SimpleMove (new Vector3 (_agents [0].nextPoint.x - position.x, 0, _agents [0].nextPoint.z - position.z).normalized * 0.5f);
    12.                      //or
    13.                       //rbody.velocity = new Vector3(pathAgent.nextPoint.x - transform.position.x, 0, pathAgent.nextPoint.z - transform.position.z).normalized * 5f;                            
    14.                             }
     
  39. Arina_29

    Arina_29

    Joined:
    Apr 18, 2017
    Posts:
    5
    Thank you so much, you really helped me a lot! )))
     
  40. itsnottme

    itsnottme

    Joined:
    Mar 8, 2017
    Posts:
    72
    Happy to help.
     
  41. PixelizedPlayer

    PixelizedPlayer

    Joined:
    Feb 27, 2013
    Posts:
    356
    Will this incorporate unity's job system for multi threading?
     
  42. itsnottme

    itsnottme

    Joined:
    Mar 8, 2017
    Posts:
    72
    The asset does have multi threading and you can choose how many max threads are used.
     
  43. PixelizedPlayer

    PixelizedPlayer

    Joined:
    Feb 27, 2013
    Posts:
    356
    I know thats not the same as whether it uses unity's job system and it's specialised compiler optimisations or not. I'm guess it doesn't - but if not i hope you can plan to support it.
     
  44. Krokozor

    Krokozor

    Joined:
    Sep 27, 2014
    Posts:
    63
    Sorry folks still no update :( Also thanks itsnottme for answering questions that i'm not answer in time.
    After new year i spend couple month to improve my health so some time no progress where done. Still now i feel much better so i returned to this project.
    I feel i need to explain whats going on right now.

    So. I tried to create dynamic obstacles. it kinda have very simple theory so it very easy to implement it at basic level. Theory is kinda small so i share it here. For example there is agent A and B and they have some velocity. We can take radius of A and B and sum them. If A velocity in direction of AB radius placed on B then it will collide at some point asuming B are dont move. To ajust to B velocity we can move this triangle to B velocity and then check if A velocity are inside this triangle.
    A.png
    Thats kinda it. If we combine all this triangles for nearby obstacles and sellect new velocity outside it then we wount collide with any of obstacles.
    There is some simplifications of this theory. For example we can just take relative velocity of A to B and check if it inside this triangle. This also will tell us if they will collide. And we dont need all triangle we can just take nearest point on this triangle
    B.png
    If we take this point and direction from relative velocity to this point we can get what delta velocity need to be applyed to base velocity so it wount collide with obstacles. Basically if we take all nearest sides of triangles and combine them we get similar to first result.
    Also there is lots of expansions of this theory you can imagine. For example if we know path of B and know it's curved then this triangle also became curved. Or it clso can be applyed to 3D. Or more neat things - for example we can fiddle with length of vector to nearest safe velocity so agents take only half responcibility to avoid each others. And so on.

    So. Agents can easly be avoided by other agents. Issue is - navmesh are not agent. it is static map of obstacles with neat shapes. To avoid it agent just need to not move towards shadow of holes in navmesh.
    For example Agent - A, have nearby obstacles marked as blue. If agent velocity outside blue or gray area then ot will never collide with obstacles. gray area are looks like shadows of blue, right?
    C.png
    And here i kinda stuck for more than month. How do i tell when velocity are outside holes in navmesh or it shadow?

    A) For example i can expand triangulation and put to navmesh not just graph of passable area but also graph to NOT passable area. Expand a bit how it's stored so simplify returning of siquences of points that represent hole. To draw this neat shadow of navmesh holes and then combine it with those triangles. But there is multiple issues:
    1) Navmesh are not one object since it divided to chunks. There is lots of junk in it borders to simplify further
    separation. So it's kinda hard to do without overhauling how graph stored right now.
    2) I dont see good way to simplify it. i still need to have any shape of allowed velocity change and also need to combine it with shadow of navmesh. Whole operation looks costly.
    3) Navmesh are 3D thing. Lots of issues also with that.

    B) Dont build whole shadow. Just take some samples using sort of raycasting. Then just take results of this rays and check them on shape of allowed velocity and check which one shorter. And then choose from this samples. There is also issues:
    1) Current raycasting are noot good enough for that
    2) Low numbers of samples are big issue.

    So. Firstly i tried variant A. This was huge failure. I tried to rewrite how navmesh stored. Then i tried to rewrite how chunks of navmesh are connected. No. Just no. It is work for another 2-3 month. It kinda worth it but kinda not. Then i tried variant B. Optimising raycasting was somewhat hard. I need to make it robust as possible and make it less work as possible. Spend around 3 weeks doing just that.
    Result was kinda good.
    Unity 2018-03-24 01-04-43-37.png
    Raycasting now fast and robust enough to plug some holes with it.
    Right now i kinda have prototype of variant B.
    Unity 2018-04-05 22-57-14-82.png
    But i still need to expand it a bit. Need more optimisation and check how it works. Also need to make more separated components for agent and uncontrolable moving obstacles. Cause obviously rolling boulder wount avoid agent but agent will avoid it and it need to take in consideration that boulder wount do same thing.
    Final thing will looks like this:
    Agent will have some field "desired velocity" and it will expect it from you. And after tick of solver you will get some "optimal velocity" agent need to maintain to avoid obstacles.

    Will check this. I also find out that raycasting are not always works good.

    Well thats an issue. There is some things still can go wrong. Is there is some errors in console?
    I will expand examples in next update. Will add some different ways to implement same thing.

    Yes. I will put it in some sort of public repository. Probably after next update. Cause i'm not planing to close code or make this project commercial.

    Actually i still dont check new job system. I know what it does. Whole pathfinding are kinda separated from what unity does so it probably won't be that hard to use it while using new job system.

    Also it will be somewhat expanded in next update. I made threaded code a bit more clean. Also i added some main pathfinder thread that separated from unity main thread. So only thing in main unity thread now is sampling world data. And all connection-disconnection-destruction and other things are now one after another but in separated thread. Now all process are a bit more streamlined and pathfinder wount try to do all things at same time. Less thread locks and less bugs. And more easy to add some other code that not interfier with current one.
     
    Last edited: Apr 7, 2018
  45. WinterboltGames

    WinterboltGames

    Joined:
    Jul 27, 2016
    Posts:
    123
    There are no errors in the console just suddenly while the game is running at 60fps it freezes and boom, crash and I double checked that my code doesn't have anything that could cause freezes (no infinite loops or memory leaks).
     
  46. Arina_29

    Arina_29

    Joined:
    Apr 18, 2017
    Posts:
    5
    Can you tell me please what options in the menu are responsible for showing the navMesh, because the navMesh is created but the agent shows that there is no path.
     
    Last edited: Apr 11, 2018
  47. Krokozor

    Krokozor

    Joined:
    Sep 27, 2014
    Posts:
    63
    E1.png
    1: Check if "Do debug" are enabled. Also enable profiler if you want to read what and when created in console.
    2: Enable everything in Cell cathegory.

    Then everything PathFinder create will be shown in scene.
    Also dont remove "_debugerScene" from scene cause this object are used to draw all this things.
    Also check if "auto update scene view" are enabled. It enabled by default. (it exist cause you can debug really heavy stuff if you enable "Full Debug". You probably want to do manual updating in this case)

    If you creating navmesh from this menu then check if properties you planing to use are placed in most top slot.
    I think i broke "Scene GUI" in last update though.

    well. i dont even know where to start unrolling this issue. do you tried to turn off raycasting in path generation? is navmesh created on procedural level?
     
    Last edited: Apr 13, 2018
    WinterboltGames likes this.
  48. WinterboltGames

    WinterboltGames

    Joined:
    Jul 27, 2016
    Posts:
    123
    Yes, but it's not really a procedural world it's just static with some moving platforms.
     
  49. itsnottme

    itsnottme

    Joined:
    Mar 8, 2017
    Posts:
    72
    I am getting these Null References when moving between scenes. Does not happen if I run the scene with PathFinder directly.
    I am currently using 2017.4.1f1, but I believe it was there before upgrading.
     

    Attached Files:

    • 2.PNG
      2.PNG
      File size:
      74 KB
      Views:
      159
  50. Krokozor

    Krokozor

    Joined:
    Sep 27, 2014
    Posts:
    63
    Alright. This thing now somewhat working. Looks jerky.

    Here is no actual pathfinding. Just navmesh raycasting and velocity obstacles. Will add some code with couple very important features and probably leave this featurewise at this point. Cause there is lot can be added to improve results but these improvements will be out of context of people projects. So i will add features but as something optional in next updates. Better spend time to optimisation.

    I mean. Is it predictable when it's happening?

    Oh this one. Yes it was. Thanks for pointing it out.
    In PathFinder/Debuger/PFDebuger.cs there is Debuger_K.UpdateSceneImportantThings()
    It probably lost reference to settings and in that case also can lost reference to sceneObject.
    Try add at the begining of UpdateSceneImportantThings() something like
    Code (CSharp):
    1. if(settings == null | sceneObj == null)ForceInit();
    Or in PFDDebugerScene.cs in OnEnable() add DontDestroyOnLoad();
    So this object will call it anyway.

    I tested this couple times in my pet projects. No clue how it slip past me. Will test changing scene before roll out next update.
     
    itsnottme likes this.