Search Unity

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

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

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

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

    5 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. christoph_r


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


    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?