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. lofwyre

    lofwyre

    Joined:
    Apr 19, 2007
    Posts:
    138
    Hi. Is there an inbuilt function for an agent to know when it should call PathFinder.QueueGraph? Like when it's a certain distance from the border of a navmesh or is this something we just manage ourselves? Also if a navmesh exists and I build over the top of it does it cost the same in performanceas the first time or is it faster the second time because it has less to do?

    Thanks
     
  2. Krokozor

    Krokozor

    Joined:
    Sep 27, 2014
    Posts:
    63
    Spend couple days refactoring path generation. Found bizzare bug i was reported some time ago. In some bizzare cases funnel algorithm can stuck on wrong node and sometimes point to wall at corners. I think now it's fixed and also better optimized.

    Edit:
    Added way to modify cost for path generation. Looks cool. Not very accurate but still userful.


    Well. Presumable it should be managed by user. I have no clue what conditions are and what space should be checked. Though i can write some code to add checkbox "around al teast X units around agent navmesh should be automaticaly generated". Right now kinda best way is to just constantly queue some navmesh around.

    Though out of curiosity: How come you need this? I mean even if you doing some sort of open world where is everything is dynamic and there is some creatures walking around, at least you have some sort of observing point. Like player. And navigation should be generated around it in first place.

    Same cost. There is not much data can be reused anyway. For example i could save voxels for static meshes but it a whole lot of voxels. Even something small like this contain this much.
    Unity 2018-11-06 14-45-21-89.png
    And this is just 50x50 in 10 units. Imagine how much memory eat up small forrest.

    But there is still some difference in first and other generations. Cause technomancy like Just-in-time compilation exist. And PF greatly benefit from it.
    Also most memory intensive parts have array pooling (array reused over and over again) so usualy only couple first generations allocate new arrays and this is take some perfomance only at begining.
     
    Last edited: Nov 7, 2018
    FerMG likes this.
  3. christoph_r

    christoph_r

    Joined:
    May 20, 2013
    Posts:
    467
    Are you considering C# jobs + Burst for this at some point in the future?
     
  4. Krokozor

    Krokozor

    Joined:
    Sep 27, 2014
    Posts:
    63
    Some information on next update. It kinda slow. It kinda exist. But those who test it report some errors that for some reason i cant catch. There is some cases when position on navmesh obtained incorrectly. Ist not a realy big deal when it comes to navigation. But not for navmesh raycasting. And part of navigation and local avoidance build on top of raycasting.
    Right now im keep working on better way to getting nearby navmesh position. I was planing to fix it from start cause it kinda big problem in current way of doing things. But since navmesh build in grid like pattern i cant update whole "map" at once. Ability to change parts of navmesh are kinda important. So after whopping 8 (!) failed attempts to fix this at 9th it was kinda success. Now there are 3 types of search layered on top of each others.
    1. like old one. pathfinder check if position inside rasterized grid. if it is - it check list of cells that lay there.
    2. in same grid now also exist grid of empty space. so if position taken in empty space then it return closest cell to that grid.
    3. if there no navmesh at all nearby it just get nearest non empty chunk and check nearest position on navmesh hull.
    Unity 2019-01-11 09-28-50-12.png Unity 2019-01-11 09-28-52-63.png
    There is way to debug it so this is how it is looking now.
    Big part of problem was its optimisation. Its kinda big amount of data that need to be updated when chunk of navmesh generated. Cause when 1 chunk updated also i need to update 8 its neighbours. Cause neighbours also need to know if their map is updated in pressence of new chunk. and all those neighbours need information in all their neighbours. information from 5x5 chunks need to be processed in order to update just 1.
    There is some tricks in order to reduce amount of work. For example if chunk dont have any empty space - it dont need to be updated. So only multi-layered complex chunks are updated fully.
    Right now updating this map takes 9-12% of total generation time. But there now lots and lots of array pooling in pathfinder so overall there is gain of 15% time that spend on that new feature. So nothing realy changed on navmesh generation perfomance. (which is neutral outcome :))

    Also there was other attempts to solve this issue. For example in 6 attempt position sampled in grid corners. and then checked closest and farest navmesh position. And anything outside it excluded from this position. result was neat and accurate.
    Unity 2018-11-20 06-00-30-18.png Unity 2018-11-19 20-50-04-14.png
    But it takes too much time to be computed. Like from 50% of navmesh generation up to 200%.

    Also also i think i finished implementation better way of extracting information from navmesh. Navigation gain new features. Information extraction sepparated into its own thing outside Agent. So now there are way to search path without dealing with agents (and Monobehaviour as result).
    Though local avoidance right now only with agents. I kinda need to change this. So agent will be just "default way of doing things" not "only way".

    Overall it kinda finished but there kinda bugs that i dont understand why and where. And new year was kinda harsh and i kinda burned out. And kinda dont know why i cant reproduce some bugs. Right now best plan is to make more complex example scene where all parts of pathfinder will be tested at same time. For example let some rudimental AI play CTF. This will probably break things in way where i can see it.

    It kinda big topic to implement relatively recent features in unity.
    In short: yes.
    In not short:
    • I planing to implemet sort of ECS support in update after next update. It kinda not hard to add sort of "struct" that contain it target position and how it should be searched and index of it path in some global array. And let pathfinder compute it in big batch. (Though to get most of it i also need to change how pathfinder stores it graphs)
    • Jobs are kinda nice thing. But kinda have no point on its own right now. Because pathfinder already compute it results in multiple threads and have its own pipeline in sepparated thread to reduce load to unity thread. So no real point in moving work from pathfinder threads to jobs threads. Also as far as i understand potentialy it can hurt. Cause in pathfinder pipeline i know when navmesh won't be changed. So it used as is. And jobs have neat feature - copy information that need to finish job to all jobs. And no point to do this. But it not that hard to move this all to jobs system. I just need to reimplement current pipeline in it. Though syncing it in main unity thread also bad idea cause even if threaded - pathfinding are heavy process. And work like "finishing graphs" or "local avoidance" also added up there. As benefit - if it all sync in main unity thread you can get path in same frame you ask for it. But it kinda not that big benefit.
    • Jobs + Burst are kinda technomancy and very cool. But to implement it - way of storing navmesh need to be heavy refactored. I plan to do this on its own. In current state there is 4 major parts in navmesh generation:
    1. Collider rasterisation into voxels
    2. Use voxels information to apply it to other voxels. like searching neighbours or make offset from borders
    3. Make raw contour graph from voxels
    4. Make navmesh from this contour
    On asset store there is refactored 1 and 2 for the most part. This parts kinda in okay shape. In current test version 3 also in okay shape. In update after next update i plan to finaly refactor 4. And this will move this project from alpha to beta state. After this there is multiple things i can do. Change graph to more perfomant version also in it. So Jobs+Burst can be a thing.
    But there are kinda multiple things i can do at that point. For example i can implement more features in controling navmesh generation. Adding user defined connections also can be nice. So for example "ladders" or "jump spots" can be user defined. Or spherical worlds. Or better way to shove "minecraft like" voxel worlds into navmesh generator so it generated in far more optimal way. Or make chunks 3d. So multilayered worlds have better perfomance and this partialy solve 2 above problems. Or implement GPU raycasting so navmesh samples will be much more userful. Or 2d support. And lots of other ideas. And they all cool.
     
    Last edited: Jan 11, 2019
  5. Firlefanz73

    Firlefanz73

    Joined:
    Apr 2, 2015
    Posts:
    1,016
    Hello,

    I have a RPG with a Environment in minecraft style. Not blocks, but chunks created randomly procedural. No navmesh or something like that.

    My Monsters / Animals / NPC have some very simple follow, just walk around or flee behaviour with a script I made myself.

    If the Player runs around a larger obstacle this is a Problem because my Monsters etc. are so stupid.

    Could this asset help me with that? Tell the Monsters where to go if they stand in front of a tree or a builind?

    They should not know the whole world but Maybe could use raycasts to know their Closer area? I am not searching a complete clever pathfinding for a maze or something, just a way to have them follow if there are some obstacles in Closer distance…

    Thanks for some info and your free asset :)
     
  6. christoph_r

    christoph_r

    Joined:
    May 20, 2013
    Posts:
    467
    Thanks for the detailed response and great to hear!

    Yes, indeed, it may be a good idea to wait for the API to stabilize and for more documentation. I do agree that if you already have a multi-threaded graph generator implementation (even though it probably won't work in .NET 4.6 because threads got replaced with async?) jobs alone won't really be that beneficial. The real power will likely come from parallel jobs which nicely balance/distribute the load for pathfinding when there is a larger amount of agents continuously updating their paths.
    And of course I completely see that there are other cool features that could be implemented - I personally think a pathfinder using ECS + jobs + burst in C# (or HPC#, as Unity fancies calling it now) would be super cool. Unity probably plans to do that _at some point_ (just as they plan to write a physics system using HPC#) but that's likely quite a way off. But of course that's all personal preferences and I'll look forward to future updates, whatever they are :)
     
  7. MicCode

    MicCode

    Joined:
    Nov 19, 2018
    Posts:
    4
    Hi Krokozor, really cool system you have here, and it's free!
    Do you plan to sell this asset at some point?
    If not, have you considered putting the project on Github and accept pull request?
     
  8. hsjaaa

    hsjaaa

    Joined:
    Apr 30, 2016
    Posts:
    13
    Hi there, @Krokozor
    Tried your asset and found that if local avoidance is used with navmesh, seems the agent would only move in a single chunk, can't move out of that.
    And sometimes could get chunkIteration too large error, appeared only about once while doing the test the agent is baked on the navmesh, and this could be encountered in other scenario when call SetGoalMoveHere and set raycast to true.
    Not sure if my implementation is wrong or it's bug. Didn't include in your assets in the test file since it is too big to upload, hope it works.
     

    Attached Files:

  9. Krokozor

    Krokozor

    Joined:
    Sep 27, 2014
    Posts:
    63
    Yay it's finaly happen! Update 0.50! PathFinder is still in it's "public Alpha" state cause it still missing some important key features and triangulation still need to be refactored.

    Only around 1/5 of passed time was actually spend on introducing new features to PathFinder. Rest of time was spend on catching bugs, huge internal changes related to data storage, optimisation, testing (lots of testing) and again catching bugs from all this changes. Some classes was rewritten more than 2 times.

    Old serialized data will be somewhat broken again.

    0.50:
    Whats new:
    * Added "Modifyer Group" thing. This is way to change costs of nearby navmesh without rebuilding it. (For applications where accuracy don't need to be exact)
    * Added "Layers" to include or exclude certain parts of navmsh from serach.
    * Added way to store Vector3-like data on NavMesh. Points and covers now considered as this sort of information. It also can be user defined. More in examples and comments on NavMeshContent class
    * Rewriten how information requests made from navmesh. There are now NavMeshQuery and classes derived from it to perform narrow search
    * Added NavmeshPointQuery to perform Vector3 point search. All results returned by NavMeshPointQuery is PointQueryResult<T>. Also it contain "weight" as navmesh distance
    * Added NavMeshPathQueryGeneric to perform Path serach
    * Added NavMeshPathQueryTargetArea to perform PathSearch for target Area
    * Added NavMeshPathQueryTargetPoint to perform search to target point type
    * Added NavMeshPathQueryVectored to perform random path search in some general direction
    * Added PathResultType.BestFit flag for cases when returned path dont reach target point and closest to target was chosen
    * Added PathResultType.InvalidExceedTimeLimit when search performed for too long time. Time can be changed by NavMeshQuery.SetMaxExecutionTimeInMilliseconds
    * Whole bunch of renaming related to BattleGrid, now is is just "Samples"
    * BattleGrid system is now searched by NavMeshPointQuery. Now it drasticaly changed and renamed to CellSamplePoint. Results no longer have connections between them and appear as struct. Old system go to drawing board and will reappear later on in different form
    * PathFinderAgent.SetGoalFindCover now have more options that implemented in NavmeshPointQuery
    * PathFinderAgent.RemoveNextNode and all variations now have optional parameter "retain last node" in case you dont want to remove last node
    * Agent Properties now contain "voxel bleed distance" option to change how far area and passability should be priortized over less prioritized one
    * PathFinder.TryGetClosestCell now also return more information in form NavmeshSampleResult struct that also tell if result position was offseted by cell usability
    * Path now have float pathNavmeshCost that contain aproximated navmesh distance of that path

    Whats fixed:
    * Refactored code related to contour generation. Slightly improved time of navmesh generation and whole lot less garbage now generated
    * Path now return correct flag when end point outside navmesh
    * Path now return some missing moving points related to jump connections
    * Fixed rare path issue when path funneled over same chunk corner and returned incorrect path
    * Removed debug messages from Agent.RemoveNextNodeIfCloserSqr version for vector3 checks
    * PathFinder.TryGetClosestCell now can return proper result even if sampled far outside navmesh (if it closer it more accurate)
    * Fixed IndexOutOfRangeException when Quicksort performed on empty chunk
    * Newly created Agent Properties no longer cause NullReferenceException when IgnoredTagsContains are checked
    * Recieveng Cover information no longer return NullReferenceException
    * Generation unwalkable area within step threshold no longer bleed below passability into it (hope i did not break anything important while doing that)
    * Fixed rare null exeption in drawing gizmos after changing scene
    * Fixed SettingsDraw null exeption that occure sometimes after serialization
    * Fixed major bug in initialization of pathfinder that lead to constant creation and destruction of primitive GameObjects
    * Fixed very long locks of object if local avoidance update called in single thread mode
    * Chunk Graph borders now contain correct empty edges
    * Local avoidance now exclude navmesh borders from velocity space a lot more accurate
    * Local avoidance now also move to borders of disabled navmesh parts
    * PathFinder folder now can be moved inside project
    * Changed a lot how PathFinder initialized. Not it is Slightly less dependent on it's helper when first time loading into scene
    * Async Scene loading now should correctly clean PathFinder data
    * Raycasting now should not fail to raycast cell borders

    Whats changed:
    * Local Avoidance now have it's own agent and sepparated from MonoBehavior agent
    * Namespaces better organized
    * Added more comments in important parts of code
    * Path.owner no longer Agent (cause it returned to query instead) now it is implemented as "IPathOwner" interface that returns fallback position.
    * Slightly improved time of path generation
    * Cover system is now searched by NavMeshPointQuery
    * Changed how Cell map of navmesh stored to be far better optimized. But old serialized data wound work with that. Rebuild navmesh is you save it
    * Improved perfomance for searching closest position on empty spaces
    * Removed PathFinderAgent.SetGoalFindNearestArea cause it was transfered to related query. Create query and use it instead
    * PathFinder.GetPath, GetCover, GetBattleGrid, GetPathAreaSearch etc now obsolete and was removed
    * Some junk code from PathFinderAgent was removed
    * Grammar changes here and there
    * Around 10-15% perfomance increase due to better pooled object management
    * Around 30-45% better memory management due to reducing amount of pooled types and better nearest array size clamping
    * Some classes now became part of PathFinder main class as partial classes
    * Rewriten serialization once again into more readable state
    * Raycasting now obstructed by ignored cells
    * removed "nearby agents" from agent
    * removed "nearest point on navmesh" from agent
    * removed agent variation for raycasting
    * changed output for PathFinder.TryGetClosestCell to struct
    * Added slightly better Manual
    * Celling "Clamp to cell borders" is now mandatory to fixmultiple problems. Instead if ahent outside navmesh first added position is nearest point to navmesh

    Biggest change is how information of navmesh is requested. Before agent was central point which requests information. Now it shifted to more specialized queries that more abstract way to take information from PathFinder and Agent is now redundant but it still here as "default" way of doing stuff, not "only way".
    There is 2 main queries at this moment: GenericPath and Point queries. And some example queries to show how information can be extracted from PathFinder in safe way.
    Though i end up copying information back and forth from PF thread to Unity thread and it probably will be changed later but right now this is safiest and most generic way to extract information from PathFinder.

    Next biggest addition is now in PathFinder there is generic way to store Vector3-like information. Battle-grid and Cover system was all reimplemented as part of it. Also you can register your own information if you implement "ICellContentValueExternal" interface and call some magical functions or just derive from "NavMeshContent" component. This type of content after it registered on NavMesh is searched by "Point" query i mentioned above. Result returned inside struct that also tells you distance to that content on NavMesh. It is not very accurate but userful to evaluate distance to multiple points at same time.
    There is 2 ways to calculate navmesh distance: adding to each point "distance" from gate it was searched or not. I.E. more accurate but expensive and siuted to close distance and quick and dirty for bigger area and lower data dencity.

    Dynamic cost change was multiple times shown above. Awesome thing. Spend some time optimising it and combining with all things above. Way to influence localy results for path and point queries.

    Some old bugs was fixed. Yep. I think there right now imposible to get "ray did not hit any cell border". And local avoidance should no longer stuck when it generate agents tree.
    Also spend some time fixing actual navmesh borders avoidance. Now agent no longer uses that half backed way with raycasting and a lot more accurate in not colliding with navmesh borders. A lot of thought was put into this.

    And final big feature is layered operations. Some navmesh parts can recieve different layers. And you can include or exclude parts of navmesh per operation. All major features can use it: pathfinding, raycasting, local avoidance and point searching.
    It will be expanded later on. Right now it is only one way to set layers and it is by using advanced areas.

    There is whole lot internal changes related to searching nearest navmesh position but that was explained on top. And realy a lot of refactoring. There now a lot (really lot) of internal array pooling and it is better optimized, pathfinder now have some cool data structures to help optimize it later on. Some things that was objects before now stored as structs in arrays so there now more benefits from processor caching. For example connections between cells on navmesh now structs. PathFinder now triggers GC a lot less.

    Also new Manual. It far from complete but better than before. And new examples.

    Also-also Agent now only a wrapper for multiple classes. All it previous functionality now sepparated to different things. Path, Cover and Samples(BattleGrid) now implemented through Queries. Local Avoidance have it's own agent right now. And will be probably reduced to struct-like agent in future updates. So now it not nesessary to use only provided agent. You can create your own agent with Blackjack and Hookers. It just have some nice stuff in single place and some nice UI.

    I hope there is no more such big refactoring in near future. This was really exhausting. With Queries that helps get information from navmesh and new way of geting nearest navmesh position there now opens 2 cool possibilities: make flood fill navigation so agents know where to go just by sampling it's position on NavMesh. And struct-based agents. Making ECS-friendly agents now not realy that hard. And some people probably will implement it without waiting for me to do it.
    Also some big plans on optimising terrain. Right now just that can take ~50% of navmesh generation time but it can be reduced a lot. And i probably need to add ability to read grass map long time ago. Will probably do it along the way.

    There was lots of "last minute change" related to how PathFinder starting up. Expect some bugs related to initialization of PathFinder and please report about them.



    Big thanks to Mark Nasr. He helped me a lot reporting most bizzare bugs and testing stuff.


    Nah threads never will be replaced. There is still ability to create new threads and thred pool.
    There is no issues with ECS. But jobs looks kinda useless for this asset right now. All calculations done in sepparated threads already. It at the point when PathFinder thread and Unity thread like never in sync. Some parts potentialy can be improved with jobs but only when unity make them userful outside Unity thread. Burst is awesome thing but it have same issues - i have no clue how to use it outside Unity thread.
    Although ECS agents can be potentialy created with current PathFinder state. Query can be easly expanded to serve multiple struct-like agents and calculate paths for them at same time. And actualy i have neat class to hold multiple paths at once. So that is definetly possible.

    Probably not. There only 2 possible reasons for me to sell it:
    1) If i see possibility to improve this asset by using money.
    2) If my life is in danger and money can solve it.
    I will probably put this asset to GitHub at some point but it really-really hard to read inside. I will probably do it when i finish refactoring critical parts of code like every 2-3 months. This is that type of code that written by a single man.
    Although i will happily accept advices, code, whatever any type of help.

    That one was fixed for sure in current build. I dont think there is way for agent to start raycasting outside it cell. Also local avoidance now dont use raycasting and a lot less prone to stuck inside some narrow spaces. Though general local avoidance is not improved much.
     
    Last edited: May 14, 2019
  10. tjoshi

    tjoshi

    Joined:
    Nov 1, 2016
    Posts:
    4
    After hearing a lot about this asset, I finally downloaded it and as soon as I imported it, I was welcomed with 6 errors.

    1) Assets\PathFinder\Generation\Graph\Triangulator\GraphTriangulator.cs(141,34): error CS7036: There is no argument given that corresponds to the required formal parameter '_worldPos' of 'Node.Node(bool, Vector3, int, int)'

    2) Assets\PathFinder\Generation\Graph\Triangulator\GraphTriangulator.cs(152,51): error CS1503: Argument 1: cannot convert from 'Node' to 'K_PathFinder.NodesNameSpace.NodeAbstract'

    3) Assets\PathFinder\PathFinderScene.cs(319,21): error CS0619: 'Graphics.DrawProcedural(MeshTopology, int, int)' is obsolete: 'Method DrawProcedural has been deprecated. Use Graphics.DrawProceduralNow instead. (UnityUpgradable) -> DrawProceduralNow(*)'

    and a bunch of the same errors above in different script. Please fix this dev.

    Editor Version: Unity 2019.1.5f1
     
  11. Krokozor

    Krokozor

    Joined:
    Sep 27, 2014
    Posts:
    63
    I kinda took some time from my work hours to push out last update. So i was kinda busy with my work.
    Now i yet again have some free time to work on PathFinder.

    Next update probably will be a lot smaller (i hope) and will be focused on improving most noticeable flaws that more or less easy to fix.

    Right now working on improving workflow with Unity Terrain. Changed terrain rasterization algorithm into slightly less accurate but a lot faster one. Before terrain took around 40% of time, now 1-2%. So large open spaces now generating noticeable faster.
    Added multisampling to reading terrain texture. Now navmesh no longer looks like jagged mess when resolution of alpha map and voxels mismatched.
    Added ability to read detail maps so grass also can affect navmesh. So agents now can avoid or hide in tall grass. (What a time we live in. AI can actually use grass in games :))
    Unity 2019-06-07 17-14-25-83.png
    Probably need to add more settings with trees. It's kinda dull that trees can be only unwalkable.

    Also local avoidance for sure need more work. Probably will spend some time with it.

    Also also reported that Mac users have troubles with scrolling in Manual. And i actually dont have Mac to perform tests. Anyone have any advice how to fix it?

    I wonder where you hearing about this asset :)
    Sure i will look into compatibility with more recent versions of Unity. It was tested mainly on 2018.4 with 3.5 Net. But i guess this slip past me.

    Which version of Net you using?
     
    Last edited: Jun 7, 2019
    StevenPicard likes this.
  12. tjoshi

    tjoshi

    Joined:
    Nov 1, 2016
    Posts:
    4
    Thanks for the reply. I have a few friends who tried out your asset and were pleased by the pathfinding capablities.

    I am using .Net 4.x, maybe that's the issue. I have a lot of dependencies or else I would've switched it back to 3.5.
     
    Last edited: Jun 11, 2019