Assets K-PathFinder

Works great now, thanks.

 

No, it's not predictable, I can happen at any time, even sometimes when I call Application.Quit()

Also, I have a question, will the path finder perform better with a static world?

 

If I want to add a house (both interior and exterior) to the navmesh (from 3dforge for example), what is the best way to use AreaGameObject? Considering the npcs can go in and out of the house.
Do I put it on everything except floor objects?
Also, is it possible to have the AreaGameObject on a parent and so it can affect all children on that parent?

 

Ugh. Well. I can see 4 variants:
* Thread termination are not working as intended. Most possible variant if use Application.Quit() and i will check this out.
* That triangulation bug. But it not stop pathfinder from forther work. Just bugged chunks never finished.
* Path search for some reason happen to conflict with navmesh generation.
* Current Raycasting bugs.
2 last will be fixed in next update. i hope i finish it within week.

No its dont matter static it or not.

Right now probably easiest way is add gameobject with MeshCollider with Mesh of house floor in it.
With current code - not. But this is not tricky. You can change how it's working in PathFinder/Generation/Collector/Collider/ColliderCollectorPrimitivesAbstract.cs
there is function protected void GenerateTemplates()

At it end there is

Code (CSharp):

1.  
2. var gameObjectArea = colliderTransform.GetComponent<AreaGameObject>();
3.  
4. //if gameobject have area then use it if not get default area
5. Area area = gameObjectArea != null ? gameObjectArea.GetArea() : PathFinder.getDefaultArea;
6. templates.Add(new MeshColliderInfo(verts, tris, area, matrix, bounds, collider.gameObject.name));

This part is in unity main thread and whatever you can use Unity API here. You can change GetComponent to GetComponentInParent for example. Or if you want to add child objects from this object to queue then modify templates list. It need mesh data and it's localToWorldMatrix and object world bounds to check is it within target space.

I will add at some poin more fancy ways to modify object Area.

 

Sorry I am not sure I understand you exactly. So in the code it would be fine if I find all the children and create a MeshColliderInfo from them right?

Also, about the house floors, how can they be added to the nav mesh, since there can be multiple floors?

 

Alright. Today is the day. I think it's finaly all fine and dandy. Tested all things i can test multiple times. If i dont break something really important tomorrow i just need to update manual and make new couple example scenes to show new things.

Reason it's took more time: New single threaded pipeline in separated thread. It had some extra-stuff and badly writen. After i start fixing it i realize that Path class are also can be writen better. So i deside to scrap it all and write more permament solution and dont fix old one. So on top of that there also will be huge performance increase in actual path search, object pooling and stuff. Also raycasting in path search now give more expected results since it's check now not just visibility of last point but also some of them in first row.

You just need to add mesh and localToWorldMatrix.
Also next patch will be soon enough and after it updates will be definitely more often than this. It will be more quality of life updates not essential like this one. If you want i will add better area editor to update after next one.

Amount of floors don't matter at all. Even if it in one big mesh. This thing writen with that in mind.

 

Good job on all the upcoming stuff.

About the GenerateTemplates() method, MeshColliderInfo doesn't have a constructor that takes 6 arguments.

Great that floors wouldn't cause problems.

 

How about something like this to add all the children under an AreaGameObject?

Code (CSharp):

1. void AddChildren(Transform transform){
2.    if(transform == null) return;
3.  
4.    if(transform.GetComponenet<Collider>() != null){
5.        //add collider
6.    }
7.    for(int i = 0; i < transform.childCount; i++){
8.        AddChildren(transform.GetChild(i));
9.    }
10. }

The AreaGameObject could have a bool whether to take into account the children or not.

This is for adding all the colliders to the navmesh in a house or anything really, instead of putting an AreaGameObject on hundreds of objects.

If you think this is good, do you mind adding it, since I don't know which class? Or you could tell me which.

 

Alright! Finaly update is on Asset Store. Though i uploaded it using latest unity version (right now i just dont have other versions). It should work okay on older unity versions. Later on will upload for older unity versions.
Now about new stuff.

This update are actualy pretty large. Rewritten lots of stuff so expect bizarre things. Rewritten path search, and also how path are stored so there wil be brobably lots of exeptions for people how heavily using old Path.
Also rewritten one important part of navmesh generation so old navmesh will cause exeptions when performing raycasting. I advice build navmesh from scratch.
Also also due to changes of pipeline for now removed automatic queue of graphs when you set goals for agent. But i added more ways to queue graph. There is now version "queue some graphs in straingt line". In general scene example you can find it used on "AgentUsage"

0.47:
Whats new:
* Local Avoidance

You can find this in examples folder along with another things
* PathFinder now have one separated thread to make batches of work in specific order. You can find it's function in PathFinder.PathFinderMainThread in case you want to add stuff there.
* Greatly improved perfomance of PathFinder.Raycast. Also now it have option to perform multiple raycasts from single starting point.
* Agents now have checkbox that enable update of it neighbours
* Agents now have checkbox that enable update of it position on navmesh

Whats fixed:
* PathFinderAgent.SetGoalMoveHere now works as intended
* PathFinderAgent.SetGoalGetBattleGrid and SetGoalFindCover errors now fixed
* PathFinder.Raycast now will not stuck if raycast started exactly on Cell border
* PathFinder.Raycast now return proper result when you specify expected area or passability

Whats changed:
* UI changes and tooltips
* actual pathfinding now a lot faster and dont generate garbage
* applyRaycastBeforeFunnel in PathFinderAgent.SetGoalMoveHere renamed to applyRaycast and it's now applyed before and after funnel to give more expected results
* Removed automatic graph queue from path, cover and grid search. So queue reasonable portion of graph in advance
* Greatly changed how Path works. To reduce garbage genertion there is now exist path pool. Path now store nodes as structs.
So path information now have very different way of returning it's information. More in documentation and comments.
* Debuger now uses PathFinder scene gameObject to debug stuff to avoid further confussion with it. You can delete old one
* PathFinder.TryGetCell now DO NOT return closest point to navmesh hull. it return something if point inside navmesh top projection at all
* PathFinder.TryGetCell renamed to PathFinder.TryGetClosestCell and now check bouth navmesh and hull. not one after another
* Added PathFinder.TryGetNearestHull to search nearest point just on navmesh hull
* Profiler now show a bit more information
* PathFinder.Raycast now return bool if it hit something or casted outside graph.
* RaycastHitNavMesh now contains more information
* PathFinder.Raycast now faster. Due to changes in Cells edges to do it - it wount work on old navmesh. So recreate it.
* PathFinder.gridSize are now cashed. expect some related to this bugs. (this is value that define chunk size)
* CellContentData represented Cell edges now all clockwise
* Added temporary checkbox for AreaGameObject that forcively add it childs meshes from mesh filter with target Area

Also changed a bit old examples

I added checkbox for area componen that tells "just include all childs meshes from mesh filters" for now. Little example on top left part in general scene. later on will add propper area editor
This is temporary toy. Collider need to be in chunk where navmesh are build. So you probably need to add some dummy colliders

 

Everything works quite nicely good job. Also, the children in AreaGameObject, but there are multiple problems of the npc getting stuck.

Two have to do with a small open space for doors.
In the first picture, there is a door object, currently open, so I removed it from under the AreaGameObject, but the npc is stuck either way.

The second picture, it's a similar space, but there is no door at all, still stuck.

Third picture is an npc getting stuck on table edges. Some might be guided off, by changing the direction, while other are completely stuck there, kind of no matter what.

Maybe some children are not added in the AreaGameObject?

I would send you the houses for testing, but it's a paid asset.

 

Eh? Well my crystal ball is broken so i have no clue what wrong. How does navmesh look in that case?

Also right now i'm working on more adequate way to edit area. Cause current one is bad. You kinda drew my attention to that problem. If you wait couple more days i can roll out micro-update with tool to solve this problem. Right now it looks like this:

 

There are separations in the navmesh as can be seen from the pictures, probably because some objects are not added to the navmesh (even though they are children of the AreaGameObject and have MeshColliders)

Let me know if you need any more information.

Also 3dforge does have a free demo asset, you can use it for testing if needed.
All these 3 links are combined into a scene:
https://www.assetstore.unity3d.com/en/?stay#!/content/17785
https://www.assetstore.unity3d.com/en/#!/content/46265
http://www.3dforge.co.za/bpvikvek.html#VillageInteriorsExteriors (Thunder Hammer Forge)

 

Actualy probably opposite. Some objects are added but in less expected shape. Right now navmesh dont check normals so it's just add tunnels as solid object. Which include door frames. Or any frames.
So objects like this will be actualy solid

You can see exact shape if you enable full debug and enable debug of voxels volume. In that cause you will see min and max values for voxels. (you will probably need to rebuild navmesh for that information to occur because no way i will serialize that)
In that case this looks like that

Right now you can work around that if you remove mesh collider from model and add multiple colliders on your own.
For example this will work fine

In case you want objects retain it mesh collider you can set it tag or layer to whatever agents will ignore and add it's navmesh collider as separate child object. In that case pathfinder will ignore it's actual collider but take it navmesh collider. And whole other world will just ignore navmesh colliders if you remove it's collision with rest.
I can make you example of that if you want.

This is inconvenient, yeah. I will fix this at some point. This can be fixed if pathfinder will also check Y axis for voxel normal. If it <0 then it point down and if >0 then it point up. And group voxels by that. But i'm not sure how it will work for more complex shapes than that. It will be bizzare if something like donut will return dozen of volumes cause some little triangle pointing in wrong direction. Will probably add component that will tell "do that. here your threshold values".

Or as easy alternative i can add to that area modifyer tool im working on little option like "make hole here". So it will punch holes in solid objects.

Also i can be mistaken about what cause that.
I suggest you to inspect voxels with full debug enabled. Maybe there is some voxels missing for whatever reason. Or there is tearings in voxel connections. Normaly it looks like that.

But if there is connection missing then pathfinder assume there is hole on navmesh. it can be fixed if you add some dummy colliders to fill gaps.
Or for whatever reason connection just wrong. In that case you might open my eyes to entire new layer of problems.

Or some little triangle that point from floor happen to have inclanation over threshold and this cause hole in navmesh.

Well. Thats cool. I will use this for testing. Yeah.
Checked exterior. After i took off door and add propper floor in left building and remove box from right building navigation start looks reasonable. Here and there bits can be fixed with changing resolution.

Later on will check cover detection on this. it need to have some fixes.
Interior dont have much colliders. Later on will play with adding colliders to that. Maybe will found out something.

 

Alright. Added some more functional to that thing.
Now it can modify area, make holes in solid shapes, add sellected shapes as solid objects on it's own.
Also probably will add checkbox "add all my child meshes as solid objects". Like current AreaGameObject do but without bugs.


Any suggestions?

 

The screenshots I sent were while using full debug, but I haven't rebuilt the navmesh.
Which settings is best to use and which Agent Properties should I use?

Also it seems that there is a similar problem under tables as can be seen in the screenshots above.
I can send better screenshots after rebuilding the navmesh.

 

I found a pretty big bug in the new version that wasn't there before. RemoveNextNodeIfCloserThanRadius() sometimes will remove the rest of the nodes (maybe all are that small?) and the following will keep happening:
SetGoalMoveHere starts then RemoveNextNodeIfCloserThanRadius removes everything.

 

Alright. Little update. (Actualy waited for year to finaly inplement this features)
Now this Area Editor have some very cool feature - Custom Area. It now can generate Area on it's own. And this is a lot more cool extention of normal Area. Cause navmesh have reference to this Area modifier and modifier have reference to navmesh Cells henerated by it. And it is very cool. There is 3 reasons to think so:
1) We can directly change cost of passing through this specific area.
2) We can toggle ability to search path through this area. For example when big metal door is closed we can now tell "here is no path". Or opposite. When wall is broken wee can tell "there is path now" without rebuilding navmesh.
3) Far more cool reason. Custom Area can have list of some Objects. And this objects can have some data. And when path generated we can add to path those Objects. Cool right? Example how this can be userful:

Blue Area on left generate it's own area. Button on right add to this area Object with Vector3 with position of that button and bool with state of this button. And also store reference to this Object. And also have trigger. When trigger happen it change bool in this object.
After that agent search path to green area. In returned path there is this object. Agent see "if this object bool is false then i need to go to Vector3 in it. if it is true then i can go to green area". This is essentially very abstract door logic. And this is cool cause you get this Object only when path going through Area with it. And since you can expand this Object you can add whatevel logic into it.
For example there is House with door and couple windows. Door closed at night. When door closed it need for example lockpicking. If AI dont have it then it can have path through window but then it need to smash it. And variable "need lockpicking" you can put on door itself. I think this simplify a lot of logic when build AI.

Also added some filtering. Now agent also check tags and layers of this thing. So for example some agents will add this area change to navmesh and some dont.
Also added filtering to this thing itself. So it will target only specific objects.
Also added order of applying this areas! So for example one area change it for A and others inside change it to B.

Also expanded a bit ways of path search. Added methods to include or exclude specific areas from path search. Also added some simple way to search for target area.

Also there is opposite: find nearest not that area. For example to get path outside specific zone.
Need a bit more work on it.

Also there is now little issue. There now more than one way to ask for path. Maybe i need to make way to ask for multiple paths at once?
For example make ability to do path requests as structs. And agent will have List of path requests, lists of bools which represent if this request should be used on next PathFinder update iteration. And list of actual results which will correspond with indexes of requests.

As long as "Full debug" enabled all gata generated along with navmesh will be avaiable for debug. Well at least before you rebuild your project. So enable "full debug" rebuild navmesh and check whats going on. After that disable "fulll debug" cause it's really slow things down and take lots of memory.

Agent Properties - just use those one where you have trouble.

Hmmm... i can't see why. And can't reproduce it. I will test more.
Maybe there is just no path? Or happen something unexpected. Recoment you to add to RecievePathDelegate check for Path.pathType. Cause right now when path not avaiable it shown in this variable. I totaly forgot to add this advice to examples.

I will test this thing more. Cause couple times i manage to get PathResultType.InvalidInternalIssue in this variable.

 

The pictures I posted before were using full debug, but the problem is. They are very hard to distinguish between other floors. The first floor navmesh will also be seen when look at the second floor.

About the Path.pathType, can you tell me how to call it? I tried pathAgent.path.pathType and it didn't work. (pathAgent object of PathFinderAgent)

For more information about the bug, haveNextNode would be true before RemoveNextNodeIfCloserThanRadius and then haveNextNode becomes false after. That is normal usually if it's close, but the agent is very far away from target and there is nothing in between, just a terrain.

Also, if you have discord or skype, it might be easier to just show you the bugs by share screen or by just chatting. If you think it can help.

 

Well. Yeah i did not put z-test on that shader. Cause some parts of navmesh are usualy obstructed by level and PathFinder dont generate height mesh yet. It's easy to see this way. Not so easy if parts of navmesh on top of each other. I will do something with that at some point but right now easiest way to see is just generate one chunk and look from side

Well you dont need to handle it every frame. Just when path actualy recieved.
You can write something like this:

Code (CSharp):

1.  
2. void Start () {
3.     agent = GetComponent<PathFinderAgent>();//Get agent
4.     agent.SetRecievePathDelegate((Path path) => {//Set delegate that will be used when path recieved
5.         if(path.pathType != PathResultType.Valid) {//if recieved path is not valid
6.             //Handle invalid path
7.             Debug.Log(path.pathType);//also write in console what is wrong
8.         }
9.     }, AgentDelegateMode.ThreadSafe);
10. }
11.  

There was no way to handle that issue. Now you somewhat can.
Sadly right now search for nearest point on navmesh can be somewhat broken cause it only search inside chunk. Later on i will expand this slightly so it will also check nearby chunks. But i need to make some refactoring before that.

That is peculiar. I still cant reproduce it in any way.

To be clear: if you store reference to Agent.path then that is explainable. Cause when agent recieve new path old one is cleared and returned to object pool. If you actualy want have permament copy of path then call Agent.path.Copy(). And call Path.ReturnToPool() when you no longer need it.

Sure. Actualy from first version there is tab in Window/K-PathFinder/Contacts where actualy my Skype listed. I dont usualy sit in discord but if you want to i can start sitting there.

Also i have short speechless video where i handle some issues in that asset. I put some extra stuff so there will be more issues than normaly are.

Spoiler

0:42 - Realized that floor and roof is same object
0:53 - Replaced mesh collider with box collider on floor
1:20 - Realized that floor have small bump that not connected cause new collider have only one height
2:29 - Door have that frame thing. Replaced it colliders
3:06 - Realized that it's not helped
3:18 - Check out voxels
3:33 - Noticed that thingy that for some reason is one big thing and it obstruct
3:50 - Hmmm... Hole still dont seems looks right
4:10 - Agent have height of 2 units. Checked actual hole height
4:26 - Changed agent height a bit so it fit hole
4:45 - This parts not connected
5:18 - Checked out voxels. Voxels shown that area is overinclined
5:39 - Fixed thingy
5:47 - Now it's alright

Also yeah. There is now UI that humans can actualy somewhat use. I slightly better organized Properties inspector so there is now more graphical information. And there is now proper chunk sellector. Function the same whay though.

I really should fix that issue with inability to add tunnels. Cause it can be sort of puzzle right now when you look what go wrong.
I doubt i fix this in next version.
My current plans is: In next version along with that Area thingy i add another feature a really want to add. And put a lot of work into it cause those features actualy was need to me like 2 years ago I had a my time to thought about that features. They are mostly to help build AI.
After that i plan to make a lot of optimization and refactoring. That include how PathFinder handle voxels so i probably will fix that issue at this point.

 

I am interested in this but i have some questions to know if its something i'd use.

Can it build run time navmeshes and update regions in run time too ? Is it multi threaded? Does pathfinding allocate memory or does it reuse collections?

 

Sorry for no news. I a bit carried away on with next update. There is not much new stuff coming up but fixing majority of bugs related to voxels. Spend some time on refactoring voxel engine. It still not ideal but much more finished than before and probably wount need this much of rework. So hurrah on performance boost. Also that painful issue with "no tunnels" finally will be fixed. Also trees with multiple simple colliders will be a thing.
Next update are kinda ready. I will test it for couple days and probably roll out if nothing broke.

Yes. This designed in mind to be used at runtime. That was main goal from start. and yes you can do partial update of navmesh and update chunks individualy.

As much as possible. It divided into 3 types of threads:
1) Unity thread - used for runing Unity API. Collecting colliders, debug, GPU rasterization if it sellected.
2) PathFinder main thread - it is used to run PathFinder pipeline. Connect/Disconnect chunks of navmesh, updating collision avoidance, updating paths, etc
3) Whatever threads - for generating individual chunks of navmesh which will be connected into whole thing in PathFinder main thread
So here really not much left in Unity thread. GPU rasterization and collection of colliders can be demanding though. Also NavMesh Raycasting can be used in Unity thread though i not recoment to.

Ah wait. That was question about Pathfinding and not generation of NavMesh. It uses pool of objects and dont allocate new memory if it dont need (or i'm not aware of it). Work queued as bunch of structs, pathfinding done in reusable templates which also have pool, result returned as class and it also returned to pool when it updated. So pathfinding dont really allocate things. Also path search are also done in multiple threads.
Also you can copy returned paths if you want to store them and return copy to pool when you want. Or whatever you can even precalculate multiple paths and use them instead and dont generate new paths at all

Also its up to you when request path. There is no things like "automatic path request" right now and it is done on demand. So you can reduce path requests to your taste. Though right now it's pretty fast. Also i have quite efficient graph. It split not to triangles like many others but convex areas. It close to most smallest graph it can be. Which also reduce search time. Although regions not implemented right now so very far path search not as efficient as it can be.

Generation of navmesh do allocate things but in next update it will be like 1/20 of current one

 

Thanks for the replies, i managed to squeeze unity's navmesh + navmesh agents up to 10,000 units but i want to squeeze it more. So with your threading and non allocation optimisations i think it will be possible, i will give it a try.

 

Great asset! Can somebody please show an example on how to get a random path? Best would be to get all walkable, reachable nodes (in a radius around a point). Is this possible with K-Pathfinder?

 

Submitted new version to asset store. Found out couple bugs with cover system. Last one was strange. it dessapear on it's own and i have no clue what happened.

Oh uh 10k units are not really what general purpose pathfinding solutions like that should do. You probably want to some sort of GPU pathfinding or something like that. Also unity solution are probably will be faster than mine. I did not test it though since here are more control over path requests and i have no clue how to compare it.

Also main target of this asset is to solve issues related to more advanced AI so i usualy pick functionality instead of perfomance.

You can achieve something like that. There is thing called BattleGrid. It return bunch of reachable points around some point in world. In General Scene there is example of something like that in BattleGridUsage.cs. On right part of example agent play hide and seek. Agent there uses those points to check visibility and walk to nearest non visible point. But you can use that data to pick just some random point and request path there. Those points have it passability so you can filter result by that.
But if you want i can make example for random path.

Sorry i did not added random path itself yet It is not hard though so i might add it relatively fast if you want.
There is multiple issues with different path requests actualy. Main one is - even if you have multiple functions to get path, you only have one output path. And since output is not immediate who know what path is there. It is a bit unwieldy when you try to build AI. I planing to change how path reqested before i add those type of functionality. So you might have something like input-output class in agent. So agent can update multiple paths at once. So you for example queue path for point A and point B and when path updated then you compare move cost to A and B and chose right one based on that. Planing something like this for next major update.

Also BattleGrid is a bit bad for what it designed to be. After i used it for some time i found some flaws. I see how it can be better. It a bit sepparated from navmesh itself and exist on it's own. So it dont take into account jump spots and in narrow coridors it can return nothing while there is some navmesh. Also it is in prototype state after this much time In update after next update i probably change how navmesh store data internaly and make it more uniformed. So requests like "get some cover" or "get some points" or whatever "find something on navmesh" will be merged to just one function and filtered by move cost.

 

Take a look at flowfield navigation. It might be a better choice for 10k agents.
@SirChick

 

Will do though i'm no good at making my own navmesh and i am fairly sure theres no navmesh flow field assets.

 

Actually, there is. Search for flowfield on the asset store.

 

Only one i found was flow field pathfinder which seems to use a grid based structure not a navmesh. Unless there is some other asset i missed?

 

Thank you for your time! I try to get into BattleGrid code and try to come up with something. But of course if you would integrate a random path function that would be awesome! A suggestion: A random point inside complete grid might be very cpu intensive, maybe there is a way to get a (maybe also random) chunk first and then a random point/voxel inside this chunk.

A random path example would be very welcome. I think this will be requested quite a lot in the future.

Also I don't know what you mean by "output is not immediate" and "only one output path". I'm not very good with pathfinding coding and haven't used K-Pahtfinder in depth. Doesn't AI always have only one path?

Anyway, thank you for this nice tool!

EDIT: Good lord, the new Area Selector is awesome! Is it possible to reduce the snap size for fine adjustment or a button to temporarily deactivate snap?

 

Wow that was quick. Usualy there is 4-5 days before it approved to asset store.

0.49:
Whats new:
* Added AreaWorldMod component for more precise Area painting and navmesh generation. Also have userful features to build AI. More in examples.
* Added AdvancedArea which only currently used by AreaWorldMod. This is new type of Area that contains reference to NavMesh and have some related to that functional
* Added Attributes.cs for common UI needs. To draw Area sellector for example
* Rewriten whole buch of code related to handling voxels. Big perfomance boost when lots of small objects in scene and fixed tunnels in mesh colliders.
* PathFinderAgent now have SetGoalFindNearestArea for search path to some specific area. (A bit rudimental)
* Added "Tag Associations" for areas. Now you can set default Area for specific Tag
* Agent Properties now have checkbox near ignored tags list that tell to check not only gameobject tag but also check all upper hierarchy tags
* Scene now have sellector to target area for navmesh building. It linked to "Build Area Sellector" in Menu

Whats fixed:
* Path.pathType now return valid path type
* Raycasting no longer return Null Exception after performed on graph loaded in OnEnable
* Rebuilding of loaded navmesh no longer cause edge exceptions
* Adding new Area now dont break NavMesh generation
* Compute Shader rasterization no longer return "must be blittable" in newer version of Unity
* Tree Colliders in scene now appear as Unity represent them (for the most part)
* Trees with multiple colliders no longer cause exeptions
* Non convex mesh colliders no longer remove hollow spots
* Adding multiple colliders no longer exponentialy reduce perfomance
* Smaller objects now added faster
* Fixed cases when specifit orientation of covers won't be generated

Whats changed:
* UI of AgentProperties now better organized and have some rudimental graphics for agent represintation
* UI of AgentProperties now have big warnings when you trying to shoot youself in the foot
* UI in Menu slightly better organized
* Sphere Colliders now appear on navmesh a 15-25 times faster and with more precision
* Capsule Collider now appear 12-20 times faster with little less precission
* Added more exception messages for more precise troubleshooting
* Added some missing tooltips
* Added graphical representation and handles for thing that sellect chunks to build from menu
* Remporary removed PathFinder.Deserialize and PathFinder.Serialize due to changes in serialization process
* Removed Unity Way of terrain collection cause it is obsolete
* Slight changes in existed example scenes

Bit thanks to itsnottme to help me find bugs and issues.


A bit expanded version on what happened.
There was big need in more direct ways to edit NavMesh. So i added simple way to store Bounds in chunks map and added simple version of that Area thingy that edit navmesh. It was easy to implement feature for the most part. Then i was pointed out "Trees return null" and i found out that Unity actualy now have half working trees colliders.

That was kinda big issue cause:
A) I cheat in collecting trees. Old method are just using some stumps that placed where is tree are. Also all list of trees are checked for all generated chunks. It was highly optimized so it dont have big impact on overall perfomance. But now i cant use that cause who know where is tree colliders are. Unity dont provide this information. When we doing BoxCast Unity just return terrain collider for each tree collider (no clue why)
B) Simple colliders like spheres or capsules are using rasterization method for meshes which way overcomplicate things. Which is bad cause trees are usualy made out from spheres and capsules
C) Adding new colliders to voxel engine are way too ineffective. I was okay of for small number but when there is 30-40 colliders in each chunk it was a disaster.

And overall issue looks big. cause. well. things like that cant sort itself:

Who know where is trees colliders are? I dont. Maybe you building game about giants in forest and you need pathfinding so they are crouch under trees. So trees must be represented in NavMesh as is.

Issue A have couple subissues. To start with: I know where is trees and i know it scale, rotation etc. But where colliders are? I dont know. Before that i can just take Collider.bounds.center and use it as position of collider. But now i cant. Cause i dont even have actual colliders to start with. Only position, rotation and scale of root object. And Unity uses some bizzare scaling mechanics for Colliders which nowhere is explaned. So lots of my sanity was pumped into solving just this puzzle. Happily Unity now have half working physics debugger so i was able to actualy see damn colliders.

Also Unity for some bizzare reason dont apply rotation of tree to it's colliders. Why? I dont know. It's a mystery for me.
Storing of those colliders was easy part. All tree data now collected into usable data when terrain first time used by PathFinder. Now on terrain appear PathFinderTerrainMetaData.cs which have all terrain colliders. And those colliders stored into Bounds map which previously used to store Area thingy bounds.

So i started to solve issue B. I rewrite Collider Collector so it treat each type of ollider individualy. Adding sphere colliders was easy and spheres became really fast. Like 15-25 times faster.
But adding capsules was not easy and i spend around 2 weeks just to solve all issues with that. I actualy did not see this algoritm anywhere and feel like i made a discovery and proud for myself

I generate and rotate elipse from slice of cylinder and move it along grid. Line clipped to plane are have very simple formula and all values are precalculated to just one elipse and can be reused. Now capsules 12-20 times faster than old general purpose approach. A bit less accurate though but it's not a huge issue.

I was not planing to solve issue C before i started and have plans to solve it after. Cause perfomance boost from solving issue B are overall spend to adding more new shapes. So overall there was very little prefpmance boost and really what changed is trees now appear on NavMesh as Unity see it.
But since i rewrited huge chunk of Collider Collector i tried to solve old issue: No tunnels. Not convex MeshCollider was huge issue for a long time cause they appear as solid object. I already pointed out to that issue multiple times and now when i have sepparated collection to individual types it was perfect time to solve this issue. And here i made huge discovery: I rediscovered LinkedList But made out from structs and 2d. So voxels can be stacked up on top of each others and it was robbust and quick. Far better than existed method. This much better that i rewrited all collection of colliders to use this method instead of old one. So i solved collection of normal colliders and collection of non convex colliders. New colliders now added alot faster and it far less demanding operation than before. But in the end i have one big lump of voxels. And old voxel engine operate in layers where there can be empty space betwin layers and some of logic was based on that. Also it generate hige amount of objects in process.
So before all those things can be userful i also need to refactor whole voxel engine. Oh boy that was quest for more than month. It was not that hard but there was just lots of old code need to be rethought. Most noticible one:
Before there was some space betwin layers of voxels that used to prevent shapes fragmentation. If two shapes can be placed into one 2d grid then they are placed to reduce layer count. Now they are already in one lump and there is no good way to sepparate layers by old method. Which is not issue if there is 2 or less layers. But multiple layers are can be fragmented and actualy have broken contour generation which lead to this kind of problems:

And there actualy is lots of robbust ways to solve layer sepparation. Like dividing navmesh into regions by ussing bassins of distance field. But! There are cool method to solve this issue but it is cpu hungry cause it involve sorting. Spend some time to implement it. Now layer sepparation are way cooler than before and actualy solve couple of old issues.


After that there was lots of bug searching and bug fixing. Cause there is now array pooling they sometimes were bizzare. And here we are. Now there is far more robust way to handle voxels. Big perfomance boost if there is lots of small colliders. Also perfomance boost if simple colliders are used (excluding box. i will write method to rasterize box after i restore some sanity). Also non convex mesh colliders now represented as thin hull around them. So "tunnels" now a thing. (i need to implement generating of convex shape for convex colliders to be accurate but this is also a problem for another day). And on top of that there now that Area thingy that allow more direct ways to edit Area of NavMesh.
Also added to agent searching path to nearest target area. It was there for test but whatever it can stay before i change way how agent request paths.
Perfomance gain overall varying but for example there is free pirate tavern on asset store. it have lots of small objects so it was huge issue before that. It was take up to 12 second to generate navmesh in that tavern and now it like 0.3-0.4 seconds. So perfomance gain can be huge in more complex levels.

Now i need to fix "triangulation" and project finaly can move from alpha to beta. Triangulation right now just bad and in bigger chunks it will take like 90% of time. also it still can fail and potentialy broke other things along the way. Like raycasting or local avoidance.

Also yeah. I probably need to implement flow field. It not that hard. Just having multiple types of agent can complicate things.

I actualy know couple better ways. We can find all near graph cells, maybe in some general direction and filter them by something (like minimum dustance), take triangles of those cells and pick random triangle weighted by it's area. And then pick random point on that triangle. I know good way to do this. In this case there will be a true random point on navmesh that in reachable space and with some constrains. Also it can be reused to something like "flee path" or opposite.

Well. In general usualy pathfinding uses just one path But it is very dull approach. For example you doing finite state machine and you need to decide what state to use. For example AI is hungry and it either go to left where bananas are or right where mushrooms are. How to choose? By walking distance in general. You can use distance to nearest bananas and mushrooms but it is not accurate measure. But you only can request one path at time. Which is suck logically. So you need to request path here, there and then compare them. It is just unwieldy to use. It is far better when multiple path requests can be made. But since agent not just for requesting paths and have lots of extra logic on top of it. So using multiple Agents are bad answer either. In general i want to make tool not only to find path but also be userful in building more complex AI. So more ways to get path and more ways to information inside navmesh need to be added.

Thank you

Well. Generation are operated in chunks. So partial update of NavMesh can be done per chunk. So i never added half chunks. But you dont need to generate navmesh in rectangles. You might just generate chunk here, chunk there or even generate new navmesh as game progress in proximity of player. Like in General Scene navmesh are generated along the way.
I will add some more options to that sellector later on. Definetly need to add button for dissabling it. Cause couple times i moved it while paint some terrain. Not a big deal cause it desapear if you close PathFinder Menu. But still.
Also i need to add more fine chunk sellection. So for example user can click on needed chunks save it sa pattern and then just make requests in that pattern. Preferable just by clicking in scene.

 

A bit more about new features. Cause i ran out of pictures in prevoius post
There is 2 examples how to use new thing but i think it need more words.

You can find it under Window/K-PathFinder/Create Area Modifyer
It is simple container of shapes. Right now there is sphere, capsule and box. A bit dull when it comes to scaling but rest is fine.

To add shapes there is "Add" button. To remove you can right click on shape in list and there will be contex menu. Also if you click on shape it will be highlited in scene with different color outline so you dont remove wrong one.
Also there is "Name" thing. If you type something there then when this gameobject sellected there will be also text in scene with that name. (feel like it's hard to differentiate those shapes otherwise)

On top there is Area sellector that uses global area list. You also now can use [Area] attribute before int so it will be drawn as Area sellector in inspector.

There is 3 behavoirs that thing can do:
1) Change Area. Simple as that. Anything inside those objects will be changed to target Area. So you can make some space Not Walkable for example.
2) Act as solid object for PathFinder. It probably userful if you want to tell where navmesh should be without placing actual object there. Or opposite if you sellect "Not Walkable" Area. In this cause just some obstacle will be placed there. Maybe if you need to avoid some space. There is small difference in this case: Agent can crouch under solid object if it presented which is not happening if area is changed. Also cover be generated using this data.
3) Make Hole. Shape will be subtracted from solid objects in this case. Comes with 2 flavors:
a) Sellected Area will be applyed to removed space
b) Area will be taken above removed space.
It is userful if you want to place hole on navmesh even it there is solid object. So for example you have destructable wall and want to check if path there can be at all.

There is Priority number. It used to define order in which those areas are applyed. Larger number come last. If number the same then priority of Area will be used.


And also there is another cool usage of this. If you enable Use Advanced Area it actualy gain some new functionality.
There is now new types of Area. Called CustomArea. If this option used then this area thingy will generate its own area specific for that object. In this case all navmesh where those area used will be stored in that area. It cool thing cause there now some bridge to affect navmesh from objects in scene.
Now there is couple userful functions:

public void SetCellsState(bool canBeUsed, params AgentProperties[] targets)
to enable or disable usage of navmesh in that area (actualy can be some issues with thread sync. i dont test it this much). If it disabled it remain existed but wount be reachable for agents and perform like there is nothing. Userful if you want some simple gate logic. Or whatever maybe occasionally floor is lava and agnets need to avoid some space without need to rebuild chunk.

public void AddCellPathContent(CellPathContentAbstract value)
public bool RemoveCellPathContent(CellPathContentAbstract value)
Cool thing. You can derive from CellPathContentAbstract and add this object to navmesh. Then when agent made path over this area - defined by you object will be added to Path.pathContent. So you can organize some more advanced logic if agent passed there. So AI can interpret those objects as keys or something like that. So for example there is gate but you only can enter if you have some item. Or some button is pressed or wahtever. Later on will expand this so some areas will be exclided from path search for individual agents.
(it wount be serialized though so you need to make your own serialization of your object and add it every time)


Tag Association
Also added this thing

There now way to change default Area for specific Tag. Yay!
So you can finaly make all yur furniture Not Walkable by default and not bother to add AreaGameObject to all things. That component is still exist though so you still can be specific. "This table is walkable and this is not"
I forgot to add tooltip
Use Root Tag checkbox for cases when you want to inherit most top parent tag. So for example you parent some things to your table and want to make them unwalkable automaticaly. Added because Unity dont suggest to change child tags.

Also AgentProperties have some basic graphics and more tooltips to help you figure out this mess.

Also better organized into cathegories.
And have one addition Use Hierarchy Tag It is simmilar ro "Use Root Tag" but for excluded tags. So any childs of excluded object will also be excluded. Userful if you want to add new colliders to your character (for example now it wear more bulky armor) but changing tags of new collider is hassle for you.

 

Wow, great update and thanks for the update on the update! Love it!

EDIT: Just wanted to let you know that in the updated version the Local Avoidance Navmesh example scene throws an error on Play:
chunkIteration too large. x -7.812235, y 0.5, z -10.73535, dx -1.603221, dy -0.9579096, max 2

 

Hm... What happened? This message are related to raycasting. xyz are position in world and dx dy are direction for x and y. max is distance of ray. I restarted this scene like ten times and cant reproduce it. Also checked this position in world. It is this position and direction and it dont seems special in any way and in my case it have result.

If you want this tester it under Tools/Testers/RaycastTester/ there is prefab and it have option to check specific position and direction.

Is settings for navmesh generation different? Maybe chunk size? Is it also occure after project rebuilded? I did not test it this extensively. Before that it really only can fail in this way if start point right on top of edge and ray fail to find exit from cell. maybe in some settings it all shifted in some way? or maybe for some reason cell are failed to generate convex shape?

Try to add this tester in scene, add properties from example and crank up Tests to 50-100 (or 1000-5000 if you fell meticulous) and move gameobject around scene. It will perform raycasts around itself. You will see something like that

If it can fail it will fail quickly.

 

Oh man, it was my mistake. I made a prefab from one of the agents in this example and used it in another scene with my own components and I totally forgot about it. xD After re-importing KP all works fine.

EDIT: Can you show an example AI with Cover, Navmesh and Avoidance combined? That would be cool.

Right now I'm trying to combine the Waypoint AI example code with the Avoidance Navmesh example code which doesn't seem too work because Avoidance and Pathfinding aren't working together.

That's what I've tried (removed comments for the sake of post size):

I took your Avoidance code and made it a function (switched charactercontroller to Vector3.MoveTowards because I do not use character controller)

Code from BasicLocalAvoidanceExample.cs from the Update function

Code (CSharp):

1. void DoAvoidance(Vector3 targetPosition) {
2.  
3.         if(navAgent.properties == null)
4.             return;
5.  
6.         PathFinder.QueueGraph(new Bounds(transform.position, new Vector3(10, 10, 10)), navAgent.properties);
7.         Vector3 position = transform.position;
8.         //expected direction agent will go
9.         Vector2 prefVelocity = new Vector2(targetPosition.x - position.x, targetPosition.z - position.z);
10.  
11.         float maxPrefVelocityLength = Mathf.Min(navAgent.maxAgentVelocity, velocity);
12.  
13.         if(prefVelocity.magnitude > maxPrefVelocityLength)
14.             prefVelocity = prefVelocity.normalized * maxPrefVelocityLength;
15.  
16.         navAgent.preferableVelocity = prefVelocity;
17.  
18.         Vector2 safeVelocity = navAgent.safeVelocity;
19.  
20.         transform.position = Vector3.MoveTowards(transform.position, new Vector3(safeVelocity.x, 0, safeVelocity.y), Time.deltaTime * speed);
21.    
22.         //_controler.SimpleMove(new Vector3(safeVelocity.x, 0, safeVelocity.y));
23.  
24.         navAgent.velocity = safeVelocity;
25.     }

Then I tried putting it into the pathfinding logic like this (see asterisk line)

Example6.cs

Code (CSharp):

1.  
2.         void Update() {
3.  
4.             if (patrol.Count == 0) {
5.                 Debug.Log("patrol.Count == 0");
6.                 return;
7.             }
8.  
9.             if (agent.haveNextNode) {
10.  
11.                 if (agent.RemoveNextNodeIfCloserThanRadiusVector2()) {
12.  
13.                     if (agent.haveNextNode == false) {
14.  
15.                         currentPoint++;
16.  
17.                         if (currentPoint >= patrol.Count)
18.                             currentPoint = 0;
19.  
20.                         agent.SetGoalMoveHere(patrol[currentPoint]); //queue new path
21.                     }
22.                 }
23.  
24.                 if (agent.haveNextNode) {
25.  
26.                     //Vector2 moveDirection = agent.nextNodeDirectionVector2.normalized;
27.                     //controler.SimpleMove(new Vector3(moveDirection.x, 0, moveDirection.y) * speed);
28.                     DoAvoidance(agent.nextNode); //*************************************
29.                 }
30.             }
31.             else {
32.  
33.                 agent.SetGoalMoveHere(patrol[currentPoint]);
34.             }
35.  
36.         }
37.     }

Now the agent moves to Vector(0,0,0) at game start and does nothing even though nextNode is somewhere else. I also added the GameMaster (RVO Updater) to the scene. Is it because of at which size the graph is queued?

I'm just trying to puzzle together an agent that can handle pathfinding, avoidance and cover. I know there are certainly other more important issues but if you find the time to help, I'd really appreciate it.

 

Sorry for not responding. I kinda busy cause i shifted my work to push out last update. So i did not have much time. Also i catch cold a bit

Right now current plan for further development:
I will probably shift fixing triangulation to update after next update and make intermediate update with some quality of life features. I kinda need to change how data which can be defined with singe Vector3 stored on navmesh. Right now BattleGrid points and Covers are bouth can be described as singe point. And they will be much more userful if along with search some sort of graph distance returned. Also i need to expose to user this sort of API. So user can place own data types on navmesh and perform graph search.
It should be something like agent.SearchNavmeshData<T>(float maxDistance)

But still. I kinda curious what happened. It should work in any settings.

I will make more complex scene later on where all things combined. Right now i can make simple scene to perform cover search. In attached file.

Also found out that its a bit broken for very simple reason: I dont have example of cover search and no clue when i last time cheked it
To fix it go to \PathFinder\Components\PathFinderAgent.cs
In public void ReceiveCovers(IEnumerable<NodeCoverPoint> covers)

Add
if(_covers == null) _covers = new List<NodeCoverPoint>();
before
_covers.Clear();
(I forgot that it null by default) You will recieve "TP work batcher NullReferenceException" if you dont do this

Well. Local Avoidance should be placed as last thing. So moving pipeline should look something like "user set move target > agent recieve path > user fiddle with path as needed > local avoidance recieve data from user > local avoidance return safe velocity to user". So i really cant skip part where user "fiddle with path" and simplify things in between. Though i can simplify things if there are more examples, prefabs, ect.

Ah well yeah i probably need some some examples on combining path and local avoidance. This part have some issues cause agent can stuck if target velocity are pointing towards navmesh. Also i need to point towards some userful things to help combining stuff.

If your agent can quicly change moving direction and you escentialy doing
agent.velocity = agent.safeVelocity;
You can strip whole lot of code. Important part with local avoidance will look like that:

Code (CSharp):

1.                
2. if (agent.haveNextNode) {
3.     agent.preferableVelocity = agent.nextNodeDirectionVector2.normalized * agent.maxAgentVelocity;
4.     controler.SimpleMove(new Vector3(agent.safeVelocity.x, 0, agent.safeVelocity.y));
5.     agent.velocity = agent.safeVelocity;
6. }
7.  

Also your code looks fine to me. I cant see what is wrong from first glance. Is agent.nextNode are where you expect it to be? Cause i have no clue why it point towards 0,0,0. If something is wrong then safeVelocity will be zero.

Also also you can enable "Debug Velocity Obstacles" In Debuger. In this case you will see something like that and inspect where agent velocity and target velocity are pointing.

White - agent velocity
Yellow - preferable velocity
Blue - local velocity

 

No need to be sorry, health and work come always first! I just hope you don't lose motivation for working on your project, since it will be marvelous once everything is in place.

The cover example is very nice. Just want to report that the agent doesn't behave as intended:

In certain situations the agent moves towards/past the "hide from" target, no matter which angle setting I choose on Example13.cs inspector.

I can't for the life of me reproduce it anymore... But should I ever get another error, I'll report it.

As for the avoidance, I can't get it to work with your snippet. But I also can't get it to work in Pathfinding Project and all other local avoidance assets. Avoidance alone = no problem but combined with pathfinding... no chance.

So I mix the Patrol code and your snippet together like this (I copied the complete update so you see what's going on):

Code (CSharp):

1. void Update() {
2.      
3.         if(patrol.Count == 0) {
4.  
5.             Debug.Log("patrol.Count == 0");
6.             return;
7.         }
8.  
9.         if(navAgent.haveNextNode) {
10.  
11.             if(navAgent.RemoveNextNodeIfCloserThanRadius()) {
12.  
13.                 //before that there was point. if after it removed here no point mean we reach end of current path
14.                 //if no points left then path no longer valid and agent get another path
15.                 if(navAgent.haveNextNode == false) {
16.  
17.                     currentPoint++;//move to next point on patrol
18.                     if(currentPoint >= patrol.Count)
19.                         currentPoint = 0;
20.  
21.                     navAgent.SetGoalMoveHere(patrol[currentPoint]);
22.                 }
23.             }
24.  
25.             //if next point still exist then we move towards it
26.             if(navAgent.haveNextNode) {
27.  
28.                 Debug.Log("<color=cyan>" + name + "</color>: I have a node.");
29.  
30.                 navAgent.preferableVelocity = navAgent.nextNodeDirectionVector2.normalized * navAgent.maxAgentVelocity;
31.                 transform.position = Vector3.MoveTowards(transform.position, new Vector3(navAgent.safeVelocity.x, 0, navAgent.safeVelocity.y), Time.deltaTime * speed);
32.                 navAgent.velocity = navAgent.safeVelocity;
33.             }
34.         }
35.         else {
36.  
37.             //get path to current point
38.             navAgent.SetGoalMoveHere(patrol[currentPoint]);
39.         }
40.  
41.     }

This is what happens:


The agents try to reach the scene center and shake like crazy when on the nav border. They move right through the obstacles. The debug line gets called, so the next node exists. Please let me know if you need more information or I can send you a small example project.

There is one other thing I wanted to ask. Since of all pathfinding assets I find yours the most convenient to use, it
bothers me that I can't use it in my current project. I have agents moving across uneven terrain with hills and paths up and down. Is there a way with K-Pathfinder to permanently snap an agent (without character controller and without gravity) to the navmesh surface?

Get well soon!

 

Ha ha i planing to work on it until i can. Cause navigation probably most solid thing that can be put into foundation of project. It can solve far more issues that it intent to solve in first place. I already burned out multiple times but always return thinking "this issue can be easly solved if i work sligtly more on that project".

Well here we are. I already pointed to this kind of issue. Example have dull implementation cause it take into account only 2 values: angle and distance from agent. If cover in angle threshold then distance is checked. And closest is sellected. It never take account of target position if first place.
Values are look like that:

It easy to see that target cover have angle less than 45 degrees and closest one by distance.
Right things to do in that case is
1) find agent position
2) find target position(s)
3) find cover points
4) weight cover points by distance to cover on navmesh
5) subtract weight by distance to target(s) on navmesh
so potential path to target points are as far as it can be from target and closest to agent by walking distance

But for that i need to change couple things. That is what next update target to do.

Hm... Well. I dont know why. I can figure out what is wrong if you give me example of issue.
But easier if i just give you example. In attached file.
Will look like that.

Fun to watch it hapening with enabled debug. Though on corners it a bit sticky. Need to add more fluid priority system on top of that. So for example agents close to navmesh borders have higher priority.

No right now not. To do this i need to reconstruct surface mesh from voxels and use it instead. Like Unity does. I plan to do it at some point but this is not an easy task right now. Right now navmesh are build only from minkowski sum of obstacles. So for example if there is some hill like that

NavMesh will still will be flat. Without that hill in center. Cause all this are in range of walkable angle. It somewhat helps that navmesh have grid pattern so at least border of chunks will follow surface but it not very userful.
I can add way to return path with all intermediate points on all crossings of edges but it is also not very userful.

Presence of height mesh can fix issues like finding nearest position on navmesh or return path along surface but i probably need to make other things before that.

 

Regarding the Patrol+Avoidance issue, for whatever reason this line was the culprit:

Code (CSharp):

1. transform.position = Vector3.MoveTowards(transform.position, new Vector3(navAgent.safeVelocity.x, 0, navAgent.safeVelocity.y), Time.deltaTime * speed);

Changing it to

Code (CSharp):

1. transform.position += new Vector3(navAgent.safeVelocity.x, 0, navAgent.safeVelocity.y) * Time.deltaTime;

did the trick.

I have to say, I really appreciate your support. Your explanations, pictures and example scenes helped a great deal, thanks! I'll watch the progression of this asset closely.

 

News.
As i already mention i probably wount fix triangulation in next update. I need to expand project internaly before that. I need to consolidate some parts of project like grid manipulations. Also i need to change how intermediate parts stored cause it is not very efficient.
Along with that i will make couple quality of life changes to project.

Problem 1:
As already was addressed about covers. You can search for covers but it is done in not very userful manner. Cause there is not much ways to change how cover are searched. Path to cover can be right in front of something that cover should cover.
Also simmilar problems with BattleGrid but even worse. It exist as self contained thing and not even connected to NavMesh. Which csn be userful in some cases but not userful for what it intended to be - cool ways to quickly sample points on navmesh. Also points should be in less strict grid manner cause in tight spots there can be no samples despite there is navmesh.
But it bouth can be described as Vector3 and bouth should be on NavMesh. Also search sould be unified.
That i already done. Also added way to add user-defined things to navmesh.
In video pay close attention to numbers. It is not linear distance. It is aproximated on navmesh distance.

Also added way to change cost of cells for search time (but probably will change how it operate).
In the end there will be something like NavMeshPointQuery<T>
that will take target type, search points, filter them, etc. And function as light weight agent.

Problem 2:
Search for closest position to NavMesh. Right now it is functional but bad. All search performed only inside one chunk. So even if there other point closer on nerby chunk it still will be ignored.
Like that:

I see 2 good ways to solve this issue.
Solution A) Add height mesh. Robust but will take lots of time to implement.
Solution B) Fix BattleGrid. Make samples more properly distributedand use those samples for search. Quick to implement.
So right now along other things i planing to also implement solution B. It is not as good as A but better that current one.
Also it intersect with some of triangulation problems like searching for closest point to connect so it will help to solve some of issues later on.

Ah i need to pay attention not to just my code. Yea now it make sence. Cause safeVelocity is velocity. Not position. It is movement vector not vector in the world.

Glad to read this

 

I'm giving this a try as it looks very good.

I'm getting these errors when trying to build in a fresh project with only K_Patherfinder added.

Code (CSharp):

1. 1>Assets\PathFinder\Generation\Graph\Triangulator\TriangulatorDataSet.cs(455,30,455,38): error CS0121: The call is ambiguous between the following methods or properties: 'DDARasterization.DrawLine(float, float, float, float, float, DDARasterization.DelegateDDA2)' and 'DDARasterization.DrawLine(float, float, float, float, float, DDARasterization.DelegateDDA1)'
2.  
3. 1>Assets\PathFinder\Generation\Graph\Triangulator\TriangulatorDataSet.cs(476,30,476,38): error CS0121: The call is ambiguous between the following methods or properties: 'DDARasterization.DrawLine(float, float, float, float, float, DDARasterization.DelegateDDA2)' and 'DDARasterization.DrawLine(float, float, float, float, float, DDARasterization.DelegateDDA1)'
4.  
5. 1>Assets\PathFinder\Generation\Graph\Graph.cs(226,30,226,38): error CS0121: The call is ambiguous between the following methods or properties: 'DDARasterization.DrawLine(float, float, float, float, float, DDARasterization.DelegateDDA2)' and 'DDARasterization.DrawLine(float, float, float, float, float, DDARasterization.DelegateDDA1)'
6.  
7. 1>Assets\PathFinder\Generation\Graph\Graph.cs(272,30,272,38): error CS0121: The call is ambiguous between the following methods or properties: 'DDARasterization.DrawLine(float, float, float, float, float, DDARasterization.DelegateDDA2)' and 'DDARasterization.DrawLine(float, float, float, float, float, DDARasterization.DelegateDDA1)'
8.  
9. 2>------ Rebuild All started: Project: Assembly-CSharp-Editor, Configuration: Debug Any CPU ------
10. 2>CSC : error CS0006: Metadata file 'Temp\bin\Debug\Assembly-CSharp.dll' could not be found
11.  

Any ideas what the problem could be?

Unity Version is: 2018.2.10f1

 

News:
I refactored for the most part code between foxelization and triangulation (where basic countour of navmesh generated and simplifyed. also things like covers appear). Spend some time in catching bugs. Turn out there can be case when node connected to itself and when cleared out it can be complitley removed. What lead to errors in triangulation. This case lead to like 95% of current triangulation errors so there was noticible increase in stability.

Also moved cover search and battle grid (which now no longer a grid) to new way of storing navmesh content. And made modifying cost of cells in proximity more accurate. Now changing cost of nearby points look like that.

In grid pattern it more clear what it return.

I will probably roll out next update soon after i'm fiddle with path generation some more. I want to that change of cost also affect patch search.
Also i find cool way to implement searching of nearest navmesh point.

Hello. Yeah i kinda know about it. For some reason Unity sometimes complain about ambiguous calls of that delegate. Despite that delegate have different signature. You can fix it if you go to PathFinder\Generation\Rasterizations\DDARasterization.cs and comment second one that uses
public delegate bool DelegateDDA2(int x, int y)
From 190 line to 360. In this version that line drawing thing stop drawing if delegate return true. I belive it dont have usage right now outside generating this error
I will fix it in next update by some renaming.

Also i read bouth email and forum At least once in couple days

 

Hey Krokozor

Thanks I'll give that a go. Does this mean I wont be able to see the grid in debug?

Also can you do an example scene with a terrain where the NPC and navigation components are added programatically?

Cheers

 

Great.

Only thing needed would be agents avoidance.
For example able to avoid other agents, moving around them without colliding with them, or choose a path that does not cross near other agents within some minimum distance.

 

Also forgot to tell in prevoius news.
I added IDs to Cells This is a little but this allow to use some global arrays of stuff that point to Cells on navmesh. After some thinking.. Its kinda easy to implement some rudimental flow field right now. Since you can tell "CellX point to CellY". Will probably spend some time on that cause this is kinda fun and userful feature.

Not really. This project have some old part where it sample some points from navmesh in grid pattern. Those points for the most part used to sample accessible points in proximity of agent. So user dont need to do things like "give me navmesh. then get some random points on navmesh. then weight those points by X".
Before those points contain connection to each others and those connections used to tell what point connected to what. But this kinda suck for lots of reasons.
In next update will be implemented way to store Vector3-like content on navmesh. So user can place some user-defined content on navmesh and tell "Hey PathFinder give me all nearby things of X type in Y distance" and this values will be returned with some extra like navmesh distance. This is way to weight something in proximity of agent and return it all without calculating actual path. Which is very userful for building any meaningful AI.

And there is that points samples and covers already. And they kinda more userful if they implemented as this sort of Vector3-like generic content. Which make old grid connections kinda obsolete cause navmesh itself used to define connectivity. Also since there is automatic jump connections can be generated they also can be used to tell where is neighbour points. (Which is not a thing in current version)
I will probably reimplement old way to connect that grid later on. But in different way. Cause those point was class and now struct and implementing dynamic graph of structs is painful enough expirience. And also i need to improve how those points sellected for bouth cases.

Ah sure. I was planing to add "infinite terrain" example anyway. In attached file.
Will look like that:

Though adding to terrain information how texture and Area connected right now is far from perfect Will improve in later version. It was done by using int array which connect indexes of splat prototypes and indexes of Area. Which is fine. But there is no actual code to use it with comfort. (its really old part of code and i totaly forgot to improve it)
But in previous updates i added attribute fot int and it can be drawn as Area sellector. Which is simplify at least converting Area to its index. More in comments in that example.

Also there is not much actual code need for that anyway. Its pretty much "Initialize Pathfinder. Hey give me NavMesh around. Hey give me path to X"
Since PathFinder heavy rely on 2 things:

• Some global settings that setted up in PathFinder menu. Like what size of world grid or what area should be assigned to some specific tag
• Agent Properties. Which is ScriptableObject that determine how navmesh is generated. And also what navmesh should be used at all. You create one and give it to PathFinder when you need something from it with this settings.

For menu there is plenty way to use it's functions from code. But there is not really huge amount of setthing there. For Agent Properties i did not add any meaningful way to create it from code. So you must prepare it and setup it from inspector.


Also yeah. infinite terrain tells me: I need to implement navmesh shifting So user can tell "Hey shift all navmesh by XY"

Also also found a bug while doing this. Turn out there can be cases when in some resolution splat maps return array out of range exeption. Changing splat map or navmesh resolution will fix this but this is still a thing. Though this is rare and i think it only occure in very small resolutions.

Oh it's pretty much already done. Also those "avoid this" points have assigned "group" and query for points have extended version that take those groups as input. So you can tell "Hey give me points and use X, Y and Z groups as weight modifyers".
Also weights can be negative So assgned values and range can be extended near this points in case you want to group some AI together.
Just need to expand path search to use this.

In next version i will sepparate Agent and how path requested a bit. So there will be just "Path Query" class that order some particular path, fire delegates when it recive it and so on. And just "Query for Path X", "Query for some bizzare path Y", "Extended query with some extra stuff but take more time". Cause multiple path requests really should be a thing. So for example when you weight some options in AI you can make decision based on how far path to X and Y and Z.

This is slightly more costly but far more userful in this form.
To compensate it i probably need to add some very simplifyed agent so it can be used as part of ECS. But this is later. Cause to benefit from that i also need to refactor Graph class.

But this is some cool stuff. I probably need to implement something like "Capture the flag" example with two teams of some rudimental AI. With this toys this is easy enough.

 

Hi Thanks for the fast information. It really sounds very cool, I'm having some trouble making it work though. I can run the examples you have but I'm still trying to guess how to make it work for my scene.

This is what I have so far;

Code (CSharp):

1.     public AgentProperties NavAgentProperties;
2.     public GameObject Npc;
3.     public Transform NavTarget;
4.  
5.     public PathFinderAgent agent;
6.     public Vector3 moveDirection;
7.  
8.     void Start()
9.     {
10.         agent = Npc.GetComponent<PathFinderAgent>();
11.         PathFinder.QueueGraph(new Bounds(Npc.transform.position, Vector3.one * 20), agent.properties);
12.     }
13.  
14.     void Update()
15.     {
16.         if (Input.GetKeyDown(KeyCode.Alpha1))
17.         {
18.            
19.             PathFinder.QueueGraph(new Bounds(Npc.transform.position, Vector3.one * 20), agent.properties);
20.             agent.Update();
21.             agent.SetGoalMoveHere(NavTarget.position, false);
22.         }
23.         if (agent.haveNextNode)
24.         {
25.             if (agent.RemoveNextNodeIfCloserThanRadiusVector2()) // for terrains should this be a vector3 test?
26.             {
27.                 if (agent.haveNextNode)
28.                 {
29.                     moveDirection = agent.nextNode.Vector3;
30.                 }
31.             }
32.             Npc.transform.position = Vector3.MoveTowards(Npc.transform.position, moveDirection, Time.deltaTime * 5);
33.         }
34.     }
35.  
36.     private void RecivePathDlegate(Path path)
37.     {
38.        // not sure what this is used for
39.     }

I've changed this around a few times, but I can't get it to work. I just don't understand what are the required steps for an NPC agent to move across a terrain towards a target position.

 

Well it kinda hard to guess Is navmesh appear if you enable it debug? Also you can use that thing you not sure how to use.

Code (CSharp):

1.  
2. void Start(){
3.    agent.SetRecievePathDelegate(RecivePathDlegate); //will set your function as delegate. this function will be called when agent recieve path and pass to it recieved path as argument
4. }
5. private void RecivePathDlegate(Path path) {
6.    Debug.Log(path.pathType); //Path have value to troubleshoot path. it can return what is wrong with it. if anything is wrong
7. }

In this case you can read in console what and when returned to agent. Also you can check values in path if you use path.pathNodes. So use Debug.DrawLine or DrawRay to check where is nodes are.

Also RemoveNextNodeIfCloserThanRadiusVector2() that big function take XZ axis. Not XY. So it's top view projection. It ignore height when removing next node while compare it to agent radius. Work slightly better on slopes. I think it have simmilar for vector3 if you prefer that. Though i think i forgot some debug in Vector3 version.
In th end this is just handy way to call path.MoveToNextNode()

So check list:
is navmesh generated? Enable "Do debug" and checkboxes under "Cell" below. maybe agent or target just far outside navmesh
Is path returned at all and valid? delegate will tell that
Is returned path look like you expect it to be? check in console agent.haveNextNode and where is it
Is agent.nextNode.Vector3 where you expect it to be?

if everything is okay then make checks with Debug.Log after each agent.haveNextNode to see what called and what is not

or maybe i just miss something really obvious. is KeyCode.Alpha1 even pressed?

 

Nice.
I think this would help for games with crowd, or games combat system with multiple characters in some zone able to move cleverly around other characters when some character is assigned to fight a specific other character.
Unity navmesh is not avoidance, it's characters sliding aorund others and stacking behind others when there is no place to slide around.

 

Hey Krokozor

Thanks for the additional information, for my understanding;

PathFinder.QueueGraph : This builds a navmesh around the player and only needs to be updated if the player moves a certain distance?

agent.Update() : should be always called before SetGoalMoveHere because it gets the agents latest position?

agent.SetGoalMoveHere() creates the navigation path and only needs to be called when selecting a new target location for the agent?

agent.RemoveNextNodeIfCloserThanRadiusVector2() : This takes a node out of the array if the agent is close to it? This is used to say I'm at the node and ready to move on to the next node?

Finally to move an NPC without a character controller is agent.nextNode.Vector3 gives me the straight line I need to move to for the current node?

The above steps are all I need for basic navigation yeah?

Thanks for the assistance and clarification.

Cheers

 

Ha ha well yeah. Unity navigation have limited usage on this part. But in general "avoidance" refered to not colliding with each others and not this bizzare contraption to avoid some places cause usualy this done through assiging areas and costs. This approach just not very useful for cases where agent need to react quickly to surrounding.
My approach also not perfect cause it calculate moving distance but not "visibility". Also it is done per cell and cells dont have unified size so its not really accurate way to do this. But this is still better than nothing.

Also some distant futue thoughts: If i finaly will done dynamic obstacles at some point (which is done through taking existed graph, carving some holes and return it to skip most hard parts) it will be cool if i in some form add "visibility" carving. So over navmesh casted something like 2D light source with shadows and this shape transfered to much harder area. In this case path will take into account actual visibility of certain spots. That will fix cases when agent run into cover in front of it for real and will be applicable too much complex level geometry.

I really need to consolidate some global userful functions in manual.

PathFinder.QueueGraph will build at target space some navmesh. It is done in grid pattern so you dont need to be accurate cause chunks dont generated partialy anyway. this function have lots of overloads so pick userful one for your taste. With bounds it just generate all chunks that include those bounds. Also there other version exist that take as input 2 positions and will generate navmesh between them. So for example you pass there agent position, target position and presumable you will get navmesh between them. Which is userful if your level have smal relative complexity. This function only add new navmesh to existed one. In will not generate new navmesh over old one.
PathFinder.RemoveGraph will remove navmesh if you desire to update it. In general example scene there is example of it in buttons that move cubes.
PathFinderAgent.Update well. Just call that standart unity function. It also cache agent position so in some cases when agent position should be exact this is userful. But realy you dont need to call it in most cases cause unity call it anyway.
PathFinderAgent.SetGoalMoveHere add this agent to queue for path generation. It dont update agent at this same moment cause all this done in sepparated thread. But usualy will return new path in couple frames. How often it should be called is for you to decide. Maybe your agent hve some funky move pattern and often lose track of it? maybe it sometimes missing moving node in front of it? if your agent moving on rails and there is no chance it go off path then you probably need to call it only once. if not then i dont know you probably know better.
PathFinderAgent.RemoveNextNodeIfCloserThanRadiusVector2 yeah. Will check if next node closer than radius and move index of current node to next one. Also there is other functions that do same thing. For example RemoveNextNodeIfCloser(float distance). also this function return bool. If true - point was removed. I suggest you to open PathFinderAgent.cs and just read parts with comments. Also-also you can just call PathFinderAgent.RemoveNextNode() if you want to just remove next node after your own calculations of distance or whatever reason.
agent.nextNode.Vector3 well. will give you position in global space for next node. This is where it is. Also PathNode have implicit operator to transform it to Vector3 so you can write something like Vector3.Distance (agent.positionVector3 - agent.nextNode). Also this is done for Vector2 but Vector2 take XZ axis and not XY. Also-also agent.nextNode have agent.nextNode.type in case you generate crouch areas or jumps. This will tell you what kind of node is next node. For jumps this is where jump start or end. For stance this is what stance agent should use to be able achive next node. Also you can just open PathInformation.cs and read what inside path and what functions it have.

Overall this is most basic stuff you probably need. Generating navmesh, generating path, interacting with path.

 

Great, thanks mate, appreciate the time to give such complete explanations. I'll stick with it and once I have the basics down I'm sure I'll be very happy with it.

Cheers