Search Unity

  1. Click here to see what's on sale for the "Best of Super Sale" on the Asset Store
    Dismiss Notice
  2. Good news ✨ We have more Unite Now videos available for you to watch on-demand! Come check them out and ask our experts any questions!
    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

    14 vote(s)
  2. Fix bugs and make features

    16 vote(s)
  3. A bit of everything in small chunks

    7 vote(s)
  4. Do all. Whatever time it takes

    11 vote(s)
  1. lofwyre


    Apr 19, 2007
    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?

  2. Krokozor


    Sep 27, 2014
    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.

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


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


    Sep 27, 2014
    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


    Apr 2, 2015

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


    May 20, 2013
    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


    Nov 19, 2018
    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


    Apr 30, 2016
    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


    Sep 27, 2014
    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.

    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


    Nov 1, 2016
    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


    Sep 27, 2014
    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


    Nov 1, 2016
    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
  13. Chifilly


    Nov 8, 2012
    I'd love to be able to use this asset, but it seems to be horribly broken in 2019.3.0a8 (either that, or there's something interfering with it in my project, or both).

    The first issue I have is if I build a navmesh (testing with a 3x3 grid of size 10), it doesn't generate in all of the chunks, and I can only use build once. If I press it again, or use the remove and rebuild, it clears out all the data and doesn't generate a new one, and hitting build does nothing. I didn't change any other settings except the build area.

    The second issue I have (which is a major issue) is if I have attempted to build a navmesh and try and enter play mode, Unity freezes up then crashes. No warning or error messages show up, it just crashes. I haven't even got around to testing navmesh generation in code, because in the process of trying to figure out how it works and whether it will fit my purposes, it crashes when trying to play. The same thing happens with the example scenes, I can enter play mode once, maybe twice if I'm lucky, then after that it crashes Unity (and some of the scenes spam a lot of warnings and don't work).

    I have no idea how to find out what's causing the crash. I fixed one of the warnings myself (a very trivial issue, since the warning told you what needed changing) but nothing indicates what the cause of the crash is, and I don't even know how to go about debugging it.

    Just tested this in 2019.1.10f1 and it seems to work (I couldn't test my project because it horribly breaks in an older version of Unity due to some preview packages I'm using, and Unity not liking serialised assets from newer versions being used in older versions)
    Last edited: Jul 21, 2019
  14. Krokozor


    Sep 27, 2014
    After little fixes here and there i start improving local avoidance. Moved local avoidance agents to structs. Now there is no local avoidance agent class and it is handled by IDs. This improved some perfomance.
    Added some offseted space. When agent free velocity space is too small it slightly change it's free velocity to add little space to avoid other agents. And use perlin noise to get random direction inside that new space. This help to move agent at least in some random direction if it is stuck.
    Fixed some general situations like proprity for agents on corners. Now if agent have hole in navmesh on it side it considered as priority agent and always avoided by others.

    Also started little research on managing crowded situations. Agents with relatively simmilar direction and speed can be combined into "groups" and treated as single agent. This remove need for agents to avoid each others inside group. Potentialy group can shift it shape and maybe behavoir? So for example it can assign group leader and other agents just follow leader while moving in line. This potentialy can improve local avoidance in some really crowded situations.

    Though it have some limitations. Agents with different radius can have really heavy math if they are part of same group. So right now only works with agents of same radius. Biggest issue is finding convex hull of group.
    group hull.png
    I know how to find red lines but this operation have a lot of steps or need to be brute forced. Maybe there is some way around.

    Will check this issue. Seems like with Unity 2019.X PathFinder have lots of troubles.

    Wow thats some big bug report. I know it have some initialization issues in builded projects (kinda hesitate to push second update. cause this issue is somewhat fixed but i'm in middle of little research project on local avoidance i mentioned above. it is hard to work on different things at once)
    PathFinder can potentialy stuck on scene change. It have little internal state machine to prevent generation of new data while scene changed. This is done to prevent issues with async scene load but Unity dont have any guidelines on how to handle this. Some events works only in editor, some events have different behavior on unity load and after unity load and some just dont work or dont exist in older versions of unity and i have no clue how to make reverse compatability in this case. And PathFinder kinda sensitive to this kind of issues cause it interact a lot with unity API and need to have strict initialization order since it live not in main thread.
    Most of issues handled by little internal state machine. You can control it with:
    Code (CSharp):
    1. PathFinder.ChangeTargetState(PathFinder.MainThreadState.NormalWork); //force pathfinder to enter it's normal state
    2. PathFinder.ChangeTargetState(PathFinder.MainThreadState.ClearNavmeshAndGeneration); //clears navmesh and generation queue but dont prevent adding new work
    3. PathFinder.ChangeTargetState(PathFinder.MainThreadState.ClearNavmeshAndGenerationAndMetadataAndStopWork); //clear all work queue and prevent getting new work
    4. PathFinder.InitCurrentScene(); //this function is private but you can make it public. this will force pathfinder to init in current scene
    I think i added this before i released previous version.
    State change handled in queue so you can stack multiple state changes one after another.

    And crashes sounds like this will be fun bug to catch. Maybe it is related to threading? Or termination of threads? Probably to fix this i should add propper thread manager and dont rely on thread pool.
    If you have some time please check if it craches with disabled multithreading. For that go there
    and disable this checkbox. This will force PathFinder to run in main thread in slightly different pipeline. Maybe it will not crash and show something helpful in console.
    Last edited: Jul 22, 2019
  15. Chifilly


    Nov 8, 2012
    Okay, after disabling multithreading it worked for longer, I could start and stop the scenes a couple of times, and I could view 3 example scenes, and then it locked up Unity, but this time it just stays frozen, and I can't interact with it anymore and I have to kill the process. It also allowed me to generate navmesh properly, and I could use build and remove and rebuild as much as I wanted. However, it also takes a lot longer to enter play mode with multithreading disabled.

    That's only with the sample scenes though, with a basic navmesh in my scene, it doesn't seem to crash or freeze (I've tested it a few times now). I'll do some more extensive tests when I have a bit more time. It would be great if I could use multithreading though, since there seems to be a noticeable speed difference.

    It seems like 2019.x is a bit of an issue, but just being able to use it now without it breaking means I can properly play with it and see if it fits my needs.

    Thanks for the info, and I'll definitely be keeping an eye on this thread, since you seem very passionate about it, and I like the way the asset is going.
  16. Pete12345


    Aug 28, 2018
    This is a really amazing asset, it will really let me work with and fit perfectly into my project. A huge thank you to the developer and all those who have helped.

    I have an issue though, that when I include multiple agentProperties, only the agent using the agentPropertiesI I listed in the menu for generating the navmesh will run. They instead print the "invalidAgentOutsideNavMesh" Debug.Log when the agent.SetRecievePathDelegate() is called.

    The other agentProperties have identical values.

    I honestly can't see anything to change to help with this so any advice would be very helpful.
    Last edited: Nov 20, 2019
  17. Krokozor


    Sep 27, 2014
    I wish i have more time to work on that asset. right now i really have no time :(
    I kinda finished agent-group interactions for the most part. Now individual agents can avoid groups like they avoid other agents.
    Though i kinda stuck with rules for automated grouping. Right now it is literaly "are you in front of me?" and in this case agent start to follow other agent and they are considered as single group. It helps to avoid collision in crowded situations since agents "snake" through obstacles and they can see groups a lot further. But this is only one way of multiple ways to implement group behavior and i kinda need good ways to expose this.
    Also Unity itself keep updating 2019 version and it is hard to keep up with it.

    Ah you probably generated navmesh only for target agent properties. I probably need to add to that menu array of properties instead of single property.

    If you want to generate navmesh from that menu then sellect property and press "Build". Then sellect other property and also press "Build". I understand that it is not a good way to do it.
    So i suggest 2 ways:
    1) Simple. Generate navmesh from code. Button in that menu just calls PathFinder.QueueGraph(int x, int z, AgentProperties properties, int sizeX = 1, int sizeZ = 1) so you can just loop through your peoperties using one of "QueueGraph" for target space.

    2) Not Simple. Modify that menu to fit your taste :) That buttons and that section of menu are in PathFinderMenu.cs in around 326 line there is function private void ImportantButtons().
    Code (CSharp):
    1. if (GUI.Button(rectBuild, buildContent)) {
    2.     if (settings.targetProperties != null)
    3.         PathFinder.QueueGraph(
    4.             settings.areaPointer.roundStartX,
    5.             settings.areaPointer.roundStartZ,
    6.             settings.targetProperties,
    7.             settings.areaPointer.roundSizeX,
    8.             settings.areaPointer.roundSizeZ);      
    9.     else
    10.         Debug.LogWarning(forgotToAddPropertiesWarning);
    11. }
    13. if (GUI.Button(rectRemove, targetRemoveContent)) {
    14.     if (settings.targetProperties != null)
    15.         PathFinder.RemoveGraph(
    16.             settings.areaPointer.roundStartX,
    17.             settings.areaPointer.roundStartZ,
    18.             settings.targetProperties,
    19.             settings.areaPointer.roundSizeX,
    20.             settings.areaPointer.roundSizeZ,
    21.             settings.removeAndRebuild);
    22.     else
    23.         Debug.LogWarning(forgotToAddPropertiesWarning);        
    24. }
    It is the only place where "settings.targetProperties" is used so you can just tell that "targetProperties" is array and loop through it in that menu when those buttons pressed. Or use "settings.areaPointer" in your code if you want to just read where is that sellector pointing.

    Also. If "other agentProperties have identical values.". Do you really need more agent properties in this case? You can reuse agent properties in different agents if they are roughly similar. Agent Properties is just a way to describe "key" to target navmesh graph in dictionary or "how to build navmesh" in case you want to build it. There is no point to create same navmesh if you already build other navmesh with same values.
    Last edited: Nov 20, 2019
    Pete12345 likes this.
  18. Pete12345


    Aug 28, 2018
    Thank you so much for your reply, I have not tried to get the code solution to work but it is working great when I run it from the menu.

    I used multiple agents because I am setting the area costs in the agents instead of the menu so a ship can have one agent with a cost of 1 on water and maximum on land and a land unit can be vice versa. That is mostly working but having multiple navmeshes for each property isn't ideal as I'm doing an RTS with already huge navmeshes.

    After that I want to use fog of war data to set a reasonably high cost to unexplored tiles so units won't know the best way to navigate unexplored terrain, which I assume the best way is to generate a complete navmesh and then replace the costs of each area with a fog cost if the team searching has not seen it?
    Last edited: Nov 25, 2019
  19. Nuno_Novais


    Dec 19, 2019
    Hi there
    First of all thank you for this great asset.
    while implementing it in my little project, i come across an issue. My project have several AIs using Pathfinder at same time. With that i was having issues (errors) in UnregisterNavmeshSample. Apparently several threads are accessing it at same time, and break it because the array is being copied by some other thread.
    Quick solutions, that may not be the best but worked was to create a lock in all function that call GenericPoolArray<int>.IncreaseSize
    Code (CSharp):
    1.             private readonly static object increaseLock = new object();
    2.             public static void UnregisterNavmeshSample(int id) {
    3.                 lock (increaseLock)
    4.                 {
    5.                     if (navmeshPositionFreeIndexStack.Length == navmeshPositionFreeIndexStackength)
    6.                         GenericPoolArray<int>.IncreaseSize(ref navmeshPositionFreeIndexStack);
    7.                     navmeshPositionRequests[id].valid = false;
    8.                     navmeshPositionFreeIndexStack[navmeshPositionFreeIndexStackength++] = id;
    9.                 }
    10.             }
  20. Roman-Ilyin


    Oct 9, 2013
    Thank you for this cool asset. Are there any plans to add formations for unit groups?
  21. Canoide


    Feb 24, 2014
    Hello, Is the library still supported?